Codeforces Round #802 (Div. 2, based on All-Russian olympiad in the name of Keld...

This Sunday will take place All-Russian olympiad for students of 5-8 grades, in the name of Keldysh. Good luck to all the participants! Olympiad is conducted under the guidance of the Moscow Olympiad Scientific Committee, in particular GlebsHP, ch_egor, Endagorion, vintage_Vlad_Makeev, Zlobober, meshanya, cdkrot, voidmax, grphil, fedoseev.timofey and, of course, Helen Andreeva.

We are happy to announce the Codeforces Round #802 based on the problems of this olympiad! It will be a Div. 2 round, which will take place at Sunday, June 19, 2022 at 09:05UTC. You might have already participated in rounds based on the school olympiads, prepared by Moscow Olympiad Scientific Committee (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657, 680, 704, 707, 727, 751, 775). Please notice the unusual time.

The problems of this olympiad were prepared by Siberian, _overrated_, Igorbunov, Ziware, _tryhard, EntitledMonkey under the supervision of fedoseev.timofey.

Thanks to 74TrAkToR for their help in organizing the Codeforces version of this contest and one of the problems, MikeMirzayanov for the Codeforces and Polygon.

Also I would like to thank the Tinkoff company and personally Tatyana TKolinkova Kolinkova for great help with organizing the competition.

Thanks to NEAR for supporting this round, details can be found in this post.

Good luck!

UPD1: Thanks to Um_nik, mhq, MichsSS, kucipendik, TeaTime, devid, Mangooste for testing.

UPD2: Scoring distribution: 500 — 1000 — 1500 — 1750 — 2500 — 3000

• 5 hours ago, # ^ | Please notice the unusual time.

• 25 minutes ago, # ^ | Thankfully, no.

• 22 hours ago, # ^ | Please notice the unusual time.

• 22 hours ago, # ^ | 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.

  • 22 hours ago, # ^ | Not only this contest previous based on All-Russian olympiad contest start unusal time plz cheak previous 775,751 etc based on All-Russian olympiad contest

• 19 hours ago, # ^ | So round intersects with the olympiad and people who saw tasks during official competition have no way to cheat.

• 18 hours ago, # ^ | It will be a Div. 2 round

• 44 minutes ago, # ^ | Not if you can't solve a problem..:(

• 17 hours ago, # ^ | A follower of devil with illuminati pfp saying that? Well that's a complete paradox

  • 17 hours ago, # ^ | Bro, his pfp is literally from Gravity Falls, a kids cartoon lol.

• 4 hours ago, # ^ | 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

• 3 hours ago, # ^ | Am I the only one that wasn't interested in politics when he was 11 yrs old ?

• 12 minutes ago, # ^ | I'm just curious to know where were your "sympathy" when Russia invaded Afghanistan and Syria?

• 16 hours ago, # ^ | 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.

• 10 hours ago, # ^ | 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)

• 4 hours ago, # ^ | orz orz big great BurningRaven I will participate in this round to support russia orz

• 3 hours ago, # ^ | Codeforces is a community for Competitive Programming. Please don't discuss politics here

• 20 minutes ago, # ^ | Please give me 1,000,000,007 dollars, and I will save more Ukrainians.

• 9 hours ago, # ^ | Why are you screaming?

  • 5 hours ago, # ^ | in what sense is it affecting you?

    • 41 minute(s) ago, # ^ | I n a s i m i l a r w a y t h i s t e x t w i l l a f f e c t y o u

• 4 hours ago, # ^ | It's there, just not at top.

• 116 minutes ago, # ^ | You have to give contest for that

• 48 minutes ago, # ^ | The Logic was Easy to think but the implementation made me say F... .

• 47 minutes ago, # ^ | big integer ?!

  • 45 minutes ago, # ^ | No, just make it '11111...' if the first char is '9' else make it '9999...'

    • 42 minutes ago, # ^ | can u look into my solution where i am wrong?https://codeforces.com/contest/1700/submission/161213454

      • 37 minutes ago, # ^ | use string, long long can't store the number.

      • 24 minutes ago, # ^ | The big number will have n digits. And 2 ≤ n ≤ 100000. long long wont store that big number, use string

    • 37 minutes ago, # ^ | then subtract x from this ?

      • 26 minutes ago, # ^ | Yes, the only catch here is the implementation, which I did with carry variable.

        • 19 minutes ago, # ^ | python and java coders have the advantage at this point.

  • 43 minutes ago, # ^ | Well, that is another reason why B is really bad, there's a bias for people who know python (and also who have configured IDE for it) I was participating unrated so I didn't bother about it and solved on C++ with some pain but I can really imagine how would I rage about this task if it was rated for me

• 37 minutes ago, # ^ | I am sure you had the solution sketch for B...it was mostly math..meanwhile in C people exploited the structure of the array. Indeed the implementation wasnt straight forward but imo it should not be swapped.

  • 31 minute(s) ago, # ^ | ← Rev. 2 →   0 my reasoning is its easy to notice the observation for b but its hard to implement it ( at least for c++ users like me) in the opposite of c i got an idea after thinking in it for about 15 minutes but i didn't have time to test it because i spent most of my time in b but you have a fair point b wasn't that hard maybe im suck in implementation problems

