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

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

Hello Codech....err i mean Codeforces!

I invite you to participate in Codeforces Round 934 (Div. 1) and Codeforces Round 934 (Div. 2) which will start on Mar/16/2024 17:35 (Moscow time).

You will be given 6 problems and 2 hours 15 minutes to solve them in both divisions. Division 1 has $$$\textbf{2 subtasks}$$$, and Division 2 has $$$\textbf{1 subtask}$$$.

Joining us on the problem setting panel are:

I would like to thank MikeMirzayanov for platforms Codeforces and Polygon.

Please do read a few problems in advance at the very least. Especially with all the subtasks, it is strictly in your benefit to read and choose the problems you want to try. Good luck. We hope you enjoy the problemset.

Score Distribution will be posted soon.

$$$\textbf{UPD}$$$ : Score Distribution :
Div2 : 500 + 1000 + 1500 + 2250 + 2250 + (2250 + 2750).
Div1 : 500 + 1250 + 1250 + (1250 + 2000) + (2000 + 1500) + 4500.

$$$\textbf{UPD2}$$$ : Sorry for the issue with the queue towards the end. Hope you enjoyed the round.

$$$\textbf{UPD3}$$$ :
Div2 :
1) WanYuanShenWanDe
2) tzc___________________wk
3) kcodex
4) mily
5) Oinng123

Div1 :
1) tourist
2) jiangly
3) gyh20
4) Benq
5) ecnerwala

$$$\textbf{UPD4}$$$ : Editorial is out.

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

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

As a tester, I would like to know when the next cookoff will be.

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

As a tester, I recommend to break your fast on this meal.

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

As a tester, Dominater069, Everule and satyam343 orz

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

As a tester, C++20 when?

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

As a tester, good luck to all participants.

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

As a tester, lunchtime when

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

Cringe announcement

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

    I understand if you don't like it, it is slightly different, but calling it cringe without any feedback isn't very nice, don't you think? :)

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

What is a subtask? Are there any prior examples to try it?

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

    Subtask means the problem will be divided into two parts, one will be easier with lower constraints and one will be harder with higher constraints.

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

      Thanks. I thought it's something special that deserved highlighting in announcement

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

As a participant, i will participate

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

[Deleted]

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

Congrats, Dominater069 on your first codeforces round!

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

So many testers !

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

I was really excited to do this contest but now i discovered that I'm a tester D:

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

As a tester, the problemsetters cooked.

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

As a tester, Dominater069,Everule,satyam343 orz.

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

I'm sorry, but Div.1 is very important, so why not take the option of postponing it?

It is a bit sudden, considering that changes in the available C++ compilers have made some libraries effectively unusable or slowed down (if you make heavy use of long longs).

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

Congratulations on your first contest, Dominater069

And also Good Luck for every parcipicant!!!!!

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

Umm... Why is the eligibility range for Div. 2 from 0 to 1899?

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

    If there is a corresponding Div. 1 round, then you belong to Div. 1

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

Dominater069 rounds gotta be one of my favourite genders

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

what do you mean by subtasks? can somebody explain please

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

Negative rated testers tho :)

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

problem in div 2 is subtask 1 in div 1 ??

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

downvoteforces

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

Lets get ready to get back what we lost yesterday (Devil face emoji)

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

As a tester, the problems are really good and I would recommend the participants to read all of them.

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

I did the round yesterday thinking that I would get to 1900 and get to compete in Div 1 this round. But the rating changes have not come through yet. Anyone know if I'll get to 1900 before the contest?

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

Is the mean of "subtask" like 1939D - Big Persimmon (one problem but have partial points), or like D1/D2 (two problems without partial points)?

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

Since so many LGM's demanding C++20, can someone elaborate what's the difference between C++14,17,20 etc...

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

Again Clashing with LC Biweekly, have to skip

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

Whoa there is negative rated tested

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

2250 for div2D is too high.

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

BCD1 with the same score, looks interesting

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

orz, I hope to reach Specialist soon. Good luck to all participants!!!

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

