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

Автор buffering, история, 5 месяцев назад, По-английски

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 09.06.2024 17:35 (Московское время) 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.net/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

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

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

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

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

Expect great and unique problems! Wish everyone good luck!

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

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

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

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

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

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

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

As a tester, this round goes hard

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

why (1000 + 1000 ) ?

you mean that there are c1 and c2 ?

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

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

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

As a problem, I liked the testers.

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

me when i see arul hii arul

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

i LOVE Global rounds hoping in another -150!!

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

As a tester, I tested the round

»
5 месяцев назад, # |
Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится
»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
5 месяцев назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

CP > IND vs PAK. :D

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

Hahaha!

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

CP(pretest passed) >>> Any other Enjoyment

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

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

»
5 месяцев назад, # |
  Проголосовать: нравится -34 Проголосовать: не нравится

hoping for + 3 contribution :3

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

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

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

    Everyone can participate officially and it will be rated for everyone

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

score distribution changed!

»
5 месяцев назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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

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

Is this contest suitable for beginners also?

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

is it a rated contest?

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

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

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

Dragon Boat Festival Health!

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

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

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

Speedforces

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

I'm in

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

good luck !!!

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

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

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

Will there be fewer contests because of Euro 2024?

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

gl & hf for everyone!

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

Why do E and F have the same score?

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

as a contestant i hope to solve the problems

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

Hoping to become Expert

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

English or Spanish?

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

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

why is cry crying (crying emojis)

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

let's go! good luck to everyone

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

all the best guys

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

is this contest is rated?

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

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

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

Literally 1984

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

Nineteen Eighty Fources

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

Literally 1434 (I lost the game)

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

ABC1C2 speedforces

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

I was not prepared for this 'Dashboard'!

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

reading statement of E be like

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

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!
»
5 месяцев назад, # |
Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

Animated Video editorial for problems [A-C2]:

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

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

    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.

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

      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.

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

        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.

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

    wow that's so cool! good work sir

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

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

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

      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

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

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

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

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?

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

    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.

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

      Rerooting technique with the original dp works too.

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

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

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

          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.

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

      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.

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

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

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

C2 hint anyone? :)

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

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

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

      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 ;)

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

        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:

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

          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 ;)

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

    in reverse order calc variants to get current value from previous

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

Thanks for this round!)

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

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

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

How to solve D?

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

    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).

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

      Oh hell

      So smart!!!

      Thanks a lot

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

        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.

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

      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})$$$.

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

        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

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

      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.

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

    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.

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

    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$$$ '

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

tasks were good btw

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

best D i have seen, orz!!

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

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

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

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

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

is problem E , pseudo independent set?

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

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

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

      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).

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

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?

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

    very close

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

      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!

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

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

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

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

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

Dpforces >>>>

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

I nearly got F and G :(

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

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

    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.

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

how to do C1 ?

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

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!

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

    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.....

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

    B made me panic as well

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

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!

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

cheatforces

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

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.

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

    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"

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

      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.

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

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

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

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

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

      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 :).

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

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.

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

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

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

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.

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

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

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

      Thank you

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

      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.

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

        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".

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

Cool round!

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

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 :(

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

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

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

      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.

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

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.

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

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

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

Never understood problem statement of E in the competition.

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

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

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

    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!

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

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

»
5 месяцев назад, # |
Rev. 3   Проголосовать: нравится -11 Проголосовать: не нравится

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?

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

    Does anything can be done about it?

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

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

    • »
      »
      »
      5 месяцев назад, # ^ |
      Rev. 3   Проголосовать: нравится -60 Проголосовать: не нравится

      I took the value 31 from cp algo article

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

        No.

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

        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.

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

    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.

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

rainboy solved problem H first

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

Problem 'H' first solved ecnerwala ?

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

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

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

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

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

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...)

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

    Relax. Why you worried about the rating changes?

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

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

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

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

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

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?

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

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

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

    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.

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

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?

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

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

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

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

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

        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.

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

          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

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

          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 :)

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

      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.

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

        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.

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

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

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

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????

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

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.net/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!

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

    Seems quite same: 264929515 264902138

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

      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!

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

.

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

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

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

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.

»
5 месяцев назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Your thinking process in extremely slow

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

not bad!

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

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