Code Jam 2020 Solutions

What is Code Jam?

Google’s longest-running global coding competition, Code Jam, call on programmers around the world to solve challenging, algorithmic puzzles against the clock. Contestants advance through four online-hosted rounds to compete at the annual Code Jam World Finals that are held at a different international Google office each year. Each round brings new challenges, and in the end, 25 contestants will have the ultimate chance to put their skills to the test, vying for cash prizes and the coveted championship title at the World Finals.

code jam logo

The 27-hour long coding competition concluded on 5th April 7:30 AM (IST). There were a total of 5 questions from which I was able to solve 3 successfully. Here I will be explaining all the 3 in layman language with code.

Vestigium (7pts)

You can read the problem statement here.

Solution in C++

This first part of the question where we have to calculate the trace of the matrix is pretty easy and done in a single for loop. If you don’t know what is a trace of a matrix then trace is defined as the sum of elements on the main diagonal. If there is 3x3 matrix A then the trace will be the sum of main diagonal elements(i.e A[1][1]+A[2][2]+A[3][3]).

Now the next part is checking if the matrix is a Latin Square. If you don’t know what is Latin Square then click here. Using a set data structure here is a better choice as we want to check if all the elements in a row and column are unique and set can’t store duplicate values. So the logic will be traversing the matrix in row-major order and column-major order and store them in a set. If the length of the set is less than the size of row or column then it contains duplicate values and hence it is not a Latin Square.

Now putting everything together the final code looks like this.

Nesting Depth (5pts,11pts)

You can read the problem statement here.

Solution in Python

In this question, we will keep a counter for the brackets. An opening bracket ‘(’ is a +1 and closing bracket ‘)’ is -1. We will compare this counter to the number that we encounter while traversing through the input. There will be 3 cases :

1. When the integer value of the counter is greater than the number at which the pointer is. So, we will add closing brackets before the number and subtract 1 from the counter until the value of the counter and the number is not equal.
2. When the integer value of the counter is less than the number at which the pointer is. So, we will add opening brackets before the number and add 1 to the counter until the value of the counter and the number is equal.
3. When the integer value of the counter is equal to the number at which the pointer is. We will skip the number and not add closing or opening bracket.

Here is the solution

Parenting Partnership Returns (7pts,12pts)

You can read the problem statement here.

Solution in Python

I solved this question using the Greedy Algorithm (There can be other ways too). Here we have to schedule activities for Cameron and Jamie so that other activities don’t overlap in their schedule and print the activities that are done by Jamie ‘J’ and Cameron as ‘C’(Solution will look something like ‘JCCCJCCJ’) and if that’s not possible print “IMPOSSIBLE”. As every activity scheduling question sort the array by its starting time. Now we have to traverse this sorted array and start putting the activity under Cameron or Jamie by comparing the end time of their last activity. For this, we will store the index of their last activity. We will give the first activity to Cameron in every test case. Now come the 3 cases:

1. We will check if the activity can be scheduled for Cameron by comparing the starting time and ending time of the previous activity and the current activity. If it can be scheduled to Cameron then we will update the variable storing the index of last activity that was scheduled to Cameron.
2. If it is not possible to schedule it to Cameron then we schedule it to Jamie as Jamie does not have any activity scheduled and update the variable storing the index of last activity that was scheduled to Jamie.
3. When Jamie has one activity scheduled then we will start comparing. Now when the next activity comes and it cannot be scheduled to Cameron then we will compare the ending time of the previous activity to the starting time of this activity. If it can be scheduled to Jamie then we will update the variable storing the index of last activity that was scheduled to Jamie. If it can not be scheduled to Jamie then it is IMPOSSIBLE to schedule it then we will print “IMPOSSIBLE” and break the loop.

While printing the final answer (When the answer is not IMPOSSIBLE) we have to take care that we print it in the format the activities are given to us. For that, I have made a deep copy of the array that contains all the activities before sorting them. Now when scheduling the activity, search them in the duplicate array and add the char ‘J’ or ‘C’ at that index the activity is in the duplicate array.

Here is the code

These are the solution to the 3 questions in layman language that I was able to solve in Code Jam 2020.

Don’t forget to leave comments! Leave constructive feedback in the comment section.