Блог пользователя ch_egor

Автор ch_egor, 21 месяц назад, По-русски

Всем привет!

В воскресенье состоится всероссийская олимпиада школьников для 5-8 классов имени Келдыша. Удачи всем участникам! Олимпиада проходит под чутким руководством московской методической комиссии в лице GlebsHP, ch_egor, Endagorion, vintage_Vlad_Makeev, Zlobober, meshanya, cdkrot, voidmax, grphil, fedoseev.timofey и, конечно, Андреевой Елены Владимировны.

Мы рады представить Codeforces Round #802 на основе задач олимпиады. Это будет Div. 2 раунд, который состоится в 19.06.2022 12:05 (Московское время). Возможно, вы уже и раньше участвовали в раундах на основе олимпиад, подготовленных московской методической комиссией (раунды 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). Обратите внимание на нестандартное время начала раунда.

Задачи этой олимпиады были придуманы и подготовлены Siberian, _overrated_, Igorbunov, Ziware, talant, Olerinskiy под координацией fedoseev.timofey.

Также спасибо 74TrAkToR за помощь с организацией Codeforces версии соревнования и одну из задач, MikeMirzayanov за системы Codeforces и Polygon.

Также хотелось бы поблагодарить компанию Tinkoff и лично Татьяну TKolinkova Колинкову за неоценимый вклад в организацию соревнования.

Спасибо NEAR за поддержку этого раунда, подробности в этом посте.

Желаю удачи!

UPD1: Спасибо Um_nik, 244mhq, MichsSS, zarubin, TeaTime, devid, Mangooste за тестирование.

UPD2: Разбалловка: 500 — 1000 — 1500 — 1750 — 2500 — 3000

UPD3: Победители!

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: Разбор

  • Проголосовать: нравится
  • +213
  • Проголосовать: не нравится

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Хочу как Nutella3000 в 2019 набрать 450 баллов

»
21 месяц назад, # |
  Проголосовать: нравится -26 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why every based on All-Russian olympiad start unusual time

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Конкурсное время должно совпадать с олимпиадным — иначе будут люди, которые знают задачи до контеста (олимпиады) — это плохо. Обратите внимание, что люди могут покинуть олимпиаду до ее окончания — поэтому конкурс должен начаться точно по времени олимпиады в 12:00 по московскому времени.

    Contest time have to match Olympiad time — else there will be people who know problems before the contest (olympiad) — that is bad. Note, that people can leave olympiad before the end — so the contest must start right in time with olympiad in 12:00 moscow time.

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      21 месяц назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +55 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

Is this contest rated for 2100+?

»
21 месяц назад, # |
Rev. 2   Проголосовать: нравится -250 Проголосовать: не нравится

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

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится -12 Проголосовать: не нравится

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

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good luck for everyone!!!

»
21 месяц назад, # |
  Проголосовать: нравится -273 Проголосовать: не нравится

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.

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +48 Проголосовать: не нравится

    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.

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +39 Проголосовать: не нравится

    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)

  • »
    »
    21 месяц назад, # ^ |
    Rev. 2   Проголосовать: нравится -23 Проголосовать: не нравится

    orz orz big great BurningRaven

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +52 Проголосовать: не нравится

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

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

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

»
21 месяц назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why this post is not on the home page

»
21 месяц назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Давайте распределение баллов за 5 минут до старта.

»
21 месяц назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i hope i can get top 10 in this contest

»
21 месяц назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Minecraft74 ну ты машина! нету слов просто

»
21 месяц назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

I think I'm not helping the nature

»
21 месяц назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

Decent round, but B is really annoying :)

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    big integer ?!

    • »
      »
      »
      21 месяц назад, # ^ |
        Проголосовать: нравится +12 Проголосовать: не нравится

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

    • »
      »
      »
      21 месяц назад, # ^ |
        Проголосовать: нравится +21 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        21 месяц назад, # ^ |
        Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

        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.

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Big integers !?

»
21 месяц назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Ok problem(s)

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Spoiler
    • »
      »
      »
      21 месяц назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        21 месяц назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Spoiler
  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    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

    • »
      »
      »
      21 месяц назад, # ^ |
        Проголосовать: нравится +19 Проголосовать: не нравится

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

    • »
      »
      »
      21 месяц назад, # ^ |
      Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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

»
21 месяц назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

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

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    lol C was easier for me than B

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can someone explain sol for Div2C to me please??

  • »
    »
    21 месяц назад, # ^ |
    Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

    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

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve problem C?

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

approach for B? Anyone

  • »
    »
    21 месяц назад, # ^ |
    Rev. 7   Проголосовать: нравится +3 Проголосовать: не нравится
    Hint-1
    Hint-2
  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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.

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
21 месяц назад, # |
Rev. 2   Проголосовать: нравится -14 Проголосовать: не нравится

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

  • »
    »
    21 месяц назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
21 месяц назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

Problem F is similar to Coin Collecting from JOI 2019.

»
21 месяц назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

Awesome D and E!

»
21 месяц назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
21 месяц назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
21 месяц назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
21 месяц назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

could solve only 1

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please share your approach for C.

:'(
  • »
    »
    21 месяц назад, # ^ |
    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

  • »
    »
    21 месяц назад, # ^ |
    Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится

    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

  • »
    »
    21 месяц назад, # ^ |
    Rev. 3   Проголосовать: нравится +21 Проголосовать: не нравится

    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.

    • »
      »
      »
      21 месяц назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I finally got the idea, thanks

    • »
      »
      »
      21 месяц назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        21 месяц назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
21 месяц назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Can anyone share approach for D? Thanks.

  • »
    »
    21 месяц назад, # ^ |
    Rev. 3   Проголосовать: нравится +17 Проголосовать: не нравится

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

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

  • »
    »
    21 месяц назад, # ^ |
    Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

    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.

»
21 месяц назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Problem B: Why my solution is wrong? :(

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

  • »
    »
    21 месяц назад, # ^ |
    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

»
21 месяц назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

My solution to F:

Spoiler
  • »
    »
    21 месяц назад, # ^ |
    Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

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

    Summary

    Solution 161214061

»
21 месяц назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
21 месяц назад, # |
  Проголосовать: нравится +78 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      21 месяц назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      wow, This website is very helpful

    • »
      »
      »
      21 месяц назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        21 месяц назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          21 месяц назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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?

          • »
            »
            »
            »
            »
            »
            21 месяц назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится

            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.

»
21 месяц назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
My solution idea and code for Problem D
  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

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

  • »
    »
    21 месяц назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
21 месяц назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

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

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      21 месяц назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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.

»
21 месяц назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

My hopes of doing better in competitive programming really goes down when I see this contest was aimed at Russian kids in grade 5-8 , who are acing these contests

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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

  • »
    »
    21 месяц назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      21 месяц назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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

    • »
      »
      »
      21 месяц назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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!

»
21 месяц назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Eagerly looking forward to the tutorial!

»
21 месяц назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

When will the editorial for this be published?

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    21 месяц назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    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)

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      21 месяц назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        21 месяц назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.