buffering's blog

Codeforces Global Round 26
By buffering, history, 7 months ago, In English

Hello, Codeforces!

We are pleased to announce Codeforces Global Round 26! Thanks to XTX Markets for supporting the initiative! In 2024, we are holding 4 such rounds. The series results will take into account the best 3 participations out of 4.

On Jun/09/2024 17:35 (Moscow time) we will host Codeforces Global Round 26.

Codeforces Global Round 26 marks the second round in the 2024 series of Codeforces Global Rounds. These rounds are open and rated for everyone.

The prizes for this round are as follows:

  • The top 30 participants will receive a t-shirt.
  • 20 t-shirts will be randomly distributed among participants ranked between 31 and 500, inclusive.

The prizes for the 4-round series in 2024:

  • In each round, the top-100 participants get points according to the table.
  • A participant's final score will be the sum of the points they earned in their 3 highest-placing rounds.
  • The top 20 participants across the series will receive sweatshirts and placement certificates.

We extend our gratitude to XTX Markets for supporting the global rounds initiative in 2024!

The problems were written and prepared by null_awe, flamestorm, le0n, and buffering.

We would also like to thank:

Round Information:

  • Duration: $$$3$$$ hours
  • Number of problems: $$$8$$$ problems
  • Score distribution:
    $$$500 - 750 - (750 + 1250) - 2500 - 3000 - 3000 - 4000 - 5000$$$

We eagerly anticipate your participation!

UPD: Editorial! https://mirror.codeforces.com/blog/entry/130252

UPD2:

Winners!
1. tourist
2. jiangly
3. Benq
4. jqdai0815
5. Nachia

First Solves
A: Benq
B: Thienu
C1: nwn
C2: Benq
D: Be_dos
E: Tom66
F: kiwihadron
G: tourist
H: rainboy

Announcement of Codeforces Global Round 26
  • Vote: I like it
  • +595
  • Vote: I do not like it

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

Woah!! Global Round again... Let's Go!

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

Expect great and unique problems! Wish everyone good luck!

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

I expect to achieve pupil rank, good luck to everyone.

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

as the #1 buffering fan and a testuwuer, this round is fire asf

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

As a tester, I really enjoyed the problems! Also, Ritwin orz

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

As a tester, this round goes hard

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

why (1000 + 1000 ) ?

you mean that there are c1 and c2 ?

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

As there is no cyan tester, I hope that I can get out of cyan to blue!

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

    I already made it out of cyan but after rating rollbacks hope this time before rating roll back.

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

As a problem, I liked the testers.

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

    As a global round, I hope I will enjoy the contestant

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

me when i see arul hii arul

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

i LOVE Global rounds hoping in another -150!!

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

As a tester, I tested the round

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

flamestorm Orz!

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

flamestorm orz!

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

CP > IND vs PAK. :D

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hahaha!

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

CP(pretest passed) >>> Any other Enjoyment

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

The round feels more solid with sum involved as a tester.

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

hoping for + 3 contribution :3

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How are Global Rounds different from any other div2 and div3's?

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

    Everyone can participate officially and it will be rated for everyone

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

score distribution changed!

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

What's your choice Ind vs Pak or this contest?

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    Ind vs Pak !! after 2 yrs T-20 World Cup ...

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

    finish the first 4 problems as soon as I can then go back to watching the match :)

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this contest suitable for beginners also?

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is it a rated contest?

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

8 questions! I hope there is something for me as well.

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

Dragon Boat Festival Health！

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will try to improve and upsolve questions from this round, best of luck everyone!!!

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

Speedforces

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm in

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck !!!

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

the number of participants are going to decrease because of IND VS PAK match

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

Will there be fewer contests because of Euro 2024?

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

gl & hf for everyone!

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why do E and F have the same score?

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

as a contestant i hope to solve the problems

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

Hoping to become Expert

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

English or Spanish?

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

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

why is cry crying (crying emojis)

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

let's go! good luck to everyone

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

all the best guys

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is this contest is rated?

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

