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

Автор Kaey, 4 года назад, По-английски

Ciao, Codeforces! We're glad to invite you to take part in Codeforces Round 701 (Div. 2), which will be held on Feb/12/2021 17:50 (Moscow time). This round will be rated for participants with rating lower than 2100.

You will be given 6 problems and 2 hours to solve them.

We would like to thank

Last but not least, we also want to thank the testers: armyalpaca, dario2994, davi_bart, DeadlyCritic, franfill, HIS_GRACE, kclee2172, lorenzoferrari, manik.jain, mattysal, namanbansal013, Osama_Alkhodairy, Prakash11, rocks03, Shusaku, simpatine, stefdasca and Retired_cherry.

The score distribution will be announced soon.

We hope you'll like the problemset!

UPD1: The score distribution is $$$500 - 1000 - 1500 - 1750 - 2500 - 3000$$$.

UPD2: For technical reasons, the round was postponed by 15 minutes. Sorry for that, good luck on round!

UPD3: Editorial is out.

UPD4: Congratulations to the winners!

Div. 1 + Div. 2:

  1. Muffinhead
  2. jiangly
  3. neal
  4. rustylake
  5. SSRS_

Div. 2:

  1. rustylake
  2. Join_VNOI_Discord
  3. Mr_Eight
  4. _Froggy_
  5. Brookli

First to solve each problem:

A: m_99
B: kmjp
C: Brookli
D: enoone
E: w0nsh
F: rainboy

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

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

As a tester, i recommend you participate in this round! Problems are very interesting and statements are well written.

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

I see what you did there.

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

lmao, poor anton!!

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

As a tester, I did not test.

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

As a person who wasn't involved in the preparation of this round, I recommend you to participate.

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

As a tester ,I reccomend you to read all the problems. The statements are short so you won't lose much time.

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

As a participant looking for negative contribution, help me to reach global minima!!!

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

Many thanks to Kaey, MrBrionix, MyK_00L, taulant and TheScrasse for preparing the Div.2 contest.

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

As an upcoming participant. I saw newbie tester :thinking:

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

    I think judging someone based on his/her ratings is a crime, it's the passion for CC that brings everyone here, even in Chess not everyone is a GM yet the people who play it enjoy it, it's high time we start judging people based on the number of contests they have appeared in, as in that case it will ultimately benefit the entire programming community.

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

Like the early score distribution, the gap between C and D isn't significant, makes me feel comfy! Hoping for a great round! :D

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

Stefan stefdasca Dascalescu is back to Codeforces/testing/setting yeah! I think its cause the exams are finished finally in some univerisities but not all :(

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

We are hopeful to have such pretests set so that many of us will not be frustrated in the final standings(In the last round it happened).Thank you.

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

As a participant, wish you all great rating changes :)

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

    Either positive or negative.

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

      "Great negative rating change" doesn't make sense, I guess.

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

        Merriam-Webster

        Great

        notably large in size : HUGE

        all creatures great and small

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

          No, I mean a "Great negative rating change" isn't a real "Great rating change" !

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

          Words can have multiple meanings. In your link, see

          4 — used as a generalized term of approval

          had a great time

          It was just great.

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

            I didn't check your profile the last time I saw your username, are you really from Finland? If yes, why the mango-lassi? Not against it but expecting a good story.

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

              It's not that great of a story. I first registered with the username "mangolassi", but lost the password (and used an old email I no longer had access to), so I made this account.

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

            Right. But for a phrase to make sense just one meaning needs to apply.

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

Thanks to MrBrionix, MyK_00L, taulant and TheScrasse for setting the problems Hopefully , we'll enjoy the contest

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

difference between c and d is 250 only. what does this represent? is it that d is not much difficult than c?

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

Again early score contribution, great! thank you!

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

As a problemsetter, MyK_00L says that problem F is easier than C.

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

Has anyone noticed that all of the authors have the same profile picture?

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

    Yes.

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

    I guess it's because that picture is the logo of the contest.(At least you can assume that)

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

      Well, not really at the beginning; I'm going to share the backstory here. At first, around 2 weeks ago, I took a picture from the Black Cherry sticker pack and set it as my profile picture on Codeforces and Telegram. A few days later, TheScrasse was looking for a profile picture to replace the Lichess horsey, and he didn't want to use a picture of himself, so I told him he could take mine. After a moment, I came up with the idea that we could all use that picture during the week of the contest.

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