Ah yes! A negative rating tester!

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

4500? Serious?

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

Dominater069 Great to see you as the author on CodeForces Contest!!

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

So many subtasks. Is it possible to make a 5-hour IOI rated contest?

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

Good Luck Folks. Hope I become -ve someday

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

What is penalty time ?

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

Amazing problems haha, Dominater069 rounds are always so fun, This one had a codechef taste (Bitwise and Game thoery), loved it.

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

I feel like if you don't know how to solve B then you don't know how to solve B there is no need for thinking or even trying

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

newbie here i come

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

In queue.

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

how to approach B ?

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

    Deleted.

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

    Hint:

    First consider the 2*n size array where, in first half all elements from 1 to n are present and in the remaining half all elements from 1 to n are present {these two half will have same xor}.

    then, try to think what will happen if we swap some of the elements.

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

      I thought through the entire process but couldn't find a way to select the numbers that aren't present in both halves. However as soon as I saw this x^x=0, I figured it out

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

imagine submiting your code in the last 10 minute and get long queue, then it give you a WA verdict after contest

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

There's a bunch of submissions in queue. Will the round be extended?

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

my code is not submitting from last 10 minutes, its stuck on pretest 1??

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

<

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

The examples seem a little simple so that I have a lot score penalty. qwq

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

These 2250 are slightly eazier than average.

Trash sample.

I'm back, GM.

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

C is a cute problem, Thank !!!

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

What was the catch in the problem C? Alice has to pick numbers in increasing order. Bob will remove minimum x such that cnt[x]<=x. Right?

Can someone provide a counter-test-case for my solution?

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

    The second smallest element with frequency 1 is the answer.

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

      If I'm not mistaken, the answer is second smallest element with frequency 1. Once we pick the first number, we can just react to what bob is doing. He will never be able to remove a number from us, unless it's value is 1.

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

        Yes, sorry, I actually meant frequency 1, don't know why I typed unique frequency. Updated. Thanks.

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

    0 0 1 1 2

    Answer is 3

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

      Ah, right. Thanks!

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

      But Bob tries to minimize the score, right? So after Alice choses 0, Bob choses 1, Alice 1, Bob 2 and the MEX is 2

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

        Alice plays first, though. Think of it has her having the ability to "save" a number before Bob gets to it.

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

        alice doesn't need to worry for any number with frequency >1, she can pick it afterwards when only last copy is left, and its her turn. She plays first so she'll try to secure the 1 frequency number, and the smallest 1 freq num to meet the MEX expectation, so the second 1 freq number is the answer as Bob can pick it.

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

      I sorted the array and found the MEX of elements in odd positions. Can someone provide some counter case? It failed.

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

        0 0 0 1

        You say the answer is 1 but it is 2. Alice can pick up the 1 then a 0. If you index from 0 then just add another 0 in the front (have the 2 in an even position)

        Your algorithm would work (I think) if you had at most 2 of each number.

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

    0 0 1.

    Alice picks 1. Bob picks 0. Alice picks 0. Mex is 2.

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

    0 1 1 2 2

    Actual answer : 3 Your answer. : 2

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

I love problem div2D.

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

My solution for D looks like shit

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

gameforces!

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

Ok, can somone please tell me whats wrong with my solution? 251789210

I ran stress test but nothing came up ...

EDIT: Nevermind ... got it

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

    Code is not public yet.

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

    Man, I'm stress testing with actual AC codes rn and nothing's coming up. What the actuall fuck

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

    Can you share the test case?

    Edit: Nvm, system tests are over

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

    Hello , I took a look at your solution , you only subtract 3 when the sequence is alternating ababababa, but it's actually you need to remove all the odd values, 3 5 7 ...

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

