By awoo, history, 2 months ago, translation, In English

Hello Codeforces!

On Sep/29/2022 17:35 (Moscow time) Educational Codeforces Round 136 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Hey Codeforces!

Check out our video from our relatively new campus in Bangkok. Harbour.Space@ UTCC Bangkok is located in the heart of this cosmopolitan city where tradition and modernity merge!

We are breaking down boundaries and working together for a better, brighter, tech-driven future!

Bangkok is Southeast Asia's most exciting capital and the number one place for launching a start-up in Asia. Look at our incredible campus and hear from some of our rockstar students!



To find out more about Harbour.Space University, visit https://harbour.space/.

Also, do not forget to follow us on Instagram.

Good luck, Harbour.Space

UPD: Editorial is out

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

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

Educational Rounds are my all time favorite rounds!

»
2 months ago, # |
  Vote: I like it -15 Vote: I do not like it

Good Luck

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

Educational Round is always favorite <3

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

    Testers are tooo f*king dumb, PRETTY DUMB enough to let many people get "Hacked" on problem B

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

hope to become pupil this time finger cross

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

This is my first Educational round can anyone tell me exactly how are they different from normal contests?

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

    They are almost the same, as far as I know.

    2 Major differences I can tell is that Edu Rounds are used to introduce new topics(sometimes) and they are followed by 12 hours hacking phase(Just like Div4).

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

That harbour video is so damn cool

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

Educational Rounds are my favorite rounds.

→ Reply

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

[SPEICALITSS] I AM COMING! I HAVE [FAILRD]. I CANT PERFORM [good] IN [Educational Rounds]

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

why there is not a Scoring distribution in Edu contest ?

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

    I think because it's treated with ICPC rules, which means that you only care about the number of problems you solved and the penality.. solving an easy problem is the same as solving a hard problem.

    During the contest, if someone solved the hardest problem only, he will have less rank than someone who solved the easiest 2 problems!

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

      Let's say there are two persons A and B. Both solved 3 problems.

      A solved first 3 problems in 5, 12, 45 minutes. B solved first 3 problems in 10, 22, 42 minutes from the start of the round.

      Time is from the start of the round. Now i think rank of B is higher than A. Am i right?

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

        Not exactly, penalty of person is the sum of minutes of each problem. A's penalty is 5 + 12 + 45 = 62. B's penalty is 10 + 22 + 42 = 76. A's penalty is less than B's. So A is higher by rank.

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

          Thanks for explaining.

          Can you also explain how ratings are calculated in normal div 2 rounds Please.

          or maybe Ammar2001 whoever have time if possible.

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

            You welcome,

            In div2 rounds, your rank is determined by your total score only, but your score is affected by the problems you solved and the score of each problem and the penalty you have. In this case, harder problems have higher score and it's possible that solving 2 hard problems will give higher rank than solving 3 easy problems. (but most of the time solving easier problems is better because you solve them quickly)

            In those normal contests there is a score table on the right that tells you how many points you will get if you solved the problem at the current minute of the contest, and shows penalty for unsuccessful submission. (also scores for problems are announced briefly before the contest)

            You lose score for each minute you wasted to solve the problem, but I don't know how much score you lose. (you can see your rank and score in the standings)

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

        As Nxxlt said, $$$A$$$'s penalty is lower than $$$B$$$ so he is higher in rank.

        In this contest the rank is determined by the number of problems you solved, then if the number of solved problems is equal, your rank is determined by your penalty

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

          I think you explained better than me :D

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

            You did the math so you are better :D

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

top 2000 inshallah :)

edit: didn't do it, but good round anyway

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

lucky

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

is it green time?

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

Really hoping to get positive delta this round

Spoiler

Edit: +72 let's go

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

Edu rounds are amazing with daily life practical problems...

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

Hoping for interesting problems! Good luck everybody!

»
2 months ago, # |
  Vote: I like it -13 Vote: I do not like it

what if people don't know chess?

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

    They don't have to. You only need to know how knight moves which is already given in description

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

hope I can become specialist again!

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

hey is c++ not allowed ? I am unable to select c++ language .

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

speedforce...

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

Wrong answer on test 2 round (⊙_⊙)?

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

.

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

    I really like your confidence. But the answer is 3 only because you choose the edge (2,3)

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

    there are 6 nodes, in optimal situation we will break 3-4 edge, and add 1-4 edge, height is 3 (that is, 1-4-5-6)

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

    This is a chain from 1 to 6, right? Use the operation on vertex 4. Now, 1 has two branches: 1-2-3 and 1-4-5-6. The larger height is the latter, which is height 3. Note that height counts the number of edges from root to lowest leaf (not the number of vertices).

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

C is the worst problem ive ever seen

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

    i spent entire contest* solving C and still didnt get it

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

    the round is really bad and very constructive ,problems a,b,c are the most constructive problems ever i seen.

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

    It was annoying, and I couldn't find a solution, in my opinion the difficulty ramping for $$$C$$$ is too high.

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

What is the test 2 of problem D?

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

    exactly!! my solution using max heap which contained the heights of all branches of the tree and replacing the top element by its half was failing on test 2.

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

    I failed on test 2 and realized that removing a path is not guaranteed to generate two. Maybe you go further than me.

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

    you can try for this test case
    1
    5 1
    1 2 3 3 3
    ans = 2

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

