AUG18 - Problem Discussion

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

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

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 https://www.codechef.com/viewsolution/19740240

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 : https://www.codechef.com/viewsolution/19707035

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

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.

ohh you missed by 48
@vijju123

Can you provide proof for that your interactive matrix solution will yield answer in less than 4N questions?

pseudo orange

Codechef wont let me become orange this easily :frowning: