Hi!

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 Jun/19/2022 12:05 (Moscow time). 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, talant, Olerinskiy 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, 244mhq, Shakespear31, _shakespeare_, TeaTime, devid, Mangooste for testing.

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

**UPD3:** Winners!

Div. 2:

Div. 1 + Div. 2:

**UPD4:** Editorial

Round was announced less than 48 hours before the start time, very unusual

Please notice the unusual time.

Is a 1500 difficulty problem A coming again ? https://codeforces.cc/blog/entry/80214 this was true last time

Thankfully, no.

CodeChef Lunchtime is also there tomorrow at the same time. :|

Please notice the unusual time.Today's problems were really amazing I just loved eve. Though I was not able to solve some problems

why this based on All-Russian olympiad contest start 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.

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

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

what about that one guy who had a 1 minute BCD solve

Is this contest rated for 2100+?

It will be a Div. 2 roundBrace yourselves for hacks and fsts in this round.

Not if you can't solve a problem..:(

While you kill people in Ukraine you organize olympiads ? Nobody cares about you stupid olympiads ! "All-Russian" should go to ________ .

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

Bro, his pfp is literally from Gravity Falls, a kids cartoon lol.

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 ?

I'm just curious to know where were your "sympathy" when Russia invaded Afghanistan and Syria?

Good luck for everyone!!!

hope it won't be shitty as sir jdurie's round

If we continue participating in russian codeforces and act as if nothing has happened, then russians will never understand and feel guilty for what they have done. There were children in Ukraine, who wanted to participate in codeforces but now eill never get a chance to because they were killed by russian soldiers and missiles.

Please, avoid participating in russian contests for all Ukrainians who were killed during the war. Please, avoid participating in russian contests to save many innocent lives of Ukrainian civilians.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.

I only need 998244353 dollars.

russia is a good country, india stands with russia

NOTICE THE UNSUAL TIMING. IT IS 5 HRS ANS 30 MIN PRIOR TO REGULAR TIMING

Why are you screaming?

in what sense is it affecting you?

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

LOL

Then I can come to be rated by div.2 XD

(I'm so like a rookie this week :(

points distribution?

Hope I would do well in this round, the last round went very badly for me.

You can do anything, just don't give up!

Why this post is not on the home page

It's there, just not at top.

I hope to get div 2 type problem unlike in last round (codeforces round 657) which was organize by the same organization which was more like div 1 round.

the last Russian Olympiad mirror didn't have a score distribution announcement before the contest, looks like we are gonna have that again xD

i hope i can get top 10 in this contest

You have to give contest for that

hi

All the best everyone.

Why am I not able to participate?

I think I'm not helping the nature

Le Fuehrer

Don'tDecent round, but B is really annoying :)

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

big integer ?!

No, just make it '11111...' if the first char is '9' else make it '9999...'

can u look into my solution where i am wrong?https://codeforces.cc/contest/1700/submission/161213454

use string, long long can't store the number.

The big number will have

`n`

digits. And 2 ≤ n ≤ 100000.`long long`

wont store that big number, use stringthen subtract x from this ?

Yes, the only catch here is the implementation, which I did with carry variable.

python and java coders have the advantage at this point.

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

reallyimagine how would I rage about this task if it was rated for meCome on, it's subtraction with carry. Made easier by the fact that you know the number is as long as the answer. Here is my entire implementation of subtraction:

In any case, solving such a task with Python should not be an issue to anyone.

I write in python but even if it is an advantage I try to use the basic approach to understand the root concept. Hope other python coders are doing that as well. (Btw: I am learning C++).

i don't know if its just my opinion but i think b would have been better swapped with c? i feel if i started with c i would have better chance to solve it b was very time consuming

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.

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

Meanwhile, Python/Java coders using BigInteger :P

yeah, another reason for me to hate b :)

Ok problem(s)

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

What has to be done in C? I could hardly observe anything useful for the solution at all.

hint: Decrease from front to back, becoming a non-increasing sequence.

SpoilerTry to make the array non-increasing from either side.

couldn't the array be made valley type for optimal answer..I mean the minimum value neither being the first or the last value?

SpoilerNope, if you apply the given operations eventually the array will become non-decreasing from one of the ends since at the end you have to make all the elements equal. You can dry run the second and third examples once to have better clarity.

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

That's the sad part..Couldn't prove it either.. Div 2 Cs of recent rounds have been guesses.

So the easiest way of making all elements equal turns out to give the answer. Guess I overestimated C.

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

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

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

