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 :) 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 :p 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 :) Let the discussion begin! asked 13 Aug, 16:27
showing 5 of 11
show all

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,j1), (i1,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. 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 preprocessing 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 :) answered 13 Aug, 17:21
1
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 preprocessing 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 :) Princess was a huge pain. Spent first day thinking its 2nd easiest question T_T
(13 Aug, 17:28)
Can you provide proof for that your interactive matrix solution will yield answer in less than 4N questions?
(13 Aug, 20:46)
1
According to my calculations, it's (25/8)*N queries on average. You can have a look here, https://drive.google.com/open?id=1UqZF6zDOYlLcEtrPkMWjpJuUbeQXfWut
(13 Aug, 23:25)
I'm talking of worst case..
(14 Aug, 01:24)
Worstcase, it'll require (3/16)NN + 2N queries. Since the query if for a random cell of all probable cells in grid, consider the situation where each cell is of form (1,2),(1,3),(1,4)...then (2,3),(2,4) and so on. Then the better approach will be of binary search, and that will take around (2N+ NlogN) queries, if everything is kept simple. But often probabilistic methods are fast enough and rather than thinking about worst case, expected value should be seen.
(14 Aug, 08:29)

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). answered 14 Aug, 17:20

For all those wondering why their solution fails for lonely cycle. Try this input:
Output should be: 1 1 2 2 11 14 7 2 25 9 24 21 16 9
link
This answer is marked "community wiki".
answered 14 Aug, 00:16
1
this case contains 15 edges but the value of m you have given is 14 :
(15 Aug, 02:21)
Thanks for pointing it out. That shouldn't be a problem earlier too since input was only till 14 edges and a single case was there.
(19 Aug, 19:04)

Two 'alternative' approaches to solve Interactive Matrix:
answered 13 Aug, 19:37
1
LOL. I used your approach one except for my search function (which selected rows to search) involved statistics and interval heuristics. I thought it was dumb of me to get AC that way but now I'm feeling good :3
(13 Aug, 21:43)

GCDMOD overflows :/ 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 answered 13 Aug, 21:04

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.. answered 13 Aug, 21:05

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 . answered 13 Aug, 21:09

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. answered 13 Aug, 22:02
This is simply not true: demo. Maybe there is a high probability of this and/or you got lucky.
(14 Aug, 02:53)
@meooow Then I must have got really lucky with those test cases :p Thank you for disproving!
(14 Aug, 14:32)

Can someone please discuss their approach for princess and dragon problem? Thank you answered 13 Aug, 23:21
1
If the princess is in an end cave, then put the strongest dragons near the princess to defend on just one side. For this, sort the dragons into decreasing order, and find the number of dragons so total power is $\ge P$ If the princess is in the middle, then first put the strongest dragon in the princess's cave. Then find the smallest number $n$ so that the next $n$ strongest dragons can be split into two groups, one group each side, sufficient to defend the princess. This is a classic hard problem, but has a dynamic programming solution when the strengths are integers, and not too large.
(14 Aug, 02:22)
1
I arrived at the same strategy, however I was unable to solve it. Can you provide any resources for the dynamic programming solution or explain it briefly?
(14 Aug, 02:25)
Yes that dp thing was deduced by me, that we need to split them such that sum of number of dragons on left and right is minimized. But even after lot of searching I was unable to find anything on it. Any resource will be really helpful!
(14 Aug, 03:19)
I also tried the similar approach of dp, first I found minimum numbers that can form p(max) and remaining numbers in decreasing order but I found counter case for that. So messed up
(14 Aug, 09:56)
1
Function count2b in https://www.codechef.com/viewsolution/19716800 gives the dynamic programming part of the solution. Given a strong test case, it wouldn't be fast enough. But often a simple greedy allocation of dragons (function quick_count2) will show that the first $n$ dragons with combined strength $\ge 2P$ can be split into two sets, each with combined strength $\ge P$. If the greedy solution fails, I apply the dp algorithm.
(14 Aug, 11:44)

For lonely cycle, I am not able to find a test case where my logic goes wrong... My submission issubmission 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 backedge 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 backedge from x to some node higher in the dfs traversal tree, I merge its out... For answer, consider for edge (ab) 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 backedge)answer is (in[b])*(out[a]) (consider a comes before b in dfs traversal) answered 13 Aug, 23:52

Can anyone share their approach of solving Safe Partition ? answered 14 Aug, 06:36

My solution is not working for SHKNUM ,for the last test case, kindly check it at https://www.codechef.com/viewsolution/19552013 answered 15 Aug, 19:01

My solution is not working for SHKNUM ,for the last test case, kindly check it at https://www.codechef.com/viewsolution/19552013 answered 15 Aug, 19:01

My solution is not working for SHKNUM ,for the last test case, kindly check it at https://www.codechef.com/viewsolution/19552013 answered 15 Aug, 19:01

My approach to INMAT was to use a 'quad search', which is a twodimensional version of a binary search, where we search recursively one quadrant at a time. This took only a maximum of 0.04 seconds per test to earn 60 points. I expect that it took more than 4000 queries in some of the later test cases. It looks as if the method needs polishing somehow, to reduce the number of queries. Here is my code https://www.codechef.com/viewsolution/19740240 answered 16 Aug, 12:49

I'll share my (partial) solution for princess and dragons that helped me get AC on subtasks 0,4,6,8. You start by reverse sorting the strength array, and define the largest value as the anchor. For each i, let the dragon with the anchor strength be at the ith position. For P <= anchor, output is n for each i. Similarly for sumoverstrengths < anchor, output is 0 for each i. For other nontrivial cases you iterate over the reverse sorted strength array trying to form two groups of sets such that the sum of strengths in each group when added to the anchor is just larger than P. We do this such that the size of the first set is <= size of the second set. Here again we have two cases : (1) We are able to get both sets, (2) we are able to get only one set. Other cases are eliminated by the two trivial cases on the above paragraph. We should aim to find set 1 and set 2 such that they have minimum size, while their sum being larger than P. For case (1): We keep the set 1(that has the smaller size) on such a side of the ith position that allows it protects maximum dragons after it. Hence, we keep the smaller set on the larger side(if it fits there). We then try to adjust the larger set after it, either on the smaller side or the larger side. For case (2): We keep set 1 on the larger side of the ith position, again so that it protects maximum positions. If that is not possible we return a string of n 0's. There are other subtleties too, such that the last element of the first set should be chosen such that the sum just equals P, and that we don't waste strength that can be used in set 2. Although this approach works for larger testcases, it couldn't even clear the smaller subtasks and hence I think I'm missing some conceptual point here that was tested in some test cases. You can check my final code here : https://www.codechef.com/viewsolution/19707035 answered 17 Aug, 03:38

Can anyone share approach of Interactive matrix in short ??
@vijju123 :D ??
I dont have any interesting solutions :( . I solved the first 4 problems and editoirals of 3 of them are already out. My solution for interactive matrix is pathetic as well :(
I dont have any interesting solutions :( . I solved the first 4 problems and editoirals of 3 of them are already out. My solution for interactive matrix is pathetic as well :(
okay np xD
Where is
being orange
treat??Who became orange? :o
Oops orange is >= 2200.
ohh you missed by 48
@vijju123
pseudo orange
Codechef wont let me become orange this easily :(
....... XD