AquaMoon's blog

CodeTON Round 2
By AquaMoon, 2 years ago, In English

Hello, Codeforces!

A wonderful summer holiday! After College Entrance Examination, we are extremely delighted to invite you to our second round, CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!), which will be held on Jul/31/2022 17:05 (Moscow time). Note the unusual start time of the round.You are given 8 problems and 2.5 hours to solve them.

All problems were written and prepared by Cirno_9baka, CoupDeGrace, Sugar_fan, ODT, Yakumo_Ran, farmerj, MagicalFlower, izlyforever, kuangbin, mejiamejia, ugly2333 and me.

Task statements and editorials will also be available in Chinese (Simplified) and Chinese (Traditional) after the contest.

We are sincerely thankful for the help provided by:

This is our second round! Great efforts have been put in during the past year. We are sincerely looking forward to your participation and we hope everyone will enjoy it. Besides, this round is sponsored, which indicates that everyone has an opportunity to get the prize!

Good luck!

UPD1: Here is the score distribution:

500-750-1250-1750-2000-2750-3500-(2250+2750)

UPD2:Tutorial is available.

UPD3: Simplified Chinese tutorial is available.

UPD4: Traditional Chinese tutorial is available.

UPD5: Congratulations to the winners

  1. tourist
  2. jiangly
  3. ksun48
  4. Rewinding
  5. djq_cpp
  6. maroonrk
  7. cnnfls_csy
  8. he_____hezhou
  9. 353cerega
  10. WYZFL
  11. ecnerwala

UPD6: Simplified Chinese statement is available.(please download it and open it with edge)



And here is the information from our title sponsor:

Hello, Codeforces!

We, the TON Foundation team, are pleased to support CodeTON Round 2.

The Open Network (TON) is a fully decentralized layer-1 blockchain designed to onboard billions of users to Web3.

Since July, we have been supporting Codeforces as a title sponsor. This round is another way for us to contribute to the development of the community.

The winners of CodeTON Round 2 will receive valuable prizes.

The first 1,023 participants will receive prizes in TON cryptocurrency:

  • 1st place: 1,024 TON
  • 2–3 places: 512 TON each
  • 4–7 places: 256 TON each
  • 8–15 places: 128 TON each
  • …
  • 512–1,023 places: 2 TON each

We wish you good luck at CodeTON Round 2 and hope you enjoy the contest!

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

Comments Comments (306)
| Write comment?
»
2 years ago, # |
  Vote: I like it +48 Vote: I do not like it

Good luck for everyone!!!

→ Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

