liouzhou_101's blog

By liouzhou_101, history, 4 months ago, In English

1738A - Glory Addicts

Author: Milesian

Tutorial
Solution

1738B - Prefix Sum Addicts

Author: liouzhou_101

Tutorial
Solution

1738C - Even Number Addicts

Author: liouzhou_101

Tutorial
Solution

1738D - Permutation Addicts

Author: Milesian

Tutorial
Solution

1738E - Balance Addicts

Author: Milesian

Tutorial
Solution

1738F - Connectivity Addicts

Author: liouzhou_101

Tutorial
Solution

1738G - Anti-Increasing Addicts

Author: antontrygubO_o

Tutorial
Solution

1738H - Palindrome Addicts

Author: liouzhou_101

Tutorial
Solution
 
 
 
 
  • Vote: I like it
  • +23
  • Vote: I do not like it

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

Guys, i dont know about editorial (it is not ready yet) but it is possible to solve C in 1 if statement. Check my submission

UPD: Okay, same as in editorial but anyway... Feel free to ask any questions :)

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain how you thought of it during the contest ??

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

      Sure! At first lets say thet even numbers are "0" and odd numbers are "1" cause we care only about parity, right? Then i started implementing simple cases like: "1100", "111111", "10000", whatever, and asked myself "what if we gonna add/remove more 0s/1s?" After a while i realized that if Alice gonna use simple copy strategy, then she will always win if amount of 1s % 4 == 0. And then i tried to think about other remainders and came up with complete solution.

      Sorry for my bad english btw, it is not my native lang :|

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    wonderful solution ,but can you please explain me why "(odd + 1) % 4 == 0)" this is independent of parity of 0's ??

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

      Sorry for not answering for a long time.

      Yes it is. When amount of odd numbers % 4 == 3 it means that Alice can take any odd number on her first move and then just copy Bobs move. This is simillar to case when odd % 4 == 0. Alice always gonna get odd number of 1's + 1 she already have after first move. Just try to implement some trivial exmaples like "111" and add some 0's to this. You'll see that this is actually works

      Some codeforces lags below, nevermind

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry for not answering for a long time.

      Yes it is. When amount of odd numbers % 4 == 3 it means that Alice can take any odd number on her first move and then just copy Bobs move. Just try to implement some trivial exmaples like "111" and add some 0's to this. You'll see that this is actually works

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Fairly sure my submission can also be reduced to only 1 if statements since it also checks all conditions whereby alice wins then if all of those don't apply returns boris.

    However your solution is more elegant since it entirely disregards the number of 0s (which is cool haha).

    Also I've coded for like a combined 30 hours so don't bully me for my code haha, advice would be appreciated though (also I did't do this in competition, and have never tried a contest, how much time should this task have taken me?).

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I strongly recommend you to participate in competitions. Rather, there is no point in not participating in them (except time issue ofc). It doesn't matter how much time you spend on a task, as long as you can solve it yourself. Actually it's the best way to improve in mu humble opinion. The next time you encounter a similar problem, you will solve it faster

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you please explain me why we are taking modulo with 4?

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

      Just try to analyze some simple case.

      For example "1111". It doesn't matter who goes first, Alice can always get an even number. Why so? because after one "cycle" of moves amount of odd numbers will decrease by 2 and Alice gonna get exactly 1. So, she needs even number of ones. two 1's multiplied by even number. That is why we are talking about modulo 4. Everything else can be deduced from this case

»
4 months ago, # |
  Vote: I like it +20 Vote: I do not like it

pov : you got wrong answer on test 5 or 36 in problem B :

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

    I got wrong answer on test 11 though.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Somehow we not able to think that zero is greater number than negative . so we can not keep like this 0 0 -6 because we thought that -6 is good to keep instead of dividing it like -3 -3 or -2 -2 -2 and make it bigger

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      if the ans. for testcase 36 is yes ,can u tell me the possible array for that??

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sure

        7 4

        [-6 ,-7, -8 ,-9]

        Ans={-2 ,-2 ,-1, -1 ,-1, -1 ,-1}

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This def needs a fix

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

Why weak pretests for problem B?

»
4 months ago, # |
  Vote: I like it -16 Vote: I do not like it

Worst round

Screenshot-2022-09-30-201328

»
4 months ago, # |
  Vote: I like it -6 Vote: I do not like it

super fast editorial.. great contest.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Q. how many weak pretests do you want?? A. YESSS!!!

»
4 months ago, # |
  Vote: I like it +19 Vote: I do not like it
Spoiler

My solution for E:

Firstly,consider a special case:there's no zero in array $$$a$$$.

We notice if we put a "partition" between $$$a[i],a[i+1]$$$,we must put a "partition" between $$$a[j],a[j+1]$$$ as well,where $$$(a[1]+...+a[i])=(a[j+1]+...+a[n])$$$ (except the "partition" in the middle).

In other words,the "partitions" are in pairs.So the answer is $$$2^{k},k$$$ is the number of pairs.

Now let's consider an array $$$a$$$ including zeros.

Remove all zeros from $$$a$$$,we get a new array $$$b$$$.

The same as the special case above,if we put a "partition" between $$$b[i],b[i+1]$$$,we must put a "partition" between $$$b[j],b[j+1]$$$ as well,where $$$(b[1]+...+b[i])=(b[j+1]+...+b[n])$$$.

Because there're zeros,the situaion is a bit more complex:

Assume there're $$$x$$$ zeros between $$$b[i],b[i+1]$$$ and $$$y$$$ zeros between $$$b[j],b[j+1]$$$,the number of plans to place "partitions" is:$$$ \Sigma^{min(x+1,y+1)}_{i=0}C^{x+1}_{i}C^{y+1}_{i}$$$.

Take care of boundary conditions:

-all numbers are zeros

-the array has zeros at both the beginning and the end

-the "partition" in the middle

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

:(

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

fsy_jiaxun_when 's currently accepted submission for problem H seems to fail on Ticket 16227 from CF Stress.

Can someone hack it for me? or let me know if I constructed an invalid testcase? Thanks.

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

    Good job! It's a pity that this case does not appear in system tests.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a dp solution for C ? if yes please share

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

    Added.

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

      Can you please explain your intuition for C with DP? I did not even realize that this could also be solved with DP.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Intuition is that you can calculate if Alice can win or not in position of 1 even, 1 odd using position 0 even, 1 odd and 1 even, 0 odd. dpAlice[i][j] = !dpBob[i-1][j] || !dpBob[i][j-1] and some other logic.

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

        the states of the game are of the form (howManyEvensLeft, howManyOddsLeft, Alice's current sum's parity, whoseTurnIsIt). from this you could write a recursive function and add memoization (thank god n is only 100 lol)

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

      Could you please explain the z+y+1 in the code?

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

        I am not 100% sure, but here are my thoughts. This DP solution was not very intuitive for me but it is clever so if liouzhou_101 can correct me.

        dp[x][y][z] gives whether Alice or Bob at a particular stage of game can get even/odd parity (z = 0 or 1) from x even and y odd numbers.

        Where x is the current count of even numbers, y is the current count of odd numbers remaining in list

        Note that when y is even parity of (z+y+1)%2 changes when moving from Alice to Bob or vice-versa.

        and when y is odd parity of (z+y+1)%2 remains the same when moving from Alice to Bob or vice-versa.

        Now in the recursion when moving from Alice->Bob or Bob->Alice we have cases

        Cases for Alice->Bob include

        Case 1: y is odd and Alice wants even parity from remaining moves.

        Bob will try to defeat Alice by taking even parity sum from remaining numbers. Hence Bob will want even parity. So parity remains same from Alice to Bob.

        Case 2: y is odd and Alice wants odd parity from remaining moves.

        Bob will try to defeat Alice by taking odd parity sum from remaining numbers leaving only even parity sum for Alice. Hence Bob wants odd parity, same as Alice.

        Case 3: y is even and Alice wants even parity sum from remaining moves.

        So Bob will take odd parity sum from remaining moves. We can see parity switches from Alice to Bob.

        Case 4: y is even and Alice wants odd parity sum from remaining moves,

        So Bob will take even parity sum from remaining numbers. Again, parity switches from Alice to Bob.

        So we can see when odd count of odd numbers is there, parity stays same. But if even count, parity switches from 0 to 1 or 1 to 0. The same logic is there for Bob to Alice.

        so parity switch in recursion is defined as z' = (z+y+1)%2

        leetcode07 ayush002024 lbm364dl if it helps.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you. I understood it. To sum up, in general say you want parity $$$z$$$, and the total parity is $$$y$$$. To achieve this, the other player should get parity $$$y - z \equiv z + y \mod 2$$$, so if they don't want you to achieve your goal, they should try to get the opposite parity, which is $$$z + y + 1$$$.

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yep, that is the mathematical proof which is something I was missing with only the observations. Thank you!

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you please explain (z + y + 1) % 2 in your solution?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's wrong with my solution for problem A?

solution

»
4 months ago, # |
  Vote: I like it +13 Vote: I do not like it

I didn't realize that D was supposed to be a graph problem, and I think the problem can be simplified a lot. Basically, the original (unknown) array $$$a$$$ can be partitioned into subarrays that alternate between $$$\leq k$$$ and $$$> k$$$. For each element in a given subarray, the value it generates in the result is always the last element of the previous subarray. The only exception is the first subarray, which always generates either $$$0$$$ or $$$n + 1$$$, depending on whether it is $$$\leq k$$$ or $$$> k$$$ respectively.

So what I did was build a 2D vector, where $$$ind[i]$$$ stores all of the indices of $$$b$$$ that contain the value of $$$i$$$. Then each $$$ind[i]$$$ actually represents an entire subarray of the unknown $$$a$$$. The first subarray is either $$$ind[0]$$$ or $$$ind[n + 1]$$$ (exactly one will be non-empty). Given the elements of a subarray, exactly one element (the one that appears last in $$$a$$$) will be generated by the next subarray while the remaining elements (if any) will not be generated at all. So we can check each element of the current subarray to find which element $$$x$$$ has $$$ind[x]$$$ as non-empty. Then we need to ensure that $$$x$$$ is added last from this subarray, and then move to the next subarray, which is $$$ind[x]$$$. Repeat until we reconstruct the entire original array.

As for finding $$$k$$$, we can add elements from the $$$\leq k$$$ subarrays to a set. We can identify whether the first subarray is a $$$\leq k$$$ subarray (if it's $$$ind[0]$$$) or a $$$> k$$$ subarray (if it's $$$ind[n + 1]$$$) and then it simply alternates. The value of $$$k$$$ is the largest element in this set at the end.

My Submission: 174151773

It's possible that what I just described is actually identical to the graph approach (where this 2-dimensional vector is the adjacency list?), but I don't think any graph knowledge is necessary at all to easily solve this problem. At the very least, I think this is easier than either the $$$O(1)$$$ or the DP solutions for C...

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

terrible pretests for B, what is this trend of skipping common edge cases in pretests?

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

    Indeed, no matter whether you believe or not, we didn't realize why many people were hacked. We tried to list every kind of generator in pretests. But even some final tests were provided by real hackings you know?

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      the most common fst was not considering first index of prefix sum array being negative, did u guys really forget to include that basic edge case in pretest?

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

        No, actually, I think. The system already noticed us all boundary cases were contained by automatically checking.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          no, that case was main test 36 which is not in pretests, you can code a solution ignoring s[0] being negative and check if u want

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

      Pretest 2 didn't have any negative numbers; that was the main reason why there were hacks.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Someone Please elaborate about the second"NO" condition in Problem B.

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

    what's the maximum number you can place in the last n-k+1 elements it's the a(n-k+2) which you calculated. Now If the sum of last n-k+1 elements is greater that (n-k+1) * a(n-k+2), you would have to put at least one number greater than a(n-k+2), but then the array won't be sorted.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      does the n-k+1 elements also includes the first prefix sum element? also thankyou for replying ;)

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        it includes the n-k+1 element from the original array .. not the prefix sum because given last k prefix sums you can only find last k-1 elements. So the maximum number you can place in first n-k+1 positions is the element found for position n-k+2 or k-1th element from the last because we want to keep the original array sorted.

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

Here's my solution to G. I think it's somewhat similar to the editorial. It looks long and complicated, but I've tried to thoroughly explain the motivation behind it, the central idea is fairly straightforward, and I think all the steps are pretty intuitive. I hope it can help anyone confused by the main editorial.

Motivation Pt. 1
Motivation Pt. 2
Proof sketch
Implementation

My AC code: 174160936

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Video editorial of Problem D.

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

It is stupid that people so heavily downvote the editorial when their complain is not about the editorial

»
4 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Seems that people have complaints about FSTs, but If every solution passing pretests will also pass system tests, what is the purpose of pretests and system tests after all?

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

    system tests is just to ensure that some heurestics which is not the actual solution doesnt pass, it doesnt mean that edge cases which really should be in the pretests get missed out. Checking logic is more important than the ability to code edge cases

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Didn't know that. Thanks for replying!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

please teach my code wrong, i am stupid.(cry)174184654

»
4 months ago, # |
  Vote: I like it +20 Vote: I do not like it

I lost my GM account after the contest, for I didn't got F correct after some wrong attempts.

Very sad :(

»
4 months ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

Can someone see what went wrong in my DP solution in C? 174187246

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here is an example test case:

    5
    1 2 3 4 5
    

    The answer should be "Alice", not "Bob".

    When you initialized your DP, you set dp[2][1][1] to be false. However, if Alice picks the (only) even number, Bob has no choice but to pick an odd number, allowing Alice to take the other odd number and secure the odd sum as desired.

    Note: there might be other mistakes, but this is the one I found that explains the issue with this particular test case.

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

      Thank you! My code got accepted after changing dp[2][1][1] to true; that was a bit silly of me, could have gotten (back) to specialist if I AC'd that problem

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It's unfortunate that you missed it in the contest, but at least it works now!

        To be honest, there was no need to hardcode cases where an index is equal to 2. The furthest back that you check is with indices $$$i - 2$$$ or $$$j - 2$$$, so as long as you correctly initialize the cases where the index is $$$0$$$ or $$$1$$$, it should have been fine to build the DP from indices 2 onwards.

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

          That's fair too, but previously I had a different DP method where I would need to hardcode this. After figuring out (and implementing) the correct solution I thought that "it wouldn't hurt to just leave the base cases like this, right?", and damn I was wrong, it hurts

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

Really funny that I went overkill and did DP on C. Well an AC is an AC, I highly appreciate the low contraints though

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

    Thanks for understanding! That's also why I set low contraints to this problem.

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

    Personally, I still think the DP approach is much easier than the case analysis, since I don't think it is obvious at all as to what the optimal strategy is in each of these cases, or even to figure out that considering the number of odds modulo 4 suffices to characterize most cases. Either way, I think it's a good problem, and it's nice that both approaches are accepted.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, that's what I wanted, both approaches are accepted.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it -9 Vote: I do not like it

    I did DP as well but I was reading the input without taking the absolute value modulo 2. Therefore I failed miserably while the DP was correct lol. Rating dropped hard this contest. I also believe DP was more straightforward than the O(1) solution, good thing they kept the input small. After the contest I sadly submitted a correct solution.

    174190808

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

      I only do this absolute value modulo trick in first several problems, aiming at pointing out something that you might not take care of.

      I'm more happy to see you guys really learned something from this problem, rather than getting fake and useless contributions from announcement.

      Best luck!

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

        Yeah, I'll surely double check the constraints from now on. Many times going slow but steady is better.

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

      tbh, allowing the values to be negative in a problem where you need to check parity is kinda a jerk move, especially since it unfairly punishes those who happened to carelessly check if mod 2 is equal to 1, whereas those who carelessly checked if mod 2 is equal to 0 (like myself, actually) are unaffected.

      By the way, you probably already know this, but although it's okay to take the absolute value modulo 2, this would not work with a larger modulo, e.g., -4 mod 3 should actually be 2 (C++ gives -1, so you need to add 3), but applying the absolute value first would yield 1, which is incorrect.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I actually didn't know that, never had to deal with problems where I didn't use modulo on some positive value so far. Appreciate the information!

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

Beginner friendly dynamic programming solution using memoization for 1738C - Even Number Addicts.

174190808

\begin{equation} solve(o, e, w, a)= \begin{cases} w & \text{if } o = 0 \ \text{&} \ e = 0\\ max \{solve(o-1, e, !w, false), \ solve(o, e-1, w, false)\}& \text{if } \text{alice's turn} \\ min \{solve(o-1, e, w, true), \ solve(o, e-1, w, true)\} & \text{if } \text{bob's turn} \end{cases} \end{equation}

In the equation above, o represents the amount of odd numbers, e represents the amount of even numbers, w is the boolean variable that tells us if alice is winning and finally, a is another boolean variable tha tells us whose turn it is. Of course we are also using memoization to not re-calculate sub-problems. Complexity is $$$O(n^2)$$$, the size of the memoization table.

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

    That's why I set low constraints. Hope you guys not only know case works but basic DP ideas.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is the clearest and most intuitive solution that I have seen.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you :)

      It's definitely the most intuitive for my level, lol.

      Grandmasters' intuitions are built different.

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain the dp approach to problem c?

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

    Let dp[i][j][k = 0/1] be whether A can always get parity k with i odds and j evens. You can see that a move is considered winning if no matter what parity B chooses in the next move, A always have a way to win. Say if A chooses an odd number, it's a winning move if A can always win even if B chooses an odd number or an even number.

    Consider dp[i][j][k]:

    Case 1: A chooses an odd number, B chooses an odd number. This is winning if A can always get an opposite parity of k with i-2 odds and j evens, hence dp[i-2][j][1-k].

    Case 2: A chooses an odd number, B chooses an even number. This is winning if A can always get an opposite parity of k with i-1 odds and j-1 evens, hence dp[i-1][j-1][1-k].

    You can see that if A chooses an odd number, it's considered winning if dp[i-2][j][1-k] and dp[i-1][j-1][1-k] are both true.

    Case 3: A chooses an even number, B chooses an even number. This is winning if A can always get the same parity with i odds and j-2 evens, hence dp[i][j-2][k].

    Case 4: A chooses an even number, B chooses an odd number. This is winning if A can always get the same parity with i-1 odds and j-1 evens, hence dp[i-1][j-1][k].

    Using the same logic, you can see that A choosing an even is winning if and only if dp[i][j-2][k] and dp[i-1][j-1][k] are both true.

    Hence we get this dp formula:

    dp[i][j][k] = (dp[i-2][j][1-k] && dp[i-1][j-1][1-k]) || (dp[i][j-2][k] && dp[i-1][j-1][k])

    , and the answer of the problem is dp[x][y][0], where x is the number of odd numbers, and y is the number of even numbers in the array.

    Small note: if j < 2, then we consider dp[i][j-2][k] to be true (since it's not possible to have that particular sequence of moves), and it's the same for the others.

    Example solution: 174190925

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For F,I can't quite understand why we should choose an unvisited vertex u "with the largest degree" ? Can someone help me?

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

    I think the way it tones down is that we need to find all the connected components and then we can color all the elements in one connected component in the same color. ( because then s_c <= n_c^2 will always hold)

    If you dont visit the vertex with the maximum degree you might not find the connected components correctly, take for example the image attached below

    If you start with lets say the smallest degree, you will find the connected components as follows

    If you are confused why its colored like this, then lets say you start with 1 degree vertices you color them and their adjacent 2 degree vertices. Now you pick the 2nd degree vertices (lets say you take the orange one), you look to its right and you see the 1 degree vertex which is already visited, so you will break and not discover the middle vertex ( with 4 degree)

    But if you explore the maximum degree vertex first, you will end up like this

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

      !Thank you very much for your splendid answer!!!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hey my personal opinion but both B and C had unnecessary negative numbers, generally when giving questions involving performing division or modulus, not giving negative numbers is a good idea due to weird stuff in compilers where -1 %2 evaluates to -1. Luckily i didnt get affected in C (did in B) but overall it shouldn't be about who remembers how compilers calculate negative values which causes the difference between a AC and WA

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For 1738A - Glory Addicts, 174195503 using PyPy3-64 gives TLE, but 174196553 using PyPy3-64 (only difference being that the first one uses len() function and second one counts manually) barely passes

and 174196785 with same code as the first one but using Python3 compiler passes with some margin.

Can someone explain this sorcery to me :'(

I mean firstly why does manually counting instead of using len() is faster, and secondly why is python3 way faster than PyPy3 in this case, as the CF editor says PyPy3 will usually be faster

»
4 months ago, # |
Rev. 3   Vote: I like it +7 Vote: I do not like it

Some of the problems are bad.

Problem B:Just a template problem.

Problem C:Why just let n<=100 ???

Problem H:You can find the problem which is even harder than this problem.

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

It was my first contest. I could only solve 1, what is the rating of the first problem?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is still unknown. Usually, few days after the contest the problems get rated.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Okay thanks

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey Vito, could you please tell me the difficulty of Codeforces round. Are global rounds comparatively tougher than div3, div4 or equivalent to div2 or div1 ?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Let's say $$$f(x)$$$ is difficulty of Div.$$$x$$$ contest. $$$f(4)$$$ $$$<$$$ $$$f(3)$$$ $$$<$$$ $$$f(2)$$$ $$$<$$$ $$$f(1)$$$.

        In Global rounds there are more problems than in normal Div.2 or Div.1 round. The first few problems are of similar difficulty as typical Div.2 round first few problems. Last few problems in the problemset are usually harder than any Div.2 problems.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me find what's wrong in my solution 174220349 for Problem C?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Dear abhinav_99, you should replace if(a[i] % 2 == 1) with if(a[i] % 2).

    In C99 it is guaranteed that:

    if B != 0{ if A < 0 then A % B <= 0 if A > 0 then A % B >= 0 if A == 0 then A % B == 0. }

    After several contests, I found that when failing because of a wrong answer on test >=3, it is always some mild but annoying bugs, because you have already passed many big tests.

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

POV: you are rainboy

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

Weirdest thing is happening for my submission for A. I submitted my code during the contest and got TLE and left it at that, but when I optimized the code multiple times I was still getting TLE, so I went and checked the submissions of others and copied and pasted it(because I had written exactly the same code as that solution) and I am still getting TLE for some reason.

My Copied Submission

Original Submission by CF user

Why is this happening??

edit : I am also doing the same thing as editorial.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You're using PyPy 3 not Python 3. Does that make a difference? (I have no idea!)

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It worked!!

      Wow, I didn't know that PyPy3 and Python 3 would make this much difference. Also when I changed it from PyPy3 to Python 3.x.x it said below that PyPy is usually faster.

      This is the first time I used Python 3 during submission as well.

      Thanks a lot of pointing it out!!!

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

        In PyPy, input and/or output is slower. Adding the following 2 lines of code at the beginning makes your TLE code work in 280 ms:

        import sys
        input = sys.stdin.buffer.readline
        
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problemA my approach is very similar to the editorial's. But over here I get wrong answer for 3rd test case, although I get the correct answer in other compiler.

»
4 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

What is wrong with my submission for problem B? (174286190) Everything seems correct to me...

Spoiler
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

c problem,I can't find why is not passed test3?help help me 174499898

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Proble-C, can someone point out an error in my DP solution — 174134613. Thank you.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot! I made an error in writing a base case. I made sure to check the base cases like 4-5 times during the content... can't belive I did such a horrible mistake...

      Btw, what is this CF Stress?? It seemed interesting

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

        cfstress.com is a website I've created that helps you find the smallest counter example for all upcoming problems on Codeforces. You can be as specific as you want, for example

        Give me a counter example, where the number of test cases is 3, array size is 7 and array values are in range [2, 9]

        and it'd give you back a counter example if it exists. All you need to do is provide your submission ID.

        But of course, it's not free to use.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

liouzhou_101 can you please explain this statement ~~~~~ (z + y + 1) % 2 ~~~~~ from problem C

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What an excellent problem C! It brought me back to the my junior-high school time!

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

c ques can be done without dp.

although dp looks bit difficult to implement.

just used a if statement for this. here's my code. 174767387 if(n is odd then alice have to select the last move and if odd element is present then he must take that one) so,if array have one or two odd elements then alice loose otherwise always won.

and if n is even then alice losse only when 2 odds are present beacuse if he picks first odd then bob picks the other one and alice loose.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

my solution Can anyone please help me with why my A is wrong? I run the same code in local/ code chef.com/ide and it gives correct output for the test case where it is failing(test 1 test case 1). I have taken types 0 and 1 in two separate vectors b and c; sorted them; and started iterating from end, if we can get another type in front of this, I add this element two times else just one, looks like I have not missed any edge case as well. Any help will be highly appreciated. Thanks :)

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for this test case :

    4
    0 1 1 1
    1 10 100 1000
    

    vector b ==> {1} and vector c ==> {10, 100, 1000}

    lets take this part of your code :

    code
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Damn!! Thanks! Thanks a lot :), I read the code like 10 times and still couldn't find this typo :( I have always used ubuntu and now I have a windows machine, which I have not yet set up; so I use codechef.com/ide, it should've thrown an error :(

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

in problem C edututorial "b≡2(mod4) which we have already proved that Bob always loses" b≡2(mod4) which might bobs winning strategy.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please explain the intuition for the problem B?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why we mod by 4 in problem 'C'?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When I run this on Codeblocks the first test cases are correct. But after submission it shows different results on first test case. Why is this so?

175502330

It got accepted if I initialized the bool values in solve function. If I don't initialize them it doesn't work. Please, kindly share the logic behind this. Thanks!

»
4 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

UPD : understood the mistake.