My Experience | Google Code Jam 2015 (Qualification Round)

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 wont 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 upto 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’s to other diner’s plate. We are asked to find the minimum minute(s) required to eat all 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 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 small set.

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