Wow! It falls on Chinese Spring Festival. May my rating increase on the first day of the new year :)

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

happy lunar new year ^^, hope this contest will be a good contest ^^

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

i hope fair pretests !!

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

As a tester, I wish all the participants good luck and I recommend you all to read all the problems.

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

As a to be participant, I wish everyone good luck and happy ratings :)

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

I will be posting solutions of problems of this contest tomorrow. On this YouTube Channel:- https://www.youtube.com/channel/UCfX-OxxzYPELHxpNojOojcw

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

как я люблю контесты от новичков :)

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

Happy Chinese New Year!

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

Not related

Just noticed that. It makes delta 0 in unrated rounds. I think it would be better if it calculates virtual rate change like this

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

I hope this contest has strong test cases, especially pretests :)

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

Is it rated

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

The last Round was a nightmare for me (even today, I didn't understand the reason), Hoping that this time things will be much different, finger crossed.

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

Happy Lunar New Yearrrr

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

Hopefully I will solve C today and become pupil

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

    To become pupil AB solving(I guess up to hour) is sufficient

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

      Well if B is of difficulty <= 1300 then I will do it easily I guess.But if its difficulty is >=1400 then I think it will be a challenge for me currently,Let's see what happens.Fingers crossed!!!!

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

As a tester, I wish all the participants good luck and I recommend you all to read all the problems.

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

Good luck everyone, i wish we all will raise our ranks

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

I hope there will be a palindrome related problem to honor the day (12.02.2021) :)

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

It's 12/02/2021 A question on palindrome would be fun to solve .

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

Happy Lunar New Year!!! :)

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

will the contest still be held? because Polygon and Codeforces will be possibly unavailable in the period between Feb. 12, 20:00 (UTC) and Feb. 12, 22:00 (UTC) because of maintenance.

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

    That would be a few hours after the contest, so it is not a problem. (the contest ends at 16:35 UTC)

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

    THe maintenance won't influence this contest because the contest will end at $$$\textsf{Feb. 12, 16:35(UTC)}$$$ :)

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

Is today CF round has some technical issue as the message is displayed ???..

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

Authors are different but their pictures are the same:D

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

As a human bean, I recommend you all breathe.

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

antontrygubO_o for not being involved and hence not rejecting any problem.
Is it a joke?

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

Why contest nowadays are not based on proper ds and algo they are mostly ad-hoc??

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

Delay :(

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

shifted by 15 min.

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

This contest also starts postponing. Hoping it will not become unrated as well.

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

CONJECTURE : If you have exam next day and you attempt a rated round. You will screw up both ratings and grades.

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

contest postponed by 15 min

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

here we go again.. delay...

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

ok lemme listen again.

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

Delayed by 15!!

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

Contest delayed...just hoping to not face a long queue!

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

delay of 15 min

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

Has the contest been moved back?

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

Now i know why they delayed the contest , They are watching LOCO CODM Cup Pro , mYm vs Godl .

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

Sorry for +15 minutes. I postponed the contest to be sure that everything is OK. I'm here, no reasons to worry. Good luck on the round!

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

Codeforces Waiting for 20,000 Participants to Cross! Agree?

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

    It is not good at all. Last time everybody shouted for the 30000 and people started coming out of nowhere. And lead to an unrated round. After that, all were disappeared, and numbers came around 20000. And now again IF you start this, IN MY OPINION people new account for such streak. which is not good.

    DownVote if don't agree.

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

hope it remains rated...

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

They should not delay the contest it is quite frustrating

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

QWQ 15 min ..

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

Delayed for 15 minutes...

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

you got je'baited

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

My first contest in the new lunar year <3

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

Even codeforces is taking time to start the contest and you think that your crush will start loving you so easily and early! ;-)

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

Don't be unrated please

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

waiting for 15 min when we are all set to go, is quite frustrating but we can wait for a better experience!

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

