Google Code Jam

I originally meant this to be separate posts for each of the rounds but then, I didn't want to clutter up my blog too much. So, I'm putting everything in one file which I shall keep updating with the rounds. This post is an editorial of sorts for all the rounds in the 2020 edition of Google CodeJam. This is my first time attempting to write an editorial for a competitive programming contest and I'm already puzzled over how I should be structuring this. I guess I'll start with an overview of the contest and then tackle every question. VAMOS!!

The solutions are coded in C++ and some questions will also have solutions that failed, so that I can provide commentary on what went wrong. The solutions aren't the best, but they do the job well enough for an AC.

Qualification Round

This round felt tougher than last year's Qualification Round. Participants needed to score a minimum of 30 points in order to qualify which meant that solving three problems was a must. I panicked a bit on Problem 1 as I followed a fallible logic and messed up (more about that below), the second one took me some time but I got through it without any difficulties. By this time, I was fairly confident of getting beyond 30 and I attempted a brute force on Problem 3 getting a few WA's before sobering up and hitting 42 points. I'd spent almost three hours in front of my screen and I didn't feel like pushing for the fifth problem. The fourth problem was an interactive problem, so that was out of the window anyways.

Problem 1: Vestigium

This problem asks us to check if a given square matrix is a Latin Square or not. In addition, the problem asks us to compute the trace of the square matrix as well.

The first thought I had was that if the matrix was a Latin Square, the sum of elements across all rows and columns would be equal to the sum of the first $n$ natural numbers. So, I first coded a $n + 1$ by $n + 1$ matrix and I added every element to the $(n + 1)^{th}$ place both row-wise and column-wise. For the trace, I added every diagonal element to the $(n + 1, n + 1)^{th}$ cell.

for (int j = 0; j < n; j++) 
{
    cin >> a[i][j];
    a[i][n] += a[i][j];
    a[n][j] += a[i][j];
    if (i == j)
    a[n][n] += a[i][j];
}

I immediately understood that this doesn't really work. For example, if $n = 4,$ possible row configurations that give us a sum of 10 are $(2, 2, 3, 3)$ and $(1, 2, 3, 4)$ out of which the former is definitely wrong.

After this fiasco, I looked at the constraints and decided to attempt a brute-force implementation. I'm not proud of it, but it did the trick. The following is my accepted submission.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector vi;
typedef pair pii;

int main()
{
    int t;
    cin >> t;
    for (int q = 0; q < t; q++)
    {
        int n;
        cin >> n;
        int a[n + 1][n + 1] = {0};
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> a[i][j];
                a[i][n] += a[i][j];
                a[n][j] += a[i][j];
                if (i == j)
                    a[n][n] += a[i][j];
            }
        }
        int rctr = 0, cctr = 0;
        for (int i = 0; i < n; i++)
        {
            int rctra[n] = {0}, cctra[n] = {0};
            for (int j = 0; j < n; j++)
            {
                rctra[a[i][j] - 1]++;
                cctra[a[j][i] - 1]++;
            }
            for (int j = 0; j < n; j++)
            {
                if (rctra[j] != 1)
                {
                    rctr++;
                    break;
                }
            }
            for (int j = 0; j < n; j++)
            {
                if (cctra[j] != 1)
                {
                    cctr++;
                    break;
                }
            }
        }
        cout << "Case #" << q + 1 << ": " << a[n][n] << " " << rctr << " " << cctr << "\n";
    }
}

Obviously, after the solution, I tried the problem again by looking at some solutions by the other participants. The best solution I found was to use sets. The key feature of a set is that it doesn't take duplicates, that makes it the ideal data structure to solve this problem. Once we insert every element of the row and column into a set, we can just check if the size of the set is equal to `n` or not.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector vi;
typedef pair pii;

int main()
{
    int t;
    cin >> t;
    for (int q = 0; q < t; q++)
    {
        int n;
        cin >> n;
        int a[n + 1][n + 1] = {0};

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> a[i][j];

        int k = 0;
        for (int i = 0; i < n; i++)
            k += a[i][i];

        int r = 0;
        for (int i = 0; i < n; i++)
        {
            set s;
            for (int j = 0; j < n; j++)
                s.insert(a[i][j]);
            if (s.size() != n)
                r++;
        }

        int c = 0;
        for (int i = 0; i < n; i++)
        {
            set s;
            for (int j = 0; j < n; j++)
                s.insert(a[j][i]);
            if (s.size() != n)
                c++;
        }

        cout << "Case #" << q + 1 << ": " << k << " " << r << " " << c << "\n";
    }
}