made a wrong submission on A, did B fast but people are faster, well C stands for Combinatorics.

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

was c a famous sequence? i searched on oeis and find sequences that matches number of ways alice can win in the sample this is one of them: https://oeis.org/search?q=1%2c%203%2c%2012%2c%2042&fmt=data&sort=created + can anyone recommend where to learn and practice combinatorics? thnaks in advance

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

    the sequence is not listed. It would be 1 3 12 42 153 560 ... the problem needs less combinatorics than you think. nCr is enough already.

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

      oh thanks alot i will try to upsolve the problem its seems alot interesting even if i couldn't solve it during the contest

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

    I too wanna learn and practice combinatorics, this topic keeps coming back at me as much as I try to avoid it, if you get any resources please share them with me.

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

      yeah sure if i got anything i will share it with you but don't depend alot on this ( im tooo lazy to search)

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

Wish me my -150

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

It feels good,but the gap between B and C is a bit big:(

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

    Actually problem C is pretty interesting once you understand what's going on. Firstly, it's easy to find: If Alex has n, Alex must win; if Alex has neither n nor n-1, Alex must lose. Then, if Alex has n-1 but doesn't have n, it's equivalent to the condition that Alex doesn't have n-1 and Boris doesn't have n, that is, the SUBQUESTION where n=n-2 and Boris goes first. Then you can solve this question using resursion. BTW, I'm totally fall in love with Warma!!!!!!

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

      I totally understand this approach, thank you!I'm totally fall in love with Warma!!!!!!

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

    thinks the same, cause I solved D instead of C……

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

C is pretty fun once you understand what is going on.

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

    What is your logic?

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 5   Vote: I like it +13 Vote: I do not like it
      1. Save n = 2 as the base case

      2. For each n, we have two three cases

      • Alex gets n and Boris gets n-1 => So Alex wins by playing n in the first row. This case is (n-1)C(n/2) because we choose n/2 cards for Boris from n-1 cards (all cards except n, as we must give it to Alex)

      • Alex get n-1, but not n. This case is essentially the same as playing a game with n — 2 cards with Alex's and Boris' number of wins reversed. This can be proven (I will do that in a separate comment).

      • Alex gets neither n-1 nor n. In this case Boris wins because the game can be played as follows: Alex plays whatever, then Boris play n-1 (must be bigger than the card played by Alex). Then Boris plays n and wins. This case is (n-2)C((n-2)/2).

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

        Writing eloquently is an art and you sir are very good at it. I was thinking the same during contest but was not properly able to separate the cases.

        Thanks for explaining.

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

        could you also explain how ncrMODp was calculated

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

          Mathematically,

          $$$nCr = \frac{n!}{r!(n-r)!}$$$

          We have to do two things here:

          1. Calculate factorials $$$mod$$$ $$$p$$$ efficiently.

          2. Calculate the reciprocal of the factorials (for example $$$1/r!$$$).

          The first task can be done by defining an array of size $$$n$$$, call it $$$fact[i]$$$. Then build it up:

          fact[0] = 1;
          
          for(int i=1; i<=n; i++){
          fact[i] = (fact[i-1]*i)%p;
          }
          

          Task one is done.

          The second task requires some knowledge about number theory. I will give you first the formula that you can use, then expand on the number theory down.

          invfact[0] = 1;
          
          for(int i=1; i<=n; i++){
          invfact[i] = powMod(fact[i], p - 2);
          }
          

          where powMod(n, m) is a function that returns $$$n^m$$$ $$$mod$$$ $$$p$$$. If you need help writing this function please let me know.

          Using $$$fact$$$ and $$$invfact$$$ arrays, we can easily calculate $$$nCr$$$ $$$mod$$$ $$$p$$$ as follows:

          long long int C(n, r){
          if(n < r){
          return 0;
          }
          return (fact[n]%p * invfact[r]%p * invfact[n - r]%p)%p;
          }
          
          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            also

            $$${i^{-1}}\mod m={-{{\lfloor {m/i} \rfloor} \cdot {(m \mod i)^{-1}}}}\mod m$$$

            so we can pre-calculate all inverses upto N and then calculate inversed factorials using them:

            int fact[n], invfact[n], inv[n];
            
            fact[0] = 0;
            invfact[0] = 0;
            for (int i = 1; i < n; i++) {
                inv[i] = (i == 1) ? 1 :
                                    MOD - MOD / i * inv[MOD % i] % MOD;
                fact[i] = fact[i - 1] * i % MOD;
                invfact[i] = invfact[i - 1] * inv[i] % MOD;
            }
            

            and it will run in $$$O(N)$$$ time, not $$$O(N log N)$$$

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

          Speaking on number theory, we would like to show that $$$\frac{1}{a} = a^{p-2}$$$ (mod $$$p$$$), where $$$p$$$ is prime.

          What does it even mean to ask for a reciprocal modulo a prime?

          Asking about $$$\frac{1}{a}$$$ (mod $$$p$$$) is like asking what is the number $$$x$$$ such $$$a*x$$$ $$$=$$$ 1 (mod $$$p$$$)?

          The answer is given by Fermat's Little Theorem:

          $$$a^{p - 1} = 1 (mod p)$$$

          .

          Based on that formula,

          $$$1/a = a^{p-2} (mod p)$$$

          as desired.

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

        "Alex get n-1, but not n. This case is essentially the same as playing a game with n — 2 cards with Alex's and Boris' number of wins reversed. This can be proven".

        Because, notice that if Alex got n-1, his only option is for surviving is to play n-1 to get rid from n, because then Boris has to play n.

        Now, we have n-2 cards left, and its Boris' turn. So, number of win for Boris is same as the number of win for Alex with n-2 cards, and number of win for Alice is same as the number of for Boris with n-2 cards.

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

        Can't we do like this, first find all the ways to distribute the cards let store it in a variable name Y and find out of them in which the alex is gonna win and subtract it from Y and store it in a variable like X, then X-1 will be the no. of ways to boris to win as draws is always 1.

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

          There are $$$n \choose n/2$$$ possibilities. Even for $$$n = 30$$$, you likely would not be able to even enumerate all possibilities in 1 second, let alone check each of them to determine who is the winner. For $$$n = 60$$$, it would literally take decades to list them all.

          Also, without the important insights on characterizing the outcomes, how exactly would you be able to check who wins in a given configuration? You would still need to figure out the optimal strategy, and if you are able to do that much, it should be much easier to use that to directly calculate the answer, as opposed to trying to simulate it.

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

    please give me the tutorial please!!!

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

I think C is harder than D. How tf there are so many solved C?

D is binary search + greedy. C is greedy and DP. Imo C requires more thinking than D.

Mass cheaters make its so hard to track my progress. There's no way to know the true difficulty of a problem anymore.

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

    for me D is harder than C

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

    hey @algoboi can you please tell me how you have written the greedy function to check whether it is possible to make height <=x using <=k operations?

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

      binary search on minHeight, then calculate greedily on how much cost would take to reduce every path to smaller or equal to minHeight.

      Greedy can be done bottom up from leaves to root, and greedily remove a node and attach to root whenever height is > minHeight, There are a few edge cases so pay attention to that.

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

    To contestants who are strong at math, C would be far more routine than D (although I agree that D isn't terrible for its spot either).

    A common proof technique in math is "induction", which asserts that a statement $$$P(n)$$$ holds for every natural $$$n$$$ by proving that $$$P(1)$$$ is true, and if $$$P(i)$$$ is true, then so is $$$P(i+1)$$$ (there are several variants and this is just the simplest one).

    This problem leads itself to a similar approach since the top two cards automatically override all others, so the outcome is heavily influenced by them. Even if one just looked at the sample case with $$$n=4$$$, it would stand out that the first player wins if and only if he gets a $$$4$$$; the fact that the first player wins if he holds the highest card is easily extended to all $$$n$$$, and by considering how the first player could still win when the second player has card $$$n$$$ — forcing it out in the first turn — one can arrive at the solution naturally.

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

      Personally, I think $$$n = 4$$$ is actually a rather misleading case, since the "only if" part of the observation of A always having a 4 when winning does NOT extend to higher $$$n$$$. For me, personally, it was the $$$n = 6$$$ case that I had to carefully examine in order to construct the correct general statement that can be proved inductively.

      That being said, I think another challenge you're overlooking is that, even if one were to arrive at the correct relation, they still need to implement modular choice. In particular, this requires computing the modular inverse, either through the extended Euclid's algorithm, or through binary exponentiation by invoking Fermat's Little Theorem. So although I personally found C easier than D, I'm not surprised that many would find C to be more challenging.

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

        Yeah, I guess that I'm a bit spoiled with my math contest experience and took some concepts for granted (although I did specify that my experience is applicable mostly to those who know a bit of math). The "only if" part is debunked with $$$n=6$$$ indeed, as $$$12 \neq \binom{5}{2}$$$.

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

    For me as well, D was harder than C.

    You don't need Dp to solve C btw, I solved C just using combinatorics only.

    As for D, I though about a wrong approach and couldn't find the right approach during contest time.

    But it is really pathetic to see people live streaming contest during contest time

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

F too misleading for $$$\Sigma\le 12$$$. I've been writing mim for the whole round when at the end of the contest i realised my complexity is wrong. I'm so weak.

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

    WTF? Why does it have "too negative feedback". Oh I'm sorry that it's not suitable to let an unrated noob to talk about such hard problem.

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

please explain problem e

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

    I used recursive DP with memoization.

    Note that since there are only two rows, the robot will never move left no matter what, or even revisit the same cell again.

    There are several cases to consider:

    1. If the robot is in a cell, where the other cell in the same column is clean, then the robot will advance to the right (no way to change this).

    2. If the robot is in a cell, where the other cell in the same column is dirty, there are two possibilities:

    a) Clean up this other cell in the same column, so that the robot advances to the right.

    b) Do not clean up the other cell in the same column. If the cell to the right is dirty, then you would have to clean that right cell instead (to avoid the malfunction). Otherwise, this doesn't cost anything. The robot will move to the other cell of the same column and then advance right.

    Note that even when 2b doesn't cost anything, it may still be optimal to spend 1 cost to choose 2a, simply because allowing the robot to change rows may end up being expensive later.

    With recursive DP, find out which of 2a and 2b is cheaper (taking into account whether 2b will have an additional cost or not) and pick the optimal choice.

    Updated submission: 174002129

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

