PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Abhinav sharma
Tester: Aryan, Takuki Kurokawa
Editorialist: Pratiyush Mishra
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Dynamic Programming.
PROBLEM:
There are K travellers who want to travel through a country one after the other. The country is in the form of a 2-d grid and is divided into N rows and M columns, such that each cell of the grid can be considered to be a city.
Each city is initially marked with either 0 or 1. Let city (i,j) (the city at the intersection of the i_{th} row and j_{th} column) be marked with number C_{ij}. If a traveller is in the city (i,j), then
- If C_{ij}=0 and j<M, then the traveller moves to city (i,j+1) and at the same time C_{ij} is changed to 1.
- If C_{ij}=1 and i<N, then the traveller moves to city (i+1,j) and at the same time C_{ij} is changed to 1.
If the traveller cannot make a move from a city (i,j), then this city is considered to be the destination of that traveller. Each traveller starts their journey from city (1,1), and all but the first traveller start their journey only once the previous one has reached their destination. Find the destination city of the K_{th} traveller.
Quick Explanation
We will find the state of the grid when k_{th} traveller starts its journey. Now, for any cell (excluding the ones on right and bottom boundary), its value in the required state is only dependent number of travellers that passed through this cell. So, initially we will compute for each cell ,the number of traveller that reached here. This can be computed using dp and initial state of cells.
For cells on right boundary, if its initial state is 0, then it will always remain 0. Otherwise if it’s 1, the first traveller that reaches this city will cross it and move to next, after that its value changes to 0 and it remains same thereafter. Similarly for bottom row.
Once we find the final state of the grid, we can move the k_{th} traveller according to the rules of the question to get to its final position.
Explanation
Let us call dp[i][j][l] as the number of travellers visiting the state at the grid (i,j) when its C_{ij} value is l. The first part of the problem requires calculation of this dp. Let us proceed with that.
- First covering the base case:
For rest cases assuming, we take another variable total as:
- Case when covering the last column, i.e j = m-1. Here if the C_{ij} value of a cell is 0 then it remains 0, otherwise it would change to 0 as soon as any visiter visits this cell and then it remains 0
- Case when covering the last row, i.e i = n-1. Similar analysis here as that for last column.
-
Rest all cases:
dp[i][j][0] =\begin{cases} \frac{total}{2} \\ \frac{total}{2} + 1 \;if\; k\;is\;odd\; and \; initial\; value\;of\;cell\;is\;0\end{cases}dp[i][j][1] =\begin{cases} \frac{total}{2} \\ \frac{total}{2} + 1 \;if\; k\;is\;odd\; and \; initial\; value\;of\;cell\;is\;1\end{cases}
With that we computed our dp. This would help in determining the final state of the grid when the k_{th} traveller will start travelling. This is because by knowing the number of people visiting a cell, we can determine the number of times the value of that cell has changed and thus find the final state of the cell when k_{th} traveller is visiting the cell. Thus knowing the state of the cell, we can just move according to the rules given in the question to get to the final position of the k_{th} traveller.
TIME COMPLEXITY:
In this algorithm, we iterated through the 2D array which takes O(NM) time. Also while traversing the 2D array according to the rules of the question for the final state of the grid before the k_{th} traveller starts its journey, at worst we would reach the bottom right cell that would again take O(NM) time. Thus in total the time complexity is O(NM).
SOLUTION:
Editorialist’s Solution
Setter’s Solution
Tester-1’s Solution
Tester-2’s Solution