Well, this looks much better than the previous attempt. So sets are something I will not forget and thankfully, the C++ STL has the implementations. Let's move to the next problem.

Problem 2: Nesting Depth

This is a very good problem, we're given a string of digits, $S$ and we need to add a number of opening and closing parenthesis and generate a string $S'$ such that:

• All parentheses in $S'$ match some other parenthesis.
• Removing any and all parentheses from $S'$ results in $S.$
• Each digit in $S'$ is equal to its nesting depth.
• $S'$ is of minimum length.

The first thing I did was to write down some test cases and their solutions, I'll list them below

This got me thinking that stacks would work very well for this problem. The stack needs to contain the number of open parenthesis as well as the current nesting depth. This will ensure that we put in the correct number of closing brackets in the middle and at the end of the string. The following is my accepted submission.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector vi;
typedef pair pii;

int main()
{
    int t;
    cin >> t;
    for (int q = 0; q < t; q++)
    {
        string s, a = "";
        cin >> s;
        stack st;
        for (int i = 0; i < s.length(); i++)
        {
            int temp = s[i] - '0';
            //cout << temp << " " << st.size() << " ";
            if (temp > st.size())
            {
                for (int j = st.size(); j < temp; j++)
                {
                    st.push(st.size() + 1);
                    a += '(';
                }
            }
            if (temp < st.size())
            {
                for (int j = st.size(); j > temp; j--)
                {
                    st.pop();
                    a += ')';
                }
            }
            a += s[i];
        }
        for (int i = 0; i < st.size(); i++)
            a += ')';
        cout << "Case #" << q + 1 << ": " << a << "\n";
    }
}

By now, I was much more confident of getting the required 30. Let's see how the third problem made things difficult for me.

Problem 3: Parenting Partnering Returns

The problem statement is relatively simple to understand, we will be given certain time slots and we need to allocate the time slots between two people such that at no time, a person will be doing more that one task. I looked at the constraints and I decided to brute force this as well. My idea was to initially kick out the test cases with time slots overlapping more than two times and then checking each slot for availability. My first attempt was a wrong answer.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector vi;
typedef pair pii;

int main()
{
    int t;
    cin >> t;
    for (int q = 0; q < t; q++)
    {
        int n;
        cin >> n;
        int ev[n][2] = {0};
        int chk[1440] = {0};
        string a = "";
        for (int i = 0; i < n; i++)
        {
            cin >> ev[i][0] >> ev[i][1];
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = ev[i][0]; j < ev[i][1]; j++)
                chk[j]++;
        }
        for (int i = 0; i < 1440; i++)
        {
            if (chk[i] > 2)
            {
                a = "IMPOSSIBLE";
                break;
            }
        }
        int cn[1440] = {0}, je[1440] = {0};
        if (a == "IMPOSSIBLE")
        {
            cout << "Case #" << q + 1 << ": " << a << "\n";
            continue;
        }
        else
        {
            for (int i = 0; i < n; i++)
            {
                if (i == 0)
                {
                    for (int j = ev[i][0]; j < ev[i][1]; j++)
                        cn[j]++;
                    a += "C";
                }
                else
                {
                    int clash = 0;
                    for (int j = ev[i][0]; j < ev[i][1]; j++)
                    {
                        if (cn[j] == 1)
                        {
                            clash++;
                            break;
                        }
                    }
                    if (clash > 0)
                    {
                        for (int j = ev[i][0]; j < ev[i][1]; j++)
                            je[j]++;
                        a += "J";
                    }
                    else
                    {
                        for (int j = ev[i][0]; j < ev[i][1]; j++)
                            cn[j]++;
                        a += "C";
                    }
                }
            }
        }
        cout << "Case #" << q + 1 << ": " << a << "\n";
    }
}

Obviously, I didn't understand that there was going to be a problem with the implementation. So, for my next attempt, I greedily sorted and allocated the time slots. My accepted solution follows.

