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

In process