SKIING - Editorial

My solution was to begin from the cell whose height is maximum and finding all the cells which can be visited by using simple dfs from that cell, and continue this process until all the cells are visited.

Thoughts behind this greedy approach : You cannot visit the cell with max height from any other cell whose height is less than it, and can be visited only by using cells with same height so in order to visit this cell you can start from any cell with same max height and do this process continuously.

Refer to this implementation for more details.

3 Likes

Hi guys, I know this might be a silly question but my submission gets TLE and I cant figure out why…I have implemented BFS in C++ , almost identical to the Editorialist’s solution. Can anyone help me? Code here
Thanks in advance!

How did you draw the dag for the above first sample input?Is there any way to draw the dag for any graph?

My implementation is much easier but complexity is more. Still got AC in 0.12s.

I have made a structure having height, row and col for each cell. Then I have sorted vector of structures according to height(decreasing order) to get the cell which has max height first. Then if the cell is not previously visited then I have applied DFS on that cell.

Time Complexity O(mnlg(mn))

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

Although during contest I have solved in O(mn)

I hope you like it. :slight_smile:

2 Likes

Can some one tell me what is the problem here. This code works fine with the testcases but give a NZEC when I submit it. I used a DFS in java.Here’s my code:
https://www.codechef.com/viewsolution/16348375

in Editorialist’s solution why has been two array dx[4] = {-1, 1, 0, 0} and dy[4] = {0, 0, -1, 1} used and sort(vals.rbegin(), vals.rend()) sorts which part of the vector?

can anyone plzz tell me in order to solve this question i have to learn KOSARAJU’S ALGO or not , i know nothing about SCC and very weak graph thory(i.e BFS and DFS)

I am sorry that I can’t comment at the top, but I want to add on to @chef_keshav and @meooow comments that this soln in JAVA works fine with dfs.

The runtime error is due to stack overflow. Apparently the stack size parameter for Java has been reduced, I’m not sure why :confused:
Here is a submission I made just now with a simple recursive function upto depth 105: 16323256. It gives RE.
And here is another submission I made in January of this year where recursion goes upto 106 without any error: 12408377.

3 Likes

I have submitted recursive DFS on Codeforces upto depth 10^6. It works fine there.

I think only solution is to do BFS on non-recursive DFS on Codechef.

1 Like

you first mark vertices as visited and then push them into stack, this is important when there are 2-length cycle in graphs. See, my exact code for details.

Yes you’re right , i didn’t notice this … Thanks for the help!

No, i use draw.io and Create Graph online and find shortest path or use other algorithm for help, along with paint.

I think the link to the tester’s solution is wrong. It is again redirecting on this page.

1 Like

Read the comments and answers here lol…

“dx” and “dy” array together form the possible adjacent vertices in grid while “sort(vals.rbegin(), vals.rend())” sorts the given array in descending order.

Hi, you can also solve it gredily also. See above comments for help.

1 Like

Can u plzz explain again where the concept of SCC is being implemented in this problem or if without SCC how to solve it ?

@coder_ishmeet, SCC is used to find the directed acyclic decomposition of graph as mentioned in editorial. The other approach without SCC is mentioned in author’s solution and comments above. like this one

1 Like

ohkay thnkss alot… i will solve this question with or without SCC both