I hope I will become pupil (if I got +209 delta and become specialist it will also be not bad lol :')

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

Literally 1984

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

Nineteen Eighty Fources

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

Literally 1434 (I lost the game)

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

ABC1C2 speedforces

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I was not prepared for this 'Dashboard'!

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

reading statement of E be like

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

I think I've caught a group of cheating noobs spreading wrong solution of B and giving +100 points to lucky participants.

Hit them hard!
→ Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

Animated Video editorial for problems [A-C2]:

https://www.youtube.com/watch?v=hS8Z3k57f6Q

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

    How could you do the animation? I'm really curious about that a long time ago, because I want to use that to draw the explanation too.

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

      I use the library Manim and the source code for this video and my other stuff can be found on my github although there are probably better people to learn manim from as my code is messy.

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

        Thanks a lot. I have to find it for a long time.

        P/S: Firstly I wonder why you could do the animation so fast in the contest, and at last I find out that you are one of the tester, which is make sense :v.

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

    wow that's so cool! good work sir

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

    Nice video. But why your voice is slowed? Is it your natural voice or it's being slowed?

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

      I think a mix a both, ig I usually talk slower than average but this video was worse because I had no time to rerecord parts that didn't sound good

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

Can the authors tell us what is the secret of 1984 ?

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

    George Orwell has never been as strong as he is today!

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

    I have been told that 1984 is when you get arrested for using the display toilets in home depot

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

In E, the answer is n- min vertex cover + 0/1 (1 if we have a node of deg 1 in min vertex cover), right? if yes, how to handle the 2nd part?

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

    You can use $$$f_{i,0/1,0/1}$$$ represent in $$$i$$$'s subtree, whether $$$i$$$ is chosen or not, and whether we have choose at least one leaf or not. The minimal cost for this case.

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

      Rerooting technique with the original dp works too.

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

        Could you please tell me what technique are you refereeing to?

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

          This is the topic. We basically calculate the classic min vertex cover dp, then do a second dfs and change dp's so that when we go from vertex v->u, the dp value's are as if u is the root. When we come back we do the same thing too. This might not be possible with certain tree dp's but in this case it is.

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

      Oh right, i am dumb, I kept trying to get a relation for $$$f_{i,0/1}$$$ where i is the subtree, and whether we have choose at least one leaf or not.

      → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It's a bit difficult for me. But these problems look very interesting!

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C2 hint anyone? :)

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

    Solve C1 by DP, and C2 is just a counting version of it.

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

      yeah i solved c1 with dp but could not solce c2, can you tell me how to do it ?

      void solve(){ cin >> n; vector v(n+1); vector dp(n+1,0); vector dx(n+1,0); f0r(i,1,n+1)cin>>v[i]; f0r(i,1,n+1){ dx[i]=dx[i-1]+v[i]; dp[i]=max(dp[i-1]+v[i],abs(dx[i-1]+v[i])); } cout<<dp[n]<<endl; }

      thanks a lot ;)

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

        Next time, please format your code properly before commenting to ensure readability. ;)

        From what I'm understanding here, in C1 you are keeping $$$dp_i$$$ as the maximum value obtainable, and $$$dx_i$$$ being the minimum one.

        We can add $$$dpc_i$$$ and $$$dxc_i$$$ to supply this process with counting. At first, $$$dpc_0 = dxc_0 = 1$$$. For any $$$i > 0$$$:

        • If $$$dx_i \ge 0$$$, $$$dxc_i = 2 \cdot dxc_{i-1}$$$, as $$$|dx_i| = dx_i$$$. Otherwise, $$$dxc_i = dxc_{i-1}$$$.
        • For $$$dp_i$$$, notice that we have two different pathways: one from old $$$dx_{i-1}$$$ and one from old $$$dp_{i-1}$$$. We should combine the number of ways for both pathways if and only if $$$dp_{i-1} \ne dx_{i-1}$$$ (two pathways should have been separated before) and $$$|dx_{i-1} + v_i| = dp_{i-1} + v_i$$$ (they should yield the same $$$dp_i$$$ value). If not, pick the pathway that would result in $$$dp_i$$$, or pick any of them if $$$dx_{i-1} = dp_{i-1}$$$.
        • If picking $$$dx_{i-1}$$$ for $$$dp_i$$$, $$$dpc_i = dxc_{i-1}$$$ or $$$dpc_i = 2 \cdot dxc_{i-1}$$$, depending on whether $$$dx_{i-1} + v_i \ge 0$$$.
        • Similarly, if picking $$$dp_{i-1}$$$ for $$$dp_i$$$, $$$dpc_i = dpc_{i-1}$$$ or $$$dpc_i = 2 \cdot dpc_{i-1}$$$.

        Sorry for the very late reply, it was midnight at my place when you asked this, and I wasn't really mentally sane to read and parse unformatted code. Now that it's morning time here and I'm a bit more conscious that I could actually read you well enough to provide an explanation catering to your own codes.

        Code references (upsolved, I overcomplicated myself in-contest so I won't show you those), in case my words were overloading:

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

          Oh right! Thank you very much for explaining it to me, and sorry for the unformatted code, I will make sure to format it correct the next time ;)

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

    in reverse order calc variants to get current value from previous

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for this round!)

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i'm too good at writing buggy code spent 2hr for simple hashing implementation :)

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

