nice

there should be a separate comments section where all of you orz fanatics can peacefully spam

omg TheScrasse round!

I'm excited to finally reach cm after this contest :D

I have an opinion about the difficulty of these problems, but some other authors and testers have very different opinions. Overall, let's say we are agnostic.

It's 2 hours and 30 minutes long. The contests page will be updated.

Hopefully tomorrow

yes you will, gl!

Well it means that the problem will have two version: The easy version, which is C1, and the hard version, which is C2(or, in case of Div 1, A1 and A2)

Me too (my another account). Good luck to you~

There will be two versions of Div. 2 C / Div. 1. A, each worth 1250/750 points (so if you solve both versions of Div. 2 C, you get up to 2500 points total). The second version is generally harder than the first; usually the two problems are the same but the hard version allows for larger input sizes.

Ufff! I was close..... maybe next time :')

Congrats! :)

Yes! (as far as I know, all codeforces contests are translated in Russian)

You can greedily set the start of the interval to be $$$1$$$. Then just try to extend your interval until you can't anymore.

my solution (still pending test so take a grain of salt)

In a nutshell if we can make the array all positive, then it's easy because you can do something like

for i in range(1, N):
  if arr[i-1] > arr[i]:
    add i-1 to i

The same thing can be said for all negative numbers. You just do it from the end of the array. The operation takes at most N times which is 20.

Now the difficulties come because array can have positive & negative numbers.

Imagine if the array has at least 1 positive number. Then we can double that number quickly by adding it to itself. The worst case is for positive number 1, and double it 5 times so it definitely exceeds 20. The operation here is another N which is 20.

Then we add this number to each number in the array, and we can be sure to have an array of ALL POSITIVE numbers. And you can apply the logic above.

So in general:

if not_has_pos:
  do the negative stack from end of the array (20 operations)
else:
  quickly double the largest positive number until it's > 20 (at most 5 ops)
  use that largest number to add to each of the array number (at most 20 ops)
  do the all positive stack from the beginning of the array (at most 20 ops)

If all numbers are negative, then just take suffix sum.
Else take any positive number and keep adding itself to it till it is less than 20.
Then add that number to all the negative numbers. Now all are non-negative numbers.
Take prefix sum.

Roughly speaking, make all elements either positive or negative (optimize this a bit), and then it's just prefix/suffix sum

if you have all element as postive then just start appling operations from beginning to a[i],a[i-1].similary for all negeative elements apply operations from last. if array contain both positive and negative you can make any positive element > 60 in atmost 6 moves by appling operation to itself then apply operation on each negative element with this element(>60) and then just solve it for all positive case. maximum moves=6+19+19=44

The main strategy is that if all numbers are not negative you can do:

2 1

3 2

4 3

5 4 ...

so in each step every number becomes at least as big as the previous

if all the numbers are not positive its the otherway around:

19 20

18 19

17 18...

You take 19 steps to do that. Now the question is: how to make all the numbers non-negative or non-positive?

If there are >= 13 positive numbers, you can just pick any of them, sum it with itself 5 times (so if the number is 1 it becomes 2, 4, 8, 16 and finally 32) and then sum with all the other negatives, which are at most 7. So you have 5 + 7 + 19 steps <= 31;

If there are >= 13 negative numbers it is similar as above.

If there are less than 13 negative and less than 13 positive numbers, just take the one with larger modulu, sum it with all the at most 12 numbers of the opposite signal and do the first process. You have 12 + 19 steps <= 31

If all element is positive, we take its prefix sum, else if all element is negative, we take suffix sum

Example: 1 4 7 2 8 -> 1 5 12 14 22;

-1 -2 -1 -> -4 -3 -1

Let numNeg is number negative element and numPos is number of positive element. We will convert all positive to negative or convert negative to positive.

I will discuss about first case, the second same.

• First, double biggest positive number until its abs larger than smallest element' abs. Let number operation need for this process is Kpos.
• Second, add this number to all negative number (after that we have a positive array)
• Third, take prefixsum
• Total cost is: numNeg + Kpos + n — 1
• Total cost for other case is: numPos + Kneg + n — 1
• We can proof that either numNeg + Kpos or numPos + Kneg (or both) not larger than 12

