huangzirui's blog

Codeforces Round #796
By huangzirui, history, 3 years ago, In English

Hi Codeforces! Happy Dragon Boat Festival!

We are glad to invite you to our first Codeforces Round Codeforces Round 796 (Div. 1) and Codeforces Round 796 (Div. 2) which will be held on Jun/03/2022 17:35 (Moscow time). This round will be rated for participants of both divisions. Participants in each division will be offered 6 problems and 2 hours to solve them. The two divisions will share 3 problems.

In this round, as the best friend of the characters in Touhou Project, you are going to help them solve the problems they meet.

The problems are prepared by xiaoziyao, Yakumo_Ran, SSerxhs, Cocoly1990, LilyWhite, Elegia and me. We hope you will enjoy this round.

Great thanks to:

Please pay attention that there will be no more than 998244353 interactive problems in this round, so learn more about interactive problems here before the contest.

Good luck & Have fun!

UPD 1:

Score Distribution:

Div2: $$$500 - 750 - 1250 - 1500 - 2000 - 3000$$$

Div1: $$$500 - 750 - 1500 - 1500 - 2000 - 3000$$$

UPD 2:

Editorial is out.

UPD 3:

Winners

Div.1:

  1. Um_nik
  2. Rewinding
  3. jiangly
  4. tourist
  5. SSRS_

Div.2:

official:

  1. Hanasaki
  2. tkended
  3. boboGM_when
  4. a_nanas
  5. rondoudou

unofficial:

  1. Teating_
  2. AgafonovArtem
  3. luogubot
  4. znqd3116
  5. XiShui_AKIOI
  • Vote: I like it
  • +746
  • Vote: I do not like it

Comments Comments (219)
| Write comment?
»
3 years ago, # |
  Vote: I like it +64 Vote: I do not like it

You mean no more than 998244352 interactive problems

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

998244352 not a prime number, 1e9+7 is the best

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

As a tester and writer,I think it's such an interesting round(and I want contribution).Good Luck & Have fun!

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

Chinese round,great!

Also the tester list is quite impressing as I know most of the people on it.

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

When I see Elegia in the setters, I know D1F won't be solvable.

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

Chinese round, good round!

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

As a writer, I want to know how Elegia's mind works. If you don't know too, please give me contribution :)

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

    As a Statement Writer, I want to know how Yakumo_Ran's mind works. If you don't know either, please give me contribution.

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

    As a partcipant, I want to know how all the writers' minds work. If you don't know either, please give me contribution.

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

Problems are really interesting, hope you all have fun!

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

As I'm a tester, I want my contribution back above 0

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

just a link to its Chinese edition

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

    世有伯乐，然后有千里马。千里马常有，而伯乐不常有。故虽有名马，祗辱于奴隶人之手，骈死于槽枥之间，不以千里称也。马之千里者，一食或尽粟一石。食马者不知其能千里而食也。是马也，虽有千里之能，食不饱，力不足，才美不外见，且欲与常马等不可得，安求其能千里也？ 策之不以其道，食之不能尽其材，鸣之而不能通其意，执策而临之，曰：“天下无马！”呜呼！其真无马邪？其真不知马也！

    北海若曰：“井鼃不可以语于海者，拘于虚也；夏虫不可以语于冰者，笃于时也；曲士不可以语于道者，束于教也。今尔出于崖涘，观于大海，乃知尔丑，尔将可与语大理矣。天下之水，莫大于海。万川归之，不知何时止而不盈；尾闾泄之，不知何时已而不虚；春秋不变，水旱不知。此其过江河之流，不可为量数。而吾未尝以此自多者，自以比形于天地，而受气于阴阳，吾在天地之间，犹小石小木之在大山也。方存乎见少，又奚以自多！计四海之在天地之间也，不似礨空之在大泽乎？计中国之在海内，不似稊米之在大仓乎？号物之数谓之万，人处一焉；人卒九州，谷食之所生，舟车之所通，人处一焉。此其比万物也，不似豪末之在于马体乎？五帝之所连，三王之所争，仁人之所忧，任士之所劳，尽此矣！伯夷辞之以为名，仲尼语之以为博。此其自多也，不似尔向之自多于水乎？”

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

luogu round!

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