• 24 minutes ago, # ^ | Meanwhile, Python/Java coders using BigInteger :P

  • 20 minutes ago, # ^ | yeah, another reason for me to hate b :)

• 29 minutes ago, # ^ | Also, thanks for not including a test with n=200000n=200000 in pretests

• 43 minutes ago, # ^ | ← Rev. 2 →   0 hint: Decrease from front to back, becoming a non-increasing sequence.

• 42 minutes ago, # ^ | Spoiler

  • 40 minutes ago, # ^ | couldn't the array be made valley type for optimal answer..I mean the minimum value neither being the first or the last value?

    • 24 minutes ago, # ^ | Spoiler

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

  • 27 minutes ago, # ^ | That's the sad part..Couldn't prove it either.. Div 2 Cs of recent rounds have been guesses.

  • 25 minutes ago, # ^ | ← Rev. 2 →   +3 So the easiest way of making all elements equal turns out to give the answer. Guess I overestimated C.

• 40 minutes ago, # ^ | 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.

• 40 minutes ago, # ^ | 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

  • 31 minute(s) ago, # ^ | ← Rev. 2 →   0 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

• 40 minutes ago, # ^ | lol C was easier for me than B

• 34 minutes ago, # ^ | ← Rev. 2 →   +4 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

• 40 minutes ago, # ^ | ← Rev. 7 →   +3 Hint-1 Hint-2

  • 29 minutes ago, # ^ | I got this observation at contest time but unable to think of that n+1 1s thing. :(

• 40 minutes ago, # ^ | If first character is not '9' then our palindrome to make is '9999...' If first character IS '9' then our palindrome to make is '1111...'

• 39 minutes ago, # ^ | 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.

• 26 minutes ago, # ^ | Take a look at Ticket 13034 from CF Stress for a counter example.

• 31 minute(s) ago, # ^ | You probably made a mistake while counting the valid swaps. For example, your code fails on Ticket 13031 from CF Stress.

  • 25 minutes ago, # ^ | thanks. I found my bug.

• 34 minutes ago, # ^ | You should hide this under spoiler tag.

  • 9 minutes ago, # ^ | Yup, didn't realize that, thanks!

• 25 minutes ago, # ^ | same here, my initial thoughts were that the answer would depend on (n?m) but then i realized it does not .. lol

• 36 minutes ago, # ^ | same here bro

  • 34 minutes ago, # ^ | If you know the reason please tell me

    • 33 minutes ago, # ^ | ← Rev. 3 →   0 The length of a number is at most 100.000 when long long can fit around 19 characters if I am correct.

      • 31 minute(s) ago, # ^ | I have also taken boundary cases yet I do not understood why I got wrong answer ton test case 2?

        • 30 minutes ago, # ^ | 19 < 100.000, look at the problem constraints carefully.

• 31 minute(s) ago, # ^ | 100000 digit numbers wont fit in LL or LLU or even uint_128...take input in a string or become a pythoner xD this problem was very pythonic

• a moment ago, # ^ | ← Rev. 2 →   0 Same here. Tried to implement some subarray-heapq-segtree shit until reread the statement xD

• 27 minutes ago, # ^ | No, your code have complexity is n^2logn. Your "solve" function have complextity nlogn and you use it n times.

  • 26 minutes ago, # ^ | Ohh yes! Thanks :)

• 25 minutes ago, # ^ | ← Rev. 2 →   +1 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

• 19 minutes ago, # ^ | 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]-suf 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 the we iterate over whole array then we will have all elements equal to mn then we will make mn equal to 0

• 17 minutes ago, # ^ | ← Rev. 3 →   +2 Problem C Make a new array bb such that b[i]=a[i]−a[i−1]b[i]=a[i]−a[i−1] and b[1]=a[1]b[1]=a[1]. Now apply operations on the given bb array, and see how much simpler it becomes! Adding −1−1 to prefix [1,i][1,i] means decreasing b[1]b[1] by 11 and increasing b[i+1]b[i+1] by 11. Adding −1−1 to suffix [i,n][i,n] means decreasing b[i]b[i] by 11. Adding +1+1 to all numbers means increasing b[1]b[1] by 11. You want to make b[i]=0b[i]=0 for all valid ii. Now the problem becomes easy and trivial.

  • 11 minutes ago, # ^ | I finally got the idea, thanks

• 9 minutes ago, # ^ | ← Rev. 3 →   0 PrefSum[i]PrefSum[i]≥≥ 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 ⌈PrefSum[n]time⌉⌈PrefSum[n]time⌉

• 8 minutes ago, # ^ | 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.

• 3 minutes ago, # ^ | 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 n (2) It is always the best to put the ii pipes in first ii 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.

• 19 minutes ago, # ^ | just check s[0] is or not '9'.

  • 17 minutes ago, # ^ | I returned 11111.....(n+1) times in the second pretest. Thus, the answer should be correct at the end.

• 17 minutes ago, # ^ | ← Rev. 2 →   0 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