Google Code Jam is an annual, international programming competition. Similar to ACM/ICPC but less restrictive since anyone who registers online can compete. Also the contest is not team based. It consists of several stages until its final onsite round. The very first stage qualification round recently took place.

I have checked the problems and proposed some solutions to those.

Disclaimer: Proposed ideas and implementations are not official, ideal, nor coded optimally. Instead, this is only one way to tackle the problem. Feel free to contact me to feedback possible optimizations!

Prerequisite: This explanation assumes that you are familiar with the terms, variables and the problem itself as defined on the official Code Jam page. If you have not read the problem description, please take your time and go through all of it.

Observations

This is an interactive problem. I.e. submitted program exchanges information with judge server more than 1 time for each test case.

In this particular problem, what conditions would cause a submission to fail?

  • When Gopher is deployed 1000 times, yet a solution is not found.
  • It takes more than 20 seconds to deploy the Gopher 1000 times.

Therefore, our hypothetical ideal approach should:

  1. Not need to deploy Gopher more than 1000 times to construct the rectangle.
  2. Have a fast procedure to decide where to deploy the Gopher.

The first condition depends on A, the size of the rectangle to construct. For instance when A \(>1000\), it is not possible to construct the rectangle at all. Since the process is stochastic, probability of successfully constructing a rectangle of size A raises as A gets smaller.

Luckily, A = 20 and A = 200 in the visible and hidden test sets respectively. Not too demanding and tolerating for algorithms that follow non-optimal strategies.

Approach

Although there are many possible strategies to tackle this problem, for simplicity and the ease of imlementation, let’s consider an approach where we:

  • Choose to construct a rectangle of size \(RxC\), whose top left cell is located at \((1,1)\) and \(RxC \geq A \)
  • \(R\) denoting the number of rows
  • \(C\) denoting the number of columns
  • Define inner cell as the non-border cells of our rectangle.
  • Deploy the Gopher only in the inner cells. In other words, do not risk to prepare any cell landing outside of our rectangle.
    • In this case, we do not need to worry about bulges.
    • Downside of this is, it gets more likely to prepare a cell that is already prepared. Which means a wasted deployment. Recall that we have only 1000 of them.
  • To mitigate the problem of wasted deployment, we would like to deploy the Gopher to a cell, where the neighbourhood of the cell (surrounding 9 cells) has the largest number of unprepared cells. Increasing the chance of preparing an unprepared cell.
  • In addition, we would like the size of our rectangle \(RxC\) as close as possible to A. Otherwise Gopher would be doing extra unnecessary work, that would require more deployments.

Notice that with this approach we need to store:

  1. Which of the cells are prepared
  2. Number of unprepared cells in the neighbourhood of each inner cell

When it is time to deploy the Gopher, simply search through the inner cells, and find the best candidate. One might notice another optimization here to decrease search time (this is about the 2nd constraint mentioned in Observations). We could decrease search time by reducing the number of inner cells to search through.

Is there a way to minimize the number of inner cells?
Yes. Given three positive real numbers \(x,y,z\) and the equality \(xy=z\), \( x+y \) is minimal when \(x=1\) and \(y=z\) or vice versa.

In our case, \(R\) (or \(C\)) can not be smaller than 3. Therefore, fix \(R = 3\) and let \(C = \lceil \frac{A}{3} \rceil \). One benefit of this choice is that the number of unnecessary cells in our rectangle could be at most 2.

So basically, our rectangle will be an horizontal strip. One more thing to consider is:
Will this strip fit in the 1000x1000 garden?
We are lucky about this. If A would exceed 3000 then the strip would be too long, but that is not that case in any of the test sets.

See below, the illustration of this approach. Green is the target rectangle and the dots represent inner cells to deploy the Gopher to. We will have \(C-2\) of them according to our approach.


On the high level, the method works as the following:

R = 3
C = ceil(A/3)
unprepared = 2d array of size [R,C], with values 1
unpreparedCount = array of size [C-2], with values 9
outputCell(unpreparedCount)
answerCell = receiveAnswer()
while(rectangle not completed AND answerCell is not fail){
    update(unprepared, unpreparedCount, answerCell)
    outputCell(unpreparedCount)
    answerCell = receiveAnswer()
}

Implementation

The following is a C++ implementation of the approach mentioned.

using vint = vector<int>;
using vvint = vector<vint>;

void solveCase(){
    int A; cin >> A;
    int cols = A/3;
    if(A%3!=0) cols++;
    vint freeCount(cols-2, 9);
    vvint free(3, vint(cols, 1));

    Pos p; // pos we send
    Pos a; // pos we receive

    p = getNext(freeCount);
    p.send();
    a = Pos::receive();

    while(a.legit()){
        updateFree(freeCount, free, a);
        p = getNext(freeCount);
        p.send();
        a = Pos::receive();
    }
}

The functionality of getNext() and updateFree() could be also implemented using a heap equipped with a custom comparator and a custom decreaseKey() operation, but again, under the given constraints, it makes sense to go with this easier to implement but slower, pair of functions.

Pos getNext(vint& freeCount){
    int maxFree = 0;
    int maxI = -1;
    for (int i = 0; i < freeCount.size(); ++i) {
        if(freeCount[i]>maxFree){
            maxFree = freeCount[i];
            maxI = i;
        }
    }
    Pos p;
    p.r = 2;
    p.c = maxI+2;
    return p;
}

When implementing the following function some of the things to pay attention are:

  • Update arrays only if prepared a previously unprepared cell
  • Neighbourhoods will share some of it’s cells with other neighbourhoods
    • Decrement counts taking this into consideration
void updateFree(vint& freeCount, vvint& free, Pos& a){
    if(free[a.r-1][a.c-1]){
        free[a.r-1][a.c-1] = 0; // not free anymore
        int onMidOf = a.c-2;
        int onRightOf = onMidOf-1;
        int onLeftOf = onMidOf+1;
        if(onMidOf>=0 && onMidOf < freeCount.size()){
            freeCount[onMidOf]--;
        }
        if(onRightOf>=0 && onRightOf < freeCount.size()){
            freeCount[onRightOf]--;
        }
        if(onLeftOf>=0 && onLeftOf < freeCount.size()){
            freeCount[onLeftOf]--;
        }
    }
}

The class used to represent a position (a.k.a. cell) is implemented as follows:

struct Pos{
    int r,c;
    void send(){
        cout << r << " " << c << endl << flush ;
    }
    static Pos receive(){
        Pos p;
        cin >> p.r >> p.c;
        return p;
    }
    bool legit(){
        return r != 0 && r != -1;
    }
};

Remarks

This is an interesting and an unconventional problem in this kind of contests. We had to be able to compute rough expectations under a stochastic process and minimize it. In addition, we had to find a way to generate an answer in each turn in a reasonable time which is an implementation-wise concern. The code we provided is not very concise but rather modular and intuitive.