Chinese Edition

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

So many famous Chinese OIers, looking forward to this!

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

Usually div.2 ABC will be easy to solve but now since so many high-skilled users from luogu participated in making problems I'll be thankful to solve A

if you agree give me contribution, or give me contribution

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

Touhou round, good round!

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

Glad to see a Chinese round and a Touhou round, sounds interesting.

Hope I can get an assert(Rating_change>0).

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

Beware of Luogu's problem group invading codeforces

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

As a Chinese round,why not set the time earlier?

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

    Ran thinks it's ok xD

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

    Because not only Chinese will participate in the Chinese round.

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

      But it doesn't mean that the author can ignore people like us who cannot get up late,especially in China.

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

      Don't you think there are too many contests at this point in time?

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

Is it needed to learn interactive problem for first 3 problem in div. 2 contest ?

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

oh yes chinese round finally

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

Touhou round, Great! xD

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

AnimeForces Round

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

why codeforces don't support emojis?

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

As a Touhou fan who has never played Touhou before . Although, I did play once. I hope to get back at it someday :D

I am looking forward to the round!

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

Animeforces round with almost all problemsetters having anime profile pictures. Is it me or the Chinese are more likely to have anime pfps than the Japanese (somewhat ironic, since animes come from Japan)?

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

Please pay attention that there will be no more than 998244353 interactive problems in this round..., but there will be a problem with mod = $$$998244353$$$, right?

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

Please pay attention that there will be no more than 998244353 interactive problems in this round, so learn more about interactive problems here before the contest.

Actually, I am going to learn more about combinatorics/counting problems after seeing that number.

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

What is rated range for div2 ?

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

Will Div1 A be Div2 D this time as both divisions share 3 problems this time?

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

A supercalifragilisticexpialidocoius Chinese Round!

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

    But as a Chinese OIer, I still cannot participant this round as the time is still too late for me.

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

    Unfortunately, the word should be "supercalifragilisticexpiadocious".

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

As an OIer in China, my parents will never let me take part in a 22:35 contest. So sad.

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

Chinese round, good round!

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

Can't wait to see PinkieRabbit get -154 rating.(

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

Hope to turn blue today :)

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

question c makes me wanna leave the contest rn

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

    I am unable to even understand the problem

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

      Some stooopid anime boy made this question, thinking he was being "cool".

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

      wtf does question C mean?????????

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

        First, read the sample test cases and then read the problem. It's not hard to understand the problem.

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

          i am a high expert on main, and i can't even understand Div2C. question is written very poorly. also, i don't see you getting AC on question C, so how about you solve it first before telling me to understand the problem?

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

            most of the people have understood the problem. it's just hard to capture the idea to solve it.

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

        you have starting string of one character a-z, you need to find that character which can be used for transformation process where you should apply next operation N times: take pair of string (x, y) from 2*N strings where x — substring of current string, y — string you should put instead of x in current string only once. ending string must be equal to final one given in description

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

storyforces

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

History repeats itself

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

I was able to solve only A lol (Div. 2, ofc)

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

Bruh Cdiv2's question is so confusing XD.

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

This contest sucks.

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

    I agree

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

    Yeah, I think div2.c is too hard (maybe have a strange idea too) and its statement is not good. Sorry for your bad experience. I hope I won't create such bad problem again.

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

sorry to say but this round really f***** my brain. did not like the problems even a bit. should've gone out with my friends instead.

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

in this contest we are all equal

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

Solved C with 0 confidence about the proof.

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

