Candy Problem for k size window

I was solving this problem and end up learning two ways to solve this problem. One is two pass method and the other is considering peak and valleys (candies - interviewstreet). Both of these are O(n) solutions.

Now, I was thinking about the generalized problem which consider k neighbors(i.e. for the ith child we have to consider children from max(1, i-k)th place to min(n, i+k)th place) rather considering only one neighbour.

So, the problem is basically for every i in range[1, n] distribute candies in the children from max(1, i-k) to min(n, i+k) in such a way that each one gets at least one candy and if there are p children who have higher rating than ith child inside the window, then they will get more candies than the ith child.

Is there any linear time solution for this?

• Please edit the question to make it self-contained so we can understand the problem and your question without having to click on an external link (and so if the link stops working, the question still makes sense). Thank you! – D.W. Aug 6 '18 at 21:33

1. Compute the sorted scores (and associated children) in the first window with a persistent sorted tree. This step takes $O(k \log k)$ time.
2. Create a DAG on children and add a directed edge from each child to each other child who is between $p$ and $2p$ places lower than it. This step takes $O(pk)$ time.
3. Shift the window forward one child at a time. Incrementally update the tree to obtain a new one for this window in $O(\log k)$ time per tree.
4. In each tree in step 3, place directed edges between pairs of children of distance $p$ where the child that entered the window in this tree is in between the children in the pair. This can be done in $O(p)$ time per tree (avoiding a $\log k$ factor) if one starts at the node obtained by insertion in step 3.
5. Assign candies to children topologically: each leaf child gets 1 candy; each internal child gets max(child's candies) + 1 candies. This runs in $O(n)$ time.
6. Sum the candies.

Note: the DAG with all of the edges from steps 2 and 4 sorts children by relative number of candies.

The resulting algorithm runs in $O(n(p+\log k))$ time.

• Ok, I can understand. Is there something more optimized in terms of runtime? – Soumen Aug 7 '18 at 2:38
• @soumen I am not sure. Step 2 is a sledgehammer to meet the requirement "if there are $p$ children...". Perhaps there is a more clever approach. And a lot of computation can potentially be reused between window positions in this step. – Solomonoff's Secret Aug 7 '18 at 3:21
• @Soumen Reusing work between windows yields a more efficient algorithm. See updated answer. – Solomonoff's Secret Aug 7 '18 at 11:43