#include <bits/stdc++.h>
using namespace std;
bool comp(pair> p1, pair> p2)
{
    return p1.second.first < p2.second.first;
}
bool co(pair> p1, pair> p2)
{
    return p1.first < p2.first;
}
int main()
{
    int t;
    cin >> t;
    int flag = 1;
    while (flag <= t)
    {
        int n;
        cin >> n;
        vector>> v;
        for (int i = 0; i < n; i++)
        {
            int x, y;
            cin >> x >> y;
            v.push_back(make_pair(i, make_pair(x, y)));
        }
        sort(v.begin(), v.end(), comp);
        vector>> j;
        vector>> c;
        int f = 0;
        j.push_back(make_pair(v[0].first, make_pair(v[0].second.first, v[0].second.second)));
        c.push_back(make_pair(v[1].first, make_pair(v[1].second.first, v[1].second.second)));
        for (int i = 2; i < v.size(); i++)
        {
            if (j[j.size() - 1].second.second <= v[i].second.first)
            {
                j.push_back(make_pair(v[i].first, make_pair(v[i].second.first, v[i].second.second)));
            }
            else if (c[c.size() - 1].second.second <= v[i].second.first)
            {
                c.push_back(make_pair(v[i].first, make_pair(v[i].second.first, v[i].second.second)));
            }
            else
            {
                f = 1;
                break;
            }
        }
        if (f == 1)
        {
            cout << "Case #" << flag << ": "
                 << "IMPOSSIBLE\n";
        }
        else
        {
            sort(j.begin(), j.end(), co);
            sort(c.begin(), c.end(), co);
            int li = 0, ja = 0;

            string ans = "";
            for (int k = 0; k < n; k++)
            {
                if (li < j.size() && j[li].first == k)
                {
                    ans += 'J';
                    li++;
                }
                else if (ja < c.size() && c[ja].first == k)
                {
                    ans += 'C';
                    ja++;
                }
            }
            cout << "Case #" << flag << ": " << ans << "\n";
        }

        flag++;
    }
    return 0;
}

That was that, I mulled over the 5th problem but there wasn't enough motivation to go at it. There's a lot of ground to cover.

Problem 4: ESAb ATAd

I suggest watching Errichto's explanation first.

The problem statement is quite long and it was tough for me to get a grip on what exactly the problem required. But after a while, I boiled it down to the following simple-looking statement.

We are given an unknown sequence with $B=100$ elements that can take values $0$ and $1.$ We can query this sequence to get the $i^{th}$ element. We need to find the entire sequence and print it. A tiny catch is that after the $1^{st}, 11^{th}, 21^{st} \cdots$ query, but before the response is given, the array is either complemented with $0.50$ probability or reversed with $0.50$ probability. Also, we are allowed a maximum of $150$ queries.

Just for fun, I first scribbled down the case when there are no changes to the sequence

int query(int i)
{
    //flushing output.
    cout << i << endl;
    int res;
    cin >> res;
    return res;
}

vector<int> solve()
{
    vector<int> res(100);
    for(int i = 0; i < 100; i++)
    {
        res[i] = query(i);
    }
    return res;
}

First, we'll consider only the flipping of bits. With probability $0.50,$ after every $10^{th}$ query, all the bits are flipped. We'll check for flipping after every ten queries by checking with our own res. If the values don't match, we'll flip all the bits in our variable. Note that we use up a query to perform the comparison. Around $B*1.1$ queries will be used as we need one additional query after every ten queries.

vector<int> solve()
{
    vector<int> res(100);
    int queries = 0;
    for(int i = 0; i < 100; i++)
    {
        res[i] = query(i);
        queries++;

        if(queries % 10 == 0)
        {
            if(res[0] != query(0))
            {
                for(int j = 0; j <= i; j++)
                {
                    res[j] ^= 1;
                }
            }
            //incremented for comparison.
            queries++;
        }
    }
    return res;
}

But what the entire problem is asking also involves flipping. We just check for one more bit next to the ones at the ends. For example, if $1 \space 0 \space 1 \space 1 \cdots 0 \space 0 \space 0$ changes to $0 \space 0 \cdots 0 \space 0 \space 1,$ we know that it was just a reversal. But if it changes to $0 \space 1 \cdots 1 \space 1 \space 0,$ we know there have been flips.

