rivalq's blog

By rivalq, history, 2 years ago, In English

Hi Codeforces!

I am pleased to invite you to Adhocforces, Mathforces Codeforces Round #832 (Div. 2), which will take place on Friday, Nov 4, 2022 at 14:35 UTC. You will be given 5 problems and 2 hours to solve them.

The round will be rated for participants of Division 2 with a rating lower than 2100. Division 1 participants can participate unofficially in the round.

All problems in this round were prepared by me and CoderAnshu.

I would like to thank:

The score distribution will be announced shortly before the round (or earlier).

Good luck and have fun! See you in the standings.

UPD 1:

Scoring distribution: 500 — 1000 — 1250 — 1750 — 2500

UPD 2:

I am flying to dhaka so will post editorials later.

UPD 3:

Congratulations to our winners!

Overall:

  1. Um_nik
  2. errorgorn
  3. turmax
  4. OtoriEmu
  5. Vercingetorix

Div 2:

  1. OtoriEmu
  2. Nephren--Ruq--Insania
  3. Silviasylvia
  4. Gu_Zhou_Suo_Li_Weng
  5. googolx

UPD 4: Editorial for A to C has been posted, will post D,E soon.

UPD 5: Editorial for D is posted.

UPD 6: Finally editorial for E is posted.

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

| Write comment?
»
2 years ago, # |
  Vote: I like it +30 Vote: I do not like it

As a tester, I can confirm that the problems are very interesting and would recommend everyone to participate in the contest.

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

Good Luck Everybody

»
2 years ago, # |
  Vote: I like it +64 Vote: I do not like it

Leafeon.

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

If it is not Adhocforces and Mathforces as mentioned above. I think It must be Observation forces

»
2 years ago, # |
  Vote: I like it +115 Vote: I do not like it

As a tester, I think my opinion on the problems is best kept until after the round, but I wish everyone participating fun!

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

    Why does this feel like a "lol yer so screwed, enjoy tho"

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

      LOL, this is me being a bit too self-conscious. I've tested maybe 10 rounds by this point and I can only remember recommending participation for one (https://codeforces.net/blog/entry/76777?#comment-613771 ), as I feel that testers recommending every contest feels insincere (not every round can be the best round ever, you know?)

      But then I think people might read too much into me not saying anything, so probably just never saying anything is better, and I thought it would be best to announce this to the world.

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

    I am waiting to hear your opinions

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

      I think the contest is great, a little challenging but not too adhoc.

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

      I thought E was very cool and none of the other problems looked particularly bad to me, but there was a very large amount of "guessforces" involved in A-D and I thought that would be a bit offputting.

      • A: I guessed separating positive and negative values would work. It was A so I didn't prove it.
      • B: I copied the idea of the second sample (swap first B with last N), submitted, didn't prove it either.
      • C: I actually solved this one legit as I like game theory problems, and think the perspective change idea is simple but cute. But I wondered how many people would write a bruteforce and guess from that instead.
      • D: I essentially started this one by guessing again: "This operation looks OP, I think answer <= 2". And it's easy to notice if length is even you can only affect one of a[l] and a[r] in one move, so it's possible to do in 2 moves iff you can zero either a[l] or a[r] in one move. As it turns out, my initial guess was correct and this condition for 2 moves also applies for the general case.
      • E: Very cool problem. There are many wrong paths to choose here (for example, trying to do some inclusion-exclusion is unlikely to work, but it almost works), and this can be either impossible if you get stuck in one of those paths, or very easy if you see the intended counting method quickly.
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I was hoping to gain some sort of insight but it turns out all your approaches for A-D were the same as mine and I'm not good enough to solve E (in contest anyways). Welp, back to upsolving I suppose.

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

          Sorry, I might be red but it still feels like I solve things by stumbling around most of the time...

          Guessing feels very dirty to me but it's fast and it tends to work for early problems in div2 rounds. When you get to harder problems you start being forced to analyze the structure to simplify the problem -- D is a problem you could have solved a lot more systematically than I did (basically looking for invariants) but that kind of approach was really only forced for E in this round, which is a very difficult problem that many reds failed to solve.

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

            I found a awesome solution for stupids like me:

            • Write an $$$O(nk)$$$ solution with binoms
            • Use factorial to replace the binoms
            • Find that the answer is like $$$\sum_i\sum_jA_iB_j$$$
            • Calculate in $$$O(n)$$$
            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I finally pushed it to a convolution form, and then what should I do

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

        I think questions with guesses is common in the Codeforces format.

        We only have a little over two hours to solve the questions, and the faster you are, the higher the score you get. Therefore, when we find a guessing that might be correct, we will try to use it to solve the problem first instead of proving it.

        But this is not without benefit to us. We practice our ability to guess the conclusion and perceive the correct conclusion with increasing accuracy. This is also true in many cases in OI competitions. Some conclusions need to be observed and guessed (the proof will be relatively easy), and some conclusions can be guessed and seem obvious but not easily proven (in which case the speed and correctness of the guess becomes important).

        I think that guessing the conclusion is part of Codeforces that brings me surprise and growth when solving problems. Of course, it does get a little tedious if you need to do this for every question.

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

        I used inclusion-exclusion to solve E successfully :) It turns out that after changing the order of sigmas, the formula can be calculated recursively. Great problem! Looking forward to the intended solution.

»
2 years ago, # |
  Vote: I like it +44 Vote: I do not like it

As a tester, I tested this so long ago that I forgot I even tested it.

»
2 years ago, # |
  Vote: I like it +79 Vote: I do not like it

As a tester, I tested this round because of the authors and I was not disappointed. Most problems are pretty cool and high-quality, good luck to the participants!

»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

As a tester, the questions are very interesting

»
2 years ago, # |
  Vote: I like it -136 Vote: I do not like it