Noo!!! delay :( Wishing everything goes well :/

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

All the best 1 min remains now

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

My sister brought a fried chicken for me at 8:30. I said I'll eat this after 10:35.

Thanks for the delay

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

delayforces :) But Actually delay is better than Unrated round :)

»
4 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится
Комментарий удален по причине нарушения правил Codeforces
»
4 года назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

Please don't make contests if u can't make one.

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

    Bruh, don't blame the writers if you cannot solve the problems.

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

    I don't see any problem with the contest. It's just that it is a little tougher than usual. And it's completely okay to have such small variations.

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

Welcome to the comment section, who left the contest unattempted after watching 1st question.

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

thanks for clear and short statements , really liked the problems

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

Contest is running now, but I cant register now, why??

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

Wow even A was pretty tough!

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

Is it rated?

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

:|

this was a hard div 2 contst

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

    It's not a shit contest, but it is made for div1 after b.

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

    Though I couldn't do my best today, I think the problem-set was pretty standard. Being unable to solve a problem doesn't mean it has to be a shitty contest.

    Besides, you don't have any right to insult a setter panel like this. I enjoyed the problem-set. And I am pretty sure they worked really hard to make this contest enjoyable and successful.

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

20,000+ Registration and somewhat 10,000 people made submissions :/

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

How to solve C,D ??
Verry toough contest for mee :(

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

    Hint : We can find all pairs $$$(a,b)$$$ by fixing remainder $$$R$$$. $$$R$$$ must be less than $$$sqrt(x)$$$ and we can do binary search .

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

    Problem D:

    LCM of all numbers from 1 to 16 is 720270. You can fill a matrix B with this number. Now all we have to do is to make differences of k^4. For that you can simply subtract A[i][j]^4 from B[i][j] in a chess pattern. Now all numbers in B are divisible with the numbers in A and they respect the conditions.

    Here is my code: 107219536

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

    For C, for one possible b, min(b-1,floor(x/(b+1))) values of a is possible I did it by breaking it in two parts doing first for b which are less than sqrt(x) and then the for the b whose multiples are less than sqrt(x). The numbers left need to be tackled separately so that any b is not counted more than once. Solution

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

lol that F was nice XD

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

How to solve C ? Plz

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

    i use a = c * (b + 1) then c = 1...5e5 (c < b) for each c find how many b and a satisfy

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

    a should be of the form n*k+k. Now n*k+k<=x, then n<=(x-k)/k. Now iterate over k from 1 to x (say). answer will be incremented by min(n,y)-k, I did this because numbers which have k as the remainder and quotient will be in between k+1 and min(n,y). Now if min(n,y) < k+1, then you should break the loop because right value is smaller than left value. You can check using simple maths that you don't need to iterate for k more than sqrt(x+1) times check to get the final answer

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

I like this type of contest :) Thanks for good problems.

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

How to do C or D ?

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

Very bad contest!

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

Unbalanced contest.

Today we had a Mathforces ! Problem C was too math oriented.

C should have been divided in two parts, with lessor and higher constraints.

I got the idea of C but couldn't implement in 1.5 hours :(

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

    I noticed a pattern in C:

    a : b : cnt

    3 : 2 : 1 <3>

    4 : 3 : 2 <4,8>

    5 : 4 : 3 <5,10,15>

    6 : 5 : 4 <6,12,18,24>

    so suppose take set for a=6 then every number in that set and b is special pair.

    .....

    a goes till x and b till y. Take approproiate minimas of x and y though.

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

    Hi, actually I had a very cool idea. But its a little bit maths oriented :(
    Approach : a should be of the form n*k+k. Now n*k+k<=x, then n<=(x-k)/k. Now iterate over k from 1 to x (say). answer will be incremented by min(n,y)-k, I did this because numbers which have k as the remainder and quotient will be in between k+1 and min(n,y). Now if min(n,y) < k+1, then you should break the loop because right value is smaller than left value. You can check using simple maths that you don't need to iterate for k more than sqrt(x+1) times check to get the final answer

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

    C could be done with binary search too

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

Unfortunately, I have seen a similar task with C when preparing for our last round...

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

Is C is really something so simple, or it is easy to google? :)

