Google CodeJam Qualification Round: Bathroom stall

Question

Problem

A certain bathroom has N + 2 stalls in a single row; the stalls on the left and right ends are permanently occupied by the bathroom guards. The other N stalls are for users.

Whenever someone enters the bathroom, they try to choose a stall that is as far from other people as possible. To avoid confusion, they follow deterministic rules: For each empty stall S, they compute two values LS and RS, each of which is the number of empty stalls between S and the closest occupied stall to the left or right, respectively. Then they consider the set of stalls with the farthest closest neighbor, that is, those S for which min(LS, RS) is maximal. If there is only one such stall, they choose it; otherwise, they choose the one among those where max(LS, RS) is maximal. If there are still multiple tied stalls, they choose the leftmost stall among those.

K people are about to enter the bathroom; each one will choose their stall before the next arrives. Nobody will ever leave.

When the last person chooses their stall S, what will the values of max(LS, RS) and min(LS, RS) be?

Solving this problem

This problem has 2 Small datasets and 1 Large dataset. You must solve the first Small dataset before you can attempt the second Small dataset. You will be able to retry either of the Small datasets (with a time penalty). You will be able to make a single attempt at the Large, as usual, only after solving both Small datasets.

Input

The first line of the input gives the number of test cases, T. T lines follow. Each line describes a test case with two integers N and K, as described above.

Output

For each test case, output one line containing Case #x: y z, where x is the test case number (starting from 1), y is max(LS, RS), and z is min(LS, RS) as calculated by the last person to enter the bathroom for their chosen stall S.

Limits

• 1 ≤ T ≤ 100
• 1 ≤ K ≤ N

• Small dataset 1

• 1 ≤ N ≤ 1000

• Small dataset 2

• 1 ≤ N ≤ \$10^6\$

• Large dataset

• 1 ≤ N ≤ \$10^{18}\$

Sample Input Output

5
4 2
5 2
6 2
1000 1000
1000 1

• Case #1: 1 0
• Case #2: 1 0
• Case #3: 1 1
• Case #4: 0 0
• Case #5: 500 499

In Case #1, the first person occupies the leftmost of the middle two stalls, leaving the following configuration (O stands for an occupied stall and . for an empty one): O.O..O. Then, the second and last person occupies the stall immediately to the right, leaving 1 empty stall on one side and none on the other.

In Case #2, the first person occupies the middle stall, getting to O..O..O. Then, the second and last person occupies the leftmost stall.

In Case #3, the first person occupies the leftmost of the two middle stalls, leaving O..O...O. The second person then occupies the middle of the three consecutive empty stalls.

In Case #4, every stall is occupied at the end, no matter what the stall choices are.

In Case #5, the first and only person chooses the leftmost middle stall.

I could solve the inputs C-small-1 and C-small-2 efficiently but my code runs quite a while for input C-large. Are there any ways that I can improve this code?

#include <iostream>
#include <string>
#include <fstream>
#include <queue>
#include <vector>
#include <math.h>

using namespace std;

// Print queue
void print_q(std::priority_queue<vector<int>>& QQ)
{
    int num =0;
    while (!QQ.empty())
    {
        cout << "Accessing for " << num << " times" << endl;
        vector<int> temp = QQ.top();
        for (vector<int>::iterator it = temp.begin(); it != temp.end(); it++)
        {
            cout << *it << " ";
        }
        QQ.pop();
        num++;
    }
}

// Input: a priority queue
// Output: an updated priority with midpoint as occupied stall

void print_vec(vector<int>& vec)
{
    cout << "content of vec: ";
    for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}

