buffering's blog

Codeforces Global Round 26
By buffering, history, 11 days 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://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
  • +592
  • Vote: I do not like it

»
11 days ago, # |
  Vote: I like it +30 Vote: I do not like it

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

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

Expect great and unique problems! Wish everyone good luck!

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

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

→ Reply
»
11 days 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
»
11 days ago, # |
  Vote: I like it +26 Vote: I do not like it

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

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

As a tester, this round goes hard

→ Reply
»
11 days 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
»
11 days 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
  • »
    »
    11 days 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
»
11 days ago, # |
  Vote: I like it +122 Vote: I do not like it

As a problem, I liked the testers.

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

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

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

me when i see arul hii arul

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

i LOVE Global rounds hoping in another -150!!

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

As a tester, I tested the round

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

flamestorm Orz!

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

flamestorm orz!

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

CP > IND vs PAK. :D

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hahaha!

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

CP(pretest passed) >>> Any other Enjoyment

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

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

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

hoping for + 3 contribution :3

→ Reply
»
10 days 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
  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Everyone can participate officially and it will be rated for everyone

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

score distribution changed!

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

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

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this contest suitable for beginners also?

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

is it a rated contest?

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

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

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

Dragon Boat Festival Health！

→ Reply
»
9 days 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
»
9 days ago, # |
  Vote: I like it -11 Vote: I do not like it

Speedforces

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm in

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck !!!

→ Reply
»
9 days 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
»
9 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Will there be fewer contests because of Euro 2024?

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

gl & hf for everyone!

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why do E and F have the same score?

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

as a contestant i hope to solve the problems

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

Hoping to become Expert

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

English or Spanish?

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

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

why is cry crying (crying emojis)

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

let's go! good luck to everyone

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

all the best guys

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

is this contest is rated?

→ Reply
»
9 days 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
»
9 days ago, # |
  Vote: I like it +44 Vote: I do not like it

Literally 1984

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

Nineteen Eighty Fources

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

Literally 1434 (I lost the game)

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

ABC1C2 speedforces

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I was not prepared for this 'Dashboard'!

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

reading statement of E be like

→ Reply
»
9 days 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
»
9 days 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
  • »
    »
    9 days 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
    • »
      »
      »
      9 days 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
      • »
        »
        »
        »
        9 days 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
  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    wow that's so cool! good work sir

    → Reply
  • »
    »
    9 days 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
    • »
      »
      »
      9 days 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
»
9 days ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

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

    → Reply
  • »
    »
    9 days 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
»
9 days 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
  • »
    »
    9 days 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
    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Rerooting technique with the original dp works too.

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

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

        → Reply
        • »
          »
          »
          »
          »
          9 days 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
    • »
      »
      »
      9 days 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
»
9 days 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
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

C2 hint anyone? :)

→ Reply
  • »
    »
    9 days 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
    • »
      »
      »
      9 days 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
      • »
        »
        »
        »
        8 days 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
        • »
          »
          »
          »
          »
          8 days 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
  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    in reverse order calc variants to get current value from previous

    → Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for this round!)

→ Reply
»
9 days 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
»
9 days ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve D?

→ Reply
  • »
    »
    9 days 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
    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Oh hell

      So smart!!!

      Thanks a lot

      → Reply
      • »
        »
        »
        »
        9 days 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
        • »
          »
          »
          »
          »
          9 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah its easier but a bit slower

          Nice aproach tho!

          → Reply
    • »
      »
      »
      9 days 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
      • »
        »
        »
        »
        9 days 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
    • »
      »
      »
      9 days 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
  • »
    »
    9 days 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
  • »
    »
    9 days 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
»
9 days ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

tasks were good btw

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

best D i have seen, orz!!

→ Reply
»
9 days 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
»
9 days 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
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

is problem E , pseudo independent set?

→ Reply
  • »
    »
    9 days 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
    • »
      »
      »
      9 days 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
