CBFEAST Editorial (Unofficial)

editorial
, , ,
1

I solved the two small cases like this:

My solution for case 1 (small case): simply iterate over them and find the sublist with max sum. (you can do it in O(n) using Kadane’s algorithm or one of the solutions mentioned here: https://cp-algorithms.com/others/maximum_average_segment.html. I used algorithm #2)

My solution for case 2 (large but positive): you’d always want to pick your range as the entire dishes. so, we only need to find out which dishes have c in [c-k, c+k] and sum up their d (we need to do this in log(n)).

  1. to find the sum of dishes in range [c-k, c+k], we find the sum of dishes with c <= c+k and subtract the sum of dishes with c <= c-k-1.
  2. so, we just need to find the sum of d for dishes with c less than or equal to certain C. To do that, we keep all dishes in a binary search tree (sorted by their c) and at each node, we keep the sum of d for all dishes in that subtree. any time you add a dish, as you go down from root to find the place to put this new node, add its d to all the nodes you visit. then you can also query the sum of d for dishes with c less than or equal to a given C in O(log(n)) time. (BTW, I got lucky and I got this problem without having to balance the BST. perhaps they could have included a sorted case where my solution’s query costs O(n))

my code: https://www.codechef.com/viewsolution/21981982

I would love to know how to solve the hard case.

1 Like
2

You can solve it completely using square root decomposition.

3

Can you be more elaborate ? I did try to think about sqrt decomposition but could not figure out the algorithm

4

You can check my code , I have done this using sqrt decomposition .

5

Following the suggested sqrt decomposition,

Choose a block size of about sqrt(Q). Call it B.
When B dishes have been added to the start or B dishes have been added to the end, then compute some partial answers as follows for this block of size B.

For each possible color c, find the deliciousness of each of the following:

  • the most delicious sequence of dishes (with colors in range [c-K:c+K]) which includes the first dish in the block
  • the most delicious sequence of dishes which includes the last dish in the block
  • the most delicious sequence of dishes in the block
  • the sum of the deliciousness of all dishes in the block

These answers are in groups. A range of adjacent colors will have the same answers. There are at most 2B+1 possible ranges, so set up an array of the break points between the ranges, and a second array of the partial answers. It takes O(B^2) time to compute these answers for a block of B dishes.

To answer a type “3” query, loop over upto B-1 dishes at the start, then up to B blocks for which we have just calculated the partial answers, and up to B-1 dishes at the end. Finding the partial answer in one of the B blocks takes log(B) steps (use C++ upper_bound function, or similar), and combining the partial answers takes O(B) steps. So total time for one type 3 answer is O(B log(B))

My implementation is at https://www.codechef.com/viewsolution/22046804.
I read the code at https://ideone.com/74ASpH to form the idea.

6

@john_smith_3’s answer seems very helpful. This looks like some dynamic sqrt decomposition, which I haven’t encountered before. Learnt a new concept today :). Thanks for sharing!