My Experience | Google Code Jam 2015 (Qualification Round)

Bony Roopchandani
Mar 6, 2017 · 3 min read

And so it ended up and ended up well. Around 23000 coders from all around the world participated in the 2015 Code Jam Qualification round which took place online on 11th April.

Overall there were four problems arranged from easy level to somewhat intermediate level. I solved small sets for all the four problems and large sets for the first two and ended up @ 2282 world rank with some penalties.

Problem A. Standing Ovation
Here the shyness level of each person is given and that he/she won't stand until other Si audience have already stood up. We need to calculate the minimum number of additional people needed for everyone to stand.

My Solution
Simply just iterate over all shyness levels and keep adding the audience up to that level. If at any point the sum goes below the number of people needed, increment the sum to that point and add the incremented value to result.
Time Complexity: O(S-max).

int N;
cin >> N;
int result = 0, currentSum = 0;
string S;
cin >> S;
for (int i = 0; i < S.length(); i++)
{
if (S[i] != '0' and currentSum < i)
{
result += (i - currentSum);
currentSum += (i - currentSum);
}
currentSum += (S[i] - '0');
}
cout << "Case #" << (cs++) << ": " << result << endl;

Problem B. Infinite House of Pancakes
Some diners are given a non-empty plate of pancakes and we have infinitely many other diners empty-handed. Each pancake takes 1 minute to eat by the diner. In a special minute, some pancakes may be transferred from one diner to other diner’s plate. We are asked to find the minimum minute(s) required to eat all the pancakes.

My Solution
At first, this problem looks difficult but here’s the logic which makes it easy.

The pancakes will be eaten in minimum time if all the plates have equal number of pancakes.

Firstly, we find the maximum time needed to eat all the pancakes without special minutes. This will be the maximum value over all values. Then we can use do a clever brute force and at each iteration try to reduce the maximum time by applying some special minutes.
This is not a very efficient solution but it works for me.
Time Complexity: O(max(Pi)*D).

// function returning special minutes
// when each plate has f pancakes
int getSpecial(int *a, int n, int f)
{
int ret = 0;
for (int i = 0; i<n; i++)
{
ret += (ceil((double)a[i] / f) - 1);
}
return ret;
}
int main()
{
int n, result = 0;
cin>>n;
int a[n + 5];
for (int i = 0; i<n; i++)
{
cin>>a[i];
result = max(result, a[i]);
}
for (int i = result - 1; i>= 1; i--)
{
int x = getSpecial(a, n, i);
result = min(result, x + i);
}
cout << "Case #" << (cs++) << ": " << result << endl;
return 0;
}

My solutions for problems C and D are not much interesting and one can always look them up on GitHub. In problem C, I used pure brute force and for problem D I just hardcoded the values since the constraints are not huge for the small set.

Overall I enjoyed the Qualification round. Next round on 18th April. Will keep you posted.

Originally published at blog.bonyroopchandani.com on March 6, 2017.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade