ch_egor's blog

By ch_egor, 7 weeks ago, translation, In English

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, _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

UPD3: Winners!

Div. 2:

  1. teacherone
  2. zsxdcfv
  3. AndrescuIII
  4. rhzmydd
  5. Yuki991

Div. 1 + Div. 2:

  1. SSRS_
  2. noimi
  3. Fysty
  4. peti1234
  5. teacherone

UPD4: Editorial

 
 
 
 
  • Vote: I like it
  • +213
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    Please notice the unusual time.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Today's problems were really amazing I just loved eve. Though I was not able to solve some problems

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why this based on All-Russian olympiad contest start unusual time

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +55 Vote: I do not like it

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

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

Is this contest rated for 2100+?

»
7 weeks ago, # |
  Vote: I like it -25 Vote: I do not like it

Brace yourselves for hacks and fsts in this round.

»
7 weeks ago, # |
Rev. 2   Vote: I like it -250 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

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

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +47 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck for everyone!!!

»
7 weeks ago, # |
  Vote: I like it -91 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it -273 Vote: I do not like it

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.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +48 Vote: I do not like it

    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.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    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)

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -23 Vote: I do not like it

    orz orz big great BurningRaven I will participate in this round to support russia orz

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +52 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    russia is a good country, india stands with russia

»
7 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

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

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

points distribution?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this post is not on the home page

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
7 weeks ago, # |
  Vote: I like it -21 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i hope i can get top 10 in this contest

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

hi

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

All the best everyone.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why am I not able to participate?

»
7 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

I think I'm not helping the nature

»
7 weeks ago, # |
  Vote: I like it +42 Vote: I do not like it

Decent round, but B is really annoying :)

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    big integer ?!

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

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

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          The big number will have n digits. And 2 ≤ n ≤ 100000. long long wont store that big number, use string

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        then subtract x from this ?

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            python and java coders have the advantage at this point.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      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

      • »
        »
        »
        »
        7 weeks ago, # ^ |
        Rev. 2   Vote: I like it +7 Vote: I do not like it

        Come 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:

          vector<int> ans;
          for (int i = 0; i < n; i++) {
            if (sum[i] - num[i] < 0) {
              sum[i] += 10;
              sum[i + 1]--;
            }
        
            ans.push_back(sum[i] - num[i]);
          }
        

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

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Meanwhile, Python/Java coders using BigInteger :P

»
7 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Ok problem(s)

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Spoiler
    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        Spoiler
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    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

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

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

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 2   Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

»
7 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    lol C was easier for me than B

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain sol for Div2C to me please??

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

approach for B? Anyone

  • »
    »
    7 weeks ago, # ^ |
    Rev. 7   Vote: I like it +3 Vote: I do not like it
    Hint-1
    Hint-2
    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
Rev. 2   Vote: I like it -14 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
7 weeks ago, # |
  Vote: I like it +43 Vote: I do not like it

Problem F is similar to Coin Collecting from JOI 2019.

»
7 weeks ago, # |
  Vote: I like it +31 Vote: I do not like it

Awesome D and E!

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

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 :(

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You should hide this under spoiler tag.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yup, didn't realize that, thanks!

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same here bro

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If you know the reason please tell me

      • »
        »
        »
        »
        7 weeks ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            19 < 100.000, look at the problem constraints carefully.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
7 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

could solve only 1

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please share your approach for C.

:'(
  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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

  • »
    »
    7 weeks ago, # ^ |
    Rev. 3   Vote: I like it +4 Vote: I do not like it

    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

  • »
    »
    7 weeks ago, # ^ |
    Rev. 3   Vote: I like it +21 Vote: I do not like it

    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.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I finally got the idea, thanks

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone share approach for D? Thanks.

  • »
    »
    7 weeks ago, # ^ |
    Rev. 3   Vote: I like it +17 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +22 Vote: I do not like it

    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.

»
7 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Problem B: Why my solution is wrong? :(

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

»
7 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

This round is better than yesterday's round.

»
7 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

My solution to F:

Spoiler
  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +16 Vote: I do not like it

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

    Summary

    Solution 161214061

»
7 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
7 weeks ago, # |
  Vote: I like it +78 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      wow, This website is very helpful

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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?

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            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.

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you so much. I missed this case.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
My solution idea and code for Problem D
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +32 Vote: I do not like it

This guy Noob_coder_042003 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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

»
7 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

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

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      uphacked

      ok, i known why my greedy is wrong

      in my code, for example

      0 1 0
      0 0 1
      

      to

      0 1 0
      1 0 0
      

      will do matched as

      0 a 0
      0 0 b
      

      to

      0 b 0
      a 0 0
      

      that's incorrect

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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!

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Eagerly looking forward to the tutorial!

»
7 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

When will the editorial for this be published?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    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)

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Tutorial link please.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like 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.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.