Please notice the unusual time.

Thankfully, no.

Please notice the unusual time.

I think because there's a contest (Lunchtime) on CodeChef at the usual time of CodeForces Rounds. Unusual timing for this round to avoid clashing contest times, so that people who want to participate in both can do so.

So round intersects with the olympiad and people who saw tasks during official competition have no way to cheat.

It will be a Div. 2 round

A follower of devil with illuminati pfp saying that? Well that's a complete paradox

Bruh aren't you the guy who put two problems on the local OJ without tests so everyone can only read the misspelled statement but cannot submit lmfao

Am I the only one that wasn't interested in politics when he was 11 yrs old ?

please, avoid saying the word "r*saians" for all Ukrainians who’ve been killed during the war. please, transfer $2000 to my bank account, it will definitely save many innocent lives of Ukrainian civilians. maybe you didn’t know, but every cent from the rewards for rounds is directed straight to the russian army, and MikeMirzayanov has a Z tatoo on his neck.

The codeforces platform is not aiding Russia in the war.

People around the world are looking forward to the end of the war, but our daily contests will not be disrupted by it.

I hope that the number of people who are extremely hateful to Russia or Ukraine is getting smaller and smaller.

(If you want to help Ukraine, then you can donate some money to Ukraine instead of denigrating codeforces here)

orz orz big great BurningRaven

Codeforces is a community for Competitive Programming. Please don't discuss politics here

Please give me 1,000,000,007 dollars, and I will save more Ukrainians.

Why are you screaming?

It's there, just not at top.

You have to give contest for that

Le Fuehrer

The Logic was Easy to think but the implementation made me say F... .

big integer ?!

Meanwhile, Python/Java coders using BigInteger :P

Also, thanks for not including a test with $$$n = 200\,000$$$ in pretests

a first condition to have all the elements equal to $$$0$$$ is to have them all equal. Considering this, we take the ""derivative"" array (that is $$$v'[i] = v[i] - v[i - 1]$$$). Now, if $$$v'[i] < 0$$$, that means that $$$v[i - 1]$$$ is too big, so we need to decrease it. Assuming we have made all elements from $$$i = 1.. i - 1$$$ equal, we can decrease $$$v[i - 1]$$$ using the operation to decrease on prefix as many times as we need. It works simetrically for $$$v'[i] > 0$$$. Then, after all these operations, we find the minimum value and increase it (or decrease it ) to make all elements $$$0$$$. Why is this optimal? Glad you asked. I do not know

Note that for any pair a[i],a[i+1] we have to decrease the half with the bigger of the two numbers.

After having done all those decreases all numbers are same, and we need another abs(a[0]) operations to make all 0.

You can equalize array with decrease operations and the adding like this

1 -2 3 -4 5
Substract 5 from (3, 4, 5)
1 -2 -2 -9 0
Substract 9 from (5)
1 -2 -2 -9 -9
Substract 7 from (1, 2, 3)
-6 -9 -9 -9 -9
Substract 3 from (1)
-9 -9 -9 -9 -9
Then just make it zero with adding 9
0 0 0 0 0

Then cost is 5 + 9 + 7 + 3 + 9 = 33

lol C was easier for me than B

for me I would say there should have been no B in the first place as it u*** my contest. At last giving up all hope I just peeked at c and the solution struck me instantly although had to think for D for some time but was able to do it after the contest sadly. so overall 'B' is a very annoying problem for me.

First observation is: if we can add 1 only to all of the numbers and other operations are only subtractions then we just need to equalize all the numbers by subtractions and then apply additions.

To equalize all numbers by subtraction on prefix/suffix we can use this way:

1) Suppose we have some prefix equal to x, and the next number is y.

2) If y > x then subtract suffix

3) Otherwise subtract prefix

We don't need the segment tree etc. because we can only store current prefix value and subtracted amount from current suffix

First make the sum 999999..., for that you can do b[i]=9-a[i], and check if first digit of b is 0 now, then you can add 11111..2 (n-1 ones and 1 two) in b that will keep sum still palindrome and your b will have same digits as a.

can you tell me which data structure is used in D/ your approach? As I solved it solely on observation and devising a small formula for some precalculation.

thank you , i knew i saw it somewhere , i think it is appeared at one more contest , maybe some gym or div1 contest. got it. https://cses.fi/problemset/task/2180 I used same solution of JOI to solve cses 2180.

not sure but motivation behind E maybe is this task https://cses.fi/problemset/task/2418

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

You probably made a mistake while counting the valid swaps. For example, your code fails on Ticket 13031 from CF Stress.

same here bro

Same here. Tried to implement some subarray-heapq-segtree shit until reread the statement xD

No, your code have complexity is n^2logn. Your "solve" function have complextity nlogn and you use it n times.

first, make the array non-increasing.

1 -2 3 -4 5
Substract 5 from (3, 4, 5)
1 -2 -2 -9 0
Substract 9 from (5)
1 -2 -2 -9 -9
add 9 for all
10 7 7 0 0

5 + 9 + 9 + 10 = 33

suppose i am at position ind and all elements from 0 to ind-1 are all equal to mn and have applied pref operation p times and suffix operation s times so cur value of my element is arr[i]-s

if cur_val of element is greater than mn then i will use suffix operation to make it equal to mn if cur_val is less than mn then i will use pref operation to make all prefix from 0 to ind-1 equal cur_val .

after then we iterate over whole array then at end we will have all elements equal to mn then we will make mn equal to 0

so final ans will be p + s+ abs(mn) as we have to make mn equal to 0

Problem C

