n^2z gave me a tle on subtask two as was expected.I wonder how yours got accepted 
Had to code nzlogn
1 Like
Any idea when the official editorials will be published?
1 Like
I did two days of tiring effort on the problem circular merging optimizing my solution to get rid of TLE only to realize that I have used long long variables due to which the computer would be doing approximately double the computations than it needs to 
1 Like
read Matrix Chain Multiplication
1 Like
Wdym? I used long long too
But you realized that greedy optimization as said by you in the other post to convert it into linear rather than circular which would require you to compute only half the subproblems than it needs to calculate for the circular.
Ohh I see 
//20charlimit
Sure bro, thank you!
Hit the Coconuts solution:
https://www.codechef.com/viewsolution/25157857
I am not sure if the code will be understandable. Strategy 1 in the code comments referes to brute force which checks for one continuous group of coconuts. Strategy 2 checks for two continuous groups of coconuts.
Overall to understand what I am doing, you must be convinced that the problem is reducible to the following problem, Actually I solved the following problem:
Given an integer z and a sorted histogram with n bars with heights a1, a2, a3,..., an (this sequence is non-decreasing since histogram is sorted). We have to pick z bars( 1 <= z <= n ) out of these n bars such that the area enclosed between chosen bars and the right wall of the histogram is minimum possible. These z bars actually represent the coconuts we want to choose.
For example, for the sequence of heights {1, 3, 5, 9} , if we chose bars with heights 1, 5 ; the area enclosed with right wall will be 12 units and will look something like in the image (Assume the width of bars to be 1 unit.)
After writing a O(n^2*k) DP for this and getting it accepted for the subtask, I observed the pattern that I stated above, that only one continuous group or two continuous groups of coconuts are optimal.
Maybe during DP array filling, he was iterating over too many values than required.
For instance, My solution takes duplicate of the same array appended to the original array to simulate the cyclic merge. Then I do simple linear merge using DP, ignoring that there is any cycle.
But when doing DP, I only iterate till only till length n of the original array, not the 2n length of the array I made.
How ? 
Even I had a O(N^2*Z) solution. Bottom-Up DP.
Can you share your solution
Just like June Long 19 was based on Number Systems, or so I was told by my friends as I felt it too. Are all Long challenges based upon to some topics for the user to get better at them? If yes, which one was July19 based on?
It was based on dynamic programming. For CIMERGE AND CCC.
Thanks, but that’s just two problems. Were the rest of them more on the general side?