Блог пользователя Wild_Hamster

Автор Wild_Hamster, история, 8 лет назад, По-английски

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

Counter-test

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

Counter-test

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 [ans1, ..., ansn].

The sum of absolute differences between each pair of elements will be (ans2 - ans1) * (n - 1) * 1 + (ans3 - ans2) * (n - 2) * 2 + ... + (ansn - ansn - 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 ansi + 1 - ansi 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 * 106 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 * log3(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(N2) solution.

I wrote this code:

Code

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 × 109 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$ are 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.

  • Проголосовать: нравится
  • +229
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

Maybe you don't believe me, but I am even happy when see discussion about my task in the blog like this one :)

I agree with things about bad testcases ( I talk generally ), it must be improved, every setter/tester should spend a lot of hours for making it better !

But many times it can not be cut ! There is more than 5000 coders on the round, certainly some are better than both setter/tester also they have three days to hack testdata. It is not so small period! People think different, so it is not expected to cover all cases , possible WAs etc...

This story is not only about HR it is situations on other platforms too, honestly it is not so often as HR, but I am not doing contests there too much as on HR ( but I had a lot of situations with totally bad greedy and other tle codes)...

CodeForces doesn't have a lot of such tasks but do not forget that here we have only 2 hours for all solutions + hacking + extra testcases which were added several time after round...

I was working on my task with danilka.pro good amount of time, we tried a lot of solutions, I strongly believed that this solutions will receive 70% score, but you added some extra modifications and hacked it. I saw several such codes, many coders solved it online and after 5-10 times submissions they received full score. Also there is a lot of codes with similar ideas which didn't pass all testcases. I am unhappy for it ( I wished difference between such codes and codes like tourist), I could put q=1000 or even q=10000 and finish conversation about that, but than some really nice online solutions wouldn't pass :)

At the end I am happy with rate of good submissions, I think that challenge located well on the sixth place, but this is one more experience for me which will help me to be better and more careful in future !

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится

    Tasks were cool, but testcases were weak.

    I think that all problems must contain a couple of testcases with maximum/minimum values for their constraints(like almost all my counter-tests).

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится -33 Проголосовать: не нравится

      I won't talk more about these tasks and testcases, certainly wasn't everything fine, I have shared my opinion on both blogs several times and got a lot dislikes :)

      I more prefer system with smaller amount of testcases and each with a lot of queries. Reason, it is faster for judge, easier for participants + easier for setters and tester. But for sure the best option is a lot of testcases each with lot of queries.

      As you written in blog for my task, that is not very big fail of testcases, but for sure I will try to avoid it in future — if I decide to prepare more tasks !

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +26 Проголосовать: не нравится

      I agree that all problems should have a couple of maxtests but there are some problems (for example, the task prepared by allllekssssa) for which it is not really clear what a maxtest is. It may either be a test with all N-s equal to 50 or a test with all N-s being different. And the author can't really predict all possible scenarios.

      And yes, it really sucks when O(N * Q) solutions pass problems with queries, but it happens. It really does happen and it has happened not only once or twice on Codeforces, too. We just don't remember that because there are no CF rounds these days :D (Just joking about the "no CF rounds" part, you are still my favourite judge, Codeforces).

»
8 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Another example — In the recently concluded sears hackathon(with >$15k prizes): https://www.hackerrank.com/contests/sears-onsite/challenges/greedy-strategy (all might not be able to see this link as the contest is private)

Many of the accepted solutions give runtime error on simple max-test — 100*100 matrix with all ones and A=1, P=1. I wonder how can the author/setter could not think of such a simple max-test.