Kudos to problem setters, really enjoyed the question set.

**Interactive matrix** was fun of all, since all I put in was sheer intuition without checking it for any sample input. My approach was to spend first (2*N) queries to get details of all elements lying is primary and secondary diagonal and mark them either as smaller or larger than the number, if the search element is found, output the answer and exit the program. Moreover from values of diagonal elements, it is easy to say if a row or column is sorted in increasing order or decreasing order. Next, with the sorting order for each row and column known, with the inputs obtained from first 2*N queries, some of squares can be marked off as smaller or greater than the value and hence canāt be answer.

Insert the remaining possible cells (pair of {row,column} ) in a vector. While vector is not empty, randomly shuffle the last element with any of element and query for this row and cell index. Mark this cell as less than or greater than, since we know the sorting order of this row and column, we can predict about the values of elements lying in same row but different column and similarly for same column and different row. So, we can basically make a call to (i,j+1) , (i,j-1), (i-1,j), (i+1,j) and mark them accordingly. And these cells then can again call their neighbhour cells and so on and every cell visited is marked in original grid as smaller or larger value and hence the further queries should only be made for those cells who values are not known.

A better approach would have been to ask for centre of grid containing unknown squares, but random picking of cell is good enough to give better expected value.

Hereās the link to my solution: https://www.codechef.com/viewsolution/19536198

**Lonely cycle** was not so lonely, the possibility of many cycles coming up together ruined my initial approach until, i finally gave up the idea of pre-processing and rather started to memorize the answer for the path travelled. A classic DP approach and the code fetching 20 points fetched 100 points.

**Kcompress**, it took me very long to understand what the question is about and then it was easy. Binary search with Max segment tree, some greedy approach and something like dsu (since elements having same value can have different compressed values) and it was done.

Spent some days but princess was out of reach :p, First, went for N! permutation approach to get 10 points, then 2^N approach to get another 10 points. I got an interesting conclusion that answer for all possible caves will be max(Sol[1]-k,p), where sol[1] is the minimum values required to sum up to given strength and k is ith cave. p is the answer for when the princess is in middle of cave. I couldnāt solve for p and kept on trying to optimize my dp.

The river problem was good too, I think the idea was of centroid decomposition but dināt tried the problem.

Looking forward for official editorials

A lot of things to learn as always