Google code jam 2020 qualifications
Tags: contest, codejam, programming
Published: 2020-04-11 17:33:41

Qualifications to Google CodeJam are now over and I'm qualified to the 1st round. It was quite a fun to solve the problems even though I had to stay till 3 a.m. at Sunday. It was my first time participating in Google code jam, so I didn't know what to expect. I solved a few problems from previous year to prepare myself at least a bit.
One takeaway from the qualifications is if solution doesn't give correct answer, maybe try a different approach. Don't spend too much time investigating why it isn't working.

Descriptions of qualification problems can be found here:
https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27

You can find my solutions to qualification problems here:
{% github serpent7776/google-code-jam-2020 %}

## Problem 1: Vestigium

This one was pretty simple. Just read the square, calculate its trace. Finding duplicate elements was done by comparing each element with other elements for equality.

## Problem 2: Nesting Depth

This problem seemed a bit hard initially, so I wrote a quick perl script that just wrapped each block of repeating digit 1 in parens using one simple regex. This worked just fine for first test case, as there could be only digits `0` and `1`.
Then I moved to the next problem. In between solving other problems I was thinking about this one. It wasn't really that hard as I thought at first.
Second test case could contain any digits, so regex approach was no longer suitable. So I read digit one by one (say, `A`, then `B`), and depending on the difference between the two (`D = B - A`), I put `D` parens right before `B`. When the difference was positive, opening parens were added, when it was negative, closing parens were added.

## Problem 3: Parenting Partnering Returns

I implemented greedy allocation that first tries to assign job that takes longest time to complete. It first tried to assign job to Cameron. If that conflicted with other job that assigned earlier, the job was assigned to Jamie. If that'd also conflict, the job was impossible to assign.
This didn't work well and was not able to solve even the first test set. Not sure why.

## Problem 4: ESAb ATAd

Solving the first test case was trivial. We have 10 bits to discover, but we have 10 reads before fluctuation happens, so just read all bits. That will be the answer.
To solve the second test case an actual detection has to be implemented.
The approach is to find two pairs of indices that have same distance from the centre of the array (e.g. first and last bit). The first pair (I called that `si`) need to have both bits the same value. The second pair (I called that `di`) need to have different values of the bits.
For example if the real bit array is `11001010` then `di` would be `0` and `si` `1`.

```
 +-si-+
 |    |
11001010
|      |
+--di--+
```

Having that two pairs of bits we can detect any fluctuation after every 10 reads.
After every fluctuation we read all 4 bits and compare with values before fluctuation:
- if all the bits are the same, no change happened
- if all the bits changed, the array was complemented
- if `di` bits swapped its values with each other, but `si` weren't, the array was reversed
- if `di` pair stayed the same, but `si` changed, array was both reversed and flipped

When writing this description I noticed that my implementation was a bit more convoluted than that, but that's what you get writing code at 3 a.m. I guess, lol.

## Problem 5: Indicium

This task was pretty difficult. Initially I was trying to find some set of specific rules I would use to generate squares. Turned out that it was not possible even for a square of size 5 or less. So instead I searched for diagonal that has given trace and then try to generate row by row by brute forcing. Worked well for smaller squares. Obviously didn't work for the second test case that had matrices of size bigger than 5.