Very strange round. problem C is hard for its place and D is easy for its place. They have to be swapped

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.can someone explain sol for Div2C to me please??

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

The quality of preparation is very good (understandable why), such a great contest. One of the best out of all recent ones on CF.

approach for B? Anyone

Hint-1you can make all numbers 9 except when the first digit is 9

like you can convert 1234 into 9999 but not in the case when it is 9234

Hint-2In that case when you can not make every number 9 try n+1 '1's like if the number is 99 you can make it 111 by adding 21 and it will always be valid

I got this observation at contest time but unable to think of that n+1 1s thing. :(

You can also substract 1 from the first digit of number and build 1XXXXX1, where X = N[0] — 1

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...'

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.

If only I had one minute more to submit D..

D is a good old algorithms&datastructures problem without tricky observations and such. Nice to have one for a change

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.

Problem F is similar to Coin Collecting from JOI 2019.

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

Awesome D and E!

what was pretest4 of D (ಥ _ʖಥ)(ಥ _ʖಥ)

Take a look at Ticket 13034 from

CF Stressfor a counter example.I am not sure if I made a bug for E but I would to confirm the correctness of my idea. A puzzle is solvable iff all cells except 1 have at least one neighbour smaller than it. Thus, we can find a 'bad' cell and attempt to try swapping its neighbours with every other cell (including itself) and check each scenario in O(1).

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

CF Stress.thanks. I found my bug.

When I spend 20 mins trying to come up with a solution, and see a solution like this for A which is literally the answer:

This wretched solution :(m * (m — 1) / 2 + m * n * (n + 1) / 2)

That's when I start questioning my practice sets :( and infact my life choices lol

You should hide this under spoiler tag.

Yup, didn't realize that, thanks!

same here, my initial thoughts were that the answer would depend on (n?m) but then i realized it does not .. lol

IN B I iterate all over numbers from n.size to 10*n.size and check if number + m is good print it and return but i got WA on test 2 anyone can explain why?

same here bro

If you know the reason please tell me

The length of a number is at most 100.000 when long long can fit around 19 characters if I am correct.

I have also taken boundary cases yet I do not understood why I got wrong answer ton test case 2?

19 < 100.000, look at the problem constraints carefully.

Somebody please tell what is wrong with my code?https://codeforces.cc/contest/1700/submission/161195566

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

Why can you just go left to right in C, I was thinking some insane subarray decomp shit

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

could solve only 1

Why is my solution to $$$D$$$ is giving TLE? Time complexity is $$$nlogA + qlogn$$$, where A is $$$10^9$$$. It should pass within the time limit. Am I doing something wrong?

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

Ohh yes! Thanks :)

Please share your approach for C.