Because all I have thought is to try solve $$$a = (b + 1)ceil(a / b)$$$ and it led me to "iterate $$$b$$$ over $$$[1; y]$$$ and add to answer $$$min(x, b(b+1) - 1) / (b + 1)$$$". But ofc it's $$$O(y)$$$ :(

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

    I literally submitted that: https://mirror.codeforces.com/contest/1485/submission/107226790

    (and it TLEd obviously)

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

    it's not o(y) because you only have to go until min(y,1e5).

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

      I don't know how to calculate sum of $$$x / (b + 1)$$$ in range $$$[sqrt(y); y]$$$. I think there is formula but not found it.

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

        After you pass sqrt(X), some values start to repeat (ie. floor(100/80) = floor(100/81) = 1)

        You can split the code into two parts, one iterate from [1, sqrt(X)], doing the same thing you made:

        • ans += X / (b + 1).

        For the rest, you could iterate on the quotient, instead of the divisor (ie. how many Z satisfy 100 / Z = 1?)

        It will end up as a pattern like this:

        • for every i in [L, R], floor(X / i) == 1
        • for every i in [R + 1, ...], floor(X / i) == 2
        • ...
        • for every i in [..., ...], floor(X / i) == sqrt(X)

        So you will end up with another loop that iterate over sqrt(X) values, doing this operation:

        • ans += (R — L + 1) * quotient
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Great Round, thanks.

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

How to calculate Summation min(b-1 , x/(b+1) ) in C . b varies from 1 to y . Is there any other way??

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

    No need to go till Y. Iterate on the remainder, the maximum remainder you require is 32000.

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

    Observe that $$$min$$$ is only useful for $$$1 <= b <= sqrt(x)$$$.

    $$$sqrt(x)$$$ isn't that high. So you can bruteforce the part with $$$min$$$.

    For other values of $$$b$$$, just do a binary search on when $$$x/(b+1)$$$ changes. As there are around $$$sqrt(x)$$$ different such values (remember harmonic sum?) this would not be that bad either.

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

      I kind of observed that , but thought it's C and shouldnt be that trickier. Knew that n/x yields same value for i <=x<= n/(n/i).

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

Was there some trick in D?

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

    Yes. 720720 is lcm of numbers from 1 to 16, i.e. 720720 is divisible by any number in our matrix. further if (i + j)% 2 == 0 b [i] [j] = 720720 else b [i] [j] = 720720 + a [i] [j] * a [i] [j] * a [ i] [j] * a [i] [j]. chess coloring

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

fuucccckkkk, I couldn't submit E because I spent the last 10 minutes debugging the fact that my ape mind didn't understand the tree input format

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

    That tree input sucks.

    It should be trivial to implement the parser.

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

      It's actually my favorite way to input a tree. You can show that v[i] is also the parent of i, which saves you from doing a dfs to separate parent and child.

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

Kudos to problem setters. Short & crisp problem statements were great!!

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

Whoa, that was tough but fun.

A was a bit tougher than usual but OK. I felt B and C required really careful implementation (especially C). I solved as far as C and I can tell by the rankings that this contest was tougher than usual.

Couldn't crack D, was interesting though.

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