»
9 days 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
  • »
    »
    9 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    very close

    Spoiler
    → Reply
    • »
      »
      »
      9 days 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
»
9 days 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
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Dpforces >>>>

→ Reply
»
9 days 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
  • »
    »
    9 days 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
»
9 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

how to do C1 ?

→ Reply
»
9 days 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
  • »
    »
    9 days 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
  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    B made me panic as well

    → Reply
»
9 days 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
»
9 days ago, # |
  Vote: I like it +3 Vote: I do not like it

cheatforces

→ Reply
»
9 days 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
  • »
    »
    9 days 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
    • »
      »
      »
      9 days 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
  • »
    »
    9 days 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
    • »
      »
      »
      9 days 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
    • »
      »
      »
      9 days 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
»
9 days 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
»
9 days ago, # |
  Vote: I like it +123 Vote: I do not like it

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

→ Reply
»
9 days 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
»
9 days 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
  • »
    »
    9 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

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

      Thank you

      → Reply
    • »
      »
      »
      9 days 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
      • »
        »
        »
        »
        9 days 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
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Cool round!

→ Reply
»
9 days 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
  • »
    »
    9 days 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
    • »
      »
      »
      9 days 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
»
9 days 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
»
9 days 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
  • »
    »
    8 days 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
»
9 days ago, # |
  Vote: I like it +5 Vote: I do not like it

Never understood problem statement of E in the competition.

→ Reply
»
9 days 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
  • »
    »
    9 days 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
    • »
      »
      »
      9 days 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
»
9 days ago, # |
← Rev. 2   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 ?,If it is just a coincidence, the I request codeforces to remove testcase 29

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

    Does anything can be done about it?

    → Reply
  • »
    »
    9 days 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
    • »
      »
      »
      9 days ago, # ^ |
      ← Rev. 2   Vote: I like it -60 Vote: I do not like it

      Can't codeforces can remove the testcase 29, I could become CM this time.I took the value 31 from cp algo article

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

        No.

        → Reply
      • »
        »
        »
        »
        8 days 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
  • »
    »
    8 days 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
»
9 days ago, # |
  Vote: I like it +7 Vote: I do not like it

rainboy solved problem H first

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

Problem 'H' first solved ecnerwala ?

→ Reply
»
9 days 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
»
9 days 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
»
9 days 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
  • »
    »
    9 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Relax. Why you worried about the rating changes?

    Spoiler
    → Reply
    • »
      »
      »
      8 days 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
  • »
    »
    8 days 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
»
9 days 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
»
8 days 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
  • »
    »
    8 days 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
»
8 days 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
  • »
    »
    8 days 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
    • »
      »
      »
      8 days 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
      • »
        »
        »
        »
        8 days 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
        • »
          »
          »
          »
          »
          8 days 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
        • »
          »
          »
          »
          »
          8 days 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
    • »
      »
      »
      8 days 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
      • »
        »
        »
        »
        8 days 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 days 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
»
8 days 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
»
8 days 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://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
  • »
    »
    8 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Seems quite same: 264929515 264902138

    → Reply
    • »
      »
      »
      8 days 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
»
8 days ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Hello dear Codeforces and [user:][user:MikeMirzayanov] I confirm that my solution is entirely my own work. I did not refer to or copy anyone else's code during the competition.I did not use any external sources, forums, or repositories for assistance. My approach and solution are based solely on my understanding and problem-solving skills.The logic and implementation in my code were developed independently. Any similarity to other submissions is purely coincidental and not due to any form of collaboration or code sharing.

And I don't know anyone participant form the given number of it . and I do my problem but my mistake is that I published the code on any amount of group which I do not ever done after it [user:system][problem:1984B]

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

    Heloo dear codeforces and MikeMirzayanov But I don't know one of them. And I use my approach for it. Please check . 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! 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 1984B from this person why I didn't cheat C2 and D????

    Thanks you.

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

Appealing for a review on https://codeforces.com/contest/1984/submission/264889510 and https://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