This problem fails for $1 \space 0 \cdots 1 \space 0.$ I hope by now, many of you have figured out the solution. We have to find two pairs such that one is a same-bit pair and the other is a different-bit pair and then perform the check described in the previous paragraph. I have to thank Errichto for this implementation. I kept messing up the flushing of the input and I gave up after twenty odd tries.

#include <bits/stdc++.h>
using namespace std;

int B;

int query(int i)
{
    cout << i << endl;
    int r;
    scanf("%d", &r);
    return r;
}

void solve()
{
    vector<int> answer(B + 1);
    int L = 1, R = B;
    for (int nr = 1; true; nr += 2)
    {
        if (nr % 10 == 1 && nr != 1)
        {
            int found = -1;
            int found_diff = -1;
            for (int i = 1; i < L; ++i)
            {
                if (answer[i] == answer[B + 1 - i])
                {
                    found = i;
                }
                else
                {
                    found_diff = i;
                }
            }
            if (found == -1)
            {
                int new_value = query(1);
                query(1);
                if (new_value != answer[1])
                {
                    for (int i = 1; i <= L; ++i)
                    {
                        answer[i] ^= 1;
                    }
                    for (int i = R; i <= B; ++i)
                    {
                        answer[i] ^= 1;
                    }
                }
            }
            else
            {
                int one = query(found);
                if (one != answer[found])
                {
                    for (int i = 1; i <= L; ++i)
                    {
                        answer[i] ^= 1;
                    }
                    for (int i = R; i <= B; ++i)
                    {
                        answer[i] ^= 1;
                    }
                }
                if (found_diff == -1)
                {
                    query(found);
                }
                else
                {
                    if (query(found_diff) != answer[found_diff])
                    {
                        reverse(answer.begin() + 1, answer.end());
                    }
                }
            }
            nr += 2;
        }
        answer[L] = query(L);
        answer[R] = query(R);
        L++;
        R--;
        if (L > R)
        {
            for (int i = 1; i <= B; ++i)
            {
                cout << answer[i];
            }
            cout << endl;
            string response;
            cin >> response;
            assert(response == "Y");
            return;
        }
    }
}

int main()
{
    int T;
    scanf("%d%d", &T, &B);
    while(T--)
    {
        solve();
    }
}

Problem 5: Indicium

Now, on to the final and the toughest problem in the round. To-do!

Round 1A

This is by far on the top of my all-time favourite contests. Every question was maddeningly difficult but not unreachable. And the solutions were simple and elegant, if you had any eye for problem solving, you'd love this round.

Problem 1: Pattern Matching

This is a very easy problem statement to understand and just like I do in the first five minutes of every contest, I assumed I had the solution already. You have a bunch of strings of the form __*___ with the blanks filled by the uppercase alphabet. Over the entire array, you are supposed to fill the asterisks with a string such that no string conflicts with the other.

I started to write some test-cases but I soon found out that Google had provided some great test-cases. They helped me further understand the problem at hand and I'll list them out below

I had a vague idea of what I should be doing but I didn't get the breakthrough idea. So, I decided I should at least get through the first test set for 5 points. For the first test case, all the strings only have one asterisk and that too at position 0. So, the idea was to isolate the longest string and check if all the other strings were substrings of that one. It passed the first test set.

#include <bits/stdc++.h>
using namespace std;
bool isSubstring(string a, string b)
{
    int ctr1 = 0;
    for(int i = 1; i < a.length(); i++)
    {
        if(a[a.length() - i] != b[b.length() - i])
        {
            ctr1++;
            break;
        }
    }
    if(ctr1 > 0)
        return 0;
    else
        return 1;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    for(int q = 0; q < t; q++)
    {
        int n, ctr = 0;
        cin >> n;
        string ans, a[n], maxs = "";
        for(int i = 0; i < n; i++)
        {
            cin >> a[i];
            if(a[i].length() > maxs.length())
                maxs = a[i];
        }
        for(int i = 0; i < n; i++)
        {
            //cout << a[i] << " " << maxs << " ";
            if(!isSubstring(a[i], maxs))
            {
                ctr++;
                break;
            }
        }
        if(ctr > 0)
            ans = "*";
        else
            for(int i = 1; i < maxs.length(); i++)
                ans += maxs[i];

        cout << "Case #" << q + 1 << ": " << ans << "\n";
    }

    return 0;
}