How does A sample passes on CodeBlocks, but do not pass on ANY compiler on cf? I have wasted approximately an hour to fix that :( 159364881 I think today is just not my day...

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

    Your toDec function might access elements outside the string giving garbage values at times.

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

      Thanks! Will be more cautious next time...

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

how to solve div 1C?

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

    Notice that an operation on prefix sums is: if $$$s[l-1] = s[r]$$$, set interval to $$$s[l-1]$$$ We can ignore non-zero $$$s$$$ values and simulate copying intervals in any order with a queue.

    You can use a set or union-find to find non-zeroes.

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

Zero idea about div2C and zero idea why my Div2D works(solved by guessing at brute force values)

Not an enjoyable contest.

Edit: My bad I should have read that the initial length of the string s in C can is 1. Stupid me.

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

    Frequency count all characters. Only one that is odd is answer.

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

    div2C is you either guess solution or you don't

    turns out the letter that occurs odd number of times (over all t's) is the solution.

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

      In that case , I wonder how so many AC's . For me Difficulty was , A < B < E < D < C .

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

        I could not understand the problem statement of E :(

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

          Yeah , that was one of the hardest things in E . I understood problem statement using Sample Testcase.
          Basically , you are given N nodes and M edges , each edge has a weight assigned to it . In each query you pass a string of length M , where for i'th index 0 represents the current edge is not present , whereas 1 represent current edge is present . Now each query returns you the sum of weight of the edges present in maximum spanning forest for the string you passed.

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

      But why??

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

        For any transformation (t1 -> t2), the character count increases by 1 for both LHS and RHS.

        Let's forget about the LHS of the first transformation first.

        For any character that is not present in the final string, it must have occurred at least an even number of times (first time on the RHS, second time on the LHS), since it's parity is 0 in the end.

        If it is present in the end, its parity is one, so add these characters to reset their parity to 0 (i.e. add the transformation "final_string" -> "").

        Finally, the only one that is present on LHS but not on the RHS is the original string (i.e. the only character with parity one).

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

      chinese lied us. they can't solve hard problems, they just guess the solutions.

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

      To me div2C looks like what I personally call "Wishful thinking" or what I think I saw, perhaps more generally, in a blog made by Mike Mirzayanov as "Bold hypothesis". You just really wish that you could ignore X. In this problem, the structure of the strings seems like the problematic part. So you just "hope" that you can ignore the structure (or the order of the characters) of the strings. Once I realised that, I reduced it to the counts and tried thinking mathematically of it. A bit of experience reminded me that if I have a bunch of ones that I either subtract or add in order to get zero, the number of ones has to be even...

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

    I think div2C was too pure lol.

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

how to solve div1 B ?

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

    first check if there is an odd number in the array, if there is then answer will be number of even numbers, because you can just add even number and an odd number and get odd number as a result, if there is no odd number then you have to create one, to created one you can should choose an even number that needs least divisions to become odd , once you get odd number then you can do the thing I mentioned above.

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

    First find the weights of all edges in m queries.

    Then, just use a similar idea as Kruskal's algorithm. Adding the ith edge with weight $$$w_i$$$ creates a cycle if and only if the value returned from the query after adding the ith edge < weight of the current spanning forest + $$$w_i$$$.

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

    sorry I replied for wrong problem

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

How to solve Div2 C?

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

    Let $$$count(c, s)$$$ be the count of a letter $$$c$$$ in $$$s$$$.

    If $$$t$$$ is given in the correct order, then for each $$$c$$$ that's not the initial letter,

    $$$\sum_{i = 1}^n (count(c, t_{2i}) - count(c, t_{2i - 1})) = count(c, s)$$$.

    Rearranging, we get

    $$$\sum_{i = 1}^{2n} count(c, t_i) - 2\sum_{i = 1}^n count(c, t_{2i - 1}) = count(c, s)$$$.

    This implies that the parity doesn't change for all letters except for the one you have started out with.

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

    For each lower case character, e.g. 'a', the total number of 'a' in all the input must be even except the initial character. You can transverse [a-z] to find the one only occur an odd number of times.

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

I think it was a very nice competition!! Thanks a lot!

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

Problem div1C was wonderful, congratulations to the authors.

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

weak pretests for div2A

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

Why x <= 2^30 instead of x < 2^30? :(

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

Wish I thought of 1546B - AquaMoon и украденная строка for today's div2C with enough time left during the contest, but alas, bricked B and kept burning time bouncing back to it...

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

Why was final string given in div 2c when it is was of no use??

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

c problem has very bad description see codeforces please see this

need to improve queue. clearity

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

    I'm sorry the description of div2.C is not so good, we will try our best to write better descriptions next time.

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

      Div2E's statement is still unclear, at least can you please update the statements now so that they can be understood easily by the ones who are/will be practicing?

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

        Could you please tell me what is described unclearly? I'll try to fix them.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +20 Vote: I do not like it
          Unclear Statement
          Issue
          What I understood from the problem statement:
          Suggestion
          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Thanks!

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

            I agree with the "Unclear statement". It took me quite some time to figure out what the author meant by it.

            It becomes difficult to understand lines this long...
            → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Can anybody tell the testcase for which my submission is failing ? https://mirror.codeforces.com/contest/1688/submission/159358654 Div2A

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

I even can not understand the Div.2 F

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

Only reason i figured out that A was by looking at Note for second test case :p.

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

Div1C is very hard for me, but quite interesting. I will upsolve later T.T

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

Happy Dragon Boat Festival to you all!

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

Pretests for D are very weak .

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

    Agreed, an obvious mistake in my programme wasn't shown by pretests, and my detla went from +150 to +7 :(

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

    Different participants got fst on different tests (as you can see in status). It's difficult to make strong pretests with limited number of tests.

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

Very fast editorial. Thank you!

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

I hated d2c until I solved it

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

WHATTTTT!!! Div2E was just kruskal? how couldn't i see it

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

Can anyone hack my submission on Div.1 D?

https://mirror.codeforces.com/contest/1687/submission/159399180

First,find $$$O(n+a_n)$$$ numbers that may be the answer; Random_shuffle the permutation,then one by one check if they are available in a query. When one number isn't available,then push it to the front of the permutation when dealing the rest queries — that makes most of the hacks of making only one number unavailable unsuccessful.

Can anyone find some hacks?

Thanks to the problem setter for not killing my code. ;)

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

    Hack mine as well 159406136

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

    Why the number of possible numbers is $$$O(n+a_n)$$$?

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

      There are two scenerios.

      1) all numbers are in the same range. In this case the answer should be $$$k^2-a_1$$$ , so there will be at most $$$O(\sqrt{maxans})$$$ numbers.

      2) not all numbers are in the same range. In this case there must excist $$$i$$$ and $$$k$$$ such that $$$a_i\le k(k+1)$$$ and $$$(k+1)^2\le a_{i+1}$$$, so $$$k\le a_i-a_{i-1}$$$, which means that there will be $$$O(\sum a_i-a_{i-1})=O(a_n)$$$ possible numbers in this case.

      Thus the total is roughly $$$O(a_n)$$$

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

I actually loved the problemset.

A can be messy if you solve it wrongly, but doesn't have to. B is rather easy interactive one. C is definitely from AtCoder Problem Generator (analyze given process and try to look for properties which might be useful), but seems more enjoyable than most of such problems, and as it's only one problem, that's perfectly fine and there are no problems with that. In D you can allow yourself for some randomization, if you feel that you do it right, which is always nice. In E you can do something without worrying too much about constants and just check with submission if it's correct. F I guess requires some knowledge (some fun with generating function stuff I guess?), and that's find for last problem.

Everything works good. The only problem is a lack of implementation-dependent-data-structure-like problems, but they doesn't have to appear every time and anyway it's a great way to go!

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

I really enjoyed Div1 A~D(I was working on E but failed). I felt every problem challenging when I was working on it, but found it brilliant after solving it. I'd say just focusing on the problems, this round is the best Div1 round recently. Thanks to the authors!

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

Div2E is easier than the observation needed to solve Div2C

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

    I mean I take some time at the beginning of the contest to think in Div2C and then skip it and solved Div2D then I return to div2C. I couldn't realize that I need to skip it again and solve Div2E lol

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

    I agree. Div2C is a great idea

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

piece of shit round

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

My first contest with >2500 performance!!

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

D1D statement:

"[Let] g(x) be the maximal square number not strictly less than x"

I think this kind of statement is unclear, especially given the range of English ability on this site. In particular, one I can see this being read is

$$$! (g(x) < x)$$$

However, this contradicts the example that $$$g(8) = 4$$$. Especially since you need to be able to read inequalities to understand the bounds on the problem statements, I think problems like this would be much clearer if stated using unambiguous mathematics. Something like "Let $$$g(x)$$$ be the largest positive integer where $$$g(x) \leq x$$$ and there is some integer $$$k$$$ such that $$$k^2 = g(x)$$$." What do you think?

Also, loved the contest. I will come back stronger.

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

    Sorry for the unclear statement, we'll try our best to do better next time. Thanks for your support!

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

    Agree. I think it is also fine to just use "at most" here.

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

    I read it exactly the way you said it could be misinterpreted lmao. I agree, it would be nice if it was stated symbolically, it removes possible confusion.

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

Was it only me or the statement for Div1B was really confusing ¯_(ツ)_/¯

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

Two last rounds, like in good old times:

If that's interesting, I find it pretty funny that I wouldn't call any of these fails "a bug".

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

    I believe this is "a curse"

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

    Unlucky! :(
    If you would have submitted your solution to E in C++20, it would have passed

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

      My skipped submission also was correct and was passing.

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

Question C is not correctly explained that things ruined the whole contest

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

Hello, in div2 C for test case: 1 2 z abcz ab abab

should not the answer be z? most submissions print c as an asnwer.

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

Is there any glitch in rating change? Many of my friend's rating didn't change till now. But my rating is changed.

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

Why didn't rating change for anyone under 8000th?

→ Reply
»
3 years ago, # |
← Rev. 23   Vote: I like it -28 Vote: I do not like it

It seems only my solution didn't pass pretests :( div2D?

I changed int to long long for n and k and it worked
worst pretests that I can saw

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

No spoiler hint for Div2D?

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

It seems that this contest is too Codeforces(in Chinese mind),which means solution(or the key idea) first.It will be much better if there would be more normal problems.

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

Hi MikeMirzayanov my rating is above 1400 but i haven't been promoted to specialist please check it.

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

    I'm went below 1400 after this contest and it still shows that i'm specialist

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

I couldn't even do task A. I'm suck.

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

    Don't lose heart. Keep in touch and you'll be able to solve it easily

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

Who can tell me why my friend passed the question in the contest but didn't get A rating change (not 0)? Another friend of mine checked question A 7 times but didn't get A rating change either. Who can tell me the scoring rules? thank you

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

I have noticed an interesting fact: the round was unrated for plenty of div2 participants. Does anyone know what's up?

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

    I think it's a bug, as another user pointed out people below a certain rank haven't been rated yet

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

Hi MikeMirzayanov, i became candidate master but the account's color still Blue And i see that no one change their color Please check it

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

MikeMirzayanov when will the bug be fixed of colour change?

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

There are some people in Div2 who didn't get their delta. Is it a bug?

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

Can somebody tell me the testcase at which my submission 159494268 for div2F fails?

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

Has anyone else noticed that Div2C (the troll parity problem) and Div2E (the Kruskal's problem) are both rated 1700, but Div2C got 1687 solves while Div2E got only 261 solves? I suspect that Div2E's low rating is caused by the overwhelming majority of Div1 getting it. In that case, wouldn't Div2C still have a lower rating than Div2E?

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

Can somebody explain how Div2E is done? I looked into a couple of solutions. I understood until the part they found the length of each track and sorted the tracks. After doing so, they iterated on tracks (shortest track first) and at each iteration, greedily checked whether the track belongs to the same forest as the shortest track. They always returned the 'value' of the forest with shortest track. This looks clearly wrong because a forest containing shortest track need not have a the least 'value'. I am definitely missing something. Any help will be appreciated.

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

    They are returning maximum value and not minimum. And if we iterate the sorted edges then you will find that if we add any edge at a particular instance, then if value is not equal to previous edges cost + current edge==> clearly implies that this has replaced a smaller edge for same connected forest.(hence we discard these edges). NOTE: jury is returning maximum value.

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

I am a newbie and I had secured a score of 726 but my ratings haven't been updated yet. Even that contest is not showing on my profile. Both of my codes were accepted and are still there on my submission page. Can anybody help?

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

    The Ranking change is still 8501 and there is no news now.

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

My ratings are still not updated does anyone knows why this is happening? And whom should I contact regarding this.

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

    Your rating is updated but with no change

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

      But I solved 3 question what about them.

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

      OKK So this means that for my 2700 rank the net change in my rating was 0.

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

My rating hasn't changed yet. What to do about it?

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

    It must have changed by now as I can see that everyone's rating and division is now correctly put up by codeforces.

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

Why you don't like the problem C in div2? It is not difficult at all!

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

stO hzr Orz

→ Reply