You are not logged in. Please login at www.codechef.com to post your questions!

×

# CHEFIHG - Editorial

Author: Misha Chorniy
Tester: Karan Aggarwal
Editorialist: Pushkar Mishra

Easy-Medium

# PREREQUISITES:

Breadth First Search, Graphs

# PROBLEM:

Given is a matrix of dimensions $N\times M$ in which some cells are marked with ".", some with "", and one with "C". The "." indicates that the cell can be visited, "" denotes restricted cell and "C" denotes the capital city. We have to give a sequence of moves of length at max $10^5$ in terms of "L" (left), "R" (right), "U" (up) and "D" (down) such that a robot starting from any "." cell in the in the grid and following the sequence of moves visits the "C" cell at least once.

# EXPLANATION:

This problem doesn't require much thinking beyond the brute force way to do it. However, it is implementation heavy.

It is given that our matrix can at maximum be of $20 \times 20$ cells. This clearly hints towards the algorithm being close to brute force. Let us think about all the "." cells one by one. To begin with, let us look at the farthest "." cell from the capital city. How far can it be from the capital city? It is given that all the border cells are "*". This means that there can be a maximum of 400 - (20 - 20 -18 - 18) = 324 cells at maximum which are "." marked.

This tells us that the shortest path from any "." cell to capital city is at max 324 instructions (instructions being "L", "R", "U", "D") long. We first make a string of moves for the cell "." that is farthest from the capital city. For all other "." cells, we will have to execute the the same moves as well. After all the commands are executed, the farthest one has reached the capital city, and the others are in some position in the grid (most likely, not in the position they were).

Then we pick another one, and make it reach the capital city. The sequence of moves it takes for this is appended to the string we had from before, and all the remaining "." cells are again moved accordingly. We continue doing this for each of the "." cells till we have made each of them reach the capital city.

What is the length of the string at the end of all these operations? We have to move at most 324 cells. As we calculated before, the maximum length for one movement is 324 again. So, in total, 324*324 = 104976. This is slightly more than $10^5$. How do reduce this to below $10^5$? Actually, if we reason a bit more, we will see that the shortest path from any place in the grid to the capital city is 324 in theory only; it is actually much less. This is because 324 will only be if during a path from a cell to the capital, one has to go over all other cells. But why would one do that? We can move in all directions, so we can simply go from one row to its neighbouring ones or one column to its neighbouring ones. This tells us that the path will definitely be much shorter, definitely shorter than something like 305. And 305 * 324 = 98820. This is less than $10^5$. So this works.

But what is the time complexity? For each of the "." cells, we need to first do a BFS to find the shortest move sequence to the capital city. Then, for all the remaining "." cells, we need to make them follow the same move sequence. There can be $\mathcal{O}(NM)$ cells of type ".". BFS takes $\mathcal{O}(NM)$. But moving all other "." cells on the same move sequence takes $\mathcal{O}(N^2M^2)$; hence, this is the costliest operation per "." cell. So the total complexity is $\mathcal{O}(N^3M^3)$. This is sufficient given that $N = M = 20$ in the maximum case.

Please see setter's/tester's program for implementation details.

# COMPLEXITY:

$\mathcal{O}(N^3M^3)$

# SAMPLE SOLUTIONS:

This question is marked "community wiki".

asked 23 Jul '16, 20:21

1.3k156581
accept rate: 4%

