AUG18 - Problem Discussion

general
,
3

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: CodeChef: Practical coding for everyone

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
4

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
5

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: CodeChef: Practical coding for everyone

  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: CodeChef: Practical coding for everyone Take a look at this solution and admire the effort put behind it…

1 Like
6

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

7

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

8

For LONELY CYLCES I constructed a spanning tree of graph such that any edge which is not included in it connects u and v such that (lca(u, v) != u and lca(u, v) != v).

Then I marked all the edges which are part of cycles as blocked and which are not in spanning tree as red.

Then I just ran dfs to calculate the number of possible vertices I can reach from a given verices using dpdown - when I go down, dpup → dp up taking care that I never visit more than 1 blocked edge.

Then calculated the answers for each type of edge, normal , red, blocked accordingly

I tried a lot of test cases and on each I was getting the right answer still got WA. If anybody can point out what I am missing…

My submission

9

In the princess and dragons problems can the values of the dragon strengths be negative?? I tried to solve the problem for the first 3 subtasks but got WA on the 2nd and 3rd but the first one passed. I am having this confusion because although it says the main constraint is 1≤Si≤105 but in the constraints of the subtask 3 which i got WA on says Si≤2,000 , nothing mentioned about the lower limit . Thank you .

10

I solved GCDMOD with a greedy approach, still cant prove that is right but i got AC
A = gcd( a^n+b^n, |a-b| ) = gcd( a^n + b ^n , |a-b|, a^n - b ^n) : assume: a>b, if(a=b) its simple
=> A= gcd( 2a^n, 2 b^n, |a-b|) = gcd ( 2*gcd(a,b)^n, |a-b|) so now its simple

11

I don’t think this was the intended solution, but in the GCDMOD problem, we get the same answer whenever n > 1. If n >= 2, set n = 2 and print the answer directly. Only special case is a == b, in which the answer is 2 \times a^n. Here’s my AC Submission.
Can anyone prove why this works?

12

Can the interactive matrix problem be solved by the following approach.
First 2*n queries to determine the nature of the rows and columns(increasing or decreasing)
Now,
Select a mid=(l+r)/2;
now in the column mid apply a binary search to find the range in which possible value of key can lie
now in the row mid apply a binary search to find the range in which possible value of key can lie
Select only those cells which are part of both row and column range and make a new matrix of only these cells.
Continue the process till only 1 element exists.

Total queries =2n+1+lognlogn

13

Can someone please discuss their approach for princess and dragon problem? Thank you

1 Like
14

For lonely cycle, I am not able to find a test case where my logic goes wrong… My submission is-submission

My logic goes as such… For each node x, I find in and out which are pairs… 1st index stores without cycle 2nd stores with cycle…in[x] means within the subtree of node x and also considering x… for this I merge its children’s “in” values and also some node in its subtree from which there is back-edge to x.

Out[x] position means same as above…It means the nodes we can visit in the tree except its subtree but including the node itself…for this I merge its parent’s out and also it’s siblings in…Also in case of back-edge from x to some node higher in the dfs traversal tree, I merge its out…

For answer, consider for edge (a-b)

case (i):(a is dfs_par[b] or vice versa… and not part of same cycle) answer is (in[b])*(merge(out[a], sibling[b]))

case (ii):(neither is parent of other but are part of cycle connected by back-edge)answer is (in[b])*(out[a]) (consider a comes before b in dfs traversal)

15

For all those wondering why their solution fails for lonely cycle.

Try this input:

1
14 14
1 2
2 3
3 4
4 1
4 5
5 6
6 7
7 5
6 8
6 9
8 10
10 11
11 12
12 13

Output should be:
1
1
2
2
11
14
7
2
25
9
24
21
16
9

2 Likes
16

I’m not able to access LONCYC and KCOMPRES Editorials. @admin please help.

17

Can anyone share their approach of solving Safe Partition ?

18

Interactive Matrix can be solved in O(log n^2) equivalent to O(log n).

First given a column we must be able to the identify the range in which the values are lesser than V (target value). This can be done using binary search.Take the first and last element of the column,identify whether its increasing or decreasing and perform binary search appropriately.Similar thing can be done to find range in which the values are greater than V.If the ranges are not complementary(that is union of them is not the superset) then the target is present in the column between these two ranges.So answer if found .From now on I would refer this functionality as range finder.

Now using rangefinder find out the ranges in first and last column.
Let range(row numbers) lesser than V in first column be [il1,ir1] and last column be [iln,irn].
Similarly the range greater than V in first column be [gl1,gr1] and last column be [gln,grn].
We can clearly see that half of our search space can be clearly discarded.
only two parts can have the solution.
First part is intersection of [il1,ir1] and [gln,grn] and all these rows contain values in increasing order.Now using range finder find the ranges in mid column only for this intersection of rows.Now in range where value is less than v we need to search right and for range value greater than v we need to search left(because rows are sorted ascending).

That is we split the rectangle under consideration into four parts and discard two parts. Its easy to see that the discarded portion is half the original rectangle.
We can repeat the same for these smaller rectangles and as well as the second part(but here rows are sorted descending).

Complexity analysis
So initially we had square of size n^2,then we discard half the space,so in the next space we search (n^2)/2 then (n^2)/4 .
So the complexity is O(log (n^2)) which is O(log n).

4 Likes
19

Just noticed I spent almost 9 days on the princess and compression only. And I so much wanted to try both lonely cycles and myst. Shame on me. Not sure 10 days is short or I’m just too slow:P
Princess sure was both annoying and enjoyable. I thought I had perfect solution for it but only got 10 points at first attempt(with 5 AC tasks). Putting princess with the most powerful dragon and creating main force most close to P and shortest with binary search, then backup force from remaining dragons. After lots of different approaches I added brute force for subtask 2 and got 20 points, and I was happy xD. Need to solve it again with the help of editorial to see what was my error.

20

My solution is not working for SHKNUM ,for the last test case, kindly check it at CodeChef: Practical coding for everyone

21

My solution is not working for SHKNUM ,for the last test case, kindly check it at CodeChef: Practical coding for everyone

22

My solution is not working for SHKNUM ,for the last test case, kindly check it at CodeChef: Practical coding for everyone