Can anyone here pls explain D to me?

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

    If you have a palindrome, say abcddcba, and you append a character x at the end. Under what condition will it remain a palindrome?

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

      How to check if the given substring itself is a palindrome, I wasn't able to check that without getting a TLE.

      My approach was if its 2-good, then it is k-good for all even numbers k, less than the string length. Similarly, if it is 3-good, then it is k-good for all odd numbers k, less than string length. But in this case, I was required to check additionally if the given substring was a palindrome. I wasn't able to think of an efficient way to do this. Can someone help?

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

      gotcha, ty broski

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

I think it wasn't a nice decision to decide to extend the round at the last minute.

  1. Many people were ready to just spoil all the solutions, and if someone didn't tell them that the round is extended, a serious accident could happen.
  2. There are also people (like me) who gave up to solve a problem because the time left wasn't enough, but if they kept trying, they could probably solve it in the extended time. It's unfair that those people could only lose more rank.
  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится -102 Проголосовать: не нравится

    there was a long queue (~10mins) towards the end of the contest, its the only fair decision

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

      No, the only fair decision is to make the round unrated (I mean, it might be a valid argument that the "unfairness" was allowable, though...).

      I received the notification of the extension only after the extra time. I was lucky to notice it at some point, but the site was too unstable and I just spent almost-offline time...

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

    Same, I left before the round was finished.

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

    Fully agreed. Also, no announcement was sent to Div1 contestants before the scheduled end time.

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

    But never give up until the last moment, right? Leaving early is not the right approach.

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

      The problem is, When there were 20 minutes left, I decided to go with problem F, which is harder but with less code. As long as I solve it, I can quickly write it in 5 minutes. But If I know I have 30 minutes, I will go with problem E, since I already solved it, but I don't have enough time to code. Extension at the last minute is useless for me, I can't do anything with C and E.

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

    I apologize that the original announcement of extension has not reached the Div1 participants. Normally, it is sent simultaneously to both contests, however, I can see that this time it has only been sent to Div2. I guess either I misclicked, or the system malfunctioned.

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

    Did not get the notice of the extension and hence did not submit D2 which was a couple minutes of debug away. :(

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

How to solve Div2D

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

    If the substring has all identical characters, the answer is zero. If the substring contains alternating characters such as ababab, the answer is summataion of all even $$$k$$$. Otherwise, all $$$k \geq 2$$$ contribute the answer, except the original substring, which will contribute only if it is not a palindrome.

    The crucial idea is : If you have a palindrome, and you append a character at the end, there are a very limited set of scenarios in which the new string would also remain palindrome (that's where the motivation for alternating string comes in).

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

    wrong

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

Fuck me , i thought problem B was finding non intersecting subarrays with equal XOR, and my Solutin passed the first test , i'm so fucking blind man

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

1C is MUCH easier than 1B.

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

    Can you share it's solution.

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

      Let the diameter of the tree be $$$d$$$.

      When $$$d$$$ is odd or $$$\lfloor \frac{d+1}{2} \rfloor$$$ is odd, select the node in the middle of the diameter for operation.

      When $$$\lfloor \frac{d+1}{2} \rfloor$$$ is even, let the middle two nodes of the diameter be $$$x, y$$$, and then operate on $$$(x, 1) (y, 1) (x, 3) (y, 3) \dots$$$

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

        Proving this is quite simple, use the fact that any operation turns at most 2 nodes of the diameter black. Since the diameter must be made black you get a lower bound of $$$\frac{len + 1}{2} + 1$$$ operations. The case when $$$len \equiv 3 \mod 4$$$ you can do the 2 center nodes tactic. To prove that you cannot do better when $$$len \equiv 1 \mod 4$$$ you can just arrange the diameter nodes in a row. Any operation that colors 2 nodes will color 2 nodes with the same index parity. But there are $$$\frac{len + 1}{2}$$$ nodes with each parity. The number is odd, thus you cannot match the last 2 nodes together and need to do them separately. This is no better than the "Take one node and all the distances" tactic.

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

      No. I don't actually know, why is $$$n \le 2000$$$, when I could solve it in $$$O(n)$$$. Probably, it is hard to create checker in $$$O(n)$$$.

      Find any diameter. Let its length is $$$D$$$ (the number of vertices on it is $$$D + 1$$$). There are two cases:

      Case 1: $$$(D + 1) \mod 4 \neq 3$$$ (not 3, 7, 11, etc.). Then we have to find one vertice on center on diameter and simply do $$$d = 0, d = 1, d = 2, \dots$$$.

      Case 2: $$$(D + 1) \mod 4 = 3$$$. In this case we can optimize one operation. Look at examples:

      *-a-b-*
        | |
        * *
      

      The upper horizontal line is a found diameter. We can take vertices $$$a$$$ and $$$b$$$ and do operations $$$(a, 1)$$$ and $$$(b, 1)$$$. Using algorithm from first case we could find following operations: $$$(a, 0)$$$, $$$(a, 1)$$$ and $$$(a, 2)$$$, which is worse.

      *-*-*-a-b-*-*-*
        | | | | | |
        * * * * * *
          | | | |
          * * * *
            | |
            * *
      

      We can do operations $$$(a, 1)$$$, $$$(a, 2)$$$, $$$(a, 3)$$$, $$$(b, 1)$$$, $$$(b, 2)$$$, $$$(b, 3)$$$.

      So, in this case we use two vertices on the center of the diameter.

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

        "Probably, it is hard to create checker in O(n)." — Absolutely right. That was the reason :)

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

        I think you forgot to say that for even $$$k$$$ we can skip $$$(a, k)$$$ and $$$(b, k)$$$, so on the last example we only need to perform 4 operations $$$(a, 1)$$$, $$$(a, 3)$$$, $$$(b, 1)$$$, $$$(b, 3)$$$

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

      I couldn't stick this solution (which you described) in during testing. I tried very hard to do it :)

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

    You might be surprised to hear that it was actually placed at 2F(1D) when I tested

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

Well done, Amazing performance Kevin114514. It was a nice comeback, indeed!!! 🔥🔥

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

Is problem D related to hashing?

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

For me this round is very Bad

Very weak samples propably on purpose

Ideas in div1B and div1C are really easy to get but corner cases are really easy to miss

Maybe its me but i really hate such rounds

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

Try random DP approach for F1 but still can't do it :((

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

Dforces

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

Can someone pls tell me how to further optimize the time taken in D(in Div 3). I did 5 iterations and this was the best I could come up with: 251788296 Thx

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

I did this in div1 problem B. Is this an intended solution?

There are three cases.

Case 1: There is only one character in a string: $$$aa \dots aa$$$. In this case the answer is $$$0$$$.

Case 2: The string is of form $$$ababab \dots aba$$$, and its length modulo $$$2$$$ doesn't matter. In this case the answer is $$$2 + 4 + 6 + 8 + \dots$$$ and if a string itself is not a palindrome, then additionally $$$+ length(s)$$$.

Case 3: Else the answer is $$$2 + 3 + 4 + 5 + \dots$$$ and if a string itself is not a palindrome, then additionally $$$+ length(s)$$$.

To check the form $$$aa \dots aa$$$ or $$$abab \dots abab$$$ of a string I used prefix sums for all characters.

To check, if a substring is a palindrome, I used polynomial hashes with segment tree.

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

    Yes, this should be correct. By the way, since we are already using polynomial hashes, can't we just compare substring hash with its reverse for equality?

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

    Checking whether the substring is a palindrome or not within the given constraints was the most difficult part for me

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

    For polynomial hashes of a substring, you can use some sort of prefix sums, instead of a segment tree, because there are no updates.

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

    I Just do what you said, but it gives WA on pre#2.

    Code:

    #include <bits/stdc++.h>
    using namespace std;
    
    class Hash {
        typedef unsigned long long ull;
        vector<ull> h, p;
        ull mod = 1145141919810LL;
    public:
        void generate(const string& s) {
            h.resize(s.size());
            p.resize(s.size() + 1);
            h[0] = s[0];
            for (int i = 1; i < s.size(); i++)
                h[i] = (h[i - 1] * 131 + s[i]) % mod;
            p[0] = 1;
            for (int i = 1; i <= s.size(); i++)
                p[i] = p[i - 1] * 131 % mod;
        }
        ull getHash(int l, int r) {
            if (l > r) return 0;
            if (l == 0) return h[r];
            return (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod;
        }
    };
    
    int main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0), cout.tie(0);
        int T;
        cin >> T;
        while (T--) {
            int n, q;
            cin >> n >> q;
            string s;
            cin >> s;
            string t = s;
            reverse(t.begin(), t.end());
            Hash Hs, Ht;
            Hs.generate(s);
            Ht.generate(t);
            while (q--) {
                int l, r;
                cin >> l >> r;
                l--, r--;
                // abcde
                // 01234
                // edcba
                // 01234
                int xl = n - r - 1, xr = n - l - 1;
                auto sum = [](int L, int R) -> long long {
                    return (long long)(L + R) * (R - L + 1) / 2;
                };
                if (Hs.getHash(l, r - 1) == Hs.getHash(l + 1, r)) cout << 0 << '\n';
                else {
                    long long ans = sum(2, r - l + 1);
                    if (Hs.getHash(l, r) == Ht.getHash(xl, xr))
                        ans -= (r - l + 1);
                    if (r - l + 1 >= 4 && Hs.getHash(l, r - 2) == Hs.getHash(l + 2, r)) {
                        // 3, 5, 7, 9, ... (r - l + 1)
                        int R = r - l + 1;
                        if (R % 2 == 0) R--;
                        else R -= 2;
                        int nums = (R - 3) / 2 + 1;
                        ans -= (long long)(3 + R) * nums / 2;
                    }
                    cout << ans << '\n';
                }
            }
        }
        return 0;
    }
    
    /*
    121212
    1111111
    
    abcdefg
      abcdefg
    abababa
    
    ababababababababababa
    
    a bcdedcbax
    b=x
    c=a
    d=b
    e=c
    
    abababababab
    
    3,5,7,9
    
    abbabbabb
    */
    
    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Try using a different modulo, preferably a prime one. Your modulo is divisible by 2 so a string whose hash (without taking modulo) is a large power of 2 would make the hash equal to zero in your code which makes it easy to create a test case where two hashes collide. That is most likely the pretest where your hash fails.

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

    I think that for checking if given substring in a string is a palindrome, we can use Manacher (but I also did it with hashes)

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

    Did exactly same, still getting WA on test 2, maybe some edge case, disappointing contest for me.

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

    You can also use manacher algorithm for checking palindrome. It's O(n).Manacher

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

