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.
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.
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?
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!
Worst-case, 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.
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
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.
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).
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.
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
Thank you for disproving!