ARRAY_OPS Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Alex
Tester: Abhinav Sharma, Nishank Suresh
Editorialist: Pratiyush Mishra

DIFFICULTY:

Easy-Medium

PREREQUISITES:

None

PROBLEM:

Given an array A consisting of N non-negative integers.

You need to perform the following operation (N - 1) times:

  • Sort the array A in ascending order.

  • Let M be the current size of the array A. Replace the array A by [(A_2 - A_1), (A_3 - A_2), \ldots ,(A_M - A_{M-1})]. Note that each time the operation is performed, the size of the array reduces by one.

Find the remaining element after (N-1) operations.

QUICK EXPLANATION:

We make an observation that after O(logC) iterations there can be at most O(logC) non-zero elements. Thus we would have an array with majority of the elements as zero. Now instead of creating large arrays with most of elements zero, we can just keep a count of zeroes and only keep the non zero elements in the array and perform operations on that array. This would drastically reduce the time to perform the operation on an array since the size of the array would be really small.

Thus we would perform operations on the array as mentioned in the question but would exclude the zero elements from the array and keep a track of it in a variable. But we would include one zero element in the array(if it exists) so as to process its immediate right neighbour.

EXPLANATION:

First we observe that after O(logC) iterations there can be at most O(logC) non-zero elements. Lets prove it here.

Let’s say after the operation we have m non-zero numbers

a_1 \leq a_2 \leq a_3 \leq ... \leq a_m

then before the operation these were differences in sorted order, so the largest element is no smaller than sum of them, the second largest is no smaller than sum of them except one (the largest) and so on

so before the operation we had m non-zero numbers which are at least

a1 \leq a_1 + a_2 \leq a_1 + a_2 + a_3 \leq ... \leq a_1 + a_2 + ... + a_m

now apply this many k times

Basically we are calculating prefix sums of an array k times

Now it’s easy to see that the last number before k operations should be at least \binom{k+m-2}{k-1}

for k = m = log_2 C + 1 it is bigger than C

Thus we can just take array and perform the operation as explained above in quick explanation.

TIME COMPLEXITY:

O(NLogC) for each test case, where C \leq 10^{18}

SOLUTION:

Setter’s Solution
Tester1’s Solution
Tester2’s Solution

2

tf was that, honestly? imo this kind of meta-problem belongs to math competitions, not programming

2 Likes
3

Can you explain the solution a bit? I don’t get what the editorial is saying :((

4

So during the contest, I generated some random samples and noticed that answer is often 1, but sometimes you get an array like [0, 0, …, 0, max] or [0, 0, …, 0, 1, max] in the process. I then noticed that sum of numbers decreases rapidly as it gets replaced by max-min every turn. The editorial is saying that you can prove these observations mathematically, i.e. after roughly log steps you will have very few nonzero/distinct numbers. I couldn’t prove it during the contest and decided not to code it.

Obviously, many people didn’t prove it during the contest either and just decided to code it anyway and got AC for straightforward simulation with frequency table. I think this makes the problem rather heuristic, which is bad imo.

1 Like
5

Oh
Looks like i don’t need to upsolve this problem now :man_facepalming:
Thanks :))

2 Likes
6

I did it like this -

Let M1 be the MSB of all nos. After one iteration atmax one no would have M1 on. Leaving proof as an exercise for readers. Shouldnt be difficult.

After first iteration, lets ignore the largest no.
Let M2 be the MSB of all except the largest no.
After second iteration atmax one no among smallest to second largest would have M2 on.
…
Inductively, we can see that after O(logC) iterations there would be atmax logC non zero elements.

13 Likes