How to solve D?

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

    Ignore all preceding a in the string. We'll get to that later, and we'll call the new string after deleting that prefix ss. It's certain that any string being the answer must be a prefix of ss (can have a few a preceeding it, we'll get to that).

    Iterate the prefixes in descending order, for each length, add all position in ss that matches the prefix — this part can be sped up using Z-Algorithm. Brute force from the start of ss to end to see if the pattern covers the string fully (and only leaving stray a at most). If not possible, ignore. Otherwise, denote $$$k$$$ as the maximum number of a to precede the patterns without sidestepping on each other, add $$$k+1$$$ to answer. $$$k$$$ can be calculated through the bruteforce, and it's better to calculate each value of maximum preceeding a count of each index before starting this step.

    Time complexity being roughly $$$\mathcal{O}(A \cdot n \log(n))$$$, with $$$A$$$ being the complexity of whatever DS you use to keep track of the indexes (I used set so one more $$$\log(n)$$$ into the mix, still works).

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

      Oh hell

      So smart!!!

      Thanks a lot

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

        I had a different approach from the solution above, it seems easier to me, maybe it will be useful:

        look at all not 'a' — let's say there are k of them. You will cover them with t-strings. So each t-string contains some divisor of k non-'a' letters. Iterate over all divisors d and check if strings

        0-th non-'a' -> (d- 1)th non-'a',

        dth -> (2*d — 1)th,

        (2*d)th -> (3*d — 1)th are the same (I used hashing)

        If so, we have found a good t, but it can be extended by additional a's on the left and right — this needs to be carefully calculated using amounts of a to the left from first t, to the right from last and between ts.

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

          Yeah its easier but a bit slower

          Nice aproach tho!

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

      I had a more different approach, you can find the count of all char except $$$a$$$, now you just need to find the common divisor of the counts of all characters except $$$a$$$, iterate on the string for each of these common divisors and then find out greedily if we can divide the strings into $$$a$$$ and a string $$$t$$$ such that count of each char except a in $$$t$$$ is $$${count/divisor}$$$ where $$$t$$$ has no preceding and trailing $$$a$$$.

      Now, Replace the substrings equal to $$$t$$$ with the character t and you have a string consisting of $$$a$$$ and $$$t$$$ only. We need to distribute the $$$a$$$'s into $$$t$$$. Time complexity is $$$O(A*n^{4/3})$$$.

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

        Woah, I actually thought of this but gave up and did the systematic one above coz' that was the easiest way to think and not break my brain down in the process. Glad to see that the one I gave up on still worked nicely :D

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

      Can you tell why hashing with binary search does not work:

      Fix the first not equal to 'a' character and its position L and iterate over the right border R of a substring that has only a's beside it then for each right border binary search the left border of extended substring that now has some a's as a prefix: inside the binary search check if it is possible to divide s into substrings by iterating over the positions j of a first not equal to 'a' characters and checking if the substring that starts with j has more or equal a's beside it than binary searched number of a's and if the substring that starts with j and has a length R-L+1 coincides with the substring s[L:R] (this can be done with hashing), after all j's are considered delete all j's that are not the starting positions of some strings in the partition.

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

    Store the indices of all character in $$$s$$$ which is != 'a' in an array $$$v$$$. Fix the number of character we will use to form a substring in $$$v$$$, let's say it is $$$k$$$. Then the substring formed by $$$v_1, v_2, ..., v_k$$$ and $$$v_{k + 1}, v_{k + 1}, ..., v_{2 * k}$$$ and ... must be the same.

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

    all possible $$$t$$$ will be of the form $$$aaax...$$$
    where $$$x$$$ is the first non $$$'a'$$$ character
    let pos be the first position where $$$x$$$ occurs iterate over all possible length $$$len$$$
    let $$$t \ = \ s[pos..pos \ + len \ - \ 1]$$$ check if t is valid or not with hashing
    if $$$t$$$ is valid $$$ans \ += \ 1 \ + \ no. \ 'a' \ can \ be \ placed \ before \ t$$$ '

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

