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

In process

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 by counting array b and somehow it got accepted.

Code

Counter-test can be generated by this code:

cout << 100000 << " " << 50000 << endl;
for (i = 0; i < 100000; i++)
 cout << i << " ";
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