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

And I liked in div2C division of the task into subtasks

The longest interval is always 1, 2, 3, ...

You can get it just by writing it down. Let's say the longest interval is actually some other, let's say it has 13. Well, the starting interval always has 1. If you add 14 to your interval, you also add 2 to the starting interval. If 12, you also add 3 and 4. So if you increase your chosen interval, the starting one also increases in size (by that number or more). So you only have to check when 1, 2, 3, 4, 5.. fails.

Assuming that the maximum value is greater than the opposite of the minimum value, and when the number of numbers less than 0 is less than or equal to 12, we can add the maximum value to all numbers less than 0, and then make a prefix sum (12+19). Otherwise, we can multiply any number less than 0 by 5 times and add it to all numbers greater than or equal to 0, and then make a suffix sum (5+7+19)

Because there is no clear strategy for an adaptive grader. So, it may punish some specific solutions, but let other solutions ask less queries.

I did it by trying 1s and 2s then doing the same thing. Let's see if it FSTs. In my opinion this problem should have hacks disallowed because even the intended solution doesn't seem to have any proveable expected runtime bounds.

You can see that if you know the range of card unlocked, you can calculate the profit (sum element subtract number element). We will handle case the last unlock operation over n by append $$$n$$$ number $$$0$$$ to array.

We will take a subset for first operation and take all other $$$v$$$ in the range we unlocked. But not all subset valid. Same as knapsack problem, let $$$dp[i][j]$$$ true if there is a valid subset of first $$$i$$$ element and sum is $$$j$$$. First, $$$dp[0][1] = true$$$

$$$dp[i][j] = dp[i-1][j] | dp[i-1][j - a[i]]$$$

But after that we cannot use subset with sum $$$i$$$ to update $$$dp[i+1]$$$ because the condition for us to use $$$a{i+1}$$$ is that previous subset must have sum greater equal to $$$i +1$$$. Just make set $$$dp[i][i] = 0$$$ before go to step $$$i+1$$$

Use bitset to speedup

Same here !!

You can think of another way. What if you already have the maximum absolute number? Then you don't need to do doubling. If all is positive/negative, you only need 19 operations, so you can use your biggest to fix at most 12 elements before doing that. (so you can have 12 positive/negative where the biggest is not at) Suppose then, there is 7 and 13. Then you use your approach of doubling (which is 5 operations) then 5 + 7 + 19 = 31

Actually I think you have to come up with a different C1 Solution to solve C2. (Well, it's only my personal opinion.)

If $$$a \geq 8$$$, then $$$2n - a - 1 \leq 31$$$ is small enough. Then, in case of $$$a \leq 7$$$, we consider getting a negative number with a maximum absolute value. It takes at most $$$5$$$ operations because $$$-1 \times 2^5 = -32 \lt -\lvert 20\rvert$$$ is small enough.

Then Let's add the $$$a$$$ non-negative numbers by the newly generated negative number. Then, respectively, do a suffix sum.

It takes at most $$$(n - 1) + 5 + a = 31$$$ operations too.

Here is the story you asked:

• Initially div2C was only one, with $$$36$$$ queries. Then, in this order, div2E and div2D.

• Testers complained about the gap between div2B and div2E (which was in div2D position at that time).

• Since coming up with new problems is hard, we decided to split div2C in two subtask: one clearly easier and one clearly harder.

• Some more testers' feedback arrived and we decided to swap div2E and div2D.

• Testers felt like solving div2C1+C2 was as has as the following problems.

• Since different people had different opinions on the relative difficulty of the problems, we decided to go for the score distribution div2C=div2D=div2E.

Taking into account that before the round one has limited information, it seems to have been a reasonable call.

I would be really interested to see what the solve statistics would look like under a different ordering of the problems; I think that the difficulty ordering is highly subjective, and the order in the round may be the main reason that e.g. A2 has more solves than B. Too bad it isn't possible to give A, B, and C to each contestant in a random order...

(fwiw, my personal difficulty ordering is A1 < B <= C < A2, but I think I tend to perform best on tasks like C. I think C is probably harder than B if you're being objective, and likely harder than A2.)

Re: the original question, my strategy going in was to read A and immediately type A1 if it seemed free and either A2 seemed time-consuming or I was pretty sure the A2 solution would involve direct modification of the code for A1. I didn't want to spend time on A1 separately otherwise because the points I'd gain from solving A1 a few minutes faster would be outweighed by the points I'd lose from being a few minutes slower to the later tasks. After assessing and possibly solving part or all of A, I planned to read B and C, attempt one based on solve statistics, and go from there.

In-contest, I figured out A1 pretty much instantly and decided to think about A2 rather than typing A1. Luckily, I figured out the trick for A2 not too long afterwards for a quick AC. I attempted B before reading C because after I finished A2, I saw that B had several solves and C had none. After finishing up B and C fairly quickly, I moved on to D and E. At the time both problems were unsolved, and because E was worth far more points than D I assumed that D would be much easier. Thus, I solved D before reading E and finished E up afterwards. (In retrospect, it would have been a bit better to do E first, but ah well--not the end of the world.)

Take a look at Ticket 17015 from CF Stress for a counter example.

-120 by CF Predictor

It's a coincidence, sorry. It also happened in the last educational round. In both cases, the statement was short and many people can come up with such statements independently.

Fun fact: I also solved that AtCoder problem more than 2 years ago, but completely forgot about it.

It is same as easier version but not harder so I think it is fine.

Thanks! :)

The intended solution in problem C is quadratic, but some contestants wrote a cubic solution, and we didn't want to cut it off.

Getting Div2. C2 accepted is a proof in itself, you can't get that problem AC without a proof.

Suffering with success

same

Trying to hack these solutions I get unexpected verdict, but there's something worse. tourist's submission won't even work if there is a path of length 499 attached to the cycle made only of the first vertex (or I messed something up), but hacking says that the hack is incorrect. My solution solves it correctly, so I guess there is no such test, but I think that it means that the model solution might be wrong?

UPD: Nevermind here, it works on codeforces, but it somehow behaves this way on my machine, so most likely I've messed something up.

UPD2: Ok, I get it now, he's tricky, he's correct on this test :P

I had the same problem. Try using long long.