tasks were good btw

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

best D i have seen, orz!!

→ Reply
»
6 months ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

C2 almost killed me, spending nearly 2 hours on it. Anyway, I think the problem in this round is pretty nice.

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This contest may not have been my best performance, but I enjoyed it a lot.

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is problem E , pseudo independent set?

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

    for every leaf, delete it and solve biggest independent set, answer is the maximum value plus 1. idk why it works.

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

      Here is what I thought: ignoring the very first root, no other subsequent roots can be leaves. (I don't count an isolated remaining vertex at the end as a root.) If a vertex (v) becomes a leaf, then clearly all its neighbors except one would have withdrawn edges from it by becoming roots and attaching that edge to the next upcoming root. This implies that no two edge endpoints can be leaves simultaneously (ignoring the first root, which can be a leaf, and its neighbor could also be made a leaf).

      → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

On D I used prefix function for the initial string ignoring (if existing) a prefix just of "a". Now, a prefix to be a good string need to appear in the string such that all non "a" characters are used. This is an easy check using a frequency array but the remaining problem is how to identify good strings that starts with "a". I brute forced this part cause I did not find any good solution on this. I am close enough to the real answer?

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

    very close

    Spoiler
    → Reply
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I understand now. I think my brute force failed when the G contains some "a" at the end and I am also considering those "a" as the new prefix for next good string. Thank you!

      → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping to get editorials that are easy to understand.Many a times these codeforces people give stupid non understandable editiorials

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what is wrong in this code https://mirror.codeforces.com/contest/1984/submission/264959968 i'm not able to find the error

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Dpforces >>>>

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

I nearly got F and G :(

My solution for G uses roughly $$$\frac12n^2$$$ operations, and I will put my submission here later.

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

    Judge solution also uses around $$$\frac{1}{2}n^2$$$ operations most of the time, and I don't think it goes over $$$n^2$$$ for any of the tests.

    We made limit $$$5n^2$$$ because we didn't think it would allow unintended solutions, and it made it slightly more flexible for contestants.

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

how to do C1 ?

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Actually every task is very cute and contains something new. But I feel B and D are difficult for it's scoring or position.(And actually I go panic during the round, oops)
Anyway thanks for good problems!

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

    I actually spent like 30 minutes panicking at D, heh. I kept rolling my chairs thinking "can this bruteforce of all string prefixes TLE?" and then completely forgot that sum of reciprocal would only growth at $$$n \log n$$$ rate instead of $$$n^2$$$, hehe.....

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

    B made me panic as well

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

Fantastic contest! Enjoyed solving A, B, C1, C2 for 3 hours!

Thanks a lot for the round null_awe flamestorm le0n buffering and all testers!

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

cheatforces

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

The B from this round will haunt me forever. I took almost one hour to solve it, haven't felt so stupid in a long time. C was such a cool problem even though I only managed to solve C1, dp is not really my strength.

Thanks for the problems and I hope everyone did well.

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

    I know right, B was a nightmare! It took too long to realize that if zero appears within x (not in the last digit), then there's no answer.

    I didn't do C1 with dp, but instead applying "Option 2" ONLY whenever the current sum is most negative; otherwise, apply "Option 1"

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

      yeah same I took too long to figure out the condition with zero. I did a pretty weird thing on C1:

      for(int i=1; i<=n; i++)
{
      auxmax=maax;
      maax=max(maax+a[i], max(abs(miin+a[i]), abs(maax+a[i])));
      miin=min(miin+a[i], min(abs(miin+a[i]), abs(auxmax+a[i])));
}

      and I was very surprised that it worked xd. C2 was a bit too much for me and I didn't really have time to solve it because of B.

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

    Me too buddy, me too. Shit happens, don't stop believing in yourself!

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

      wow, How did u thought and wrote that C2 in 13 minutes. Godly recovery of the contest 😲

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

      thanks! It's not too bad, I only lost a few points so I'm good, at least I can do Div. 4 on Tuesday :).

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

For problem E. Why is the answer 6 for example 4. I figured the answer is 5. If you pick v to be node 1, then you can shuffle 10-6-4 and get 5 leaf nodes.

I think I still don't understand the problem statement of problem E actually. So it is saying repeat step 1 and 2 recursively I believe for the subtrees. But I still don't know how to get 6 from the 4th example.

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

Problem G: https://mirror.codeforces.com/gym/103414/problem/L

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good tasks, enjoyed solving C1 and C2 (I solved them without DP). Went blank on B, hence implemented a DP solution there.

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

On problem D, how is the answer to the string "abbaaaabbb" 3? I understand that t="b" and t="abbaaaabbb" work, but I can't figure out the third string.

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

    This was a really common question asked, "bbaaaabbb" also works.

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

      Thank you

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

      Actually I was stuck thinking about the same testcase. Eventually after a lot of thinking (in hindsight I have no idea why I couldn't spot it immediately) I got why it was 3. But I was considering asking you problem setters during contest.

      This makes me wonder, is it allowed to answer such doubts during contests? To understand why the answer for the samples is such? I usually don't know what can be or what can't be answered and don't wish to waste the problem setters' or my time by asking such questions and then waiting for the answer.

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

        We are not allowed to answer such questions (unless the statement is unclear and it's our fault). We received around 50 questions about that specific test case and answered all of them with "check carefully".

        → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Cool round!

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

Being stuck in C1, then turn to D, then fail many times until 2 hours passed :(

Then I discovered that C1 and C2's implementation is way more easy than D :(

Luckily a master in my room made some weak hashes, and only changed his hash into double hash, then multi-hash, all of them had fixed bases and modulos, and I gained extra +250 points :)

But still to have a negative delta :(

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

    can you take help of others in your room? I dont understand how it works can you explain?

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

      Er, it doesn't mean that the master made weak hashes delibrately to give me points. I locked my D problem so I can see their solution to D, and then I can make hacks.

      Maybe he just didn't know the importance of randomizing his hashes so he made mistakes again and again, which enabled me to gain points many times. In the end he still couldn't pass D because I was hacking him.

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

upd: the above seems the reason of following

My curiosity, but are there any antihash test in D originally or is it caused by hacking? It seems many D gets FST strangely.

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

is my observation correct for C-1 you only have to use operation of type-2 once or never?

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

    yeah But how you observe? could u explain me yet i didn't understand

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

Never understood problem statement of E in the competition.

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

Most of B's hacked submissions have several identical but illogical pieces of code. Is that really a coincidence?

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

    somebody leaked a solution which included two bugs (checking if the sum of digits was 35, checking if length of number was 10). most who copied did not realize that these were incorrect which resulted in all the FSTs and hacks.

    hopefully this is a lesson to not cheat!

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

      All these guys need to be perma banned. Cheating is very annoying for those of us working hard for our rating.

      → Reply
»
6 months ago, # |
← Rev. 3   Vote: I like it -11 Vote: I do not like it

In D question ,I used p=31 for hashing in solution 264942064 and I got wrong answer on testcase 29 and then I only change the value of p to 27 and It get accepted 264969257,

As you can see in above submission.What is the mistake in this?

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

    Does anything can be done about it?

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

    Most probably it is an intentional hack. I can advise you to use a random p next time.

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
      ← Rev. 3   Vote: I like it -60 Vote: I do not like it

      I took the value 31 from cp algo article

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

        No.

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

        Sadly no. I hope you could learn that in an environment like Codeforces where exploiting is possible, if you wanted a heuristic method to pass, you should at least cover its constants well so that it would not be reverse engineered for counter-testcase production.

        Original comment up above already showed you one way of doing so. You could also randomize and/or add more prime modulus into the hashing.

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

    Hacked!

    You should randomize your hash, random modulos or bases are all OK, simply changing anothor fixed base can't prevent you from being hacked.

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

rainboy solved problem H first

→ Reply
»
6 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Problem 'H' first solved ecnerwala ?

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by buffering (previous revision, new revision, compare).

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Whoever has leaked the solution to B, must have intentionally put a bug in the code so that everybody gets hacked.

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

I thought that as long as none of the submitted problems passes the pretest 1 (samples), the round will not be rated.

Did I misunderstand, or has this changed? (I just lost 166 points because I left the round after a few minutes...)

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

    Relax. Why you worried about the rating changes?

    Spoiler
    → Reply
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are right, I don't care much about the points, but still want to understand the rules. Now I learned.

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

    It has always been like this and nothing has changed. You should have absolutely no submission to be unrated.

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i didn't manage to debug my D solution in time, now i finally got AC, and want to understand why it works. After cutting the a-parts from the sides, i am looking only at prefixes, that have at least one symbol of each non-a type that is in the string and also checking for all of them, that their number in prefix is a divisor of total number, and if it's all satisfied, i just check for O(n) with z-func etc. Is it true that i check no more than O(√n) prefixes?

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the problem D, why does 'abbaaaabbb' have 3 valid string t?

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

    Valid strings for $$$t$$$ are abbaaaabbb (obviously), b (the rest are just a) and bbaaaabbb (valid partition being a + bbaaaabbb = abbaaaabbb, notice that $$$t$$$ only needs to exist at least one, not necessarily at the beginning of the partition).

    Took me a while there during contest as well.

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

I really like problem H, it is possibly the best geometry problem I've ever seen.

However, I do think G is a bit implementation heavy, and the difficulty gap between F and G is a bit too big. Was this intended or the writers overestimated the difficulty of problem F?

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

    We overestimated problem H (see the rating predictions), maybe it would have made sense to give G and H the same amount of points.

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

      (This is not a complaint) You underestimated G more than you overestimated H, so the F G gap became large

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

        Yes, I think G was a bit too hard for its position (or maybe F was too easy). We were considering having to solve F in n log n (as a subtask or just on its own), maybe this would have helped -- but it would have also increased implementation.

        → Reply
        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it -19 Vote: I do not like it

          i dont think adding a mostly implementation subtask helps, like difficulty is always a secondary concern and quality should be primary.

          I wasnt complaining, just informing Scrasse that he got the wrong issue. H wasnt underrated by a lot(it shows 3250 on predictor) and 7 AKs is very reasonable. Nice contest

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

          Why would you be aware of a somewhat interesting optimization and not set it for F :(. Hate when authors only leave the iq test and not the more interesting part

          Overall this was one of better recent contests to me tho :)

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

      From the predictions and the actual difficulties, it seems that G was underestimated too much. If G was indeed as 3000 rating problem, that would be much more balanced.

      Just curious why all setters and testers think G is that easy. All my friends around my level agreed that G should be at least of difficulty around 3200 to 3300.

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

        We initially solved this problem for odd $$$n$$$ and extended it for even, so it might have been that for the setters it was easier to extend the logical line of reasoning for the solution. I think more testers could have been beneficial (at least higher rated ones) to get a better sense of G, we received some comments about hard implementation but nothing that made us worried about the difficulty. We’ll try to get a more wide sense of difficulties next time.

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

        I was unable to solve E or F but found G pretty easy.

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

264891491 264900499

How this solutions is equal??

it's same idea but not the same code

It is normal to have similar ideas on the same problem

and if i cheat C1 from this person why I didn't cheat C2 and D????

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello dear Codeforces and MikeMirzayanov. I want to tell you that I got a message where it was said

Внимание!

Ваше решение 264929515 по задаче 1984B значительным образом совпадает с решениями других участников и находится в группе одинаковых решений 228r1A67J8/264902138, npan/264902312, kushagramaster2004/264903471, TinyHunter01/264904007, sayedul/264904177, Nishant9058/264904344, -Gogeta-/264906759, YoussefAmr_/264906843, Farhan_Tahsin/264906979, -Sentinel_Prime-/264907922, shaik_mohisina/264908032, coderSnehasish/264908090, ritik21413/264908173, 22501a1203/264908208, CodeNomad001/264909184, _back_dated_/264909465, Invincible_RYOMEN_SUKUNA/264909854, Shaolin_Shark/264910691, imh10045.21/264910955, nguyenhongnam207/264912803, Shubhi257/264913119, f20220118/264913123, codehero/264913130, saturina/264913442, MohdAftab011/264914088, rutul_bhosale/264914093, Yuvansh_0211/264914203, real_Cheri_Cheri_lady/264914460, Thunder_strom007/264914500, kavya020805/264914593, maithili31/264914756, Kliver_07/264914790, anand_kunwar_027/264915051, no_p/264915197, epicman_06/264915351, shukla_01/264915521, kavyachauhan_13/264915666, -Absam-/264915852, -shreyash_d_coder-/264915884, omanand2100/264915888, Chandan_mehra94/264915894, jprrrrr/264916041, Colin_Liu/264916057, hemlatasachin/264916167, ayushsinge2027a8975/264916270, whaleeeee./264916346, wew123/264916434, FrugalBoy/264916884, sancxo./264917114, CodeMonsterShu/264917268, Sleepydog/264917631, amaan328/264917638, hesky/264917848, jainlakshit/264917979, shashikumar_tony/264918069, iammrhrr/264918225, booty_eater_69/264918258, snamandeep40/264918397, Neogeek/264918524, mittalyas1234/264918584, Ryuk_01/264918596, __Midoriya__/264918820, Harshil_12/264918863, NemesisX99/264918909, amrendrakr/264919143, Tejas_Panchal21/264919229, gautam_0001/264919288, shovonisnewbie/264919535, big_foot05/264919705, abnafisa/264920027, devatraj/264920064, vedant_agarwal/264920078, Forget26/264920348, kombat__b/264920594, sanketchopade777/264920690, exquisite27/264920988, pbikram005/264921113, sohag_cse07/264921129, Ai_Code/264921298, mutitest/264921649, nayasha434/264921732, tusharsingla63114/264921871, baiganin/264922035, vishnujha10/264922223, Momhad_Faraz/264922379, Ashish_Jha_10/264922408, moh_k_35/264922743, pratham.programming7/264922893, Chirag_Agrawal45/264924017, _unknown_guy/264924098, TungAnh2008/264924792, Aditya_1735/264924831, 22501a4432/264925043, RAHMAN_misbahur/264925334, redflagpewpew/264925368, tanu1377/264925459, ajay.16/264925720, arian71/264926206, iitiantejashvi/264926223, keasar/264927413, Anaswastaken/264927737, raushanahir0311/264927745, akkuu04/264927858, Shalabh2002/264927893, maykkkk/264928106, SARVANII/264928296, maxvin32/264928508, joelmanohar/264928565, One_piece_is_real_26/264928566, prabalminotra1/264929361, akshay07k/264929398, ritik85/264929428, hackstar/264929515, Shubhamyadav23516/264929650, codewithyogesh/264930749, deepak0003/264930794, r6mez/264931068, abhi_mishra/264931530, navakanth/264931543, blisterfalcon/264931584, CodeAlpha07/264931774, rakibul-wdp/264932350, pk_prakash/264932757, Piyush82525/264933298, syedfaraz173/264933747, harshie_/264934776, ultralegend/264934976, manasagrawal326/264935314, Mr_ADP/264935555, UTKARSH0192/264935712, md_asifuzzaman_shanto/264936136, anand.7/264936326, Sapihahaha/264936441, Justadi698/264936500, ayush.d/264936559, Ballakari_Sucharitha/264936621, kaushalanant02/264936623, MIG25/264936685, Adhirajg22/264936924, dushyantxo/264937166, VYash/264938355, .sempai/264938541, mkrn123/264938786, DarkHome/264939208, amanpandey_09/264940104, M.A.Kabir/264940496, MR_Omkar967/264941569, Abbashaider/264941627, abhiramaddanki/264942033, ricky16x/264942635, Cpdhamp_Hg/264942913, ayuxh_11/264942933, vris/264943140, phoenixxx01/264943597, abhinav789/264943802, rohitverma017/264944030, sparsh19.gupta/264944119, K4LIBRE/264944549, Phoenix31/264945065, its_me_ganesh/264945642, sanchay_15/264945713, mani_pranshu/264946312, prakalpmanav1711/264947985, maverick_2003/264948615, roorkeeboy/264948644, Ammozon/264948839, aryan_me/264949033, errorhandling/264949305, Vidhan0527/264949837, namangautam172/264950792, coder_vicky/264951022, srivastavpranjal2/264952069, its_Pegasus/264952552, G.K.T/264952631, omjoshi7206/264954438, ankitsingh1221/264954441, jamilahmed9500/264954483, Gyanendu02/264955759, Moe.Awad/264956257, abdmaamun1/264956673, sriso/264958383, rajarora2277/264958421, Kirtan007/264958565, nickname0/264958585, SnehilK/264958890, 2200030517/264959181, Vudatala_Sravanti/264959325, Tanvir_Shihab_/264960753, roy_101/264961642, KraKen15/264961942, sakyasekhar/264962342, 3rdSS/264962432. Такое совпадение является явным нарушением правил. Отметим, что непреднамеренное утечка тоже является нарушением. Например, не следует пользоваться ideone.com с настройками по умолчанию (публичным доступом к вашему коду). Если вы имеете неоспоримые доказательства, что совпадение произошло по причине использования общего источника, опубликованного до соревнования, то напишите комментарий к посту о раунде со всеми деталями. Подробнее можно прочитать по ссылке http://mirror.codeforces.com/blog/entry/8790. Такое нарушение правил может являться основанием для блокировки вашего аккаунта или других штрафных санкций. В случае повторения нарушений, ваш аккаунт может быть заблокирован.

But I don't know one of them and task B was easy. I mean 8532 people solved task B, there can be solutions that are similar to each other. I want you to check my code again please. Check everything that you know, please!

Thanks you in advance!

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

    Seems quite same: 264929515 264902138

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

      Yes it seems quite same, but I wrote it myself. I can prove you with everything. I don't know either of them. And there can be a reason when I blocked my solution. After someone in my room could block his solution, and just shared or gave my code to others, because he knows that if he will share his code his solution can be ignored.

      Please check this! I think you comprehended me, so thanks in advance!

      → Reply
»
6 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

.

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

Appealing for a review on https://mirror.codeforces.com/contest/1984/submission/264889510 and https://mirror.codeforces.com/contest/1984/submission/264917529 . The only matching parts are a for loop from 1 to n — 1 and the use of intitializer_list variants of std::min and std::max (which I think is pretty usual for this case). I did not post this solution anywhere during the contest and I have not copied it from somewhere else either.

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

I was trying to login to my cf account that is kxhitz. But it doesn't login then i commented on the last contest then I got to know by a cf candidate informed me that my account has been banned. But I haven't cheated anyone's code in any contest. I have written the code by myself in every contest I had given till now. Even Sir I haven't received any warning message on cf account or on my registered gmail id.

Please reopen my account so that i can participate on further contests and also practice the questions.

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

Your thinking process in extremely slow

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

not bad!

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

null_awe, buffering, were the winners of t-shirts announced?

→ Reply