int main(int argc, const char * argv[]) {

    ifstream myfile;
    myfile.open("./Desktop/codes/GooglecodejamQ2/C-small-practice-2.in");
    int num_case,num_stall,num_person;
    myfile >> num_case;
    cout << "Nm of cases: " << num_case << endl;

    while ( num_case!=0 )
    {

        myfile >> num_stall;
        myfile >> num_person;
        cout << num_stall <<  endl;


    struct CompareByLength {
        constexpr bool operator()(vector<int> const & a,
                                  vector<int> const & b) const noexcept
        {
            int aa = (a[1]-a[0])+1;
            int bb = (b[1]-b[0])+1;
            return aa < bb;

        }
    };

    std::priority_queue<vector<int>,vector<vector<int>>,CompareByLength> qq;
    vector <vector<int>> double_vec = {{1,num_stall}};
    for (vector<vector<int>>::iterator i = double_vec.begin(); i != double_vec.end(); i++)
    {
        qq.push(*i) ;
    }

    while (num_person != 0)
    {
        std::vector<int> tt = qq.top();
        qq.pop();

        int left = tt[0];
        int right = tt[1];

        int occ = tt[1] - ceil((double(tt[1])-double(tt[0]))/2);

        vector<int> l_stall = {left, occ-1};

        vector<int> r_stall = {occ+1, right};

        qq.push(l_stall);
        qq.push(r_stall);

        if(num_person ==1)
        {
            cout << "********** LAST PERSON CASE #" << 101- num_case <<" ***************" << endl;
            cout <<  "max(LS, RS)" << max((l_stall[1]-l_stall[0])+1,(r_stall[1]-r_stall[0])+1) << endl;
            cout <<  "min(LS, RS)" << min((l_stall[1]-l_stall[0])+1,(r_stall[1]-r_stall[0])+1) << endl;
        }
        num_person--;
        }
        num_case--;
    }
    myfile.close();

    return 0;
}

Answer 1

For a start, 25% of that code is dead code: neither of the two debugging functions is actually called. I'm not going to bother reviewing them.

But I also see

    myfile.open("./Desktop/codes/GooglecodejamQ2/C-small-practice-2.in");

and

            cout << "********** LAST PERSON CASE #" << 101- num_case <<" ***************" << endl;
            cout <<  "max(LS, RS)" << max((l_stall[1]-l_stall[0])+1,(r_stall[1]-r_stall[0])+1) << endl;
            cout <<  "min(LS, RS)" << min((l_stall[1]-l_stall[0])+1,(r_stall[1]-r_stall[0])+1) << endl;

which isn't the correct output format, and breaks if the number of cases isn't 100.

In future please post your actual code for review, not a hacked debug version.

---

The indentation is rather messed up. I suspect the original code mixed tabs and spaces with a tabstop other than 4. StackExchange converts tabs to four spaces.

---

The whitespace doesn't seem particularly consistent. Compare, for example,

  while ( num_case!=0 )

and

      while (num_person != 0)

---

Similarly, the use of namespaces is inconsistent. Most of the vectors are vector<int>, but there's the odd std::vector<int> floating about.

Not that vector<int> is the clearest way of doing things. It would increase readability (and maybe even performance) to define a struct for the intervals. It would also reduce the potential for confusion of the name CompareByLength: when comparing two vectors by length I generally expect the code to look at the length of the vectors, not the difference between their first two values.

---

Coming back to CompareByLength:

    struct CompareByLength {
        constexpr bool operator()(vector<int> const & a,
                                  vector<int> const & b) const noexcept
        {
            int aa = (a[1]-a[0])+1;
            int bb = (b[1]-b[0])+1;
            return aa < bb;

        }
    };

The two +1 are pointless. But more importantly, there's no tie-breaking. This absolutely needs a comment explaining why it's not necessary to break ties.

---

    vector <vector<int>> double_vec = {{1,num_stall}};
    for (vector<vector<int>>::iterator i = double_vec.begin(); i != double_vec.end(); i++)
    {
        qq.push(*i) ;
    }

Seems a rather long-winded way to initialise a queue with a single item.

---

        int occ = tt[1] - ceil((double(tt[1])-double(tt[0]))/2);

Why use tt[1] and tt[0] after pulling them out into variables with intelligible names? And why convert to doubles? Just rewrite as

    int occ = left + (right - left) / 2;

---

Finally, note that the test data's explanation included an observation:

In Case #4, every stall is occupied at the end, no matter what the stall choices are.

So given input

1
1000000000000000000 1000000000000000000

this code will run for a very long time even though I can tell you without running any code that the output should be

Case #1: 0 0

Do you think this might be a hint that it's not necessary to explicitly work through the sequence of stalls occupied? In fact, you can take it as a golden rule of challenge programming that the constraints

• 1 ≤ K ≤ N
• 1 ≤ N ≤ 10¹⁸

mean that you're expected to find a solution which takes o(K) time.