pls downvote me!:)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As a participant I wish you guys a very good luck

»
2 years ago, # |
  Vote: I like it +19 Vote: I do not like it

You had me convinced to partake at antontrygubO_o

»
2 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Hoping to cross 2100! Good luck!

»
2 years ago, # |
  Vote: I like it +19 Vote: I do not like it

As a fan of karuizawa kei ayanokoji i must participate in this round.

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Best of Luck everyone.

»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Hope everyone good luck!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I was looking forward to the problems of this contest, hoping to surprise me.

»
2 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Can anyone explain me, why score distribution is always posted shortly before the round and not earlier?

»
2 years ago, # |
  Vote: I like it +18 Vote: I do not like it

As a Kanye west fan, I can confirm "George Bush Doesn't Care About Black People" and would recommend everyone to participate in the contest.

»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Find Minimum of Maximum Of Minimum of Maximum...............

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Mathforces

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

Dekuuuuuuuu ^_+

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I'm afraid of Mathsforces as mentioned...

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hoping to get back my color (-_-)

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

Hope to see indian names in problem statement,

»
2 years ago, # |
  Vote: I like it +17 Vote: I do not like it

another garbage speedforces

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

    There are only 5 problems, so it's likely to have large gaps between C and D or similar.

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

    yeah the round is so speedforces that you could not even solve D

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    I hate any problem contains alice and bob most of them are very hard and take much of thinking.

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

      I love any problem contains alice and bob most of them are very hard and take much of thinking.

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

      Huh, and here I thought thinking and stimulating your brain was the point of CP

      • »
        »
        »
        »
        2 years ago, # ^ |
        Rev. 2   Vote: I like it -15 Vote: I do not like it

        And where is the other points of cp ? for example there is problems require programming skills and problems require usage of algorithms and the techniques of cp like dp. why I learned tens of algorithms if the kind of problems like that?

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

          Codeforces problems with difficulty <= 2100 typically don't involve too complicated algorithms, but they require deep thinking and interesting math observations, and the solution is often short. In terms of learning, I think solving such interesting problems can help you better understand complicated algorithms. Personally I like those thinking-intensive problems and that's why I'm a user here.

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

            For example this educational round really balanced and diverse ,it contains 4 problems under 2100 but if you look at it you will notice that problem C and D requires dp and graph algorithms and only problem A which about math and thinking .
            In my opinion educational rounds is the most benefit for me.
            Btw ,I like your profile picture ,it express the real:)

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

      It requires taking lot of examples and finding which one gives answer

      1)taking parity of minimum or parity of array length ? or parity of total sum ? or is it parity of some other thing like parity sum-(n-1) ?

      I am bad at solving problems which require a lot of case work and I thought this problem was one of that kind

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        you are right this problem just thinking only and doesn't corresponding to algorithms and data structures . un necessary problem and any company interview doesn't contains garbage problems like this .

»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I solved C after 3 WA and more than an hour and I wish I could find a way Alice and Bob both lose .. man I suck I couldn't see the simplicity

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

Operation forces, speed forces.

»
2 years ago, # |
  Vote: I like it -21 Vote: I do not like it

I didn't understand E problem's second test case 1,2 how it is possible 26?

I found the 01 02, 011 002, 0011 0112, 0001 0122

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Length 4 : (0001, 0122) || (0011, 0112) || (0111, 0012) Length 3 : (001, 012) || (011, 012) || (001, 022) || (011, 002) Length 2 : (01, 02)

»
2 years ago, # |
  Vote: I like it +23 Vote: I do not like it

POV: u hesitate to submit C's Solution due to its simplicity :""

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

    So true. I submitted C only after partially proving it mathematically.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      orz, I could not figure it out for 2 hours straight lol, I'm so terrible

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

        Nahh You're not terrible :)

        We sometimes don't do well in some contests due to lack of concentration ,being exhausted or just need to practice more :".. , so just keep in mind to continue in your journey till reachin' ur glory.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks for your kind words, appreciate a lot :)

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

    I don't think you need rigorous proofs for each question, I am sure you must have solved B as well without proving that there is no other optimal way. Proving greedy algos is very tough in most cases. In problem C, you can easily conclude that only the minimum element in the array and the first element are relevant, you don't even have to look at other elements. This intuition comes from the fact that at each operation one of the elements reduce by one and each player can choose a specific element and try to reduce it to zero.

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

    Honestly, if I were to prepare a contest ever, I will random-shuffle the problems (not based on difficulties). Most people submit A/B/C without proof.

    Difference between contests and actual math is that you have one more technique of proof in contests. Namely, this seems to be the right kind of solution for a problem worthy of being Div 1/2 A/B/C/D. This is why experience has a slight advantage over rigour and creativity in CP.

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

After Every round & specially after reading editorials/solutions...Why I feel like noob?

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

