AUG18 - Problem Discussion

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

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

1 Like

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)

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

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

Can anyone share their approach of solving Safe Partition ?

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

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.

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

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

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

Please help me to find counter test case of my code of the problem KCOMPRES. Only two task remaining. My solution included segment tree approach. My Code

My approach to INMAT was to use a ‘quad search’, which is a two-dimensional 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 CodeChef: Practical coding for everyone

I’ll share my (partial) solution for princess and dragons that helped me get AC on sub-tasks 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 sum-over-strengths < anchor, output is 0 for each i.

For other non-trivial 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 test-cases, it couldn’t even clear the smaller sub-tasks 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 : CodeChef: Practical coding for everyone

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

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

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