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
??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
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 
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
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.
Can you provide proof for that your interactive matrix solution will yield answer in less than 4N questions?