i think most of the contestant solved problem C without prove.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I still didn't got the logic. Can u please, explain the logic after the end of contest.

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

      The element that Alice chooses is the element that Bob has to check for 0 and decrements in the next turn, and the element that Bob chooses is the element that Alice has to check for 0 and decrements in the next turn. Furthermore, the element Alice chooses is guaranteed to be outside index 1 when it's her next turn, and likewise, the element Bob decrements is guaranteed to be outside index 1 when it's his next turn.

      Therefore, the fastest way to get an element to 0 is to always pick the same element (and this is guaranteed to always be available). Specifically, it should be the smallest element available to them, since they want to have decremented to 0 first.

      Let's refer to the first element of the initial array as $$$x$$$. Alice should pick the smallest element available to her, which is the minimum of all elements except $$$x$$$. Let's say this element is $$$y$$$.

      What can Bob do? Everything except $$$x$$$ and $$$y$$$ was originally $$$\geq y$$$ and would now be $$$> y$$$ when it's Bob's turn to choose, so Alice would win this race if Bob picks any of these. Bob cannot pick $$$y$$$, because Alice claimed it. So Bob's only possible hope of victory is to pick $$$x$$$. If, at the original array, $$$y \geq x$$$, then Bob wins. Even when they're equal, Alice has to decrement $$$x$$$ before performing the swap, so Bob wins that race.

      Overall, the solution is very simple: find $$$y$$$ as the minimum of all elements except the first element ($$$x$$$). If $$$y \geq x$$$, Bob wins. Otherwise, Alice wins.

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

      if you have the first turn you can always force the opponent to decrease the minimum element from the array. How? It's easy, just move the minimum element to the a[0], now your opponent is forced to decrease the a[0] and swap, and you just repeat and force him again. However, if the minimum element is already at a[0] then you are doomed because your opponent will beat you with the same strategy

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Here is my complete logic: Is 1 showing up somewhere? If showing up as a1, then Bob will always win. Why? Because after Alice operation, a1 will be 0 and swap with ai. So Bob can always take this 0 back to a1 in the next step. So Alice lose. Else if showing up as a2/a3…, then Alice will always win. Why? Because after Alice operation, she can take 1 as new a1, then following the first half of this paragraph, Bob will lose.Now what if 1 is not showing up? Let’s focus on 2. If showing up at a1, then we know after Alice operation, ai will become 1, then following the logic from step1, Bob will always win. Else if showing up at a2/a3…, following the logic from step1, Alice will always win. …we can observe that the location of the smallest value matters: if at a1, then Bob win, otherwise, Alice win.

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

    Here's my draft:

    $$$[1]\ [a_2]\ [a_3]$$$ — when you(player) see this — you are losing

    $$$[a_1]\ [1]\ [a_3]$$$ — when you see THIS you are winning ($$$a_1>1$$$). Know how?

    $$$[2]\ [a_2]\ [a_3]$$$ — losing

    $$$[a_1]\ [2]\ [a_3]$$$ — winning ($$$a_1>2$$$)

    etc.

    Then we LOOK and SEE and WATCH.

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

      That's cool! I use similar approach to solve game theory problems, writing small states as winning or losing helps a lot and usually the winning/losing strategy hidden becomes obvious :)

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

      You have a nice explanation. I finally understand the problem! Thank you!

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

      thank you guy

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

Does D implementation has lots of case work? I thought about D but It required me to do lots of things with prefix and suffix and also checking for 0's in the array. Was I in the right direction? I was just finding whether prefix or suffix on [L, R] can have 0 Xor if not then check whether atleast one 0 Xor subarray is possible in that range.

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

    Odd range is trivial. For even range, yes, check whether prefix or suffix can have 0 xor. No need to check for subarrays. These are all the cases: 179253302

    Submission
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Bro, whats in Dhaka?

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Yaaaay, another speedforces

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

Solution for D:

We notice the operation will not change $$$XOR[l,r]=a[l]⊕a[l+1]⊕...a[r]$$$.So if $$$XOR[l,r]≠0$$$,no solution.

Let's consider the case of $$$XOR[l,r]=0$$$.

  • If $$$a[l]=a[l+1]=...=a[r]=0$$$,$$$ans=0$$$;

  • Else if $$$r-l+1==2$$$,$$$ans=-1$$$;

  • Else($$$r-l+1>2$$$):

    • If $$$r-l+1$$$ is odd,$$$ans=1$$$;
    • Else if $$$a[l]==0$$$,or $$$a[r]==0$$$,$$$ans=1$$$;
    • Else,we need to find $$$x$$$,which makes $$$a[l]⊕a[l+1]⊕...a[x]==0$$$ and $$$x-l+1$$$ is odd.If such $$$x$$$ exists,$$$ans=2$$$.Otherwise,$$$ans=-1$$$.

How to find $$$x$$$:

Use prefix xor-sum.Note $$$XOR[i]=a[1]⊕a[2]⊕...⊕a[i]$$$.

We just find $$$x$$$,which makes $$$XOR[x]==XOR[l-1]$$$ and $$$x-l+1$$$ is odd.