i nearly died implementing B.

how to solve C?

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

    Imagine if there are two 0's, two 1's, two 2's, ..., two 100's. Will Alice be able to guarantee a MEX of 101?

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

      can you explain a little more? bob can delete 2 elements eg 2 and 2. so how is it possible thanks

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

        Let's say Alice starts by deleting 0.

        If Bob deletes, say 17, Alice will make sure to get the second 17 (before there's no more 17s, capping the potential MEX to 17). Bob deletes another element, then Alice makes sure to get that second element, etc.

        Hope that makes sense!

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

        When bob deletes first 2, alice will take second 2. This way alice can follow or go after bob.

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

    Group the numbers into two groups. One group containing numbers that are repeated only once (single-repeated numbers), and the other group contains numbers that are repeated 2 or more times (multi-repeated numbers). Sort the single-repeated numbers.

    Now, the single-repeated numbers are the main thing both Alice and Bob fight over. Because the other numbers are repeated 2 or more times, so if Bob picks one such number, Alice can pick the other copy of the number so both of them will have that number.

    So if there are 0 or 1 single-repeated numbers, Alice will grab the number first.

    If 2 or more, both of them try to take the single-repeated numbers in ascending order. So Bob will take the second smallest single-repeated number (that may become the MEX).

    Now just insert these single-repeated and multi-repeated numbers into a set and find MEX.

    Submission for reference

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

Can someone help me what's wrong with my B solution?

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

I am so mad at myself atp, because I missed not in 1B, and I was trying to solve it the whole time >:(

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

How to do div2D (shortest way)

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

    For even: if k < full_length_substring, good = all characters are same
    For odd length: if k < full_length_substring, good = all even position characters are same & all odd position characters are same.

    full length needs to be calculated manually, I used manacher algorithm.

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

The king is back in the game...

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

is there any other way to solve Div2 D without using Manacher algorithm(tourist 251709195 used it) but it seems a bit tricky Anyone with any other approach

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

When will the system testing start ? @dominator

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

tourist #1 jiangly #2 what a beautiful sight to see

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

Can someone explain what is wrong with this solution for C problem of div2:

{
 
            List<Integer> res = input.nextInts();
            int n = res.get(0);
 
            List<Integer> arr = input.nextInts();
 
            Map<Integer, Integer> fre = new TreeMap<>();
            arr.forEach(it -> fre.put(it, fre.getOrDefault(it, 0) + 1));
 
            int mex = 0;
 
            while (mex < n) {
                if (fre.getOrDefault(mex, 0) > 0) {
                    mex += 1;
                    if (fre.containsKey(mex)) {
                        if (fre.get(mex) <= mex) {
                            break;
                        }
                    } else {
                        break;
                    }
                } else {
                    break;
                }
            }
 
            output.write(mex + "\n");
        }
»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

251791328 Div2-D why this submissions RE?It run ok in my computer.

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

Problem E, found centroid and then just dfs'd out as far as possible and printed unique distances... what case does it WA? https://codeforces.me/contest/1944/submission/251783755

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

In div2D, how do you check if a substring is a palindrome or not in constant time?? I implemented the rest of it completely but just didn't know how to get through this part. It was incredibly frustrating ffs.

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

    You can use rolling hash (aka. Rabin-Karp) or Manacher's algorithm.

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

    You can use string hashing. If you're afraid of implementing string hashing by yourself, you can use this mini library provided by USACO guide.

    Library

    Using this library, the code is as simple as

    # Hash str and rev(str)
    if hash.get_hash(l, r) == revhash.get_hash(n - 1 - r, n - 1 - l) 
        s[l...r] is a palindrome
    

    My Submission

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

I solve div2E as follow first i try every node as starting then i try every adj pair as starting the operation and take the best out of all why it didn't pass any countr example??

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

Is there solution for C with bs and min heap or something like?

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

For Div2E it doesn't work to compute the shortest distance between all vertices and then greedily choose $$$v$$$ and $$$d$$$ such that as many vertices are painted as possible? E: It doesn't, greedy is too tempting!

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

Few days notice before the contest

Don't discuss problems in public, talk in private

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

What's wrong with my solution 251724861 for Div 2 1944B - Equal XOR?

Edit: Got it

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

nice balanced round, good job, guys

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

What a beautiful round !

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

Test case : 9 1 0 7 7 7 6 1 2 0 Output must be 3 but its 2 as if Alice choose 0 then Bob would choose 2

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

    Think what if Alice instead of taking 0 initially she took 2 and then Bob if goes for 0/1 there will still be 0/1 left to take.

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

    Alice would choose 2 in the first move as in the next move irrespective of whatever Bob chooses 0 or 1, there are more than one 0 and 1's

    So the game would go on like-

    A-2 B-0 A-0 B-1 A-1

    Alice has 0 1 2 making the MEX equal to 3

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

For Div1E, why is the answer 3 here?

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

    If you try to get mex=4, Alice chooses 2, Bob removes 2 copies of 3, 2 copies of 1 and 1 copy of 0, Alice chooses 0(or 1, it doesn't matter), Bob removes 2 copies of 1 and 3 copies of 3, Alice removes 1(or 3, it doesn't matter), Bob removes 5 copies of 3, loss for Alice.

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

Can any one help me in DIV-2(C). why it is compulsory to traves loop till (i<=n) [submission:https://codeforces.me/contest/1944/submission/251814298] which giving me right answer but not till (i<n). which is giving me wrong answer. [submission:https://codeforces.me/contest/1944/submission/251813998]. I just need one test case to understand this.

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

    0 1 1 2 2

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

    the loop ensures that it checks all integers from 0 to n inclusive, ensuring that it covers the entire range of possible non-negative integers. This is why it's compulsory to traverse the loop until i <= n

    what about this test case?
    1
    1
    0
    
    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Hey, it seem's that only in your testcase need to travse till i<=n otherwise it will work till i<n. Check my last Accepted solution I just handle your testcase in if condition and rest code is working fine. Thanks for help

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

Nice Round. Upsolved Div2 D after the Round. Learnt How to check s(l...r) is palindrome or not in constant time using Hashing by converting to Integer in base 26.

One doubt , I stored these hashed values mod 1e9 + 7 , it passed the cases but Isn't it possible that two string might give same hashed values mod 1e9 + 7 ? If yes how to avoid such cases ?

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

    possible, but very unlikely

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

    you should do double hashing to make sure it doesnt happen in the future

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

    You can store two hashes with different constants to almost completely eradicate this possibility. I got hacked during the competition because I used only one hash, fortunately I managed to add another hash in time. This is my submission. There is also a good paragraph about reducing collisions on cp-algo.

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

    or you could use manacher's algo which will give you the longest palindromic substring at every center. Its much easier as code is available at gfg.

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

Big gap between 2C and 2D, and IMO 2B was harder than 2C. Problems were good.

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

Anyone has any hint how to go from 1D1 to 1D2 ? Thanks

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

    The Inclusion-Exclusion Principle.

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

      We can solve it by just modifying the solution of 1D1 too, we just need to observe that transitions from states of index to the next are like range arithmetic-progression add updates, which can be processed in $$$O(k)$$$ per index. Since there are $$$O(n)$$$ indices, we have an $$$O(nk)$$$ solution.

      251801445

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

      Can you explain, what are the conditions for the array to be good?

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

For Div2 Problem B Equal XOR I have the following submission https://codeforces.me/contest/1944/submission/251835494 but it gives wrong answer l is not subset of a[1, n] (test case 37) for test 2 and I have 0 idea why. I sorted the indices in l and r so this shouldn't happen unless l contains elements which are not in [1..n] (or [0..n-1] as I have them 0-indexed in my program). Does anyone have at least an example for which my solution fails?

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

    1

    3 1

    1 2 2 1 3 3

    Your solution greedily takes the value. So when it encounters the first 1 it immediately insert it into the first array .As a result the output contains 1 less element

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

      Thank you very much! I should've first choose the pairs, and than the elements in separate halves. Now I got AC. Thanks!!!

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

Yes, it's tourist ranking first, finally! Hope tourist can get back to the rating leader again!

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

received WA 15 times on pretest 2 for problem 2C/1A

discovered that there was no output on one test case 1 0

fixed and immediately got AC 🤡

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

Trash D1 AB, and Terrible samples

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

Код для задачи а t=int(input());s=0 for i in range(t): n,k=map(int,input().split()) if (n-k)>1 or k==0: print(n) else: print(1)

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

When will the ratings be updated?

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

    Some contests take some time in System Testing. But In this case System Testing is done. Most Probably They're recalculating.

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

Congratulations,jiangly goes back to the first rating.

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

Winner of Div. 2 is called WanYuanShenWanDe??? Why Genshin Impact ("YuanShen") is everywhere, even in Codeforces?

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

    "Yuanshen" is translated directly in China,and gradually becomes a meme because of its popularity.

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

Good problems,thx.

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

So when will the ratings be updated?

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

As a tester, good luck to all participants.

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

When will the ratings be updated? Why is the rating updated so slowly this time?

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

in problem 3 of div2 9 1 0 7 7 7 6 1 2 0 let this be the test case, i think here answer should be two but it's three

explaination->in first turn alice choose 0, then bob choose 1, then alice choose 1,then bob choose 2 and thus by any next turn alice will not get two and mex will be two

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

the contest is rated or unrated

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

When the rating will update ?? It's taking a lots of time

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

please provide an update on when the rating will be updated?

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

When will the ratings be updated? On some div1/2 contests, it is as immediate as lightning once the round ends, rating updates. On other hand, for other contests, it delays. This delayed lot.

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

i got WA on D because someone found strings with the same reverse hash. with this, you can hack anyones code. is this fair?

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

there was a discussion between the contest writer Dominater069 and LGM's regarding that all of Div1 participants did not receive the message. convo I guess they might be checking manually the number of affected Div1 participants so they can get their round unrated as it happened in the last round where 18 people were manually addressed.

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

Может ли кто-то объяснить D2D?

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

Finally became a Expert haha

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

my actual rank in this round is 1192 and its showing in common standings but in my recent contests its showing my rank is 4811 and i got a 106 negative .. can someone address my problem ?

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

negative/xia

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

Check 4th test of problem A

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

wrong output format Unexpected end of file — int32 expected (test case 200)

what does this error mean?

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

Can someone give an example test case where single hash might fail on Div2D?

I submitted a single hash solution which got AC, but someone in the comments said that their single hash solution got hacked.

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

    Test case 13 is a good example. If you use base=131 and unsigned long long without mod, you will fail in this case.

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

    Here you go, I hacked you to illustrate.

    1
    20 1
    hcnrinqugrwpxdnkotqu
    1 20
    

    The point is you can somewhat easily find collissions for single-hashes if you know the modulo/base, so you should default to double hashes usually.

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

Why write codeforces help mesage

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

too easy C.too hard D.

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

Wow, I arrived slightly late in this contest just to discover there isn't a single question in the 1300-2000 difficulty range. Welcome to speedforces, and I already lost before it even had began

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

Can someone suggest what is wrong in my submission for div2 C problem.

251924677

My idea was that Alice and Bob will always pick up the smallest available element that occurs once in the array. What is wrong in that?

My submission failsin 363rd test case.

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

In my opinion the score of Div. 1 E should be 1250 + 2250 instead of 2000 + 1500...

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

Ended up getting wrong ans in D due to hash collision, changing the value of p worked.

Incorrect submission-https://codeforces.me/contest/1944/submission/251985522

Accepted-https://codeforces.me/contest/1944/submission/251985606

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

    It didnt work, it just didnt get hacked yet. Why not just pick a base randomly? (Or mod works too but you have to make it prime)

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

For those of you still waiting on some editorials, this may be of slight help. My editorial on Div2 A to D (the last two being Div1 A, B): https://www.youtube.com/watch?v=fZK7hiemXOE&t=10s

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

For Div2 C / Div1 A

for the test case 9 1 0 7 7 7 6 1 2 0

how the output is 3 ? First Alice removes 0, then Bob removes 1 then, Alice removes the second 1, now Bob removes the 2 and now Alice cannot get a 2 and cannot make MEX equals to 3

Kindly help me understand this

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

    Alice removes 2 first.

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

      Can you please explain the optima strategy and how it works ?

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

        Alice picks 2.

        If Bob picks 0, Alice picks 0 in the next move.

        If Bob picks 1, Alice picks 1 in the next move.

        If Bob picks something else, Alice can just pick whatever.

        With this strategy, Alice can always pick 0, 1 and 2.

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

        Optimal strategy: notice how Bob cannot do anything about Alice picking a number if it has more than one occurrence (as Alice can pick that on the next move) so he attempts to pick one that has exactly one occurrence. But since Alice goes first, she can pick the one occurrence Bob would pick.

        Problem boils down to finding the second number Alice cannot pick (because she already picked one that has one occurrence).

        Submission link: link

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

tourist is back

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

HURRY UP HURRY UP HURRY UP HURRY UP HURRY UP HURRY UP HURRY UP HURRY UP HURRY UP HURRY UP HURRY UP

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

Good Luck for every participant!!!