In this post I will describe inadequate solutions for 4 hackerrank problems from last 2 codesprint contest, that I participated(with difficulty hard-advanced), that get 100% score and provide counter-test to each solution.

NCR Codesprint, Coconut Plantation

At first we will water plants, as described in official editorial:

For example, we need to water squares (2,2,3,3) and (3,3,4,4). We add one to the highest cells of this square and decrement one from cells under this square. After we do this with all rectangles, we can get array of watered coconuts by simple cycle:

for (int i = 0; i < r; i++)
 for (int j = 0; j < c; j++)
  b[i][j] = (i>0?b[i-1][j]:0) + a[i][j]; // a[i][j] is array from the picture

We got array b and now we change values of b[i][j] to 1 if b[i][j] >= m else to 0.

In official editorial something is said about HopCroft-Karp algorithm, but I don't even know what is it. So I will try to solve it greedily. We go through all array and find out cells that have only horizontal or only vertical neighbours. It's obvious, that then for horizontal neighbours we have to draw horizontal line through this cell and for vertical neighbours we have to draw vertical line.

We can do nothing after that and this solution will already get 32.00/60.00 points, but it doesn't work even on my random picture case. Code

I will name non-harvested cells free now.

Now we go through all not harvested cells and find out for each cell max(free cells that we can reach from this cell moving horizontally, free cells that we can reach from this cell moving vertically).

Then we sort this cells by decreasing order of this value. Now we go through cells and from each free cell we move horizontally or vertically depending on where is more free cells left. And BOOM, it gets 60/60. Code

Counter-test:

1
7 7 3 1
0 0 6 1
0 0 2 5
4 0 6 5

NCR Codesprint, Area of Triangles

For this task you can just look at this pseudocode and picture and you will understand my solution.

S=0
double dy = 10000000./n;
double dx = (maxx-minx)/dy;
for (double i = minx+dx/2; i <= maxx; i+= dx)
   S += area of triangles on the line x=i //for example for sample case for i=3 area will be equal to 3, for i=2 area=4
print (maxx-minx)*S/dy

Code

Counter-test:

2
-1000000 0 -1000000 1 -999999 0
1000000 0 1000000 1 999999 0

University CodeSprint, Array Construction

I think, I wrote pretty cool solution for this challenge, but it still shouldn't pass TL. Assume, that the answer array for each queue is [ans₁, ..., ans_n].

The sum of absolute differences between each pair of elements will be (ans₂ - ans₁) * (n - 1) * 1 + (ans₃ - ans₂) * (n - 2) * 2 + ... + (ans_n - ans_n - 1) * 1 * (n - 1)

We can go on dp[i][j][k], where dp[i][j][k] means if it's possible to get sum j and sum of absolute differences k for first i elements.

Passing from state to state then will be:

if (dp[i][j][k]) dp[i + 1][j + l * (n - i)][k + (n - i) * i * l] = true

where l is ans_i + 1 - ans_i and we are iterating l from 0 to the time when j + l * (n - i) > 200 or k + (n - i) * i * l > 2000, it will be at average 4 iterations, I guess.

So I precalced dp for all n = 1... 50. It seems, like complexity of this should be O(n * n * s * k), what is very much, but it takes only approximately 67 * 10⁶ operations if we make this dp recursively, but it still couldn't pass TL(precalc was working for 3.3s in CF custom invocation). While dp was done recursively, I was remembering current array, so I could save the answer, when I met triple(i,j,k), that is required from the queries.

But still it works for 3.3s. So I decided not to iterate through all n = 1... 50, but only through n, that was required from the queries and my solution passed in 1.83s. That's not a very big fail in testcases, but it still makes sense.

Code

Counter-test:

50
1 0 0
2 0 0
...
50 0 0

University CodeSprint, Counting On a Tree

I was trying to come up with normal solution like O(n * sqrt(n) * log(n)) or O(n * log³(n)) for whole day, but then I saw this comment. You can see nothing special here, just mad guy, but if you pay more attention to this comment, you will see this sentence: "Problemsetter of last problem said that he will change the test cases, because I told him my old solution with complexity N^2 passed"

CHALLENGE ACCEPTED. It's time to write O(N²) solution.

I wrote this code:

for (i = 0; i < q; i++)
	{
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		ll ans = 0;
		while (!upper(x1,y1))//upper(x1,y1) is function, that check if y1 is in subtree with vertice x1 
		{
			b[a[x1]]++;//a[i] is value of i-th vertex
			x1 = pr[x1];//pr[v] is ancestor of v
		}
		while (y1 != x1)
		{
			b[a[y1]]++;
			y1 = pr[y1];
		}
		b[a[x1]]++;
		
		while (!upper(x2,y2))
		{
			ans+=b[a[x2]];
			x2 = pr[x2];
		}
		while (y2 != x2)
		{
			ans+=b[a[y2]];
			y2 = pr[y2];
		}
		ans+=b[a[x2]];
		cout << ans << endl;
	}

It worked maximum in 1.8s on all testcases and it got WA, because I was not assigning array b to zero and didn't substract the length of two paths intersection. I could go through path (x1,y1) and assign b[a[x1]] to zero, but it would take approximately 0.9s more, so 2.7s will not pass. I almost surrendered trying to optimize this so it will pass in 2s, but then I got an idea. Java got 4s time limit on hackerrank, so I can try to make this solution pass in Java.

I don't know, what's wrong with Java compilator, but same solution was getting randomly TL from set {5,8,11,14,17} of testcases. For example for first time it was getting TL 5,8,14, and for second time it was getting TL 11,17. I separated finding length of two paths intersection by LCA and going through whole path and counting array b, somehow it got accepted.

Code

Counter-test can be generated by this code:

cout << 100000 << " " << 50000 << endl;
for (i = 0; i < 100000; i++)
 cout << 1 << " ";
cout << endl;
for (i = 0; i < 99999; i++)
 cout << i << " " << i+1 << endl;
for (i = 0; i < 50000; i++)
 cout << 1 << " " << 100000 << endl;

My code will get TL for sure and WA because the answer will be approximately 5 × 10⁹ and it doesn't fit an integer.

P.S. This post doesn't contain offense to hackerrank admins and community. I just want to show mistakes, so maybe they will improve. Contests with prize pool 15000$ is pretty cool, but I think that Hackerrank must pay more attention to creating testcases by writing naive solutions to each problem and stresstesting, so inadequate solutions will not pass during the contest.