For the entire problem however, I needed a more general approach. Assume that the given strings have asterisks both before and after the alphabets, we would then just have to print the alphabets without the asterisks. Now, if we had alphabets before and after those asterisks. We need to perform the same checks as above. After performing the checks, we use the longest prefix, all the letters in between and the longest suffix. Check out the code:

#include <iostream>
using namespace std;

void solve()
{
    int n;
    cin >> n;

    //Store the prefixes, suffixes and final answer.
    string a[n], pre[n], suf[n], ans = "";

    //Position of the longest prefix and suffix. (Initialization important)
    int lp = 0, ls = 0, chk = 0;

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];

        //We extract all prefixes and suffixes
        pre[i] = suf[i] = "";

        //Note how the `for` loops are implemented
        for (; a[i][0] != '*'; a[i].erase(a[i].begin()))
            pre[i] += a[i][0];
        for (; a[i].back() != '*'; a[i].pop_back())
            suf[i] = a[i].back() + suf[i];

        //Check for longest prefix and suffix
        if (pre[i].size() > pre[lp].size())
            lp = i;
        if (suf[i].size() > suf[ls].size())
            ls = i;
    }

    //Check whether all prefixes and suffixes are matching (substr())
    for (int i = 0; i < n; i++)
    {
        if (pre[lp].substr(0, pre[i].size()) != pre[i])
        {
            cout << "*";
            return;
        }
        if (suf[ls].substr(suf[ls].size() - suf[i].size()) != suf[i])
        {
            cout << "*";
            return;
        }
    }

    //We build the answer by using the longest prefix, suffix and everything but asterisks in between.
    ans = pre[lp];
    for (int i = 0; i < n; i++)
        for (char c : a[i])
            if (c != '*')
                ans += c;
    ans += suf[ls];
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    for (int q = 0; q < t; q++)
    {
        cout << "Case #" << q + 1 << ": ";
        solve();
        cout << "\n";
    }

    return 0;
}

Problem 2: Pascal Walk

We're given a Pascal Triangle and a number. We need to traverse the cells of the Pascal triangle such that the sum of numbers in the cells equal the given number. Some initial observations I had were that the sum across the rows of the pascal triangle follow the rule that $\text{sum}_r = 2^{r - 1}.$ This shows that we probably need to find the binary representation of the number. For example, if the number is $19,$ the binary representation will be $(10011)_2$ and the answer will be the cells in the 1st, 2nd and 5th rows. But the question says we can only traverse neighbouring cells starting with $(1, 1).$

So, one way to solve it is to go along the edges, adding ones until we reach the required row. Of course, this would be for the numbers greater than 30. For numbers less than 30, we could just add ones all the time.

The main thing I learnt to do in this problem was to use bit-operations and make things simpler. For example, n>> performs a right shift a.k.a divides by 2. a&1 checks if a is odd.

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    long n;
    cin >> n;

    //For small n, we just return the first cells in each row
    if (n < 30)
    {
        for (int i = 0; i < n; i++)
            cout << i + 1 << " 1\n";
        return;
    }

    //For large n, we only need to account for the difference with 30
    n -= 30;

    //This counts the number of ones we need to add at the end
    int ctr = 0;

    //To keep track of whether we're at the left end or right end.
    bool chk = 1;

    for (int i = 0; i < 30; i++)
    {
        cout << i + 1 << " " << (chk ? 1 : i + 1) << "\n";
        //Check if a row-traversal is required by using the binary representation.
        if ((n >> i) & 1)
        {
            //Check for where the current pointer is and traverse accordingly.
            if (chk)
                for (int j = 1; j <= i; j++)
                    cout << i + 1 << " " << j + 1 << "\n";
            else
                for (int j = i - 1; j >= 0; j--)
                    cout << i + 1 << " " << j + 1 << "\n";

            //Swing the end to the other side now that traversal is done.
            chk = !chk;

            //Increment number of 1's skipped with every row-traversal.
            ctr++;
        }
    }
    //Add the ones required
    for (int i = 30; ctr > 0; ctr--, i++)
        cout << i + 1 << " " << (chk ? 1 : i + 1) << "\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        cout << "Case #" << i + 1 << ":\n";
        solve();
        cout << "\n";
    }

    return 0;
}