PROBLEM LINK:
Author: Jatin Nagpal
Tester: अनन्य शर्मा
Editorialist: Jatin Nagpal
DIFFICULTY:
HARD
PRE-REQUISITES:
Implementation, Maths
QUICK EXPLANATION:
From the questions you can ask, you determine which type out of 8 types (for N\neq M, there were 4 types) the Whirlpool is. Now, you have to implement a general Whirlpool which is common for all types.
EXPLANATION:
First of all you have to determine which type of whirlpool is it out of 8 types as explained:-
- Anticlockwise and Clockwise(4 each)
- Ends at which corner out of 4 corners
To find this, we take first element of the first 2 rows(although you could opt for other variations as well), then we determine, it’s type of rotation, by checking the difference between elements(4 possible cases). With the directions, we check where the maximum element is present which has value N*M for which you can check all 8 cases or create something generalised.
Now Starting from the maximum element N*M, you have to fill the entire matrix decreasing value by 1 and taking the type of rotation into consideration, for which you have to heavy case work.
Or what you could do is fill the matrix in the inside with zeroes and outside with -1, giving direction value to each direction, like 0-North, 1-East, 2-South and 3-West, and moving in such a way that for example in Anticlockwise(Clockwise for moving from max element to 1) either the direction remains same or gets incremented by 1 modulo 4, preferring the first. Repeat the steps untill you fill the last element 1.
Time Complexity:
O(N*M)
AUTHOR’S AND TESTER’S SOLUTION:
Author’s solution can be found here
Tester’s solution can be found here