can anyone explain the approach for the C problem, first I found out the total number of ways in which cards can be distributed and then did total_ways/2 + total_ways/10 to count Alex's wins. this was working for all the sample inputs except the last, can anyone plz tell me the intuition

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

    If it's X's turn, 1. X hold's the strongest card can guarantee a win. 2. Otherwise, it becomes the same situation as X's opponent with n — 2 cards and in this case X plays second.

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

    Lets divide numbers as sections of four numbers 1 2 | 3 4 5 6 Alice can always win by taking the biggest number of current section. (here its 6). Again alice has chance to win in future if he takes 4, 5 not taking 6. Bob can only win if he takes biggest number in current section and one of the second or third higest number.

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

Nothing to say much.

It was my mistake that i participated in this round.

authors and testers have nothing to do with it. It was just my mistake that i participated in today's round.

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

how to solve D with binary search?

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

How to solve C ? I noticed that after calculating nC(n/2) (let it equalt to k) for n > 4, The number of ways Alice can win is 60% of k and the number of ways Boris can win is 35% of k and the number of ways to draw is 5% of k. Is this correct or just a coincidence ? I didn't manage to get it to work because modulus opeartions and other stuff, but I am asking about the idea itself.

  • »
    »
    2 months ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it
    • #draws = 1
    • nCr(n, n/2) are the ways to distribute n cards between 2 player.
    • Bwins(n) = nCr(n, n/2)-1-Awins(n)
    • Awins(n) = nCr(n, n/2)/2 + Bwins(n-2)

    Bwins(n) should be easy to understand. There are nCr(n, n/2) ways to distribute the n cards, and if you subtract the draws and Awins(n) from it, then you end up with Bwins(n).

    Awins is a bit harder. Let's get an example: n = 10, cards: 1 2 3 4 5 6 7 8 9 10

    we have 4 cases:

    • A has 10, A has 9 => A wins
    • A has 10, B has 9 => A wins
    • B has 10, B has 9 => B wins
    • B has 10, A has 9 => this has to be calculated:

    if B has 10 and A has 9, then A needs to play 9 to get rid of B's 10. Now the game becomes easier, because we now have a game with n = 8, same rules, just that B starts. Meaning we have the solution: A wins half the time plus the times B would have won if we played with n-2 cards = nCr(n, n/2)/2 + Bwins(n-2)

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

