Can Anyone Tell How this solution Got Accepted in Recent CookOff72

general
, , , ,
1

So i was checking some High rated Coder’s Programs and i went through this solution

Problem : - This is the problem
Solution : - This is the solution
Programmer : - Here he is

Can anyone understand this code and tell me how did he solve it?

4 Likes
2

amazing solution…what the hell is this?

3

There are probably not such strong cases which can beat the random output solution. Maybe not for this question :3

4

Amazing…
He prints random string of length 10^5.

There will always be such combination such that we can get to the cell with value “C” (capital city).
There will be a high probability such that it gets to the cell with capital city.

1 Like
5

He just got lucky. I submitted this code after reading this and got WA twice, but on third attempt I got AC too. Weak test cases I think.

6

Here is one more such solution. Short and Sweet! :slight_smile: Right now it is the top rated solution in practice section, with minimum time and memory. I think it’s truly amazing to have coders like these. Cheers to @codemart786

https://www.codechef.com/viewsolution/10902880

To those who are wondering how it got AC, it is because they got lucky. It is not a proper algorithm and you might get WA a few times before it gets accepted. I wish setter had put stronger test-cases.

Here is another solution from @codemart786, which got WA:

https://www.codechef.com/viewsolution/10902867

Other such example is as follows:
By @cc15:

WA:
https://www.codechef.com/viewsolution/10902371

WA:
https://www.codechef.com/viewsolution/10902375

AC:
https://www.codechef.com/viewsolution/10902398

The code is exactly same in all the three links.

Can anyone understand this code?

Yes! They have printed out random instruction of length 99999 OR 100000, and b’coz they got lucky, it got AC.

3 Likes
7

really shocked to see that first soln. why do they put such question when you are not deterministic about solution. I even tried that random thing during contests but it failed system tests so should i blame my luck or your question making abilities.

I would be glad if can you help me know where i am getting this wrong

https://www.codechef.com/viewsolution/10900068

My approach ->

  1. precompute all path strings from one city to another using dfs

  2. start from each city , find the new posn the robot reaches after covering the string we have made so far

  3. add to the string dp[new _ pos _ row][new _ pos _ col][city _ row][city_ col] + dp[city _ row][city_ col][ cap _ row][cap_col]

8

Why was so many steps as 100000 allowed? I find it tricky to create test cases requiring more than just 1000 steps.

9

@tony_hager I think so you haven’t read the tutorial. You will understand it why 100000 steps, once you go through the editorial. I agree with you that 100000 steps are more than required. But if you look at the corner cases, 1000 steps aren’t sufficient either. We need way more than 1000 steps to come up with a correct answer.

1 Like
10

Can you show a test case needing way more than 1000 steps?