:'(Is it only me or the last 3 contests DIv2 B and C are strange and too annoying than earlier rounds :'(

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.

I finally got the idea, thanks

Interesting solution. How did you get the intuition of making the difference array?

The intuition is to think an array as a function which maps integer $$$i$$$ to $$$a[i]$$$. Difference Arrays can be thought as derivatives (Prefix sums as integration). To add a fixed number to some segment $$$[i,j]$$$ of array means its "derivative" is only gonna get changed at points $$$i$$$ and $$$j+1$$$, as the value of every other element in array at index $$$i$$$ relative to index $$$i-1$$$ doesn't change.

Able to solve only problem A. I feel problem C was slightly confusing.

Did anyone else use binary search in D? I binary searched on the minimum possible answer(k), checked if (max from 1 to k of (prefixsum(k)/k)) $$$\leq$$$ t (i.e. the time queried) (to check that if we open first k taps, we can fill at-least those locks) and if (k*t) $$$>$$$ total sum (to check that if we open first k taps, we can fill the remaining locks as well).

It involved the use of double so I wasn't sure if it would FST or not. Code: 161214410

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

Can you please explain your res array? How you are filling it?

Can anyone share approach for D? Thanks.

$$$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.

Problem B: Why my solution is wrong? :(

https://codeforces.cc/contest/1700/submission/161216752

just check s[0] is or not '9'.

I returned 11111.....(n+1) times in the second pretest. Thus, the answer should be correct at the end.

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

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 thingsOops...Thanks :)

This round is better than yesterday's round.

yesterday's round was make me feel strange

My solution to F:

SpoilerThe key idea of problem F is the horizontal distance is known which is $$$\sum abs(p[i]-q[i])$$$,where p[i] or q[i] is the column of the i-th one of the first or the second matrix .

Then you need to minimize the vertical distance without changing the horizontal distance .

If you minus the first matrix from the second matrix ,suppose the result is $$$a[i][j]$$$, and let $$$pre[i][j]=\sum_{k\leq j} a[i][k]$$$,then the horizontal distance is $$$\sum abs(pre[1][j]+pre[2][j])$$$,the horizontal distance won't change iff $$$abs(pre[1][j])+abs(pre[2][j])=abs(pre[1][j]+pre[2][j])$$$.

So you need to adjust the '1's to make the condition above holds.

Use dp to calculate the optimal answer.

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

SummaryView the problem as moving the ones from one place to another. Of course, if the number of ones is different, it is impossible.

Consider a divider moving from left to right.

We track two variables

If the their sign is different, balance them out by moving a one between top and bottom row.

The cost is the number of ones moved on the top row, on the bottom row, and between the top and bottom row.

Solution 161214061

The round is not bad,but B and E are too sad,or you can say it is annoying.

C also :'(

https://codeforces.cc/contest/1700/submission/161217713 can anyone help me why this submission is wrong ?

how to solve C?... i am unable to build a approach :(

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

Ok thanks

To not keep you waiting, the ratings are updated preliminarily. In a few days, I will remove cheaters and update the ratings again!

really appreciate that bro.

My implementation for B : Link

I first added smallest number of length n to the given string s of length n and then I found the next largest pallindrome greater than or equal to that number and then I subtracted the latter from the given string.

For ex: s="1243" add "1000" -> "2243" -> find next pallindrome >= "2243" -> "2332" and then I subtract "2332" and "1243" to get "1089".

Anyone can tell me what's wrong with my submission?161219672 of Problem 1700E - Serega the Pirate, I spend more than 2 hours on it and still don't find out. I am very frustrated.

Take a look at Ticket 13074 from

CF Stressfor a counter example.wow, This website is very helpful

A suggestion for your product: generate more overflow test cases, I just checked my overflowed solution and your site haven't extracted any cases for that.

I think you are not aware of the full customisation features offered by the website. There's no corner test case that we store, we generate them on the fly, tailored for each submission. So, the website implicitly has the overflow test case, to extract it out, you need to edit the table, and increase the array values and the array size to a large number. This will result in an overflow and the website would display you the corresponding test case.

Oh I see. I used it the first time and I thought it adjusts its parameters according to the problem. Can I use this during the contests or problems appear there only after the finish?

Of course you cannot use it during contests.

And the problems don't magically appear after the contest, unless someone explicitly adds them in the backend.

Help Please,

In problem D test case number 4 there are 50 elements where the sum of all elements equal 2509. The last element is 31. So the rest of element's summation is 2478. Why, the result of query "51" is "-1"? Why not "50"?("50" is my solution output)

I think if we open all 50 locks for 51 seconds, then there is a possible solution.

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).

Thank you so much. I missed this case.

E seemed similar to IOI seats to me, at least it is how I got idea.

161177712 Here's my unsuccessful submission for B.

161220520 However, after adding two lines for fast io, it's accepted (alas, after the contest). Didn't know these make such a difference.

My solution idea and code for Problem DFirstly notice: If there are N pipes that are open, it's best if all of those N pipes are the leftmost.

Then, do a binary search on the answer for each query, but how do we check if M open pipes are enough, there are 2 checks: the total water should be enough to fill everything (M * t >= sum), apart from that, the first M pipes should be enough to fill the first M locks (this can be stored using DP).

[If you're wondering when would this matter: here's a case, consider that the first lock is very large, while the next (M — 1) locks are very small, i hope you can figure out the rest on your own]DP[i] will be at least DP[i-1] and it could be more if the water overflown from the previous pipes plus the water from the current pipe is not enough to fill the current lock. See my code for better explanation: https://codeforces.cc/contest/1700/submission/161205339

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.cc/contest/1700/submission/161202315

This guy amber_100 has been cheating since day 1. What he does in order to avoid plagiarism is that between every 100s of lines of commented code he writes a small piece of copied code.

Even in today's contest he used FPC language to submit problem C & D which were shared on the online cheating sources. And I am 100% sure that he doesn't even know what FPC is.

MikeMirzayanov please look into this matter and punish him according to what you think he deserves. I hope to see a reply to my appeal soon.

Some of his solutions from today's contest: 161215138 & 161201924

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

Yes, Codeforces should ban him immediately, but the fact that he finds a way to skip the plagiarism check is a big loss for the MOSS Plag Checker.

That vuln. of MOSS was long ago lol...infact changing for(0<=i<n) to while(0<=i<n) would break MOSS XD...however it helps catching those blatant cases whose appeals can be found on every other contest

Yeah, that's true that we can break MOSS in various ways but real CP lovers would never do that and I only want that repeated case of plagiarism like this should be taken into consideration.

BTW thanks for showing your concern and replying to my comment.

My solution for C, and i think it's easy to understand and code. First, calculate minimum steps to make array equal. Easy to see, it's sum of all different of pair i and i-1, call it K. Now after K steps we have an array with all elements equal to x, we need to find x, if we can find it, just plus abs(x) to K, it's the answer. We know number of steps to make first element (a[0]) and last element (a[n-1]) equal to x is K (because of suffix and prefix). Call L is number of steps to make first element equal to x, and R is number of steps to make last element equal to x. We have two conditions L+R=K and a[0]-L=a[n-1]-R. Basic math, after calculate L or R, calculate x and print the answer.

Can someone please suggest a way to solve problem B without using strings to represent the input number? Thanks a lot.

Btw here is my submission: https://codeforces.cc/contest/1700/submission/161207107 . I struggled finding a way to convert char to int and vice versa. Lucky how I was able to do so at the end after searching for the syntax on the internet (hopefully it is not illegal xD).

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

It seems that the testcase for F is weak though it has quite large number of tests. I have uphacked myself with a totally random test..

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).