Solution for C:

The number of draw:

We notice it's always $$$1$$$.

The only distribution is:

$$$A$$$={$$$n-1,n-2,n-5,n-6,...$$$},$$$B$$$={$$$n,n-3,n-4,...$$$}.

The number of A win:

The distribution schemes are:

$$$A$$$={$$$n$$$,...} , $$$B$$$ ={...} , There're $$$C^{n-1}_{\frac{n}{2}-1}$$$ schemes.

$$$A$$$={$$$n-1$$$,$$$n-2$$$,$$$n-3$$$...} , $$$B$$$ ={$$$n$$$,...} ,There're $$$C^{n-4}_{\frac{n}{2}-3}$$$ schemes.

$$$A$$$={$$$n-1$$$,$$$n-2$$$,$$$n-4$$$...} , $$$B$$$ ={$$$n$$$,$$$n-3$$$,...} ,There're $$$C^{n-5}_{\frac{n}{2}-3}$$$ schemes.

...

The sum is $$$S=C^{n-1}_{\frac{n}{2}-1} + \Sigma_{i=3,5,...}(C^{n-i*2+1}_{\frac{n}{2}-i}+C^{n-i*2+2}_{\frac{n}{2}-i})$$$.

The number of B win:

$$$C^{n}_{\frac{n}{2}}- S - 1.$$$

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

    In fact, we don't need to calculate the number of times B wins, just output the total number of situations minus the number of times A wins and then subtract one

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

For problem C, I kept getting RTE with STATUS_ACCESS_VIOLATION on test case 1 (samples), even though my code (link) worked perfectly on my PC.

After 6 barely different submissions giving RTE, I hard-coded the dp and it ACed: link

Did anyone have a similar issue? Also, when does this error occur and what does it really mean?

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

https://codeforces.com/contest/1739/submission/173969835 What is wrong in my solution?? used all brain cells but didnt find the correct answer my approach 1) open the mod function 2) if (d[i] + a[i — 1] < 0) then take a[i — 1] — d[i] 3) if (a[i — 1] — d[i]<0) then take d[i] + a[i — 1] 4) if both are positive and are equal then only single answer will exist if not then multiple answer can exist

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

    let ans be the final array ,v be given array .then ans[1]=v[1] and from i=2 to n you can just check

    if ans[i-1]>=v[i] and v[i] > 0 then print -1 because you can either add or subtract v[i] which clearly shows multiple possible arrays.

    else ans[i]=ans[i-1]+v[i];

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

      i have also applied same logic but failed at Test Case 3

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

        try to remove unwanted statements and try to write smaller code so that you can check corner cases easily

        for example

        if (d[i] + a[i — 1] < 0) this statement is not required since given d[i] and a[i-1] both should be >=0

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

          yes i also found this that i have written unwanted code my code got accepted after removing unnecessary part thanks

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

