Dominater069's blog

By Dominater069, 5 weeks ago, In English

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.

  • Vote: I like it
  • +515
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +54 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

As a tester, Dominater069, Everule and satyam343 orz

»
5 weeks ago, # |
  Vote: I like it +116 Vote: I do not like it

As a tester, C++20 when?

»
5 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

As a tester, good luck to all participants.

»
5 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

As a tester, lunchtime when

»
5 weeks ago, # |
  Vote: I like it -56 Vote: I do not like it

Cringe announcement

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it -32 Vote: I do not like it

As a participant, i will participate

»
5 weeks ago, # |
Rev. 2   Vote: I like it -69 Vote: I do not like it

[Deleted]

»
5 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Congrats, Dominater069 on your first codeforces round!

»
5 weeks ago, # |
  Vote: I like it -24 Vote: I do not like it

So many testers !

»
5 weeks ago, # |
  Vote: I like it +34 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

As a tester, the problemsetters cooked.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

As a tester, Dominater069,Everule,satyam343 orz.

»
5 weeks ago, # |
Rev. 2   Vote: I like it +150 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Congratulations on your first contest, Dominater069

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

»
5 weeks ago, # |
  Vote: I like it -21 Vote: I do not like it
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

Dominater069 rounds gotta be one of my favourite genders

»
5 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

what do you mean by subtasks? can somebody explain please

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Negative rated testers tho :)

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 3   Vote: I like it -69 Vote: I do not like it

downvoteforces

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Is the mean of "subtask" like 1939D - Большая хурма (one problem but have partial points), or like D1/D2 (two problems without partial points)?

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it -63 Vote: I do not like it

Again Clashing with LC Biweekly, have to skip

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Whoa there is negative rated tested

»
5 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

2250 for div2D is too high.

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

BCD1 with the same score, looks interesting

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Ah yes! A negative rating tester!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

4500? Serious?

»
5 weeks ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck Folks. Hope I become -ve someday

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is penalty time ?

»
5 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

newbie here i come

»
5 weeks ago, # |
  Vote: I like it +31 Vote: I do not like it

In queue.

»
5 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

how to approach B ?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Deleted.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

»
5 weeks ago, # |
  Vote: I like it +41 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 6   Vote: I like it -69 Vote: I do not like it

<

»
5 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it -47 Vote: I do not like it

These 2250 are slightly eazier than average.

Trash sample.

I'm back, GM.

»
5 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

C is a cute problem, Thank !!!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    The second smallest element with frequency 1 is the answer.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      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.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    0 0 1 1 2

    Answer is 3

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ah, right. Thanks!

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Haven't thought of that. Thanks!

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    0 0 1.

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What if Alice picks 2 first... I made the same mistake.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    0 1 1 2 2

    Actual answer : 3 Your answer. : 2

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I love problem div2D.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for D looks like shit

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

gameforces!

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

I ran stress test but nothing came up ...

EDIT: Nevermind ... got it

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Code is not public yet.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it -10 Vote: I do not like it

    Can you share the test case?

    Edit: Nvm, system tests are over

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah that's the issue .. Thanks for the response :)

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone here pls explain D to me?

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

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

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

      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?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      gotcha, ty broski

»
5 weeks ago, # |
  Vote: I like it +234 Vote: I do not like it

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.
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -102 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it +146 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same, I left before the round was finished.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +56 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +44 Vote: I do not like it

    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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div2D

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    wrong

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Lol I did the same mistake too..

»
5 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

1C is MUCH easier than 1B.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you share it's solution.

    Spoiler
    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        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.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +27 Vote: I do not like it

      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.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it -30 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is problem D related to hashing?

»
5 weeks ago, # |
Rev. 3   Vote: I like it +65 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Dforces

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

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

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -53 Vote: I do not like it

    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
    */
    
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +10 Vote: I do not like it

    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)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i nearly died implementing B.

how to solve C?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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!

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          ohh i got it now . thanks for explaining

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Spoiler
»
5 weeks ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do div2D (shortest way)

  • »
    »
    5 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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.

»
5 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

The king is back in the game...

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the system testing start ? @dominator

»
5 weeks ago, # |
Rev. 2   Vote: I like it +27 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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");
        }
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.com/contest/1944/submission/251783755

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1
    4
    1 2
    2 3
    3 4
    
    Hint
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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!

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Few days notice before the contest

Don't discuss problems in public, talk in private

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What's wrong with my solution 251724861 for Div 2 1944B - Равный XOR?

Edit: Got it

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your idea is correct, you are just going outside the boundaries of the vector !

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

nice balanced round, good job, guys

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What a beautiful round !

»
5 weeks ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

For Div1E, why is the answer 3 here?

9 5
8 9 6 10 10 9 3 10 7 8
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    0 1 1 2 2

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
    
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

»
5 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

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 ?

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

    possible, but very unlikely

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

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

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

    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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    The Inclusion-Exclusion Principle.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +31 Vote: I do not like it

        You need for every i , $$$a[i] <= a[i-1] + a[i+1]$$$

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For Div2 Problem B Equal XOR I have the following submission https://codeforces.com/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?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 🤡

»
5 weeks ago, # |
  Vote: I like it -61 Vote: I do not like it

Trash D1 AB, and Terrible samples

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Код для задачи а 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)

»
5 weeks ago, # |
  Vote: I like it +45 Vote: I do not like it

When will the ratings be updated?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Congratulations,jiangly goes back to the first rating.

»
5 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good problems,thx.

»
5 weeks ago, # |
  Vote: I like it +47 Vote: I do not like it

So when will the ratings be updated?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

As a tester, good luck to all participants.

»
5 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

the contest is rated or unrated

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    They should clarify, because if it is rated then rating would have been updated.

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Finally became a Expert haha

»
5 weeks ago, # |
  Vote: I like it +38 Vote: I do not like it

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 ?

»
5 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

negative/xia

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Check 4th test of problem A

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

what does this error mean?

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why write codeforces help mesage

»
5 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

too easy C.too hard D.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    Imagine such testcase:

    1
    0
    

    What will be the answer and what is your code answer?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My code answer will be 1. First Alice will pick 0 and then Bob picks 1, so final answer becomes 1.

      C9rrect answer will also be 1

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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)

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, got hacked so used a random generator now

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Alice removes 2 first.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

tourist is back

»
5 weeks ago, # |
Rev. 2   Vote: I like it -12 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it -12 Vote: I do not like it

Good Luck for every participant!!!