Can someone share their approach to JCWC00?

Problem Link

It would be really helpful, thanks.

1 Like

The array is divided into k blocks so
1,…,k - 1 is the first block,
k,…,2 * k - 1 is the second block,
2 *k,…,3 * k - 1, is the third block,

So now you cannot select two elements from the same blocks. And for two consecutive elements in the subsequence their index difference should not be equal to k

Consider N = 3, k = 2 and A = {30,10,25}

if 30 is selected then 25 cannot be selected for our subsequence, so our answer for this case was max(30,10 + 25) = 35

Create a priority queue of pair of integer and push {0,inf} in it initially
Traverse the array block-wise from last element to first element, for every element, choose a element from the next block and the difference between their indices should not be equal to k.
Link to my solution :
https://www.codechef.com/viewsolution/25961042
I have submitted a O(N) solution.
Hope you understood.
I am too bad at explaining things (-_-’) .

1 Like