for Div 2 C1 you can easily solve it by a greedy approach you are fine with the operations if all numbers are negative, positive or all numbers are 0 then you can easily do it otherwise for 50 operations just spend 5 operations to make any non zero number >abs(20) then add this number to all the numbers to make same parity as it has then simply do like all negative and all positive

but for Div2 C2 the catch was you have to know how many numbers are positive and negative suppose if you have any of these given count of numbers >=13 then the other numbers count will be at max 7 then in this case you just need to again spend 5 moves for any non zero nubmer from the 13 numbers and spend at max 7 more the make the parity same the number of operations inclusive will be 5+7 =12 and rest you can do 19 operations to make it non decreasing otherwise if maximum count of nagatives and positives <13 then just select a largest non negative element from the array and make all the oppositve parities numbers (which can be maximum 12) to same parity it has then do rest 19 operations on making the array non decreasing

continuous subarray from 1 that is factor of n

You need to use the fact that product $$$n$$$ consecutive numbers is divisible by $$$n$$$. So this kinda works

rep(i,2,1e18) {
    if (n%i != 0) {cout << i - 1 << "\n"; return;}
}

I don't know if this is the intended solution. I had just not enough time to code it up, but I think it should work.

Case1) All are zero. Then we're good

Case2) All are non-negative. Then we're good, just submit {2,1} -> {3,2} etc and you get a increasing array in <= 19 operations.

Case3) all are non-positive. Then we're also good, just submit {n-1,n} -> {n-2, n-1} and you get an non-decreasing array.

Case4) There is roughly same number of positive and negative entries (maximum 4 difference in number of negative and positive entries). Then take the element with biggest absolute value and use it to make all entries positive/negative. This takes maximum 12 operations. Afterwards you can do the same as in case2/3. This costs you maximum 19 operations. Together it costs exactly 31 operations maximum.

Case5) A there is much more positives than negatives or vice versa. Then take one element from the group there is most of, and add it to itself until it becomes 32 or larger in absolute value (this takes maximum 5 operations). Then it is bigger than all other entries, and you can use it to make all the other entires negative/positive. But, there is maximum 7 other elements of opposite sign (else we'd be in case 4). This takes maximum 5 + 7 = 12 operations. But, after this we're back in the situation of case 2/3, which we know takes 19 operations to sort. And again 5 + 7 + 19 = 31, so we can exactly do it even in case 5

Yes, it's a shame, they wouldn't hurt me either.

Can't agree more. Internet also gave up on me seeing my iq. Literally fucked up this one

I assume you found the largest $$$r$$$ such that the segment $$$[1, r]$$$ works, right?

There is an easy proof that this works. Consider any range $$$[l, r]$$$. Let $$$m = r - l + 1$$$, the number of integers in this range.

We can notice that within these consecutive $$$m$$$ integers $$$l, l + 1, l + 2, \dots, l + m - 1$$$, exactly one integer is a multiple of $$$m$$$. Within the first consecutive $$$m - 1$$$ integers $$$l, l + 1, l + 2, \dots, l + m - 2$$$, exactly one is a multiple of $$$m - 1$$$ and so on, until the first consecutive $$$1$$$ integers $$$l$$$ (trivially) has exactly one being a multiple of $$$1$$$.

This means that within the original range $$$[l, r]$$$, there is a multiple of each of $$$1, 2, \dots, m$$$ (where $$$m = r - l + 1$$$) and thus, we get that $$$n$$$ is also a multiple of each of $$$1, 2, \dots, m$$$. This way we get a new range $$$[1, m]$$$ which is as long as the original one, but starts at $$$1$$$.

Suppose the answer to the problem (for specific $$$n$$$) is $$$x$$$; this means that there exists some good range $$$[l, l + x - 1]$$$. But as we showed above, the range $$$[1, x]$$$ must then also be good. This proves that we always can find an optimal range by setting $$$l = 1$$$.

oh my god it got skipped im never making this mistake again