uphacked

ok, i known why my greedy is wrong

in my code, for example

to

will do matched as

to

that's incorrect

Actually this was from a flaw in my custom made istream.

Your input had additional whitespace after the sequence of numbers which made my istream read whitespace and newline as number 0

Change "1\n1 \n0 \n0 \n1 " to "1\n1\n0\n0\n1" will work correctly

Test cases for E are weak; no tests with 3 or 4 bad cells that are solvable using one swap.

Is it possible to write a solvable test with 5 bad cells?

By bad I mean has value $$$v$$$ > 1, and all adjacent values are greater than $$$v$$$.

Hey friends, I don't do many videos on CF, but got a few requests for C and happened to be around — https://youtu.be/8IbZ23SCXAM — let me know what's up!

Eagerly looking forward to the tutorial！

When will the editorial for this be published?

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.

Where can I get solution, or someone can help me in D, thanks everyone

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.

Clearly tutor, thanks bro

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)`

Amazing idea!

Editorial?

Tutorial link please.

can someone explain the test case 4 (https://codeforces.cc/contest/1700/submission/161300579?mobile=false)

Note the colon at the end of the string below:

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

I have some dp idea for d but it does not seem to pass. I don't know the error in my proof, so hopefully somebody can help

Let dp[i] be the number of seconds it takes to fill first i locks, and c[i] be the overflow of water into the river after dp[i] seconds.

dp[0] = v[0] and c[0] = 0 (first pipe takes v[0] seconds to fill the lake, and there is no overflow after v[0] seconds).

Inductive step:

let the new lock be v[i]. Then we need at least dp[i-1] seconds, so if that pipe is open it will now only have v[i] — dp[i-1] volume left. We can also subtract c[i-1] since that was the extra flow from the left hand side.

So this leaves v[i] — dp[i-1] — c[i]. If this amount is negative (call it a) then we simply set c[i] = abs(a).

Otherwise, we have i+1 pipes pouring into this lock, so we find how many seconds it would take to fill the remaining amount with this, and update the overflow accordingly (i.e. if we had a 6 depth lake and 5 pipes were filling it, it would take 2 seconds and overflow 4 litres).

After this we can recover the answer normally. I get WA on test 5

Submission: 161427665

Take a look at Ticket 13878 from

CF Stressfor a counter example.Thank you. If anybody is interested, my proof is not wrong, and my logic is correct.

The error came from the accumulate function, accumulate(v.begin(), v.end(), 0) overflows, and we need to write accumulate(v.begin(), v.end(), 0LL) instead.

That was my guess as well :) That's why I reverse engineered the testcase, so you get the opportunity of spotting the bug yourself.

That's really cool, thank you, I appreciate it :)

Today rating changes of this round are updated and i got a message that my solution coincides with 4 other people for question B.I don't know how,it's my own code and i think solution of question B is just printing the formula for the answer in two cases viz. if first character is 9 and other case if it is not 9,i just write my own code,but it might possible that it coincide with other people too. I sewar i haven't cheated in this round, so i request MikeMirzayanov Sir to give me my ratings back.

Hi, Can someone please explain why my SUBMISSION is failing test case 7? I tried CF Stress as well. It couldn't find any counterexample.

Thanks.

Take a look at Ticket 14156 from

CF Stressfor a counter example.Changed float to double and it works now. Thanks though.