CHEFIHG - Editorial

@ aayush_10zn Yes the test cases are now modified , now they are not accepting the solutions, which have randomly generated output…:frowning:

really shocked to see that first soln. why do you 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.

Edit : its still accepting that random soln.

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]

If do start bfs from point C and build a string array s[i][j].s[i][j] is the path from point C to point (i,j).After bfs just go to every (i,j) which is ‘.’ and reverse the string and replace ‘U’ with ‘D’ and ‘D’ with ‘U’ and R with L and L with R. Add all strings which contain path from (i,j) to C .
complexity is O(n^2).
if u manipulate string arrays while calculating bfs then complexity will be O(N).

Why does one need to find the string for the node farthest from the capital? Why can’t one start from any random node and follow rest of the procedure?

The random output solution still gets accepted.

The exactly same random output solution, might give different verdicts when submitted more than once, because its output is not same every time.

And one might have to submit it more than once to get AC.

Can we select one non-prohibitted area which is near to the Capital city and then move to the capital city. This requires only two characters in the command but solution can be correct.
Please correct me if I am wrong because this way the solution can be very very easy.

I have a doubt regarding this question. It was mentioned that we can choose any non prohibited cell as the starting point. To reach C any of the U,D,L,R should be non prohibited. So, if I just start from any non prohibited cell that lies either U,or D,or L, or R of ‘C’ and then just take it to C using single instruction, why am I getting WA? Pardon me if I understood the question wronmg.

@karanaggarwal I started from the Capital and went to each and every city and then reversed the string and replaced L with R, U with D and vice-versa. For all my custom test cases the code worked fine. But still its not getting accepted (WA). If you could help me figure my mistake out, I would be grateful. Below is the link to my code.

Thanks

Small question - does anybody know how to find exact probability of random string of length L being a solution to some particular input file?

Like I showed in CF comment, it has at least 15% chance to fail in this problem.

Random note regarding bounds on total sum of path lengths - in order to have cell with distance 300 from capital, you need to have a cell with distance <=1, a cell with distance <=2, a cell with distance <=3 and so on - all of them will be on the path from our “bad cell” to the capital. With this observation you can safely decrease bound to something like 53k.

BTW, just curious - what’s the input file on which this algo produces longest possible string, and what’s the length of that string? :slight_smile:

The Qs is still accepting solutions which are randomly generated.

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

We had discovered it during the testing, we tried some test cases which can break some of the randomized solution. It was really hard to generate test cases for it. I would be interested if someone has a good test case to break such solutions.

2 Likes

What was that :3 :3 :3

“That guy would have never guessed this thing .”
That guy is one of the top competitors worldwide, so I’m pretty sure he would have.

2 Likes

I <3 Tanya Romanova :stuck_out_tongue:

This isn’t I_love_Tanya_Romanova’s solution, this is solution of Tanya Romanova ( romanova | CodeChef User Profile for Tanya Romanova | CodeChef )

4 Likes

Exactly lebron | CodeChef User Profile for Bohdan | CodeChef
And this is his solution : CodeChef: Practical coding for everyone

A case like this would not have allowed this: :frowning:
20 20
C…
.

.


.

.


.

.


.

.


*********.

.
.
.
.
.
.
.
.
.
.

to enforce boundary restriction u can make the case for 1919 and then put '’ along the boundaries to get a 20*20.

I know he isn’t I_love_Tanya_Romanova, I meant to say that, I love this(not orig) Tanya Romanova :stuck_out_tongue:

Who told that ?
Non-determinism is something which can never be beaten-

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

3 Likes