Again, I realized how bad my math is :(

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

I think problem F is easier and lighter(implementation wise) than usual. Otherwise, A pretty nice round. Thanks for the problems.

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

it sucks so bad when you realize how D can be solved after coding a dumb ass recursive solution and there is only 1 minute left.

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

For D. Notice that minimum number that divide each element is $$$720720$$$. We should make difference between adjacent elements equal $$$k^4$$$ for some $$$k$$$. Consider our matrix ass chess desk with white and black cells, so each white cell will be adjacent to black cells and vice versa. So we can set black cells equal $$$720720$$$, and white $$$720720 + M[i][j]^4$$$ what is less than $$$10^6$$$ and difference condition is met.

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

for $$$C$$$ the answer will be $$$\sum_{b=2}^{Y} min(X/(b+1),b-1)$$$. Can anyone tell how to compute this efficiently?

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

    This is what I did: up until b=1e5 just apply the formula you mentioned, and after that it is clear that $$$X/(b+1)$$$ will be the minimum for whatever value of X, so figure out a way to efficiently do $$$\sum_{b=1e5+1}^{Y} X/(b+1)$$$

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

107225945 why my code getting tle ? explain me!

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

I corrected a mistake in my solution for E just two minutes after the contest was over, and then it passed the sample test case. I met such a situation again and again. o(╥﹏╥)o

Anyway, I'll try my best next time and wish myself to keep calm during the contest for better debugging.

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

Please Help Suppose I submit a correct solution of a problem and a minute later i again resubmit another correct solution of the same problem . Will the second solution get a penalty of 50 points because that is what happened with me today in problem A despite never having a wrong submission . Instead of 478 points I got 428

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

    Yes, it does happen that way. Even if your original submission happens to be correct, (which is not something that is known during contest as only pretests are run) you still incur a penalty.

    If I am not wrong, the only submissions that don't count towards penalties are

    1. the first submission (not counting any compilation issues beforehand)

    2. Submissions that fail to compile.

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

Unfortunately, weak pretests for B.

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

    wrong answer 80200th numbers differ — expected: '930343232', found: '576709456628597052'

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

    I got FST on B for a very simple case which is when l==r, this type of simple cases should be present in the pretests.

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

      I also got FST on B I forgot the case for n=1 , today I had the chance to become expert but I missed it :(

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

if i have 2 more min, i would AC B :(

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

Thanks for the great problems. What is the fastest way of finding any positive solution to $$$ax + by = c$$$?

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

My bad.

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

    It's too late to hack in contest, but CM's and above can uphack, which would add the test for future upsolvers. It won't change anyone's rank in contest, but it's still useful (not to mention fun). If you send me the submissions and the hack test, I could uphack them for you.

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

    test case 26 has n = 1.

    so no, not a "lotta solutions" fail to cover n = 1.

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

like task D

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

Dear Kaey, I am very sorry that I complained irrationally about math today. I may have hurt your feelings unintentionally. I may have disrespected your hard work. I didn't want to do that. I loved today's problem set. I deeply appreciate your hard work. As I suck at math and I didn't have anything to do, I irrationally started trolling you guys without thinking a bit. But one of my friends made me realize that I was very wrong. I am extremely sorry. Please accept my apology. I hope to see you guys set more awesome contests like this! Thank you.

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

Easy D (1750), LOL

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

oughh... Pleeassee make pretests hard :'( it hurts so much

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

$$$\lfloor \frac{a}{b}\rfloor$$$ forces

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

Nice contest..... I like that there are hints in editorial before giving out the solution

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

Don't know about others, but coming from a math background, this contest was really enjoyable. Kudos to all the authors! :)

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

A-D are math problems

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

Can anyone tell why B failed on System Test 5?

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

Thanks for good pretests in B...

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

if I read D before C, I would AC D :( Why in this contest D is much easier than C?

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

Thanks for the contest :)

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

I tried to calculate $$$Dp_i$$$ from bottom to top in problem E, but got wa on test 3. It works like this:

sort(stage[i].begin(),stage[i].end(),cmp);
ll Max=-Inf;
rep(j,0,stage[i].size()-1){
    int k=stage[i][j];
    f[fa[k]]=max(f[k]-a[k]+maxx,f[k]+a[k]-minn);
    f[fa[k]]=max(f[fa[k]],a[k]+Max);
    Max=max(Max,f[k]-a[k]);
}
Max=-Inf;
per(j,stage[i].size()-1,0){
    int k=stage[i][j];
    f[fa[k]]=max(f[fa[k]],Max-a[k]);
    Max=max(Max,f[k]+a[k]);
}

Where $$$i$$$ is the depth. The nodes in $$$stage[i]$$$ has the same $$$dis$$$ which is $$$i$$$.

$$$minn$$$ is the minimum of $$$a_i$$$ at the same stage, $$$maxx$$$ is similar to $$$minn$$$.

Could anyone explain that why it is wrong? The submission : 107250435

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

Hello everyone, this is my first time making a tutorial if you like then please like and share and if there is any concern then please comment: https://youtu.be/fMZIuQU7fqY Solutions for problem A,B,C,D

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

Why have the recent rounds started adding so many Adhoc, Math and Constructive questions? We should have more DP, Graph, Range Queries etc.

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

A very cool problemset. Thanks.

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