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

×

SKIING - Editorial

2
1

Problem Link

Practice
Contest

Setter: Hasan Jaddouh
Tester: Amr Mahmoud
Editorialist: Bhuvnesh Jain

Difficulty

EASY-MEDIUM

Prerequisites

Strongly Connected Components, Bfs / Dfs

Problem

Find the minimum number of cells to select in a matrix so that we can reach every cell from it through a series of moves which is, "You can move from one cell to another only if they are adjacent (i.e. share a side) and the height of destination cell is not more than height of current cell."

Explanation

The edges in the graph will be between cells $(i, j)$ and $(x, y)$, only if they share a side. Also, the edges will be directed as the edge exists from a cell into another only if the height of destination cell is not less than the height of the current cell.

For example in the sample input 1, the edges will be as follows:

Now given a directed graph, we want to select a set of cells so that all cells are reachable from it. The first observation is 2 decompose the graph into Strongly connected components, as there may be cycles in the graph. This is because all the vertices in a cycle can be visited by starting from any vertex.

Now, we have a directed graph in which there are no cycles. (It is also called a DAG). In this graph, we claim that we chose only vertices with indegree $0$ to be in our set as the possible candidate solution.

Reason : Let us say there is an edge $P$ to $Q$ in the DAG. Let us denote the set of vertices reachable from $Q$ to be $S$. Then all vertices in $S$ are also reachable from $P$. But $P$ is not reachable from $Q$. So continuing this process, we will see that only vertices having indegree $0$ are not reachable from any other vertex but they as a set cover all the vertices reachable from it.

The DAG of input sample 1 is give below:

In the above figure, $1$ represents the set ${1}$, $2$ represents the set ${2,3}$, $3$ represents the set ${4,7}$ and $4$ represents the set ${5,6,8,9}$.

Thus, the algorithm is as below:

  1. Construct the directed graph from the grid. Complexity is $O(N * M)$. Also, the number of edges in the graph is bounded by $(8 * N * M)$ as each cell can have at most 4 neighbors and it can have edge in both directions.
  2. Decompose the graph into one with no cycles. You can use Tarjan's algorithm or Kosaraju algorithm for this step.
  3. Find the number of vertices with indegree $0$ in DAG.

Author's Solution

The solution counts the number of components having same heights, such that all adjacent components are less (strictly) than it.

Proof: Each such component consisting of all cells of same height can be represented by 1 cell only. Now, each component can either have all adjacent components less tha it or not. If all cells adjacent to it are smaller, the those can be reached from the current cell, so they are ot counted towards the answer. If we repeat this process, for each component, we are bound to find only those cells which will contribute to the answer. Also, if we assume some cell that shouldn't be in answer was counted by above process, the it would contradict the fact that all adjacent components are lesser than it.

The above process can be simply implemented by a dfs call from every vertex and check if all components adjacent to it are smaller than it or not. For details, refer to author's solution.

Time Complexity

$O(N * M)$, per test case.

Space Complexity

$O(N * M)$

Solution Links

Setter's solution
Tester's solution
Editorialist's solution

This question is marked "community wiki".

asked 19 Nov '17, 21:27

likecs's gravatar image

6★likecs
3.7k2481
accept rate: 9%

edited 21 Nov '17, 09:03

admin's gravatar image

0★admin ♦♦
19.8k350498541

1

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

(22 Nov '17, 12:22) yadnesh_viper3★

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.

link

answered 20 Nov '17, 09:13

shubhamkothari's gravatar image

4★shubhamkothari
513
accept rate: 0%

Solution with DFS for this question gives me runtime error. But this works fine with BFS.

Same thing happend during September Long challenge with FILLMTR question.

Is here anyone who solved this question with DFS in JAVA?

Thanks in advance.

link

answered 20 Nov '17, 02:24

chef_keshav's gravatar image

5★chef_keshav
623
accept rate: 0%

3

The runtime error is due to stack overflow. Apparently the stack size parameter for Java has been reduced, I'm not sure why :/
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.

(20 Nov '17, 06:10) meooow ♦6★
1

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.

(20 Nov '17, 13:20) chef_keshav5★

@chef_keshav faced same problem.. DFS accepted in cpp. giving NZEC in java..

link

answered 20 Nov '17, 02:55

nik_84's gravatar image

5★nik_84
537
accept rate: 0%

@chef_keshav & @nik_84

Regarding implementing DFS in JAVA:

It seems as though implementing DFS recursively will result in a NZEC. The JAVA wiki suggests implementing DFS with a stack instead to prevent this problem. I did as suggested and got the answer correct. My solution. If anyone has managed to implement DFS recursively in JAVA please include your solution.

link

answered 20 Nov '17, 03:02

xyoends's gravatar image

2★xyoends
313
accept rate: 0%

edited 20 Nov '17, 03:04

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. :)

link

answered 21 Nov '17, 16:46

muditsaxena1's gravatar image

1★muditsaxena1
212
accept rate: 0%

edited 21 Nov '17, 22:29

I dont like this. They should have reduced the constraints. My same solution with c++ got AC but NZEC in java. And i had no clue why i was getting NZEC.

link

answered 20 Nov '17, 06:54

siddharthp538's gravatar image

4★siddharthp538
2555
accept rate: 11%

Hi there, my Python implementation (committed after the competition ended) uses something like BFS, not recursive. I receive NZEC when I submit, but it works fine in my tests, even the one with 1000x1000 of 10**9 height as input.

I couldn't figure out why it's crashing. Can anybody help me, or suggest an input that will cause it to crash? Thank you!

Note: I know there's a logic mistake there. I didn't fix it because I was too busy looking for the cause of NZEC. In the 4th test case example I showed that it produces an incorrect result, but does not crash, so I'm still lost.

Thank you all in advance :)

link

answered 20 Nov '17, 06:42

bilalakil's gravatar image

3★bilalakil
32
accept rate: 0%

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!

link

answered 20 Nov '17, 23:06

mstou73's gravatar image

4★mstou73
1
accept rate: 0%

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.

(21 Nov '17, 00:51) likecs6★

Yes you're right , i didn't notice this .. Thanks for the help!

(21 Nov '17, 01:59) mstou734★

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

link

answered 21 Nov '17, 10:07

gautamcse27's gravatar image

2★gautamcse27
375
accept rate: 0%

No, i use draw.io and graphonline.ru/en/ for help, along with paint.

(21 Nov '17, 18:07) likecs6★

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

link

answered 22 Nov '17, 21:54

shubho96's gravatar image

1★shubho96
1
accept rate: 0%

Read the comments and answers here lol....

(22 Nov '17, 22:09) vijju123 ♦♦5★

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?

link

answered 27 Nov '17, 06:38

gautamcse27's gravatar image

2★gautamcse27
375
accept rate: 0%

"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.

(28 Nov '17, 15:50) likecs6★

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)

link

answered 28 Nov '17, 21:09

coder_ishmeet's gravatar image

4★coder_ishmeet
214
accept rate: 0%

1

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

(28 Nov '17, 23:39) likecs6★

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

(29 Nov '17, 00:10) coder_ishmeet4★
1

@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

(29 Nov '17, 18:31) likecs6★

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

(30 Nov '17, 14:59) coder_ishmeet4★

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.

link

answered 17 Aug '18, 00:45

aman_robotics's gravatar image

6★aman_robotics
1217
accept rate: 6%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,855
×1,024
×801
×593
×102
×98
×38
×34

question asked: 19 Nov '17, 21:27

question was seen: 2,260 times

last updated: 30 Nov '17, 14:59