2.5k53136170

 27 Look at this solution. Just random Output gets AC :/ answered 25 Jul '16, 00:04 415●1●14 accept rate: 8% 4 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. (25 Jul '16, 00:07) What was that :3 :3 :3 (25 Jul '16, 00:11) lohit_974★ 4 "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. (25 Jul '16, 00:33) xellos07★ I <3 Tanya Romanova :P (25 Jul '16, 00:40) lohit_974★ 8 This isn't I_love_Tanya_Romanova's solution, this is solution of Tanya Romanova ( https://www.codechef.com/users/romanova ) (25 Jul '16, 00:52) mgch6★ Exactly https://www.codechef.com/users/lebron And this is his solution : https://www.codechef.com/viewsolution/10893264 (25 Jul '16, 01:10) biggy_bs4★ A case like this would not have allowed this: :( 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. (25 Jul '16, 01:16) sandeep93★ I know he isn't I_love_Tanya_Romanova, I meant to say that, I love this(not orig) Tanya Romanova :P (25 Jul '16, 01:22) lohit_974★ damn... i tried 2 different values in srand and both got WA, but srand(0) gets accepted (25 Jul '16, 01:28) Would love to hear the reasoning behind this! (25 Jul '16, 15:04) noob3335★ showing 5 of 10 show all
 11 Well, even the tester's solution is random output :3 then why add such a question? answered 25 Jul '16, 00:20 4★lohit_97 342●8 accept rate: 4%
 8 My solution is somewhat simpler: find some decent paths to the capital from every free cell, e.g. by $NM$ times looking at all cells which don't have a path yet and which have a neighbour with a path start with the array S = all free cells while true: add the path to the capital from one of them to the instructions, simulate it from each cell in S, discard those which reach or pass through the capital I didn't really think about how fast this is other than using at most $N^2M^2=160000$ instructions. I wouldn't mind this passing. But random... answered 25 Jul '16, 00:31 7★xellos0 5.9k●5●42●92 accept rate: 10% 1 @xellos0 A random output is giving AC to this solution, so is there a guarantee that everyone who solved it did it correct? Maybe they also got their luck, right? What kind of problem is it? (25 Jul '16, 18:12)
 2 It seems the test cases are modified after the contest. It no longer accepts random generated output. The tester's solution needs to be updated to pass the new test cases. My submission(Copied from the one who tried random approach): https://www.codechef.com/viewsolution/10900542 Note 1: The PROBLEM section needs editing. Typo in "'" instead of "*" answered 25 Jul '16, 00:40 21●1 accept rate: 0% 5 Who told that ? Non-determinism is something which can never be beaten- https://www.codechef.com/viewsolution/10900841 (25 Jul '16, 01:23) sandeep93★ LOL That is awesome! _/_ (25 Jul '16, 01:26) lohit_974★
 0 Well The borders are always blocked with "*" so it can solve most of the cases as dpraveen said..though someone can still find an awesome test case to challenge the solution..:P answered 25 Jul '16, 00:19 23●3 accept rate: 0%
 0 Could someone please find the error :( ?? Solution answered 25 Jul '16, 00:21 1 accept rate: 0%
 0 I implemented the same approach,but was getting WA..whats the problem ? https://www.codechef.com/viewsolution/10899912 answered 25 Jul '16, 00:29 3★sandeep9 478●2●8●27 accept rate: 4%
 0 Could any one provide any test case I implemented the same algo getting WA :( https://www.codechef.com/viewsolution/10900398 answered 25 Jul '16, 00:35 1 accept rate: 0%
 0 @ aayush_10zn Yes the test cases are now modified , now they are not accepting the solutions, which have randomly generated output...:( answered 25 Jul '16, 00:57 21●1 accept rate: 0% My randomized solution with checker passes in same time as during a contest, so I'm not sure if tests are actually updated somehow. (28 Jul '16, 21:48) lebron7★
 0 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 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] answered 25 Jul '16, 05:20 5★saisumit 11●2 accept rate: 0%
 0 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). answered 25 Jul '16, 12:14 1●1 accept rate: 0% Can you share O(N) code? If you mean area of input as N, still it sounds interesting, as you claim that you can build a good string which has size O(N). (28 Jul '16, 21:50) lebron7★
 0 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? answered 25 Jul '16, 13:16 1 accept rate: 0%
 0 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. answered 25 Jul '16, 13:27 1.1k●2●11 accept rate: 10%
 0 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. answered 25 Jul '16, 14:58 1 accept rate: 0%
 0 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. answered 25 Jul '16, 20:20 3★ksut28 31●3 accept rate: 0%
 0 @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. http://ideone.com/gbpAUM Thanks answered 28 Jul '16, 19:02 2★punit13 1 accept rate: 0%
 0 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. answered 28 Jul '16, 21:52 7★lebron 3.3k●3●17 accept rate: 24%
 0 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? :) answered 28 Jul '16, 21:59 7★lebron 3.3k●3●17 accept rate: 24%
 0 The Qs is still accepting solutions which are randomly generated. https://www.codechef.com/viewsolution/11205902 answered 19 Aug '16, 15:51 5★abbi_18 1 accept rate: 0%
 -2 Sir I have one doubt what if by applying the 324 step on the further most,what if any random block becomes the further most(robot moves to further most block),then it is not necessary it will work by this approach. answered 25 Jul '16, 00:51 3★ryuzakil -3●1 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,643
×1,672
×1,218
×505
×59

question asked: 23 Jul '16, 20:21

question was seen: 6,968 times

last updated: 25 Sep '16, 02:56