cooooooool

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    hope it will be more friendly to newbie

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      Orz! I believe you will get a big suprise o(*^w^*)o (

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        As a last-minute tester, solving the problems in this contest has re-sparked my interest in competitive programming, something which I have forgotten about for a while now.

        Thank You, AquaMoon

        CodeTON2: AquaMoon's Blessing on This Wonderful World!
        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +2 Vote: I do not like it

          Wow! Thank you! I believe you will be an excellent programmer! Keeping your original dreams and interest is wonderful ๑(≧▽≦)✧

          → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          How to be a last-minute tester?

          → Reply
»
2 years ago, # |
  Vote: I like it +27 Vote: I do not like it

I hope it is not Mathforces again!

→ Reply
»
2 years ago, # |
  Vote: I like it +27 Vote: I do not like it

I am SUPER excited for this round!!!!!!!!!

→ Reply
»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

please no math

→ Reply
»
2 years ago, # |
  Vote: I like it -31 Vote: I do not like it

Math Round!!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Best of luck！

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Gook luck! I believe you can do it! (❁´◡`❁)

    → Reply
»
2 years ago, # |
  Vote: I like it +19 Vote: I do not like it

So many nice people in the helper list, this competition will be great.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Thanks for your support! Wish you good luck! =❁ω❁=

    → Reply
»
2 years ago, # |
  Vote: I like it +38 Vote: I do not like it

the previous contest of AquaMoon is too hard..hope this round can be a normal round.

→ Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Since Yakumo_Ran is (again) a problemsetter, will there be Touhou statements?

→ Reply
»
2 years ago, # |
  Vote: I like it +12 Vote: I do not like it

As a tester, good luck to everyone!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hope this round will be interesting

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Of course. Good luck and enjoy yourself! (●'◡'●)

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Yay codeton

→ Reply
»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

4 weeks ago

→ Reply
»
2 years ago, # |
  Vote: I like it +97 Vote: I do not like it

As a tester, I think some of the problems are very interesting.

Hope all of you will enjoy it!

→ Reply
»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Super data structures round?

→ Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Is AquaMoon a girl?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Of course she is!

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Suiseiseki is one of my best friends, you can trust him. No doubt I am a girl ~ (☆▽☆)

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +41 Vote: I do not like it

My glad to be a tester again. Thanks to all of the authors!

This round will be very interesting.

Wish everyone good luck!

(The statements are short and pretests are strong and give me contribution XD)

→ Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Why is spaghetti.code shown two times in the registrants page with a red highlighted number?

→ Reply
»
2 years ago, # |
  Vote: I like it +22 Vote: I do not like it

What's the prize distribution?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    We will update it later. Now it is still mysterious to stimulate your interest! (≧▽≦)

    → Reply
»
2 years ago, # |
  Vote: I like it +51 Vote: I do not like it

Cute AquaMoon's cute round with cute problems!
Hope everyone enjoy it :)

→ Reply
»
2 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Can't help but notice Aquamoon trying too hard to be cute in every comment and blog-post.

No offence o(*^w^*)o (●'◡'●) ヾ(≧▽≦*)o (❁´◡`❁)...

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    She is indeed very cute. I treat her as my own sister. When I chat with her on QQ, she has a lot of expressions, at least I am used to it.

    → Reply
»
2 years ago, # |
  Vote: I like it +29 Vote: I do not like it

I hope it is Mathforces! 0w0

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

so many people!

→ Reply
»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I'm too curious to see your face!

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +65 Vote: I do not like it

    Just imagine a cute girl! ☆(≧▽≦)☆

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +33 Vote: I do not like it

      It's been proved for me that imagination is never close to the reality ^_________^

      → Reply
»
2 years ago, # |
  Vote: I like it +20 Vote: I do not like it

WOW!!

So many testers in this round XD

→ Reply
»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

AquaMoon orz ❤❤

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

Are u really a cute girl? Don't dig traps for me. ;-;

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +64 Vote: I do not like it

    Yes, I promise! o(> ω <)o

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I can guarantee that because I am one of the writers, you can trust me.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have been bamboozled so hard

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        so hard I really had to scroll up to check

        → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        No, I am indeed the account of one of the writers. It's just that for some reason, I don't use that account to leave a message. You can notice a fact: if what I say isn't true, aquamoon will definitely ask who I am.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          ok but afaik alts are illegal? intensive thinking

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            I thought the use of alts are okay as long as you don't participate in a contest with more than one account at a time based on what others were saying

            → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone encourage me to participate please I only lose my rate *_*

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Don't worry too much about your rating. Just ignore it for now and the only way to improve faster is to participate in as many contests as possible.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope it will be a good round.

→ Reply
»
2 years ago, # |
  Vote: I like it +27 Vote: I do not like it

We hope you will enjoy this round >_<

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I think it is gonna be a very creative and unique round. Hope I can reach BLUE thru it though a bit worried...

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Note the unusual timing ...

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

"after college entrance examination".

You mean gaokao in China? In India we have JEE.

Did all the authors get into tsinghua university?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Chinese editorial! That's great!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck and have fun!!

→ Reply
»
2 years ago, # |
  Vote: I like it +54 Vote: I do not like it

My nightmare of Round #732... Now the problemsetters come back again!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck! but I am not skilled in math problems :(

→ Reply
»
2 years ago, # |
  Vote: I like it +22 Vote: I do not like it

As a tester,wish you good luck and enjoy the contest!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this contest rated for everyone?

→ Reply
»
2 years ago, # |
  Vote: I like it -23 Vote: I do not like it

Really enjoyed Round 732 <3

→ Reply
»
2 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Hurray we have traditional Chinese statements and editorial!!! I am a HongKonger (not shown in my profile though) and I'd love to see that!

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

where is the score distribution ?

→ Reply
»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Chinese statements! Cool!

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Chinese statements and tutorials will be updated after the contest. (๑•ᴗ•๑)

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck for everyone XD

→ Reply
»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Everyone should have a dream, and I hope I can reach 1400 points through this round.

→ Reply
»
2 years ago, # |
  Vote: I like it -16 Vote: I do not like it
Fun fact
→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

what is ton

→ Reply
»
2 years ago, # |
  Vote: I like it +57 Vote: I do not like it
Codeforces users when they see a problemsetter who is actually a girl:
→ Reply
»
2 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Why was I marked as a tester of this round? I haven't solve it. Will Can I take part in this round?

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I invited you, maybe you forgot.Thank you so much for taking our test! You can ask me on discord for specific things.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +57 Vote: I do not like it

      Ohh! I checked it one more time and i really tested your round few month ago. Sorry for this fake message :D

      → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    Hi dear friend! In fact you have already tested it a few months ago ~

    I guess you forget it ~

    So I am afraid that you can not participate in it o(T︿T)o

    → Reply
»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Hope it will not be mathforces again

→ Reply
»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

CUTEFORCES

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck to myself and good luck to everyone in the rankings!

→ Reply
»
2 years ago, # |
  Vote: I like it -70 Vote: I do not like it

I wish I could get rank 1 in this contest and defeat tourist too and impress AquaMoon

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +63 Vote: I do not like it

    I can understand wanting to win first place, but I don't understand the point of impressing aquamoon, she has a boyfriend, good luck.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    did you seriously make an account just to simp for AquaMoon ._.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      Sorry, I noticed that your message was not a reply to me, but I can't delete it, please ignore it.

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what is div1 +div 2??

i mean what will be the difficulty of questions

→ Reply
»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

8 prblms in 2.5 hrs . Hmm seems like Div3 level i guess ??

→ Reply
»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Good luck

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope there is not too large gap of difficulty between any adjacent problems.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The difficulty gap between the problems is at most $$$998244353$$$

    .
    .
    .
    .

    =❁ω❁=

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +62 Vote: I do not like it

    What ToroTN wants:
    A:2400, B:2500, C:2600, D:2700, E:2800, F:2900, G: 3000, H: 3100
    Yep that seems legit.

    → Reply
»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

When will the scoring distribution be announced?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If somebody won't take their prizes, will it pass to the next ones?

→ Reply
»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

I got a feeling that the problemset is bound to be nice, given the grand problemsetter & tester team.

→ Reply
»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Hoping for a balance round!!

→ Reply
»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Hope I will reach CM after this round

→ Reply
»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Good Luck EveryOne!

→ Reply
»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

So will the score distribution be announced?

→ Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Second "note the unusual start time" comment.

→ Reply
»
2 years ago, # |
  Vote: I like it -8 Vote: I do not like it

I'm so happy to be able to compete with the big boys again!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally today the Great Battle between the top 3

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

giving a CF rated contest after almost 3 months . lets relive those days again

→ Reply
»
2 years ago, # |
  Vote: I like it +25 Vote: I do not like it

dang it, I think tourist will be dethroned today

→ Reply
»
2 years ago, # |
  Vote: I like it +98 Vote: I do not like it

Who the fuck wrote problem D's statement?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +85 Vote: I do not like it

    What was wrong with it? It was clear to me

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The "For every" part is vague, mainly because he asks you for the number of type 2 operations, which kills the assumption that all arrays have the same number of operations.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        I see two occurrences of "for every" in this statement and I do not see any ambiguity with them. Also, where did you get the assumption that all arrays have the same number of operations from???

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I mean the second one, It kind of went that the actual operation eric was doing is doing an operation for every array.

          Also, I am 100% sure I am not the only one who didn't understand this part.

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            "There are two operations that Eric can perform on an array ct:" — I don't see how you can get such assumption with this specified. It's quite clear that each operation concerns one specific array and the "for every" part doesn't change that. I don't see any fault on the authors side

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              lol, Okay then how come this passes 166396472

              That's how I understood the problem too but I wasn't able to solve it until I made that assumption.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                2 years ago, # ^ |
                  Vote: I like it +8 Vote: I do not like it

                It passes, because it is a correct solution even without assuming your false assumption

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                    Vote: I like it +8 Vote: I do not like it

                  OHHHHHHHHHHH, okay lol my bad just noticed.

                  → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    I feel pity to read this comment cuz actually author team rewrite and polish the statement of D for many times. Personally speaking, I don't think the misunderstanding you mentioned is that frequenct for others, I feel it sounds more like a accident. ;w;

    → Reply
»
2 years ago, # |
  Vote: I like it +55 Vote: I do not like it

02:29:15, wow!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve $$$E$$$?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    How to fix Wrong answer on pretest 5 in $$$E$$$? :(

    I thought the answer is: Sum of all values that will reach the sink plus amount of steps in which the sink won't output any number. These steps can only happen in the first $$$~1010$$$ steps. But I got WA pretest 5. :/

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You should terminate if there is nothing left I think.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, I stop searching for steps in which the sink won't output any number, if there are no more values left to be output.

        → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you calculate the amount of steps in which the sink won't output?

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 2   Vote: I like it +5 Vote: I do not like it

        Every node $$$i$$$ has an array $$$a_i$$$ with $$$a_i[0]$$$ being the input. We sort the nodes topologically and start propagating along edges $$$i \rightarrow j$$$: $$$a_{j}[t+1]:=a_{j}[t+1]+a_{i}[t]$$$. This makes one timestep. This won't be exactly right if simulating it, since the values don't get propagated all at once, but they will have to wait in the next node either way.

        Then I take a look at $$$a_{sink}[t]$$$ and iterate $$$t$$$, adding the value to the variable $$$occupied$$$. After each step $$$occupied$$$ is reduced by one. If $$$occupied$$$ reaches $$$0$$$, we have a step with no output. We only need to check the first $$$~1000$$$ steps. See also 166388098.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh wow, the case $$$a_i=0$$$ for all $$$i$$$ was my mistake. Had to change a $$$0$$$ to a $$$-1$$$. That is disheartening.

            → Reply
»
2 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Tourist with the CLUTCH SOLVE to beat Jiangly!!!!

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Hints for problem D?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    Notice, that the first operation doesn't change sum of prefix sums and the second one decreases it by 1.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      Thank you so much. It was a very unique observation. Can you also give hint for how to find the number of operations please?

      UPD: Never mind

      → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    hint
    → Reply
»
2 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Tourist nailed it at the last minute and came on top! What a competition!

→ Reply
»
2 years ago, # |
  Vote: I like it +46 Vote: I do not like it

I tried D for 2 hrs and was not able to solve it

And tourist managed to read, think, code and submit it in just 3 mins !!!!!!

How???

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +23 Vote: I do not like it

    $$$\sum i \cdot c_t [i] $$$ is same for each row except the special row $$$k$$$, for which it is one higher for every operation done on it.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Not only is his IQ much higher than ours, it is also likely hyper-concentrated in quick assimilation of information, mathematical accuracy, and logical creativity.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    After solving a zillion different problems about prefix sums, you would be able to spot in three minutes that the sum of prefix sums decreases by 1 for the special array, and for the rest, it remains constant

    → Reply
»
2 years ago, # |
  Vote: I like it +43 Vote: I do not like it

tourist's last minute submission. Damnnnn...

→ Reply
»
2 years ago, # |
  Vote: I like it +117 Vote: I do not like it

When I thought that jiangly will finally reach top 1:

Then this happened:

dramatic.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

nice round, but disgusting problem D :(

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is TL in E so unnecessarily strict? I have $$$O(n*(n+m))$$$ solution which does not cross TL, but according to the constraints, it should pass easily.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    It's not strict, you forgot to check vis state in DFS.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +39 Vote: I do not like it

      fuc******** cant believe missed AC by 1 line

      → Reply
»
2 years ago, # |
  Vote: I like it +17 Vote: I do not like it

1 min before the end of the contest: Jiangly will beat tourist! After the contest: what? tourist solved G at 02:29:15?

→ Reply
»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

wowww..! tourist's last minute clutch!!

→ Reply
»
2 years ago, # |
  Vote: I like it +20 Vote: I do not like it

It's dramatic that tourist overtook jiangly 1min before the contest ends.

→ Reply
»
2 years ago, # |
  Vote: I like it +61 Vote: I do not like it

Thanks, OEIS!

→ Reply
»
2 years ago, # |
  Vote: I like it +41 Vote: I do not like it

F is much too weird. Maybe it's better to set $$$n\le 1000$$$ for those who doesn't know the conclusion?

→ Reply
»
2 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Problem E can __int128 hold all variables?

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 3   Vote: I like it +4 Vote: I do not like it

    Of course not , the maximum variable can be about $$$O(2^{n/2})$$$ .

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can java BigInteger or Python pass it?

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how's that O(2^(n/2)) calculated? can u prove it?

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 2   Vote: I like it +30 Vote: I do not like it

        Say if you had a graph like this

        Initially, assume a value 1 at node $$$1$$$. After $$$t = 1$$$, this value will go to nodes $$$2$$$ and $$$3$$$, and at $$$t = 2$$$, they will combine to become 2 at node $$$4$$$. At $$$t = 3$$$, the value will go to nodes $$$5$$$ and $$$6$$$ and at $$$t = 4$$$, they will combine to become 4 at node $$$7$$$.

        So, the value will keep doubling every $$$N/2$$$ nodes, resulting in $$$2^{N/2}$$$.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Thank you! Learned a lot from u.

          → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why would you want to do that if we are asked to compute modulo an int?

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Because it seems to be small enough, not the case of 1 million bit, it is like we use bitset for 64 times faster. If a type can hold it, we can simulate it using O(n*n).

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I solved it like that as I didn't think of simulating the first $$$n$$$ iterations: 166393805. Note that the big integer operations work in O(n/2/60 = 9) in the worst case.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Cool. So mine will be ok if I replace int128 to some BigInt-like struct. Thank you.

          → Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Whoever came up with problem D is an artist. Best problem of this year

→ Reply
»
2 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Fight between tourist and jiangly is always legendary and dramatic for 1st position !

→ Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I live to see Tourist vs Jiangly.

→ Reply
»
2 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Sorry, I hate this round very much.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

In G, I reduced it to the following problem:

Given arrays $$$\left\lbrace a_i\right\rbrace_{i\in\lbrace 1,2,\ldots,n\rbrace}$$$ and $$$\left\lbrace b_i\right\rbrace_{i\in\lbrace 1,2,\ldots,m\rbrace}$$$, find all positions $$$j$$$ such that the array $$$c=a[j{.}{.}j+m-1]$$$ is equal to or greater by $$$1$$$ than $$$b$$$ in every position: that is, for every $$$j\in\lbrace 1,2,\ldots,m\rbrace$$$ $$$c_j=b_j$$$ or $$$c_j=b_j+1$$$. Recall that if we remove the $$$+1$$$ possibility (that is, $$$c_j$$$ should be equal to $$$b_j$$$ for all $$$j$$$) then this is simply a substring search task that can be solved using KMP.

Any ideas for "weak substring" problem?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let's split the numbers that appear in a in b by numbers that appear a lot and numbers that don't appear a lot. Try to match a number x in b with numbers x or x+1 in a.

    For numbers that appear a lot use fast convolution, for numbers that don't appear a lot use brute force. This ends up in $$$O(N\sqrt{NlogN})$$$ if you split numbers at frequency around $$$O(\sqrt{NlogN})$$$ I think.

    → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +28 Vote: I do not like it

    Using Fast Fourier transform we can calculate $$$\sum_{i = 0}^{m - 1} (a_{i + j} - b_i)^2(a_{i + j} - b_i - 1)^2$$$ for every $$$j \in \{1, 2, \ldots ,n - m \}$$$ in $$$O(nlog n)$$$ time. Each $$$0$$$ in this sequence corresponds to "weak substring" starting from position $$$j$$$.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      Yep, that's a nice generalization of "match strings with questionmarks", that is also computed with

      $$$ \sum\limits_{i=0}^{m-1} a_{i+j} b_i (a_{i+j}-b_i)^2 $$$
      → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    Another way to do it is to do string matching with wildcards twice, on even and odd values.

    For the first matching on even values, we mark all odd numbers on $$$a$$$ as wildcards. For all odd numbers in $$$b$$$, we add $$$1$$$ to it. Then this becomes the usual string matching with wildcards.

    The second matching is done similarly. We just have to check that the substrings match in both cases.

    → Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Can't believe I guessed the second part of answer for D based on the test samples and some data I collected for the first part.....still no clue why it works.....but somehow I have confidence that it would pass the system test....

→ Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Even though I sit for almost 2 hours thinking about D and I feel totally useless, I have now read the required observation and it's just beautiful. I wouldn't mind failing miserably every time if the problems are like this one. Thanks to the author.

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve 1704H1 - Game of AI (easy version)?

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 3   Vote: I like it +18 Vote: I do not like it

    I got it slightly late :(.

    We case on B. Each element $$$k$$$ of b falls into 4 types, depending on the two decisions $$$b[k] = k$$$, and whether there exists i!=k such that $$$b[i] = k$$$.

    Let's say there are i elements such that b[i] = i, and j of those appear again in the array. The total number of such arrays is the product of:

    $$$\binom{n}{j}$$$ -- number of ways to choose elements such that b[i] = i

    $$$\binom{i}{j}$$$ -- number of ways to choose elements (b[i] = i) that appear again

    $$$\binom{n - i}{n - i - j}$$$ -- number of ways to choose elements (b[i] != i) that appear again

    $$$j \cdot (n - i + 1)!$$$ -- number of ways to set the values for the n-i elements that do not equal themselves (This is non-obvious, but try creating a recurrence relation)

    Then for each of these b arrays, there are $$$(n-i)^{i-j} (n-1)^j$$$ a arrays that correspond to each.

    Summing over all $$$i,j$$$ gives the answer.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh wow, that's completely inverted line of thinking to what I was thinking was much more natural. I thought to characterize for each a how many bs we can get and sum over that (which actually looked quite viable, but didn't manage to do so)

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        I spent most of my time doing that, but when I switched perspectives it worked really well (but not fast enough :( ).

        I couldn't really come up with any ideas to combat the fact that things in a can have high 'indegree'. What were you coming up with?

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          In this problem we are dealing with functional graphs. If we focus on one connected component then it is almost a tree and the problem is easily solvable on trees by some dynamic programming. We would like to maintain two numbers for a tree that we assume has some outgoing edge of the root. Namely, how many final configurations we can get depending on whether the root will make a move or not. If these pairs for our subtrees are

          $$$(a_1, b_1), \ldots, (a_k, b_k)$$$

          then if we denote the pair for the root as

          $$$(A, B)$$$

          then

          $$$A = \sum_{i=1}^{k} i \cdot \sum_{|B|=i} \prod_{j \in B} b_j \prod_{j \not\in B} a_j$$$

          and

          $$$B = A + a_1 \cdot \ldots a_k$$$

          and this is computable through some dps (possibly in $n^3$ as we can use preprocessing)

          The idea would be to improve this approach to handle the additional edge somehow and combine various connected components in a knapsack-like fashion with some Newton's symbols along the way.

          → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          I guess that's what I was doing, looks like I'm the only stupid guy with hundred lines of weird dps instead of 5 lines of formulas (I still don't understand your solution). 166399131

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            Ok, the main idea is that for each array $$$b$$$, we want to count how many $$$a$$$ will work.

            If we have $$$b[k] = j$$$ for $$$k \neq j$$$ that forces $$$a[j] = k$$$ (because $$$j$$$ must have invaded $$$k$$$). This means that if we have $$$n - i$$$ elements of $$$b$$$ that are not fixed points (and $$$i$$$ fixed points), then $$$n - i$$$ of the values of $$$a$$$ are fixed.

            Now for the indices $$$ind$$$ for which we do not know $$$a[ind]$$$ that were invaded, they can have any of the $$$n - 1$$$ possible values, as we can just assume they are placed later in the permutation than the thing that invaded them, and everything will be consistent. For the indices that survived, they can go anywhere that does not have $$$b[k] = k$$$ because we can assume their invasion was overridden later.

            Basically any $$$a$$$ that does not cause simple contradiction is possible, because we can just place certain elements at the beginning or end of the permutation.

            → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +84 Vote: I do not like it

(I'm not good at English so I used DeepL translation. So if there is any unnatural English, I am sorry.)
This image is a Google search result during Coding Phase.
They (the uploaders of the top 3 videos) seem to upload their solutions to YouTube during the contest, isn't this a violation of the terms and conditions?
(if I misunderstand and this is not a violation, sorry.)
PS: I took my friend's advice and improved the grammar of this comment.
https://twitter.com/kenkenokkuu/status/1553781614941175808

→ Reply
»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

How to solve H1?

→ Reply
»
2 years ago, # |
  Vote: I like it +24 Vote: I do not like it

E is cool, D is too unnatural to be a good problem, but it's decent, B and C both very boring problems with standard greedy, A is fine

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How do you solve problem A efficiently ? I tried recursive memoized approach, got TLE.

My Submission

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You just check if the last m-1 characters in string a is the same as the last m-1 characters in string b, where m is size of b. Then just check if the first character in b exists somewhere in string a before the last m-1 characters. If both are good, then its true.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Notice that you can't change last m-1 symbols of string a. So if last m-1 symbols of string a are not equal to the last m-1 symbols of string b, then the answer is "No". Now we should check b[0]. Consider two cases:

    1) b[0] == '0'. If a[0:n-m) contains '0', then we just apply (n-m) min operations to string a to get '0'. We can't do that ONLY if string a[0:n-m) consists of n-m '1' symbols (as min(1,1) = 1; max(1,1) = 1).

    2) b[0] == '1'. If a[0:n-m) contains '1', then we just apply (n-m) max operations to string a to get '1'. We can't do that ONLY if string a[0:n-m) consists of n-m '0' symbols (as min(0,0) = 0; max(0,0) = 0).

    We can check these conditions in O(n).

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I'd really appreciate if people told me why did they downvote my answer.

      This approach works (166352851).

      → Reply
»
2 years ago, # |
  Vote: I like it +81 Vote: I do not like it

Why there wasn't any announcement that the statement for E changed? I was debugging for an hour just because of the third example. :(

→ Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Finished E after contest (at least I think finished)
Dropping out of violet because of the wrong submission for A...

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My idea is pretty much optimized simulation

    Cannot check whether it is right until systests finish though

    → Reply
»
2 years ago, # |
  Vote: I like it +23 Vote: I do not like it

For the guys who solved D. How did you come up with the prefix sum observation? Had you solved similar problems before?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought about prefix sum as well but my final solution does not have it

    → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +42 Vote: I do not like it

    I was looking for an invariant. I didn't find a prefix sum observation (although it is the same after all).

    First idea was sum of values... though this stays also the same for the fake-row. So it was of no use.

    Next idea was alternating sum. That was strange and I couldn't get any information out of that.

    Third idea I imagined the values as stones. Each operation is moving one stone to the left and another one to the right. Now the stones are worth some points. I needed the pointvalue to stay constant after an operation. So I decided, moving a stone to the left removes one point. Moving it to the right adds one point. So every stone contributes as many points as its position. Doing the normal operation keeps the total score constant. Doing the fake operation adds one point. So $$$\sum_i i \cdot c_t[i]$$$ was my invariant which I could directly use to find the fake row and calculate the number of operations on it.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      Same here

      I thought that it should be possible use some array with only two nonzero elements

      Then thought where should those elements be

      Then after experiments and thoughts about centers of mass ended up with these formulae

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thinking about the center of mass is nice too indeed! It also stays constant under the first operation and moves on the second operation. Cool physical interpretation.

        → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      It can also be interpreted as the position of the center of mass (multiplied by the mass).

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Still, Why would anyone come up with i * ct[i]? Why are we multiplying? You yourself are saying every stone contributes as many points as its position so total points is just sum of stones (no use). After this how do we get i * ct[i]? All logic before this seems intuitive but the formula does not. How does one come up with this?

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        Imagine you played a game. You place stones on a score track. At the end your total score is the sum of all stone's scores. This is your situation right now:

        How do you calculate your total score?

        → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    It's a common technique. When you have operation like adding or subtracting, see what's the effect on the prefix sum/difference array.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I was thinking in terms of parity of the difference array but couldn't get anywhere.

      → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Its common to take prefix/suffix sums when we consider operations on adjacent indices. Another recent example problem: link

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody tell me what is wrong in my code for B ? i spent much time to this due to which i solved C very late and had only 20 min for D https://mirror.codeforces.com/contest/1704/submission/166395252

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Your approach fixes $$$v$$$ to be equal to the first value of $$$a_i$$$ after a change (or at the start), but this is not necessarily optimal. For example, if your $$$k = 3$$$, and the first two food piles have values $$$4$$$ and $$$10$$$, then you should actually use $$$v = 7$$$ to eat both without changing.

    Instead of actually choosing the value of $$$v$$$, you should instead keep track of the maximum/minimum so far. As long as the difference is $$$\leq 2k$$$, then there exists a value of $$$v$$$ that can handle all those elements. Once the difference becomes $$$> 2k$$$, a change is required and you can reset maximum/minimum.

    → Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

For E how actually to take mod without influencing the final answer. I suppose taking mod before calculating maximum will produce WA, so there is no way to take mod before output (but then the answer can reach 2^300 somehow)... Got stuck for the whole contest orz.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I guess we can just take the last vertices without outgoing edges, then we don't need to think about maximums

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it -79 Vote: I do not like it

.

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 3   Vote: I like it -43 Vote: I do not like it

    .

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it +20 Vote: I do not like it

      Could you or someone else please point me to an official statement regarding the usage of pretests during the round? I'm not trying argue with you, I'm genuinely curious about this. Obviously, pretests reduce the pressure on the system, but also, they are a nice tool to make the whole experience more exciting (like freezing in ICPC). Another thing is that pretests make you a better coder. Yeah, it sucks when you get FST, but the danger of it makes you more careful both when solving and coding. Lastly, pretests make the whole hacking process possible.

      All I found is this from the contest rules:

      It is known that pretests do not check solution completely. Usually there are 2-10 pretests, and the fact that the solution passed pretests says only that it is quite reasonable. Typically pretests not contain the maximal tests, corner cases, etc.

      And also this from the contest preparation rules (from this post):

      In general, pretests should include: a test with maximum size of input (e.g. maximum n), a test against integer overflow, a few random small tests. All corner cases that are easy to miss. If you deliberately don’t include some corner case, talk to the coordinator about this.

      These rules also say, that wrong solutions should be prepared for integer overflow and for case work. These solutions should also fail pretests, which kind of contradicts the first citation:)

      → Reply
»
2 years ago, # |
  Vote: I like it -6 Vote: I do not like it

While some might complain that the contest was too hard (I think it's fine for a Div1+2 though), I don't think anyone can complain about the quality of the sample input/output. Very robust set of input/outputs such that a matching output is unlikely to be a coincidence. You still need to consider edge cases by yourself, of course, but I really appreciate not having to deal with the paranoia that the general idea is wrong even when the sample output matches.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Me:

  • Reads statement of D.
  • Immediately takes prefix sums.
  • Notices operation $$$2$$$ is just operation $$$1$$$ with extra subtraction.
  • "Hmm...how can I possibly tell these two operations apart?"

FML

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

does eng Tutorial of G,H gonna be available later or only Chinese are given?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    They will be later The editorials of problem G and H will be adding soon. (from editorial)

    → Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Wow! Now tourist has a one kiloTON of crypto!

→ Reply
»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Weak tests in E, why are solutions that just simulated using big integers passing?

→ Reply
»
2 years ago, # |
  Vote: I like it +27 Vote: I do not like it

As a tester, I'm sorry for not realizing that the main test for E is weak :(

I've submitted an uphack just now.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    So will have a re-run?

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also uphacked my solution with a test that provokes overflow, as I had forgotten to take mod in some places. But I couldn't find other solutions failing with the same test. Maybe because my approach is a bit different to most other solutions. Thanks for the weak tests anyway :D

    → Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it +7 Vote: I do not like it

What was the point of such strict time limit in E? (one second for seemingly intended O(n^2), n = 10000)

My python solution doesn't pass, c++ — easy.

I understand when it is intended to cut down inefficient c++ solutions but was there really anything like that here?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    N=10000 (O(N^2)=10^8) is not the same as N=1000, T=10 (O(T*N^2)=10^7).

    I edited your last python submission, changed the number of steps from 10000 to 2000, and it passed 166417578

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. I really didn't pay attention to the first part of constraints and just assumed that we can have 10k vertices....

      And now that I look at my code again I should've added break if not changed, then it wouldn't matter

      → Reply
»
2 years ago, # |
  Vote: I like it +79 Vote: I do not like it

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

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    It's very sad when attempts are ignored because of random coincidences. I am not a cheater, but I have no evidence that I did not cheat. I just love solving contests, I don't even have a suggestion on how to fix the random match situation. Just sad :(

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Rating: 1900

Hope removing cheaters will not reduce my rating :laugh:

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Generally speaking, removing cheaters will increase other people's rating.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it +20 Vote: I do not like it

      Though it is what happens often, it is not so obvious for me why it is the case.

      Say cheaters had a negative delta, then on average their removal should decrease everyone else's rating.

      I would assume that on average cheaters like anyone else have neutral delta and so their removal should also be rating-neutral (on average)

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It is much likely that cheaters have positive delta simply because they have cheated and therefore could solve more than they normally would.

        → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        So, if a negative delta seems inevitable during the round, would tricking MikeMirzayanov to believe you're a cheater help you avoid this negative delta~ ha~

        → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it +53 Vote: I do not like it

      So. With cheaters being removed my rating decreased by 1 )

      → Reply
»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

editorial for Traditional Chinese, I will ask aquamoon to update it to the announcement tomorrow. https://hackmd.io/nSTr3Ky4SyWNyvatJOXefw?view

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It is my regret that I did not attend

→ Reply
»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

D is really nice, but I wonder what's an issue with using just $$$n=2$$$. The conditions seem pretty contrived to me.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    I'm the author of question d, and dannyboy has suggested the same thing, but I feel like discovering what multiple arrays have in common would make the question more interesting, just a personal opinion.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This round changed my impression to chinese round.
If F is not an oeis problem or make a subtask for n^2, it will be better.

→ Reply
»
2 years ago, # |
  Vote: I like it +68 Vote: I do not like it

How can I recieve the prize in TON?

→ Reply
»
2 years ago, # |
  Vote: I like it +42 Vote: I do not like it

So how could we receive the prize sponsored by TON?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    We got a response and mike will post a blog on how to get the bonus.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What a great round!

→ Reply
»
2 years ago, # |
  Vote: I like it +19 Vote: I do not like it

I must say that problem D was terrific. Thanks for the round.

→ Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Could someone explain to me the intuition behind mx - mn > 2 * x in B?

The way I solved the problem is that I checked if the intervals of [a_i - x, a_i + x] had overlap. If yes, update interval to intersection, else use new interval of current a_i and increment counter. This passed.

However, everyone seemed to solve the problem using the inequality mx - mn > 2 * x. I understand how this comes from manipulating abs(v - a_i) <= x. However, I do not understand it intuitively. Like, how does that work practically? How is double the value of x and the difference between max(a_i) and min(a_i) related in such a way to solve this problem? Like beyond the maths of it and rather intuitively.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is actually pretty much the same thing you did. Instead of looking at "how long will my $$$2x$$$-long intervals ('intervals of [a_i - x, a_i + x]' as you call them) overlap" this looks at "How long can I place new points, such that a $$$2x$$$ Interval still can overlap all of them".

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +45 Vote: I do not like it

Attention!

Your solution 166365821 for the problem 1704C significantly coincides with solutions ruimina/166361635, xxh1999/166365112, siganai/166365821, shobonvip/166366942, OpKos/166367243, bharat007/166373462, Aksnov/166374356. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

I received these messages, but I did not cheated. I think it is a false detection of the fast input code. Fast input code is published on https://gist.github.com/ShubhamKJha/f16f5eb7e6da41da5f4b95d004b55d6e

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    I received these messages too. And I agree with you.

    The logic of this problem is very simple. Our logic in the main function is similar, but there are still differences in our code. Fastio is commonly used in Python for fast reading and writing. I use it in every problem.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    I'm on that list, and received the same message. I agree with you too.

    If I use Python/Pypy without FastIO, I'll often get TLE. Once I had failed system tests with TLE due to I/O slowness, and since then I've always used it.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I received the same message, the only similarities i can see between our solutions is that we all use FastIO for Python, which was clearly published before the competition. I don't know if it triggers those false alarms regularly, but maybe FastIO should be whitelisted from the cheat detection system.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I received these messages too. I agree with you guys. I've been using FastIO for a long time, so do other people I think. It seems the main function part of our solutions are significantly different.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the contributors of this contest. I become an Expert!

→ Reply
»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Why is the Simplified Chinese statement machine translated?

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    Why do you think so? This is manually translated by me and kuangbin, aquamoon, maybe the quality is not very high, but we spent a lot of time.If your message is said without any evidence, it will only lead to more and more Chinese round authors giving up on making Chinese statement, because it is a thankless task.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am very sorry if my comment is offensive,but some part of that is quite weird.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Can you give some examples? Let's improve it. (I think we all translate very seriously)

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Like the fourth line in "Input" of D,the sentence does not make sense.

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it +16 Vote: I do not like it

            This question was not translated by me, but I looked at the place you mentioned, and there is indeed a problem. We will review all statements and then update it, it may take some time, thank you for your feedback.

            → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
            ← Rev. 2   Vote: I like it +8 Vote: I do not like it

            I reviewed the entire statement with aquamoon and temporarily updated a version. Sorry for the late update, because I'm not a student, I have work to do, and my sister aquamoon has been busy lately. I'm asking izlyforever and CoupDeGrace to review it again, we should have another update over the weekend. Then, when I reviewed it, I found that the quality of the translation was really poor, no wonder it was suspected of being a machine translation, and I am very sorry for that. If you find any problems, please give feedback in time, and we will change it until almost everyone is satisfied.(UPD: We updated the version reviewed by izlyforever and CoupDeGrace.)

            → Reply
»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Hi,

Out of curiosity, when will the problem ratings for these problems be updated in the problemset? Some of the more recent contests have their problem ratings assigned already (like the Division 3 round and the Educational round) but this set is missing them.

Thanks!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Very nice problems, thanks！

It seems that the statement in Chinese has broken. Would you mind updating the statements, if possible? Or if it's just my own problems, could you show me how to operate it appropriately？

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nope, no damage, I tried it. Please try the following steps: 1. Download it. 2. Check whether the extension name of the file is mhtml (note that if the operating system is set to hide the known extension name, please set it to display the known extension name) 3. Open with edge.

    → Reply