Store all positions where $$$XOR$$$ values and parity are the same in a linear table(or STL set).Then we just do binary search(or use lower_bound) to find $$$x$$$.

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    Yea, but how we are finding that x effectively?

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

      Use prefix xor-sum.Note $$$XOR[i]=a[1]⊕a[2]⊕...⊕a[i]$$$.

      We just find $$$x$$$,which makes $$$XOR[x]==XOR[l-1]$$$ and $$$x-l+1$$$ is odd.

      Store all positions where $$$XOR$$$ values and parity are the same in a linear table.Then we just do binary search to find $$$x$$$.

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

    Else,we need to find x,which makes a[l]⊕a[l+1]⊕...a[x]==0 and x−l+1 is odd.If such x exists,ans=2.Otherwise,ans=−1

    How can you do this in log or smaller time? This is the only part where I got stuck in.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      just maintain 2 sets

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

      You can store all prefix xor values in a map value : vector of indexies and then take lower_bound for l in map[prefix xor value of l-1] that will give us the nearest next index with the prefix xor = prefix xor of l-1 and if val^y=val we know that y = 0 so we can use it if y <= r. We should also care about segment to be with an odd length — for this we can have two maps — one for even indexies and the second for odd. My approach works so.

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

    bro finding that x is the most crucial part of the question, rest is easy

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Completely agree ... I wanted to know this part the most !

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

        For finding the $$$x$$$, I used two maps of vectors, one that stores the odd indices of each prefix XOR, and another that stores the even indices of each prefix XOR. If an odd-length substring that begins at index $$$\ell$$$ has an XOR of 0, then the prefix XOR at the end of this substring should be equal to the prefix XOR at index $$$\ell - 1$$$. The map retrieves a vector of all odd or even indices (we want the parity to match with $$$\ell$$$) that have this prefix XOR, so we can binary search to see if any of them are between $$$\ell$$$ and $$$r$$$.

        imo I think the bigger roadblock is on determining whether the output is 0 or not. Although understanding the objective is simple (all values in the range need to be 0), checking this efficiently would, I believe, require a range query structure like a sparse table or a segment tree, so those who are not familiar with such structures would likely be unable to solve D. Everything else can be solved with cumulative prefix arrays and an efficient way to find indices that have a particular prefix XOR value (like a map).

        EDIT: I'm dumb, we can just a prefix sum to check if a range is filled with 0s or not, lol. I did not need to build the segment tree after all. Well, I got Pretests Passed regardless, so I have no regrets. I hope it gets AC though...

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I understand, thank you very much ! Ps, I didn't know that we could use lower_bound on maps

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

            I didn't use the lower_bound on the map; I used it on the vector. The map is of type <long long, vector <int>>. It maps the prefix XOR value to a vector of even/odd indices that contain this value. It's on this vector that I check if the first even/odd index after $$$\ell - 1$$$ that has the same prefix value as $$$\ell - 1$$$ is before index $$$r$$$ or not.

            btw if you want to lower_bound on map, you should use the built-in method, e.g., mp.lower_bound (target), which runs in $$$O(\log(SIZE))$$$ time by traversing the red-black tree. Do NOT use lower_bound (mp.begin(), mp.end(), target, since this will try to perform a binary search as if it's a linear structure, incrementing the bidirectional iterator to find a particular "index", which would take $$$O(SIZE)$$$ time. It's not relevant for D, but please keep this in mind for whenever you do want to binary search on a map (or set).

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Lol just make a prefix sum array, if the sum of subarray $$$[l,r]$$$ is $$$0$$$. Then all elements are $$$0$$$.

          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yeah, I only just realized that, lol. I guess D is a lot more accessible than I thought. I guess the logic can be tricky though, but it's nice to know that nothing more advanced than cumulative prefix arrays are required here.

            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Can You please eleborate . I didnt got how to find x ?

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

                I have two maps of type <long long, vector <int>>. Let's call them evmp and odmp, denoting even and odd indices respectively.

                Let's use an example to help demonstrate this: [7, 0, 7, 7, 0, 2, 5, 7, 0]

                The prefix XOR array would be: [7, 7, 0, 7, 7, 5, 0, 7, 7]

                The maps would map a prefix XOR value to the even/odd indices it appears in. Specifically, we have:

                • evmap[5] = {6}
                • evmap[7] = {2, 4, 8}
                • odmap[0] = {3, 7}
                • odmap[7] = {1, 5, 9}

                Let's say our query is 3 8, which has even-length and neither index 3 nor index 8 (of the original array) are 0. The only way to make index 3 become 0 is to get an odd-length substring that begins at index 3 which XORs to 0. We're using $$$x$$$ to denote the last index of this mystery substring that may or may not exist. Note that $$$x$$$ must have the same parity as $$$3$$$, i.e., since 3 is odd, $$$x$$$ must also be odd (so that $$$[3, x]$$$ has odd-length).

                If $$$x$$$ exists, then the combined XOR of index 3 to x would be 0, so prefixXOR[x] = prefixXOR[2] = 7. So now we find the first odd index after index 3 whose prefixXOR is 7. The odd indices with a prefixXOR of 7 can be found using odmap[7] = {1, 5, 9}. We look for the first index that's $$$\geq 3$$$ (can binary search for 3) and check if it exists and is $$$\leq 8$$$.

                The binary search should yield 5, which is $$$\leq 8$$$, so $$$x = 5$$$ is a valid choice, i.e., apply the operation on the range $$$[3, 5]$$$ first to turn them into 0, then apply the operation on the remaining range $$$[6, 8]$$$ to turn those into 0.

                Please let me know if you're still confused by anything. There may be better approaches than this, but this is what to came to my mind, which I implemented. My submission might not be clean (I messed up earlier attempts during the contest), but may be helpful to check out regardless: 179275716

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey, seeing the solution, especially the last part

    • Else,we need to find x,which makes a[l]⊕a[l+1]⊕...a[x]==0 and x−l+1 is odd.If such x exists,ans=2.Otherwise,ans=−1.

    What about the array [0, 0, 0, 0, 2, 2]. Since, you will find $$$x=2$$$ and the partition — 0 0 0 | 0 2 2. You would report the answer as 2. But isn't the $$$ans=1$$$, as the subarray [0,0,0] needs $$$0$$$ operations and the subarray [0,2,2] needs $$$1$$$

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

      In this case,$$$a[l]=0$$$,so we just do operation $$$[l+1,r]$$$ ,the answer is $$$1$$$(see the previous line).

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also came up with exact same approach. But it took me like 2.5 hours. Here is my Accepted submission . ( I tried to make it very readable).

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If such x doesn't exist, how do we know there is no answer? I got stuck wondering if there can exist arrays which need 3 or more operations to clear.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Consider an operation sequence: $$$[?,?], [?,?],..., [l, p] $$$, we can prove that the operation $$$[l, p] $$$is always equivalent to $$$a [l] ⊕ a [l+1] ⊕ ... ⊕ a [q] $$$, no matter what the previous operations are.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Somehow my solution for D passed 100 000 stress tests but could not beat the pretest 2 LOL. Im not even mad, just curious

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

    Well, don't you hate it when that happens? xD.

    Take a look at Ticket 16407 from CF Stress for a counter example.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Have you tried generating tests with few (<= 4) bits?

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

what will be the approach for problem C ?

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

    Step1: find out the minimum element in the array (let's say mn is the smallest element in the array)

    Step2: if( firstElement == mn) then Bob is Winner Else Alice Wins.

    Spoiler

    Explanation: You can see that if the first element is equal to minimum then when Alice swaps this element, Bob can swap it back to the first place, and in the end alice gets 0 on first position so loses. Otherwise if the first element is not minimum, alice can choose always this minimum, so Bob loses.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but how to prove this solution?

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

        It's optimal for a player to always pick the minimum element that's available to them. The element that a player picks will not be available to the next player in their turn, but it is guaranteed to be available again after that. Therefore, Alice can keep picking the same element, and Bob can keep picking the same element.

        Alice picks the minimum element from all except the first element of the array. The only way for Bob to stand a chance is if this first element is initially less or equal to Alice's choice. Note that this first element decrements on Alice's turn, so Bob gets a head start and would win even if this first element is initially equal to Alice's choice. But if Alice's choice is strictly smaller than the initial value of the first element, then Alice wins.

        Basically, if $$$a[1] > \min (a[2], a[2], \ldots, a[n])$$$, Alice wins. Otherwise, Bob wins.

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

    Bob and Alice chose minimum number from numbers he/she can choose from and how quickly make that number to 0. Alice got advantage because she chooses first from a[1..(n-1)]

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Video Solution for Problem C

    Hint:
»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

if it's not adhocforces then i am fucked

»
2 years ago, # |
  Vote: I like it +69 Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Why do you set the time limit for E so tight? My algorithm is linear, but can only pass when choosing c++ 20, while c++ 17 gave me TLE. This has cost me three penalties.

My submission: Submission

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Great contest!!! I love it!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the topic i can use to solve c

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

    if ur the winner, keep $$$minimum \neq a[1]$$$

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you mean that it is just an imp problem?

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        game theory problem but not classical actually, you can solve those problems by observing the win/lose state

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

How to solve D? I can only think of this solution but couldn't prove: If segment is odd size, then xor the whole thing must be 0. If it is then result is 1. If segment is even size, then check if there is a way to split the array into two odd segment, each of which total xor is 0. Do this by finding the nearest index from r which is true. An exception is when there are zeroes on left and right side, which should be taken intp account since the result might be 1 or 2.

Is it correct or am i missing something?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can also reduce even length segment into odd one if a[l] or a[r] = 0

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      true. But if they are not one then the answer is going to be 2 right? assuming we can split the segment into two part of total xor 0.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yeah, that's the hard part of the problem imo

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Prefix xor, keep track of last index that had prefix xor value x?

          then if at i the xor is x then we can find the index with last x

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I got it but still failed pretest, because there is case with zero at the end of an interval. In this case you only need 1 operation

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If the segment has only zeroes then the result will be 0.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If every element of the segment is 0, the result should be 0.

    If the segment is even size, If a[L]=0 or a[R]=0, the result should be 1. If there isn't a way to split the array, it's -1.

»
2 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Thank you

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone point out what's wrong in this code? Link

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

    Take a look at Ticket 16408 from CF Stress for a counter example.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I often overthink and write needlessly long and complicated solutions for extremely simple questions, but you... You have surpassed me in every way possible, I am awestruck and bow down in the glory of the sheer 200-IQness of your solution.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem C isn't a classical game theory problem (like a graph win-lose), so I liked it ... but I think most of the contestants had emitted hypotheses and just coded it hoping that it would pass all the tests.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    In fact it is easy to prove the conclusion
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

wow I accidentally swapped numbers 1 and 2 in two places and that's why i got wa2 in D, sad

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody explain the logic of Problem C that how the answer is Bob when the minimum value of the array is equal to the first array element

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can see that if the first element is equal to minimum then when Alice swaps this element, Bob can swap it back to the first place, and in the end alice gets 0 on first position so loses. Otherwise if the first element is not minimum, alice can choose always this minimum, so Bob loses.

»
2 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Pure shitty round as always like all Indian rounds !!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How did people figure out if a[0]<=min element then Bob wins and it works for all cases? What is the observation here?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Optimal play is always taking the smallest number. I figured that out by looking at how a game ends and which steps need to have happened before that.

»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Why is TL quite strict in Problem E?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to solve E?

    $$$d1[i] = a[i] - a[i - 1], d2[i] = b[i] - b[i - 1], \sum d1[i] = n, \sum d2[i] = m$$$
    $$$ d1[i] \ne d2[i] = 0$$$

    that's all i found. i guess it could be solved by including-excluding principle.

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

What is wrong with my A task solution?

int main()
{
	int t;
	std::cin >> t;
	while (t--)
	{
		int n;
		std::cin >> n;
 
		ll sum = 0;
		while (n--)
		{
			ll temp = 0;
			std::cin >> temp;
			sum += temp;
		}
		std::cout << abs(sum) << std::endl;
	}
	return 0;
}
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try llabs instead of abs

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

      Why do you think this is the issue? The abs function defined on <cmath> and <cstdlib> has the overloads for long long, so it should be returning a long long, same as what they passed to the arguments.

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

        Because I got the same submission as them, just with llabs instead of abs. ¯\_(ツ)_/¯

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

          I don't know, my submission got passed just fine with abs.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I see a lot of the same solutions from other people and they use abs for long long. It works for them. I am really angry that my code doesn't work on second pretests and can't understand why it doesn't work

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

        For C++, use std::abs instead of abs.

      • »
        »
        »
        »
        2 years ago, # ^ |
        Rev. 2   Vote: I like it +6 Vote: I do not like it

        I reproduced your problem. It can be fixed by either changing the includes to #include <bits/stdc++.h> or by using llabs

        your submission: 179289807

        llabs: 179290278

        stdc++: 179290542

        Edit: Or listen to the poster above me. That is good to know!

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

        Oh, I see the issue now. You are not using std::abs. Either use std::abs or llabs.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        My guess is that the overloading for the abs function with long long types is in a library that you did not include. I copied your exact code and replaced all the includes with # include <bits/stdc++.h> (which, btw, includes all the libraries, so there is no need to include anything else with it ever) and it was accepted. Submission: 179294076

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

          Damn. I guess it should be ADL messing things up.

»
2 years ago, # |
Rev. 2   Vote: I like it -20 Vote: I do not like it

Deleted

»
2 years ago, # |
  Vote: I like it -27 Vote: I do not like it

Definitely great round, thanks!

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

    Is your criteria for considering a round great based on you getting positive rating change from it?

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It probably seems so

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ~~\yes~~

      Also, on problems not being insanely stupid.

      not to offend you, but
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        Not really sure what kind of jab you're trying to make, but I have only other comment other than my previous reply here. Clearly, I'm depressed over only getting +69 (haha sex) rather than +70.

        Anyways, to baselessly call this a great round is stupid. It certainly isn't a bad round, but nothing about it makes it anything more than average.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      did you get a negative rating change?

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

        No.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          then why are you attacking him like that

          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
            Rev. 2   Vote: I like it +24 Vote: I do not like it

            Because his point is stupid and clearly biased. Also not sure where I attacked him in the comment you're referencing?

            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              It's a scathing attack on TimDee, don't try and pretend that it's not

              • »
                »
                »
                »
                »
                »
                »
                »
                2 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                I reserve my scathing attacks for Saarang only.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice job, strong pretests!

»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Sir, why are you travelling to Dhaka?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess the round could have been better if the problem E had an easier version with lower constraints...

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That may be too easy I think. Like just *1900

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I blundered

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Smh WA on D because of the case with zero at the edge of an interval with even length.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it
where is wrong about my A problem ?
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
long long a[N];
long long t,t1,t2; 
int main()
{
	cin>>t;
	int n;
	while(t--)
	{
		cin>>n;
		t1 = 0,t2 = 0;
		for(int i = 1;i <= n;i++)
		{
			cin>>a[i];
			if(a[i]>=0) t1+=a[i];
			else t2+=a[i];
		}
		long long ans = 0;
		ans = abs(abs(t1)-abs(t2));
		cout<<ans<<endl;
	}
	return 0;
}
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

is there a way to solve D with a sparse table

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

    You don't even need sparse table. All you need are cumulative prefix arrays and a dictionary/map.

    Key Observation: Performing the operation on some range will not change the result of applying XOR on all elements of that range, i.e., the combined XOR for the range is always the same before and after the operation.

    This should be easy to prove if you think a bit. From there, you should be able to figure out the solution. It involves several cases, which may require different techniques and different structures to solve, but none of the structures are too complicated. Try to think about it before inquiring further on details (which I wouldn't mind sharing).

    EDIT: Yes, there is one particular case (checking if all elements in the range are already 0) in which a sparse table can help. But a prefix sum array would be a simpler way to deal with that case.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I couldn't believe C was just finding min element! Thought my solution will get hacked for sure

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

Can anyone explain why i am getting WA in test case 1 in problem B?

Spoiler
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    in case 2 : after applying operation (3, 4) string look likes : BABNAN so this string still contains "BAN" as a subsequence.

»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Great contest. C was cute. Enjoyed solving D.

»
2 years ago, # |
  Vote: I like it +20 Vote: I do not like it

How to solve E?

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +32 Vote: I do not like it

    Rough solution, will post full later

    First Let's try to count the number of lists possible. The above problem is equivalent to counting the number of ways to reach (n,m) from (0,0) such that you always move closer to (n,m). There exists an obvious n*m dp solution.

    If there is only 1 dimension then ans = 2^n-1 (that is m=0). So we can try to break the grid into several 1-d paths. We can club every path by breakpoints, by breakpoints we mean points we will surely pass through and from them, we will turn right. There can be at most min(n,m) breakpoints. The number of ways to select i breakpoints is C(n,i)*C(m,i). Hence answer should be ans = sum(C(n,i)*C(m,i)*2^(n+m-i-1)) for i=0 to i=min(n,m).

    In the same way, we can find formulas for the expected number of moves to reach from (0,0) to (n,m). Define f(i) as the contribution of paths with i breakpoints. f(i) = Number of paths with i breakpoints / Total Number of paths. Let d(n) be the expected number of moves in the 1-D version of the problem. d(0) = 0 else d(n) = (n+1)/2.

    E(x) = sum(f(i)*(i+d(n+m-i))) for i=0 to i=min(n,m).

    P.S: It was Expected value before, hence ....

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Alice and Bob should just get a room.

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

gimme downvotes, because round need to be unrated :)

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

when will appear ratings of the problems?

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

E, nice problem, it's ok. Though isn't the time limit and memory limit too strict? I know you want not to make O(Nlog^2 N) (or maybe O(NlogN) which I don't know how to), but 2 sec is enough to and there is no reason to make memory limit 256MB.

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

    In testing we had an O(n log n) solution that worked in 3 seconds for the given constraints. Given that the O(n) solutions we had were working in 150ms and using less than 100MB of memory, 1 second seemed like a safe place to confidently separate the linear and the FFT solutions. I think we may have been unlucky to have tester solutions that were a bit too fast, and looking at the runtime for the accepted solutions during the contest 2 seconds would have been a better choice.

»
2 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Yeah! It is a wonderful contest and good problem .

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What could be the possibly rating of Problem C ????

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain the logic of problem C?

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

    Well this is not a formal mathematical proof but just an intuition:

    Whoever gets access to the minimum element first can win the game no matter what. There are two cases:

    1. If the minimum element is at a[0], then Alice does not have access to that element since she can only pick elements from i = 1 (0 based indexing). In this case, once she performs the operation on any index, the minimum element decreases by 1 and goes to that index. Notice that it is still the minimum element, and now it's Bob's turn, so Bob has access to that element first.

    2. If the minimum element is at a[i] where i > 0, Alice has access to this element first.

    After a player gets access to the minimum element, he/she can just move that element to a[0], which will force the other player to decrease its value on their turn. This will go on till a[0] becomes 0 and the other player can no longer make a move.

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

Hello everyone! In problem B for n = 3 my answer is: 2 1 5 7 8

So, it's obviously going to be like that: BANBANBAN -> AANBBNBAN -> AANBBNABN (no BANs)

Also, for n=4 my answer is 2 1 5 7 11

BANBANBANBAN -> AANBBNAANBBN (no BANs I guess?)

My solutions are: 179271785 (wa4) 179276239 (wa3) 179288511 (wa4)

I couldn't check the tests while competing and actually got very upset as I couldn't solve B.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1) n = 3 : if you'll delete elements with numbers 1, 2, 3, 4, 6, 8, you'll get BAN. 2) same for n = 4

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

meghna gupta bewafa h :)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what could be the rating of d?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I nearly dropped to pupil:(

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any proof for the answer for B? I kind of just guessed.

»
2 years ago, # |
  Vote: I like it -26 Vote: I do not like it

A is harder then E

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

45th ICPC World Final's all the participants Welcome to Dhaka. Best of luck. Hope you will enjoy Bangladesh.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why are almost problems from A->C greedy? That is my observation about some current contests.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Has anyone used segment trees for D? To answer the queries I checked for the xor of segment l to r, If the xor is not 0 then the answer is -1, if it is 0 and all the elements of segment are 0 the answer is 0, if not then if length is odd then 1 else if length is even then 2, this approach fails on some testcases, but if anyone has approached the problem in this way, please share the solution.

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

For C,

Here is my complete logic: Is 1 showing up somewhere? If showing up as a1, then Bob will always win. Why? Because after Alice operation, a1 will be 0 and swap with ai. So Bob can always take this 0 back to a1 in the next step. So Alice lose. Else if showing up as a2/a3…, then Alice will always win. Why? Because after Alice operation, she can take 1 as new a1, then following the first half of this paragraph, Bob will lose.Now what if 1 is not showing up? Let’s focus on 2. If showing up at a1, then we know after Alice operation, ai will become 1, then following the logic from step1, Bob will always win. Else if showing up at a2/a3…, following the logic from step1, Alice will always win. …we can observe that the location of the smallest value matters: if at a1, then Bob win, otherwise, Alice win.

»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

guessforces

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

guys in problem 2 BAN BAN

i submitted a useful answer for test case 2 where the number of BAN is 4 but my answer was still rejected the ideal answer was 2 1,12 4,9 giving and answer of NANNANBABBAB my answer was 2 2,6 8,12 resulting in BNNBAABNNBAA which is true but was rejected although the problem clearly stated that any possible output is accepted can u please tell me if this is an error in the testcases or not

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

    BAN must not be a subsequence in the resulting string anywhere. The resulting string which you mentioned, contains BAN, eg. B in index 1, A in index 5, and N in index 8 (1-based indexing). You might have mistook subsequence for substring. A substring must be contiguous but a subsequence may or may not be contiguous. P.S. the definition of subsequence is mentioned in the first few lines of the problem statement too.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is not true because from BNNBAABNNBAA if I delete NNBABNBAA from left to right then still BAN is left there! You have missed the definition of subsequence I guess. So you should swap all the leftmost A with rightmost N or B with N. Hope you get it

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In $$$D$$$, I was thinking for a while about the proof for the following part:

For a given query $$$L-R$$$, assume $$$arr$$$ is the subarray enclosed by $$$L-R$$$. If there is no odd-length prefix of $$$arr$$$ has $$$0$$$ XOR (and accordingly no odd-length suffix as well), then answer is $$$-1$$$.

We can prove it as follows:

Assume we do an operation on an odd-length subarray $$$l-r$$$ within $$$arr$$$. All odd-length prefixes of $$$arr$$$ (and odd-length suffixes) that totally enclose $$$l-r$$$ or do not overlap at all with it will not change their XOR.

For those that partially overlap, either all the partially overlapping odd-length prefixes or suffixes will overlap in even number of values. So the XOR of each one of them will change to the XOR of a smaller unchanged odd-length prefix (or suffix) XORed with $$$0$$$ (coming from the even number of overlapping values). So their XOR remains non-zero.

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Editorial ?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I need editorial for problem D

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +15 Vote: I do not like it

    I don't know when the editorial would be posted, but I can try to help explain Problem D.

    Key Observation: If we apply the operation on some range $$$[L, R]$$$, the combined XOR of the values in $$$[L, R]$$$ remains the same.

    Proof: If the combined XOR for the range was initially $$$x$$$, then the operation replaces each element in the range with $$$x$$$. When calculating the new combined XOR, each $$$x$$$ will cancel out another $$$x$$$ until only one remains (note that the length is odd), so the combined XOR is still $$$x$$$.

    This leads to the following cases. Note that each case assumes that the previous cases do not apply.

    1. If everything in the query range is already 0, then we already achieved the objective without needing to perform any operations, so the output is 0. This case can be checked by pre-computing a prefix sum array. You could use Sparse Table (max), Fenwick Trees (sum), Segment Trees (sum/max) instead, but they're kinda overkill.

    2. If the queried range does not already have a combined XOR of 0, then it is impossible to turn all its values into 0 (since that would require changing the combined XOR). Such cases have an output of -1. This case can be checked by pre-computing a prefix XOR array. Could use Fenwich Trees (XOR) or Segment Trees (XOR) instead, but still overkill

    3. From this case onwards, the combined XOR for the range must be 0 (but there must be at least one non-zero value in the range). If the queried range has odd-length, we can apply the operation on the entire range to turn them all into 0s, so the output is 1. Checking odd length is trivial

    4. Now the queried range must have even length. If the first or last element of the range is already 0, then we can apply the operation on everything except the first/last 0 element, to turn everything into 0. The output is 1. Checking endpoint values is trivial

    5. Now the queried range has even length but the endpoints are both non-zero. Now let's look for an odd-length prefix of this range such that this prefix has a combined XOR of 0. If such a prefix exists, we can apply the operation on it to make them 0 (including the first element). Now we can perform another operation (like step 4) to turn everything else to 0. The output is 2. This can be tricky to check, I'll discuss this afterwards

    6. If there is no odd-length prefix with a combined XOR of 0 within this range, then it's impossible to make the first value in this range a 0. Even if we try to perform other operations first, each operation will preserve the combined XOR values, so there will never exist such an odd-length prefix with a combined XOR of 0. Therefore, the output is -1. This is the last remaining case, so there is nothing to check here.

    My approach for checking Case 5 might not be the best, but it works. If such an odd-length prefix exists, i.e., a range $$$[\ell, x]$$$ with odd length whose combined XOR is 0, then observe that the prefixXOR value at index $$$x$$$ must be the same as the prefixXOR value at index $$$\ell - 1$$$ (or equal to 0, when $$$\ell = 1$$$). Furthermore, $$$x$$$ has the same parity as $$$\ell$$$ (either both even or both odd) in order for $$$[\ell, x]$$$ to be of odd length.

    So what I did was build two maps (dictionaries), each mapping a prefixXOR value to a vector that lists all even or odd indices respectively that have the same prefixXOR value. When I reach Case 5, I check $$$prefixXOR[\ell - 1]$$$ and pull up the corresponding vector from the corresponding map, and then check if any of these indices are between $$$\ell$$$ and $$$r$$$. This check can be done by binary searching (lower_bound) for $$$\ell$$$ and checking if the result is $$$\leq r$$$.

    Runtime: $$$O(n\log n + q\log n)$$$. The $$$\log n$$$ factors are both due to Case 5 (both preprocessing and checking), so if there's a better way to deal with Case 5, the complexity might improve.

    My Submission: 179275716 (it's not very clean since I changed a bunch of stuff while struggling in the contest, and yes, I did build two segment trees)

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      my solution also has same time complexity and it's giving me TLE on test case 3 :( 179565550

      • »
        »
        »
        »
        2 years ago, # ^ |
        Rev. 2   Vote: I like it +12 Vote: I do not like it

        Your algorithm is efficient; the only issue with your submission is that the I/O is too slow. This is actually very well-known for competitive programmers in C++. Briefly, there are two issues:

        1. When using cin or cout, the default behavior is that they should be synced with stdio (i.e., scanf and printf), e.g., if you read input with scanf and then try to read input with cin, the default behavior is that cin will read the next input that was not read at all (and should not read what scanf already read). This synchronization takes some time for each use of cin or cout.

        2. When you want something to be printed as output, it is first stored in a buffer. The buffer is only emptied and displayed (aka flushing) when something triggers it. By default, cin and endl would invoke flushing. Each buffer flush takes some time, so having a lot of flushes would slow down the program. When the program terminates with no errors, the buffer is flushed.

        Solutions:

        1. To avoid synchronization delays, one option is that we can simply use scanf/printf instead of cin/cout. But if you prefer to use cin/cout, another option is to turn off synchronization (between scanf/printf and cin/cout) by adding one line of code to the program: ios_base::sync_with_stdio(false);. Note that turning off the synchronization means that using both cin and scanf or both cout and printf would allow them to overlap, so make sure you never use scanf/printf if you choose this (except for some rare scenarios where you can exploit non-synchronization). Your submission gets AC by adding this: 179941502 (but 920ms is dangerously close to the time limit)

        2. As for flushing, this can be dealt with by simple leaving all the output in the buffer without flushing. When the program terminates with no errors, all of the output will be flushed anyway. To avoid early flushing, you should never use endl and instead print \n. Your submission now gets AC with a comfortable 374ms with this replacement (in addition to turning off synchronization): 179940064

        Your submission doesn't suffer from this issue, but it is often convenient to output the answer to the current test-case or query before we read in the next test-case or query. In this case, the following cin would flush the contents of the previous cout. This can be avoided by adding a line cin.tie(NULL);, so flushing is only done at program termination (if there are no errors). The latest submission includes this (but it doesn't do anything for your code because you decided to read all the queries early for some reason, before printing any output).

        A downside to cin.tie(NULL); is that if you interactively test your program, you would only see the output when the program terminates. You can temporarily comment this line out for such interactive testing. Otherwise, you can simply provide in the entire input before you receive the output to check.

        By the way, for interactive problems, you need to flush the buffer for the interaction, so for these problems, you should use endl or cout.flush() after your query (but stick to \n if it's in the middle of the query) before reading the response.

        tl;dr start every program with the lines ios_base::sync_with_stdio(false); and cin.tie(NULL); and don't use endl (print \n instead), except after querying in interactive problems.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks for such a good explanation. I had seen blogs on this before but never tried to read it since I never came across a problem like this. Thanks again :)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

-1 for no editorial, and another -1 for much comments on how simple solution to C is without explaining it.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is D actually solvable on python?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem D. I am getting TLE on test case 3. I think my solutions's time complexity is O(q + nlogn). Many others have gotten AC on this complexity. Can some tell what's going wrong on this? 179541379