Make a new array $$$b$$$ such that $$$b[i] = a[i]-a[i-1]$$$ and $$$b[1] = a[1]$$$. Now apply operations on the given $$$b$$$ array, and see how much simpler it becomes!

Adding $$$-1$$$ to prefix $$$[1,i]$$$ means decreasing $$$b[1]$$$ by $$$1$$$ and increasing $$$b[i+1]$$$ by $$$1$$$.

Adding $$$-1$$$ to suffix $$$[i,n]$$$ means decreasing $$$b[i]$$$ by $$$1$$$.

Adding $$$+1$$$ to all numbers means increasing $$$b[1]$$$ by $$$1$$$.

You want to make $$$b[i]=0$$$ for all valid $$$i$$$. Now the problem becomes easy and trivial.

Yes I also did the same :) Code: https://codeforces.net/contest/1700/submission/161205697 (Except I didn't use doubles)

$$$PrefSum[i]$$$ $$$\geq$$$ time $$$*$$$ (no-of-pipes-positioned-less-than-i+1)

should hold for all i, and from this relation we can also find the minimum time at which this equation starts being true and if it's true then answer will be $$$\lceil \frac{Pref Sum[n]}{time} \rceil$$$

You never want pipe x on if pipe x-1 was off (as all excess water overflows upwards and is only wasted if it falls off the end.). You can therefore calculate how long it will take with 1 pipe and build from there by adding each of the next pipes using DP (for every new pipe x you need to know the minimum time to fill locks x-1 and how much overflow there was) and end up with a decreasing array where a[x] is the number of seconds if x pipes are on. Finally you answer the queries with a binary search on this array.

A simple way is to solve the inverse problem instead: given that you can use i pipes, what is the minimum time to fill all locks?

Then some observations:

(1) The time needed is at least sum of all elements divided by $$$i$$$

(2) It is always the best to put the $$$i$$$ pipes in first $$$i$$$ locks

(3) Some large locks at the front are bottlenecks, can you formulate the bottleneck mathematically? (hint: observation 1)

If you solve the mentioned problem and store them down, given any time, you can do O(log n) BS for the minimum pipe required.

Because you have digit 11. And you print not n-digits number

1
3
900

Your output: 11011

I think that verdict from your submission wrong answer Token parameter [name=B] equals to "675102927261069662248365861045...5410685638422669610627292105911", doesn't correspond to pattern "[0-9]{100000, 100000}" pretty sure explaining things

This is how I solved it, the logic is simpler than D.

Solution 161214061

C also :'(

we will use the third operation only once. we try to make every consecutive element equal, 1) if both are positive - use 1st operation till v[i] (v[i] number of times) , and 2nd operation from v[i+1] to v[n] (v[i+1] times) 2) if one is positive and the other is negative - say second(v[i+1]) is negative , so we leave the negative one and make v[i] equal to v[i+1] by performing 1st operation v[i+1]-v[i] times 3)if both are negative then we leave the smaller number side and use 1st or 2nd operation on the larger element depending on the side. = at the end we will have all elements equal and equal to some negative number , now we use the 3rd operation and make everything equal

really appreciate that bro.

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

Lock 4 can't be filled that quickly (at the end of 51 seconds there is 204 water in the first 4 locks, but to be full you need 235).

Actually,you don't need the DP, here is a more clear submission ()161194282

Actually if you just find out the smallest time $$$t'$$$ which you need to fill all blocks if you turn on all the pipes then you don't need to make the second check for times larger than $$$t'$$$. This is because you can assume that each pipe gives $$$m*t$$$ units of water. Any water will be "wasted" only when all tanks are full(provided that $$$t > t'$$$).

My submission at time of contest — https://codeforces.net/contest/1700/submission/161202315

This looks like he wants to avoid the plag if we can get him banned or removed it's a big dub

It's not illegal no, but there's no way you can store the number other than in a string

True. Currently accepted submissions of Bobocan and Allen_3 would fail on the following randomly generated test cases.

Ticket 13247 and Ticket 13248 (See Ticket 13285 for a smaller testcase).

The last editorial of round that based on Russian olympics was extremely slow.

So I'm afraid that we should wait at most 3 days.

In D You first notice that you must choose a prefix of pipes, because after $$$t$$$ seconds the amount of water is fixed when the number of pipes is fixed, and water can always flow from front to back.

Then you could just do it by binary search.

Remember to check the minimum time $$$t_0$$$ to fill all locks when all pipes are chosen. When $$$t<t_0$$$ binary search may tell you that there's a solution but in fact there isn't.

There is a method which doesn't involve binary search at all, and it's actually very simple.

Firstly (as in binary search solutions) — find the earliest time at which it is possible to fill all lochs. For a given loch, the earliest time it can be filled is ei = ceil ( pref(i) / i ) (1-indexed). Here, pref(i) = sum(a1 to ai). Therefore t >= max(ei) is the earliest time it is possible to fill all lochs.

Note that if it is possible to fill all lochs, then the required volume is always pref(n), i.e. the sum of all the volumes of the lochs. A lower bound for the minimum number of pipes to achieve this in time t is clearly k = ceil (pref(n) / t). This bound is always achievable by choosing the left-most k pipes, since transfer to the right is instantaneous.

Therefore the solution is really simple: if t < max(ei), impossible, else ceil (pref(n) / t)

Note the colon at the end of the string below:

"127895006043806503257722920349...514195900199804976707038772613:", doesn't correspond to pattern "[0-9]{802, 802}" (test case 4)

From the ASCII table, ':' comes after '9'.

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

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