Can anyone share approach of Interactive matrix in short ??
@vijju123 
??
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?
pseudo orange
Codechef wont let me become orange this easily
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
1 Like
Check out this type of case- [4,4,4,3,4,4,4]. For K>0 the sequence B should be of form [2,2,2,1,2,2,2] instead of [1,1,2,1,2,2,2].
No, the main constraint said they will be greater than 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
1 Like