Why is the binary search + greedy not working for D T_T

If anybody is interested in checking my sol

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

Is there a way to solve C without computing modular n choose k?

The way I did is precomputing nCk matrix (or using modular division algorithm) since theres only 60.

Consider n and n — 1, there are 4 cases where these 2 can bi distributed. Then just compute the nCk + dp to get solution for n.

How are there 3.5k AC on this problem?

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

    There are many good ways of computing n choose k.

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

    3.5k AC is possibly because there was a relatively recent contest problem (1717D - Madoka and The Corruption Scheme) that also required computing modular n choose k, so everyone who solved that problem (whether during the contest or afterwards) should be familiar with modular n choose k.

    EDIT: nvm, found another comment about the contest being streamed on YouTube... Cheaters gonna cheat >_>

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

    A guy has given the whole contest streaming on Youtube. link: https://youtu.be/SkkNIbKrjok

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

spent 1.5 hrs on seeing my rating fall

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

My Approach for C
- Find total ways to distribute cards nCr(n,n/2)
- # of ways for draw = 1
- Total ways for Boris = total — # of ways Alex wins — draw
- Calculate # of ways Alex can win

  • # of ways he can get card with value n nCr(n-1,(n/2)-1) plus
  • # of ways he gets cards with value n-1, n-2, n-3
  • otherwise alex gets cards with value (n-1,n-2) and boris gets (n,n-3) and no one wins in the first 2 rounds. So, this becomes same as finding # of ways for n-4 cards.
    »
    2 months ago, # |
      Vote: I like it +19 Vote: I do not like it

    C was more confusing than Inception.

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

    During contest this guy has given the whole contest streaming on Youtube. Here is the ID & proof link: https://youtu.be/SkkNIbKrjok cf id : https://codeforces.com/profile/libnguyen2 @MikeMirzayanov please take proper steps. Thanks

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

      I am not suspecting you, but how did you find out that? Didn't you search something relates to this contest on youtube and find out it?

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

        one of my friend told me that in every contest he found something illegals. Today he give me the prove with provided link.

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

          your friend is just genius

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

    Solution for D:

    Use binary search for the answer,the problem is transformed into:

    Use the least operation to make the height of the tree to $$$mid$$$.

    $$$(*)$$$Find the deepest node $$$x$$$,then:

    -If $$$depth[x]<=mid$$$,we don't need to do any operation.

    -Otherwise,we need to operate on at least one of the following nodes:

    $$$x$$$,$$$p[x]$$$,$$$p[p[x]]$$$,...,$$$p[...p[x]]((mid-1)times)$$$.

    We notice it's always optimal to do operation on $$$y=p[...p[x]]((mid-1)times)$$$.So we just find such $$$y$$$,delete the subtree of $$$y$$$,then come back to $$$(*)$$$.

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

      https://codeforces.com/contest/1739/submission/174007362

      Can u tell why it is giving TLE on test case 13

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

        You visited a node multiple times. Your code get AC after just modifying the 4-th line in dfs0(). 174008844

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

      Why can't we use a greedy approach from the root node? Let x be the current node. If $$$depth[x] > mid$$$, then we have to make a cut. By doing so, the height of x becomes 1 and the heights of the child nodes are then adjusted accordingly.

      174079619

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

        Consider case:

        5 1

        1 2 3 3

        When $$$mid$$$ is $$$2$$$,according to your method,node $$$4,5$$$ are cut and the cost is $$$2$$$.

        In fact,the optimal scheme is cut node $$$3$$$,which's cost is $$$1$$$.

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

          Oh I understand my mistake. Can you please explain why going from the deepest node towards the root node will always give the optimal answer?

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

            That's because the subtree of $$$x$$$ is contained by the subtree of $$$p[x]$$$.

            And if you cut $$$y=p[...p[x]]((mid−1)times)$$$,it will clear all the node in subtree of $$$y$$$.

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

    Well, I guess the colour is not going to change anytime sooner :(

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

    Ahahahah nice pretest for B

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

    what is this test case in problem D?

    wrong answer 1981st numbers differ — expected: '2', found: '3'

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

      6 1 1 2 1 3 3

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

      The test case is:

      6 1
      1 2 1 3 3
      

      But more importantly, see this submission to learn how I was able to discover this test case, so that you can reveal these kinds of test cases in the future by yourself: 174005886

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

      Thanks!

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

    hundreds of people watching youtube stream where C was solved...

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

    For problem D: I stored in an array the total number of nodes at each level. Then while k>0 I was finding the longest subarray with number>0 and I was turning the mid of that subarray to zero if depth[mid]<=k , otherwise I was reducing the search space to mid,n. Lastly I was printing size of longest subarray with elements>0.

    Can you tell if this intuition will work? My code was failing on one testcase. when it was skewed tree.

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

    Hackforces

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

    Well it looks like they just named a normal Div 2 round as Educational Round lol

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

    The test case for problem B was really weak!!!!!!!!!!

    »
    2 months ago, # |
      Vote: I like it -37 Vote: I do not like it

    Who also used Aho-Corasik in F?

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

      Reading such a comment when I struggled with C the whole contest and got hacked for B is honestly depressing and makes me think I am so far.

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

    if mistakes makes someone strong testers who tested b should be at least gm lol

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

    Weak pretests for B. A lot of submissions are hacked.

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

    How to solve problem C using DP ??

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

      If A has the $$$n$$$ card (highest card), A auto-wins. There are $$${n - 1 \choose n/2 - 1}$$$ such possibilities. Otherwise, if A has the second highest card, then A can play it to force B to play the highest card. After that, it becomes B's turn, with only cards $$$1$$$ to $$$n - 2$$$ in play, so we can use DP to retrieve the result for this smaller case (but note that B is the one who goes first in this case). Therefore,

      $$$DPAwins[n] = {n - 1 \choose n/2 - 1} + DPBwins[n - 2]$$$

      If B has both $$$n - 1$$$ and $$$n$$$, B auto-wins, since B can play one of them on A's turn and then the other on B's turn to win. There are $$${n - 2 \choose n/2 - 2}$$$ such possibilities. Otherwise, as described earlier, if B has $$$n$$$ but not $$$n - 1$$$, then A can force B to play $$$n$$$ and the scenario reduces to $$$n - 2$$$ but with B going first.

      $$$DPBwins[n] = {n - 2 \choose n/2 - 2} + DPAwins[n - 2]$$$

      (Note that if A has, for example, both $$$n - 2$$$ and $$$n - 1$$$, and plays $$$n - 2$$$ to force B to play $$$n$$$, this is still equivalent to the $$$n - 2$$$ case, because the $$$n - 1$$$ card that is still in play is now identical to a $$$n - 2$$$ card in terms of its relation to all remaining cards)

      The only scenario for a draw is if each player can force the other player to burn the highest card. So A needs $$$n - 1$$$ to force B to play $$$n$$$, then B needs $$$n - 3$$$ to force A to play $$$n - 2$$$, then A needs $$$n - 5$$$ to force B to play $$$n - 4$$$, etc. This is one single specific distribution of cards, so the draw answer is always 1.

      Of course, for the AC, you don't need to solve all three scenarios. Solving two answers (or guessing from sample tests that the draw answer is always 1) allows you to calculate the third (by simply subtracting from the total number of possibilities, which is $$$n \choose n/2$$$).

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

      lets say that we have the answers for n cards already calculated, and we want to calculate the answers for n+2 cards,

      Let's first notice that it's always true that: - there is only one distribution of cards that ends with a tie. - the number of distributions where the first player losses is equal to: choose(n, n/2)-(winning distributions)-(tie distributions). - then we only care to count the number of winning distributions for n+2 cards,

      now we have 2 extra cards to distribute between the 2 players, and for that we have the following possibilities:

      one of the players gets the n+2 card, and the other gets the n+1 card and the remaining n cards stay as they were when we only had n cards, so we add the count of all possible distributions of the n cards to the number of winning distributions of n+2 cards, which are equal to the sum of all positions of the n cards game, or can be also equal to choose(n, n/2).

          dp[n+2][win] += choose(n, n/2)
      

      now, what about when the first player gets the n+1 card and the other gets the n+2 card, then it can be shown that in that case in the first round, the first player must play the n+1 card in order to force the second player to play the n+2 card and prevent him from using in in the second round and winning, so after that initial round, we left with old n cards and a fresh game starts from the second player, so in order for the first player to win in the n+2 cards game, the second player must lose in the n cards game, so we add the number of loosing distributions of the n cards game.

          dp[n+2][win] += dp[n][lose]
      

      now we are done with the possibility that each player get one of the 2 extra cards, now let's think about the distributions when one of the two players gets the 2 extra cards, that player is absolutely winning, if he was the first player he can use the n+2 card in the first round, or if he was the second player, then he can use the n+1 card in the second round, so lets add those winning distributions of the first player to the answer:

          dp[n+2][win] += choose(n, (n+2)/2)
      

      in short:

          dp[n+2][tie] = 1
          dp[n+2][win] = choose(n, n/2) + dp[n][lose] + choose(n, (n+2)/2)
          dp[n+2][lose] = choose(n+2, (n+2)/2) - dp[n+2][win] - dp[n+2][tie]
      
    »
    2 months ago, # |
      Vote: I like it 0 Vote: I do not like it

    hackforces! :(

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

    Weak pretests! almost 2000 people have already got hacked.

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

      test case on which majority got hacked ??

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

        Problem B.

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

          Can I see the testcase that they hacked the solution with?

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

            That's out of rules

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

              Is it? The contest is over, so I don't think the no-communication rule applies now. There does not appear to be any rule that specifically forbids sharing hacks that could be inferred as applying to the post-contest hacking phase. Note that no points are gained from successful hacking.

              Although Codeforces doesn't reveal the hacks until the hacking phase is over, I don't think it's actually against the rules to share them during this post-contest hacking phase. Of course, the hacker can simply choose not to share, but I don't think there are any rule concerns here.

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

        1 2 2 2 ans=-1

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

      Did you mean 4000 people?

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

    weak pretests for B!

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

    How to solve E?

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

      Dp optimized with some datastructure.

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

        It's too complex. Just simple dp. See my code for further details.

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

          Very ugly dp. I hated writing it.

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

      I think it's actually quite a simple DP. Observe that the robot never moves left. Let "cost" refer to the number of cells that you clean by yourself, and we need to minimize cost. Let's say the robot is in row $$$r$$$ and column $$$c$$$, and the row that the robot isn't in is $$$\bar{r}$$$.

      If $$$(\bar{r}, c)$$$ is clean, then we can assume the robot will move a step to the right (you can think a bit about why this is a valid assumption for every scenario that satisfies this condition). There is no way to change this. The robot will then be at $$$(r, c + 1)$$$.

      On the other hand, if $$$(\bar{r}, c)$$$ is dirty, then there are two choices:

      1. You can choose to clean up $$$(\bar{r}, c)$$$. This has a cost of 1, and the robot will move a step to the right (as mentioned earlier), to $$$(r, c + 1)$$$.

      2. You can choose not to clean up $$$(\bar{r}, c)$$$, and let the robot clean it for you. However, if $$$(r, c + 1)$$$ (the cell immediately to the robot's right) is also dirty, then you need to clean $$$(r, c + 1)$$$ (cost of 1) to prevent the robot from malfunctioning. In this case, the robot moves to the other row, and then right. In fact, since $$$(r, c + 1)$$$ is guaranteed to be clean here, the robot moves right again, and is now at $$$(\bar{r}, c + 2)$$$.

      (Note about option 2: if you only consider moving to $$$(\bar{r}, c + 1)$$$, then you have to make sure the state of $$$(r, c + 1)$$$ is updated, which can complicate the implementation, but this can be avoided by moving further right to $$$(\bar{r}, c + 2)$$$ as observed)

      Use DP to get the answer for both of these scenarios and choose the minimum of the two. Here is my updated solution with simple recursive memoization: 174002129

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

        Hello,LightBrand99, can you please tell your intuition of how you even thought of 1739E - Cleaning Robot approaching with DP. Like during contest, I was thinking can we do something with multi source BFS.(just one of my random wild thought). I also thought of DP. Can we do it with DP but was mostly hit and trial.Actually was not sure what to do with it. And what demotivated me the most not to use DP was actually that I have hard time proving optimal substructure property.

        So how you think about DP. Was it only through developed intuition by solving previous questions or what fact/point you noticed in the question??

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

          I think intuition from past DP experience is definitely a factor, but I also think that the biggest hint for me was the observation that, when the robot malfunctions, it is because of exactly two dirty cells and not more. I did consider a greedy approach, but when I constructed a counterexample for that, I shifted to DP.

          Admittedly, my initial approach was actually incorrect, where I restricted the DP to only consider which of the two dirty cells of the same distance to clean up (not realizing that it could be beneficial to clean up a cell that isn't causing a conflict, simply to prevent the robot from changing rows). However, this approach still led me to the DP construction of always advancing to the right, but possibly changing rows. So after getting WA on test 17, I started to wonder why my approach didn't work, and then decided to generalize my DP to cover all scenarios where cleaning up a cell can affect the robot's behavior, and this extension was quite easy from my earlier (incorrect) approach.

          To be honest, I don't know if I could have come up with the general approach from scratch during the contest, if I did not initially think that my naive incorrect assumption (only clean a cell involved in a conflict) would work. So I suppose one suggestion I could give is that you shouldn't fully disregard ideas that you figured would not work, because you might be able to come up with a way to extend it to become correct.

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

            I got the point LightBrand99, you explained so well and clearly and have put your time into replying. Heartily thanks to you bro. Thank you very much .

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

    3000 successful hacks on Problem B and counting. The question itself is actually pretty good but yea, more extensive test cases would've been nice. That said, it is making the open hack phase more exciting/terrifying.

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

    Hello everyone. please ,anyone will say me that how can i stop a hacker hacking attempt of my solution in CodeForces. . If my accepted solution is hacked. It means that "Is my algorithm so weak" ? @ Mike Mirzayanov

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

      yes sometimes there a test case that is not covered by the testing and either your code

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

    can anyone give an example that makes this WA: 173977008 I changed the method and got ac, But I don't understand in what situations it doesn't work properly

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

    I hate combinatorics ;( how can I getting better ?

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

    [Deleted]

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

      What was the small mistake?

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

        Sorry, but that out of rules.

        If the tests were not weak, they would see WA and fix it fastly.

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

    Hacking on fire ......

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

    Very weak test cases for problem B :(
    got hacked because of small mistake '='

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

      Very weak "solution" for problem B :( got hacked because of a big mistake '='

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

    Can anyone helps me with this code 174016645 Problem D

    Thanks in advance ^_^

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

    deleted

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

    This round was a wow round (⁠ᗒ⁠ᗩ⁠ᗕ⁠) C was very interesting

    »
    2 months ago, # |
      Vote: I like it -8 Vote: I do not like it

    Waiting your solution of B to get hacked Pics-Art-09-29-10-38-58

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

    These edu rounds always kill my ratings, I am 2 out 13 now for positive deltas in Edu rounds. Usually I don't mind because I tend to learn something but B was rough.

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

    I tried to solve E and got WA for 2 times. Here are few hacking cases might help if you get WA on 17.

    10
    0100110001
    1100010010
    6
    13
    0001100010011
    0100100110001
    9
    
    »
    2 months ago, # |
    Rev. 3   Vote: I like it +10 Vote: I do not like it

    [DELETED]

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

    I think problem F should change "have first 12 letters" to 13 or 14. So that the complexity of search all possible permutation will be obviously wrong. I waste time to try searching, so it was a few minutes to accept.

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

    in problem C there's only 30 different input/output there are lots of people who just ran the code locally and hardcoded their answers. I wonder if that is against the rules ?

    [1, 0, 1], 
        [3, 2, 1], 
        [12, 7, 1], 
        [42, 27, 1], 
        [153, 98, 1], 
        [560, 363, 1], 
        [2079, 1352, 1], 
        [7787, 5082, 1], 
        [29392, 19227, 1], 
        [111605, 73150, 1], 
        [425866, 279565, 1], 
        [1631643, 1072512, 1], 
        [6272812, 4127787, 1], 
        [24186087, 15930512, 1], 
        [93489272, 61628247, 1], 
        [362168442, 238911947, 1], 
        [407470704, 927891162, 1], 
        [474237047, 614943428, 1], 
        [319176974, 87534470, 1], 
        [131938523, 955113935, 1], 
        [558075845, 644336680, 1], 
        [544270478, 253841470, 1], 
        [209493498, 700054910, 1], 
        [859106804, 457241336, 1], 
        [921005664, 6522991, 1], 
        [366933608, 353887625, 1], 
        [142064435, 432533537, 1], 
        [741221694, 874398972, 1], 
        [297907370, 545598131, 1], 
        [341102826, 248150916, 1],
    
    • »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I tried to apply PnC, left this question finally but many of the participants have this code only xD

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

      It is not against the rules. There is nothing wrong about it

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

      How did they come up with the numbers?

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

    I believe the pretests for Problem B could have been better. A lot of people got hacked because of a missing [ = ](equal to) sign.

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

      like 6 6?

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

        Most people checked the condition : input[i] - result[i - 1] < 0 to find out whether there are more than one answers. However it should have been : input[i] - result[i - 1] <= 0.

        And there were no tests to check this behaviour in the sample test cases.

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

          It depends on your solution, we have 2 ways to get result[i], arr[i-1]+result[i] it's always a valid solution but arr[i-1]-result[i]it's only valid if the result is non negative so it's obvious that it should be >= 0 Or maybe i didn't get you right

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

            The point is that the system tests should have ensured that solutions that did not consider equality would have failed. Note that this is an ICPC-style contest, so the system tests are supposed to be strong (unlike the score-based contests where pretests can be weak in order to encourage the hacking aspect of the contest).

            That being said, I think the purpose of the 12-hour hacking phase in ICPC-style contests is to allow the community to provide stronger tests that the contest organizers somehow overlooked. So it is likely that the tests not catching equality errors was actually unintentional.

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

      same here

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

    Amazed to see other contestants' Binary Search based solution for D. My first seeing of an implicit binary search in a tree based problem. Could not even think of binary search based solution. If anyone has encountered similar tree-based implicit binary search based problem, can you please share. Thanks.

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

    E is a good dynamic programming problem, it requires you to make good constraints on state transitions.

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

    I know the fact that Hacking Phase is a thing in Edu Rounds. But, for problem B, I guess test cases during contest should be a little more strong. A huge number of problem B got hacked. :(

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

    my code of 2nd question passed pretests during the contest but now submission of 2nd question is marked wrong? How is it possible?

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

      new test case added and pretest is weak

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

      This type of contest features a 12-hour hacking phase after the contest ends, where anyone can try hacking any of the submissions (i.e., provide test cases where they think the submission will fail). After this hacking phase, system testing will be performed, where ALL submissions will be judged against ALL tests, including the tests from successful hacks.

      Note that there is another type of contest where the hacking is done during the contest itself (so there is no 12-hour hacking phase afterwards), with successful hacks earning additional points while unsuccessful hacking attempts lose points. These are also the types of contests where each problem has its own score (so harder problems are worth more), and the submissions during the contest are only judged using relatively weaker pretests (and any hacks that are attempted, of course). For those kinds of contests, the system testing happens immediately after the contest ends, and it's a lot more likely for submissions to fail system tests (since pretests are not meant to be very thorough, and not every submission gets examined by an experienced hacker).

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

    A lot of solutions hacked in 12 hours. They are hacked because elements of array A can be equal to 0. So a lot of people forgot about "=" and write "<" (or ">" ) instead "<=" (or ">=").

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

    Educational missing education where's the tutorial ?

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

    why my problem B test time is so long? [submission:174082455][submission:174081857]

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

    What is the solution for problem D?

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

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

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

    can anyone help me in D 174111099

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

    Why my rating has gone

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

      "Rating changes for last rounds are temporarily rolled back. They will be returned soon."

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

    Hi .. I have submitted my own, ORIGINAL code in my unused, secondary account as I wanted it to have a better rating and it's an educational round. I also thought that violation is only cheating, communication, sharing ideas and other ways of getting help from someone else which I assure never happened. That's why I thought it was ok as it's my code and my account without the help of anyone neither helping anyone. Now I got violation of having the same code with someone else .. which is me but another account. Hope you appreciate it.

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

    Why is the rating rolled back after a week?