AUG18 - Problem Discussion

Hey guys!!

Finally after 10 tiring days the August long concludes. Lets share our approaches for the problems here while editorials for problems come out (at this moment not all of them are out)? Got any interesting approach which you cant wait to share? The wait is over :slight_smile:

So, which was your favourite problem? I had best time solving Interactive Matrix :). The princess gave me a run for my score xD - so I let her stay with dragons and be by herself then :stuck_out_tongue:

But on a serious note, anyone who was able to save the princess (or prince…? :p). I kept on getting WA for larger TCs, so I appreciate any approaches for it :slight_smile:

Let the discussion begin!

1 Like

Can anyone share approach of Interactive matrix in short ??
@vijju123 :smiley: ??

For K-Compressed problem, I thought it could be solved using topological sort. Think about it as there is an edge from smaller vertex to larger, in subarray. Vertex with 0 inDegree is assigned currentNumber, and currentNumber is incremented on each iteration. Vertex with same values are assigned together.

Got 40 Points. Turns out Segment Tree is the answer ¯\(ツ)

I dont have any interesting solutions :frowning: . I solved the first 4 problems and editoirals of 3 of them are already out. My solution for interactive matrix is pathetic as well :frowning:

I dont have any interesting solutions :frowning: . I solved the first 4 problems and editoirals of 3 of them are already out. My solution for interactive matrix is pathetic as well :frowning:

If you look at the question from direction of “Ok, how do I make the sequence B” you get the problem reduced to "You need to find maximum element in given range to assign correct value to B_i". This gave a big hint of seg tree for me.

okay np xD

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 (2N) 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 2N 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 :slight_smile:

A lot of things to learn as always :slight_smile:

4 Likes

River problem was finding “Minimum vertex cover” (i.e. minimum number of nodes to remove to disconnect entire tree, in other words, minimum nodes to remove so that degree of all remaining nodes is 0).

Lonely cycle was hugeeeee pre-processing for me. Too me 2 days to get the idea and another hour to get it working.

Interactive matrix was fun and a nice mix. Although the distribution of problem in divisions tell me it was solved by more people than intended, but loved this question nonetheless :slight_smile:

Princess was a huge pain. Spent first day thinking its 2nd easiest question T_T

1 Like

Where is being orange treat??

I would argue that segment tree is not the answer, it is only the means to calculate the cost for a particular K quickly. The crucial part here is binary search.

2 Likes

A nice set of problems, looking forward to the editorials :slight_smile:
My only complaint: I would have preferred a more approachable challenge problem, especially since the other problems were harder than usual. A challenge problem is usually fun and something I turn to and try to optimize whenever I am stuck with the other problems. But this is just my opinion, others may disagree.

1 Like

Two ‘alternative’ approaches to solve Interactive Matrix:

  1. Write a function which takes a row index as input and searches for the key in that particular row. To reduce the number of queries, design a small ‘value predictor’ function which attempts to calculate the minimum and maximum possible value of the cell (i, j). Query Chefina only if the value to be searched lies within the predicted value range.
    Now, select random row indices, and feed it to the above function (YES, random rows, because quite obviously, one cannot completely the search the matrix using this approach; therefore, “take a chance”).
    Solution link: https://www.codechef.com/viewsolution/19605485

  2. Well, there is always an option to implement binary search in real life… Search through the first 400 rows and note down the test cases passed. Then search through the first 200 rows and repeat the same, until you obtain the set of row indices which might contain the key. During the final run, search through these obtained row indices only.
    Solution link: https://www.codechef.com/viewsolution/19620555 Take a look at this solution and admire the effort put behind it…

1 Like

True. I tried so hard but it seemed like writing a barely working code for challenge problem was a challenge indeed!!

Who became orange? :o

Oops orange is >= 2200.

A Lot of Programmers got 40 points for KCOMPRES.

I have used binary search+ max segment tree and I am not getting why my last test testcase of final subtask Failing!

can anybody look into it

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

ohh you missed by 48
@vijju123

Can you provide proof for that your interactive matrix solution will yield answer in less than 4N questions?

GCDMOD overflows :confused:

I submitted it ~10 times in C++ trying out variations of bigint classes which all failed

Then I tried to implement it in Java with bigint(I’ve never used Java before :p) and that TLEd for the second and third subtasks

So I took the easy way out and stuck to Python