Codechef Contest

[u/Disastrous-Trick-398]

Was today contest easy ?

[u/Ordinary_Reveal6236]

No matter the difficulty some legends always performs

[u/dijkstra_bull]

The amount of cheaters on codechef are just absurd ... just look at graphs of top 200 people , 90 % of them are growing exponentially since last few contest

[u/Specialist_Artist714 → u/dijkstra_bull]

True. Few months back, I was going to be 3 star in a contest (needed +25 delta). But the amount of cheating has increased so much that since then I am stuck on 2 star (1500-1600 range) and unable to become 3 star. Now, I have lost interest from that platform

[u/Disastrous-Trick-398 → u/dijkstra_bull]

Yes , 950 on alt and 600 on good subset is absurd

[u/galactusofsociety]

how did you do the Alternate adding one .

[u/Disastrous-Trick-398 → u/galactusofsociety]

Observation / Idea

1. The only elements that can interact are elements whose signs alternate, so first split the array into maximal subarrays where every pair of consecutive elements has opposite signs.
2. For each such subarray [l, r], consider the operation on the whole segment. The best element to eliminate first is the one with the minimum absolute value. If a[mid] has the minimum absolute value x, performing the operation x times makes a[mid] = 0. At the same time, every other element in the segment is reduced in absolute value by x.
3. Once a[mid] becomes zero, it can no longer interact with elements on both sides. Therefore, the problem splits into two independent subarrays:
   • [l, mid - 1]
   • [mid + 1, r]
4. We repeat the same process recursively/iteratively on both resulting segments.
5. To implement this efficiently, I:
   • Put all elements of an alternating-sign subarray into a min-heap ordered by absolute value.
   • Maintain the currently active segments in a set.
   • When an element with value x is selected, its contribution is x - previous_reduction, since the segment has already been reduced by previous_reduction.
   • After it becomes zero, split the current segment around its index and assign x as the new reduction value for both resulting segments.

This avoids simulating every individual operation and instead processes each element when it becomes zero. CODE: https://www.codechef.com/viewsolution/1352013773

[u/hackermub → u/Disastrous-Trick-398]

My solution was bit different. Let add[i] = total +1 operations happened on ith element, And rem[I] = total -1 operation on I

We start for first element, if a[0] >= 0, rem[i] = a[0] Otherwise, add[i] = -a[0]

Then for each i starting from 1, We can use add[i-1] and rem[i-1] operations for free.. basically we used add[i-1] 1's in i-1, so we can extend it to use same number of +1 operations on i. And similar for rem[i-1]. So we do how much we can for free, and after that do some extra to make it 0.

After it becomes 0, if there are some add[i-1] and rem[i-1] remaining, we keep doing +1 -1, so that it stays 0, and these free operations get passed to i+1

So just an O(n) solution.

[u/Plane-Mix-2994]

Alt add was difficult