Educational Codeforces Round 118 [Rated for Div. 2]
By awoo, history, 3 years ago, translation, In English

Hello Codeforces!

On Dec/01/2021 17:35 (Moscow time) Educational Codeforces Round 118 (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, Roman Roms Glazov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: Editorial is out

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

Comments Comments (238)
| Write comment?
»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Educational rounds are the best always good problems with good ideas

Good luck everyone and happy solving

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

    Bro why aren't the ratings yet updated?

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

      When will they update ratings?

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

        I guess we need to make some sacrifice to codeforces god for updating ratings

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

          The codeforces god was not pleased with your sacrifice so even the previous ratings are rolled back

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

    When will the Codeforces rating update?

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +79 Vote: I do not like it

I always had a question, How do you prepare educational contests so fast? Because creating new problems in one week is so difficult! awoo BledDest

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

    They have a lot of experience

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

      I know they are so experienced, But creating a new problem (actually a new hard problem which has standards of CF) is difficult, and I appreciate them for their hard work, Good job !

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

    They must have unlimited problem generator AI...

    → Reply
»
3 years ago, # |
  Vote: I like it -36 Vote: I do not like it

Hoping to become specialist after this :)

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A long wait of almost 10 days after this contest : ( Waiting for this contest to be awesome and welcoming the fellow coders to have great competition : )

→ Reply
»
3 years ago, # |
  Vote: I like it -21 Vote: I do not like it

Educational rounds don't charge penalty points for wrong submissions??

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

    The penalty for each incorrect submission until the submission with a full solution is 10 minutes.

    Maybe read the blog?

    → Reply
»
3 years ago, # |
  Vote: I like it +79 Vote: I do not like it

As a Romanian, it's pretty cool to participate in a Codeforces round on the National Day of Romania (which is today, December the 1st)!

Light-hearted meme
→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why codeforces has become speedforces from past 2 — 3 contests.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -46 Vote: I do not like it

Okay fine D is the best problem I have ever seen, like enough already

→ Reply
»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Just one question... Monocarp is some type of reference or the name of a famous person? I have also seen Polycarp

Maybe carp means something that I don't know in english

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

    Carp is a large fish that lives in lakes and rivers

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

    The name Polycarp (which is a usual Russian name, though an uncommon one) was very commonly used in contests made by authors from Saratov State University, namely MikeMirzayanov and his students. The name Monocarp (which is NOT a usual Russian name) was originally used as a one-time joke for one of the ICPC qualification stages in our region (as a reference to Polycarp), but later on, we chose to make Monocarp the main character of most our problems.

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

      Oh, what a story! I really didn't expected that.

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

      Was that inspired by Monogon? :)

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

        The first contest with Monocarp was in 2018, so, actually, Monogon was inspired by Monocarp.

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

    I used to read it as PolyCRAP and MonoCRAP

    → Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

The difficulty gap between C and D is just too much. C is too easy for its position and D is too hard...

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

    Also I found B to be easier than A

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

    Just try E

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

      how to solve E? i was trying bfs from lab vertex is that correct ?

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

        yes. You then just have to check that you don't have more than 1 dot as neighbour.

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

          i am doing that ,though getting wa on test 3.

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

            What you are doing seems quite complicated, I believe it's you trying to debug your code.

            my code should show that the approach works and is quite readable (just don't ask me why I converted chars to int to convert it back at the end!)

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

              thanks ,i got the mistake ,it was in the implementation.yeah it was very difficult to debug it ,thats why i was doing multiple submissions

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

              Comment partly deleted to reduceit's size since intimidator found his issue. not much value in it anymore and it took plenty of space in the thread

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

          realized it just after the contest...

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

      I had one approach like, mark all the free cell + except the cells that helps in forming a cycle within a matrix. Because, robot just not follow the command and will move in cycle infinitely.

      Is this a right approach ?

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

        Also you don't need to mark as + vertices that don't have a path to L. And finding all vertices that are on a cycle doesn't look like a very easy task.

        → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

Please list out the 7 sequences for sample test 4 in quest D

4

0 1 2 3

which satisfy

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

    I wasn't able to find them either

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

    [0], [0, 1], [1], [0, 2], [0, 1, 2], [0, 1, 3], [0, 1, 2, 3]

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      how [0,1,2] is valid?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 3   Vote: I like it +12 Vote: I do not like it

        we have b = [0,1,2]

        i = 1 -> mex(b[1]) — b[1] = mex(0) — b[1] = 1 — 0 = 1 <= 1

        i = 2 -> mex(b[1],b[2]) — b[2] = mex(0,1) — b[1] = 2 — 1 = 1 <= 1

        i = 3 -> mex(b[1],b[2],b[3]) — b[3] = mex(0,1,2) — b[1] = 3 — 2 = 1 <= 1

        Don't forget that mex(x1,x2,...xk) = smallest element that no appear in that sequence, mex != max!

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

        mex(0) = 1; |0 — 1| = 1

        mex(0, 1) = 2; |1 — 2| = 1

        mex(0, 1, 2) = 3; |2 — 3| = 1

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

    0 1 01 02 012 0123 013

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

    Same Doubt

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

    0

    0, 1

    0, 1, 2

    0, 1, 2, 3

    0, 1, 3

    0, 2

    1

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

    Wasn't it stated in problem description that here you can take any sequence? edit: nvm

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

    1) [0]

    2) [0,1]

    3) [0,1,2]

    4) [0,1,2,3]

    5) [0,1,3]

    6) [0,2]

    7) [1]

    → Reply
»
3 years ago, # |
  Vote: I like it +34 Vote: I do not like it

How to solve F?

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

    Let's solve it by inclusion exclusion principle, let's denote $$$f(x)$$$ as the number of permutations with at least $$$x$$$ edges such that $$$c_{child} = c_{parent} + 1$$$. The answer to the problem is $$$f(0) - f(1) + f(2) - f(3) + f(4)$$$... up to n.

    To compute $$$f(x)$$$ for some fixed $$$x$$$, $$$x$$$ nodes should have exactly one child with their value minus one (it is impossible to have more than one since it is a permutation).

    Let $$$g(x)$$$ will be the number of ways to select $$$x$$$ edges such that there are no two edges with the same parent node, this can be reduced to a knapsack problem, with the degrees as items, all $$$g(x)$$$ can be solved in $$$O(n\log^2{n})$$$ with divide and conquer and fft since the sum of all items is up to n.

    Finally, $$$f(x) = g(x) \cdot (n-x)!$$$ since $$$x$$$ numbers are equal to the number of their parents minus one, so there are $$$(n-x)!$$$ possible permutations.

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

      Thank you, can you please clarify a bit more on reducing the problem of selecting X egdes to knapsack problem? And how you can find all g(i) in O(n Log^2n) ?

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

        For each node, 1) you choose a child that has their value minus one (select one edge) 2) not choose any child (no edge selected) There are (number of child) ways to choose 1). By multiplying (x + number of child) for every node, we can get a polynomial which the coefficient of x^i represents g(N-i). Multiplying N linear polynomial can be done in O(Nlog^2N) using FFT and divide and conquer.

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

      How to proof f(x)=g(x)⋅(n−x)!, I just can't notice that...

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

        Also took me a bit of time to understand this. I think the proof below works.

        You need to prove that there is a bijection between a valid configuration (i.e. values that satisfy the parent-child constraint for each of the $$$x$$$ selected edges) and the relative ordering of non-child nodes (there are $$$(n - x)!$$$ relative orderings). Note: with child nodes I mean the children of the $$$x$$$ selected edges.

        If there is a bijection it means that both sets are of equal size, and therefore there are $$$(n - x)!$$$ valid configurations.

        To prove that it is a bijection we need to prove that

        • For each valid configuration there is exactly one corresponding relative ordering of the non-child nodes
          • Proof: Since all values in a valid configuration are unique, the relative ordering of the values of the non-child nodes within the valid configuration is unique.
        • For each relative ordering of the non-child nodes there is exactly one corresponding valid configuration
          • Proof: If we fix the relative ordering of the non-child nodes, then the relative ordering of the child nodes is also fixed. Because for every child node its order must be equal to the order of the parent minus 1. Therefore there is exactly one way to achieve a valid configuration starting from a relative ordering of the non-child nodes.
        → Reply
»
3 years ago, # |
  Vote: I like it -7 Vote: I do not like it

how to solve b?

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

    x mod y always gives values between [0,y-1] if we choose y as smallest element of the array then it is obvious that our requirements are met (given in the question)

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

      Ah wow, how did I not realize this.... :(

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

    take the smallest number as y in all pairs. since x % y < y it satisfies the conditions

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

    Just take y as smallest element in array so that remainder is [0 , y-1] which doesnt exists in the array

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is test 2 of D ? I cannot figure out the edge case i am missing.

→ Reply
»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Wasted a lot of time in D , could have done E instead.

→ Reply
»
3 years ago, # |
  Vote: I like it +23 Vote: I do not like it

For me, A > B and D > E. In other words, I felt E was easier than D and B was easier than A. Although A was easy too, just some bit of implementation.

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

    It was very easy to lose yourself into the implementation details of A and this is why I also felt like A was (much) harder than B.

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

      I guess much of A's implementation can be made easier if you consider x1 and x2 as strings rather than integers!

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

        That's actually what I did, as I struggled a lot with x1 and x2 implemented as ints, and then I thought: "screw it, I'm gonna do this cheap string trick"

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

        Or you can just subtract min(p1, p2) from p1 and p2, and then if min(p1, p2) + 8 < max(p1, p2), number who has bigger p is bigger, else you can just multiply x1 with 10^p1 and x2 with 10^p2, and check them like usual numbers.

        → Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Who thought that E was that hard and even harder than D man, that problem can be even a harder div2C, it's just a bfs.

→ Reply
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

I love the problem D, the solution is beautiful and it has two of my favorite subjects, combinatorics and DP!

→ Reply
»
3 years ago, # |
  Vote: I like it +43 Vote: I do not like it

Once again!!

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

    I found C easier than B , and i think my solution to B is terrible, because i used brute force and depended on the case (f[1]!=0) 137676564

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

    Bro C was just binary search. It was easier than most Cs we see in div2. I was surprised at how direct it was actually

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

      My purpose is to tell how hard D is compare to A,B,C :> i'm not telling that C is hard.

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -26 Vote: I do not like it

Question C could be solved with iterative binary search (https://mirror.codeforces.com/contest/1613/submission/137689165) but was giving TLE(at test case 5) with recursive binary search (https://mirror.codeforces.com/contest/1613/submission/137672043). This cost me 3 wrong submissions and a lot of time!

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is my first time attending cf contest!

Just curious that if I'm currently unrated, would this contest be rated for me?

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

    Yes.

    The rating takes a bit of time to be updated, partly becasue of the hacking phase. If you want an idea of your future rating, you can check cf predictor

    Edit : As beginners, since I am one too, I believe we shouldn't focus too much on ratings. Just start solving problems, enjoy and check where we land in a couple month =D

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

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

    Use dynamic programming. You can get that there are only some types in mex correct sequence. First of all, Thre are a sequence which starts with 0 and looks like 0 0 0 .. 0 1 1 1 .. 1 2 2 .. 2 ...(from 3 to n-1) n n .. n n n. In this case, you can expand this sequence with adding n, n+1, or n+2. Also, there is another type of sequence. which also starts with 0 and like 0 0 0 .... (from 1 to n-1) ... n n n ... n+2 n n+2 n+2 n n n (don't have to alternative, just after all, you should add either n or n+2) In this case, you can exapnd this sequence with adding n or n+2 Finally, you can think about this kind of sequence: which is composed with only 1, like 1 1 1... 1. count first two kinds of sequences with dynamic programming with dp[i][j]=number of sequence which ends with i and type is j(either first or second) and count last one with just counting the number of 1. number of last kind of sequence is 2^cnt-1

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

      I found this observation during contest but couldn't figure out how to implement in dp.Anyway I will now learn, thanks for help

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

        Once you get that observation, then I think checking with some cases(which are on the above)will be helpful to you. I also struggled with some wrong cases at first.

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

      1 1 1... 1 sequence could be a special case of 0 0 0 .... (from 1 to n-1) ... n n n ... n+2 n n+2 n+2 n n n . So there is only two types of sequences: MEX n with max n — 1, MEX n with max n + 1.

      → Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

any idea why this is wrong? this is problem C, I did binary search and pretty sure it is correct, but it gives wrong answer, ;_;

like I dont even get why 456 is not a correct solution for the last test case of sample tests? I am getting 456 as my answer to binary search and 456<470 (given answer) Help! please

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

    maybe you should use this: min((i+1<n?a[i+1] — a[i]:(int)2e18-a[i]),mid)

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

      Man, you are right!! Thanks a lot!!!! But what is the difference between the two? ;_; I dont think I would have ever been able to debug this.

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

        maybe you read the wrong question，the poison affect is refesh, not stack. And the time to kill dragon may bigger than 1e18

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

          Can you explain how the answer can be bigger than 1e18. I wanted to hack a solution because of this but could not come up with a case that has ans > 1e18.

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

            I mean the time to kill dragon may bigger than 1e18, not the ans. ans <= 1e18. if n = 1 and h = 1e18 and a[1] = 1e9, than the answer is 1e18 but you will kill the dragon at the moment of 1e18 + 1e9 — 1 which is bigger than 1e18

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

    a[i+1]-a[i]?

    Also (int)1e18 will overflow. Use long long.

    → Reply
»
3 years ago, # |
  Vote: I like it +39 Vote: I do not like it

Nice problemset, I enjoyed solving A-E! Looks like I'll also learn a lot from F once the editorial is published.

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -79 Vote: I do not like it

[Deleted]

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

    why??

    everyone knows that endl is slower than "\n"

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -51 Vote: I do not like it

      but not like more than 3 times slower

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

        actually, it's more than 10 times I guess. After I read this I changed my code from using endl to "\n", and the 2000ms tl become 217ms AC. Really learn a lesson in this problem.

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

    You learnt something new! What I would do after something like this, is try to find out why this happens. I would recommend you to do the same ;)

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Thanks to this contest that I realise "cout << endl" will get TLE for the first time 137704588 137708870

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

    That particular test case you are flushing the console 10^6 times hence TLE

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Is there any idea to solve F? I enjoyed A to E but I couldn't get some idea to solve F. I think there should be some combinatorical good theory to solve.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone knows why my submission for A is getting WA? As far as I know, it's mathematically correct but I can't figure out a test case that breaks it, thanks a lot. (The idea behind the solution is to represent both numbers as x+(10^p) and then take it log10 to reduce its size and compute the number) (also note that lli is defined as double)

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

    you use a and b as length, but then when you compare them, if you have a = b, you print equality, although this is equality of lengths, not numbers

    → Reply
»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

For those struggling with TLE at test case 16 in E , when printing out the grid change from $$$endl$$$ to \$$$n$$$ and TLE will be gone

→ Reply
»
3 years ago, # |
  Vote: I like it +124 Vote: I do not like it

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

Can someone help me better in understanding what i could have done better to avoid wrong answer for problem C?

Here is my solution -> https://mirror.codeforces.com/contest/1613/submission/137670768

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

    In check function value will get overflow when n = 100

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

      not really.He has added n+1-th element too.See in the main function

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

    v.pb(1e12);

    Here,because h can up to 1e18..that's why you are getting wrong answer

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

    v.pb(1e12) and h = 1e18 => ans maybe > 1e12

    "wrong answer 1st numbers differ — expected: '433940482775969078', found: '1'"

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

    Add 1e18 to your array instead of 1e12.

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

      Adding just 1e18 to the array wouldn't be enough, see https://mirror.codeforces.com/contest/1613/hacks/773649

      This contest offered so many amazing hacking opportunities. Weak pretests made the hacking stage very entertaining. And it's still not over, because the incoming system test (with all hacks included) is likely to claim even more victims.

      → Reply
»
3 years ago, # |
  Vote: I like it -25 Vote: I do not like it

E. 2000ms for 1e6 input == Downvote

→ Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I am not a detective, but this group of contestants looks sus fifijonil nexoxogoc ybgbsydvh ouhtek robot_bobot

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

Could someone explain why my submission to A fails?

I am converting both numbers to scientific notation and then comparing the numbers. Does it have something to do with errors regarding precision?

Update: Well I did not know about such precision issues. But it turns out the error in my program is actually in the while loops because I was not converting numbers to scientific notation. In my old solution, I have > 10 when it is should be >= 10. Here is an accepted solution of converting the numbers to scientific notation.

tldr: converting to scientific notation seems to be a valid solution to A.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Indeed it has

    eg. if I run this code

    double x = 0.1;

    cout << (x * 3 == 0.3) << endl;

    result is 0 (false) for me

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why getting wa in 2nd tc?

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

    you can't compare numbers after mod operation, order is lost.
    (7 mod 5) > (10 mod 5), but 7 < 10

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any standard concept for solving problems like C?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As this is a DIV 2 contest, why does nothing change, when ticking the box "show unoffical". Do I miss something?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hints for dp states of problem D?

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

    Edit: For thorough explanation: See my video explanation

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Video Editorial of A,B,C

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It was a great round, was able to solve 3 problems for first time in div 2 contest!!! Just had a confusion while solving A by generating the two numbers using pow function and using long long integer type , why did I get wrong answer on test case 2 ? Why did it fail, am I missing something?

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

    long long int is USUALLY (it depends on the compiler) coded on 64bit which means it's in a range -9e18 +9e18. To get the real limits, you should read <limits.h>.

    Anyway, in A, the exponent can be up to 10^6 so you will get numbers up to 1e1000006 which will overflow by a LOOOOOOOT,

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How does https://mirror.codeforces.com/contest/1613/submission/137705083 work but https://mirror.codeforces.com/contest/1613/submission/137689153 WA on Test 10? Is this a thing with Python, or specifically with the math module in Python?

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

    h can be up to 10^18. Numbers above 2^53 cannot all be represented exactly by floats, so you lose precision.

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

E was pretty easy compared to D..the setters should try to place problems at the right place.A good contest btw

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The heart is too anxious to miss green name. Too many penalties。 But the experience is better

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

Why don't you let $$$O(n\sqrt n\log n)$$$ pass F?

upd: I try my best to make it $$$O(n\sqrt n)$$$ and it finally passed.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope not to be heacked……

→ Reply
»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Where are the editorial for the problems?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Need help in question E.

Getting WA.

My approach was as follows.

1)Start BFS from Lab

3)While traversing push the co-ordinates of the cell which is free, only if at max there are 2 direction in which you can go(one of which will lead to lab).

Please tell what is wrong with my approach

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    try this testcase:

    1
5 5
##.##
.....
.#.#.
.#.#.
..L..

    All the . should be + in answer.

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

    Not max 2 but max 1, you should replace '.' with '+' after each steps to reduce it down to 1 (if possible)

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I love problems like F. It requires unique ideas and has simple implementation(if you have the code for FFT).

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm surprised that everyone uses BFS for problem E.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why my java code is giving tle for 'D' problem, it's giving AC in c++ 137748948

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just a small question, DFS on E gives runtime error while BFS passes. So in c++, cant we make 1 million nested function calls ? Does anyone know approx. what is the maximum number ?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

O(NlogN) for N<=100 solution C instead of expected O(Nlog10^18) https://mirror.codeforces.com/contest/1613/submission/137680384

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

Update: Ok it got hacked

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    input
    output
    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is a really good contest, especially problem D, what a amazing problem! Hope to do a contest like this again!

→ Reply
»
3 years ago, # |
  Vote: I like it -12 Vote: I do not like it

When will we get editorials?

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

    I guess it will be similar to past educational rounds? I don't get why people who have already participated in educational rounds keep asking the same sort of questions again and again? Do y'all run some script which posts some preset comments on recent blogs?

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

      you should learn how not to overreact on things unnecessarily

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

        I agree, maybe I could have stated my point a tad bit more politely. However, I am still curious as to why you posted the comment you did. Were you hoping for early editorials this time? If yes, then why? If no, then why the comment?

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So when are the ratings coming?

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

    Have patience bro and do upsolving because hope you was not able to solve all the problem.

    → Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Here are the video Solutions to the first 5 Problems in case you are interested.

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

First Submission
Second Submission

Submitted problem D twice, the only difference was in one line (I commented out "cerr << ..." in the second submission). Got idleness limit exceeded in the first submission. Can anyone tell me why this happened? And why did the idleness limit exceed on test 2, not test 1? Should it maybe be rejudged?

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

    Even though cerr output is not interpreted as the answer and does not get rejected as WA, it still causes a significant slowdown. The only mystery is why was this failed submission reported as "Idleness limit exceeded" instead of TLE?

    → Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Why aren't the ratings still updated?

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

My submission

can anyone find the flaw in my idea for problem D it passes 2 test cases and give WA on 3rd

my idea I used dp

the required sequence can be only of three types 0->0,1,2,3(consecutive) 1->0,1,3 (one skipped) 2->0,1,3,1,3,1,.....(alternating after one skipped)

so i created a dp[n+1][3] where first state corresponds to ending number of a sequence and second corresponds to type of sequence my transitions

  • for i>=2
  • dp[i][0]=(dp[i][0]+dp[i][0]+dp[i-1][0]);
  • dp[i][1]=dp[i][1]+dp[i][1]+dp[i-2][0]
  • dp[i][2]=(dp[i][2]+dp[i][2]+dp[i+2][2]+dp[i+2][1]+dp[i-2][2])
  • for i==0
  • dp[0][0]=(dp[0][0]+dp[0][0]+1)
  • dp[0][1]=0;
  • dp[0][2]=(dp[0][2]+dp[0][2]+dp[2][1]+dp[2][2])
  • for i==1
  • dp[1][0]=(dp[0][0]+dp[1][0]);
  • dp[1][1]=dp[1][1]+dp[1][1]+1;
  • dp[1][2]=(dp[1][2]+dp[1][2]+dp[3][2]+dp[3][1]+dp[2][2]);

can anyone explain why this is wrong

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

    And what is the result? sum of all dp[][] values?

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

    There is one main thing you are missing in this transition in $$$i==0$$$ case,
    $$$dp[0][2]=(dp[0][2]+dp[0][2]+dp[2][1]+dp[2][2])$$$
    Now, $$$dp[2][2]$$$ will store count of sequences ending at 2 and which are of the alternating form. There are two such sequences,
    1. 0 2 0 2 0 2....
    2. 0 1 2 4 2 4 2....
    But, you can append 0 to only the first type not to the second one by the definition of Mex-Correct sequence.
    You will have to change these transitions in $$$i>0$$$ cases as well because of this logic.
    One thing you can do is to make 2 separate $$$dp$$$ arrays(or increase the second dimension) to store these two types of alternating sequences.

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

      ohh now i understood what i was missing thanks for your reply Enigma20:).

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

        UPD:

        Finally got AC by using another dp2[n+1][2] this is to calculate alternating sequences of type 3.

        where first is the ending number of sequence and second specifies whether the ending number is increasing number of alternating sequence or decreasing number of alternating sequence.

        for example 1. 0 2 0 2 0 2.... 2. 0 1 2 4 2 4 2....

        here 2 is increasing number in alternation for sequence of type 1 and 2 is decreasing number in alternation for sequence of type 2

        Finally AC

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

How to solve E?

EDIT: I tried it to some extent but couldn't end up with a correct solution.

My main observation was that a cell will be only + if there are only two or one way to exit this cell for example x,y is a free cell and x+1,y is blocked and x-1,y is blocked so this cell can be a '+' provided it leads to the lab

so I ran a bfs starting from the lab. I enter only those cell which has only two ways or 1 way to exit it and I turn it into '+'.

But this solution is giving WA!

is my observation flawed or am I missing anything?

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

    you should compare the number of neighbors that is '+' or 'L' with the number of exit this cell, not just check the number of exit this, e.g.

    #..

    .L.

    ...

    although a[2][3] has three exit directions, it is '+'

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

can anybody help me? In problem D I have a solution based on dp[i][j] the number of sub sequece that i is the last number of Mex-correct subsequece and j is a type of Mex-correct (if j = 0 then mex of subsequece must be i — 1 otherwise of j = 1 then mex shuld be i + 1).

thus we have dp[i][0] = 2 * dp[i][0] + dp[i-2][1] and dp[i][1] = 2 * dp[i][1] + dp[i-1][1] + dp[i+2][0] but I got WA.

here is code

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Why Ratings are still not updated?

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Today is 2021，1202, which is a palindrome. we should celebrate it. wait for 20：21 in your time zone and see what will happen.(maybe a rating update)

→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

What has happened to Codeforces? The system testing is not over yet?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

During contest time I submitted my code and it was accepted on the second attempt. But after system testing I found WA because of TLE in the 7th test case. I found no reason behind it. Plz help me. Here is my submission link https://mirror.codeforces.com/contest/1613/submission/137660678

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

    Your code only passed weak pretests during the contest time. Then there was a 12 hours long hacking stage and people could freely submit their own stronger testcases (also known as hacks) to exploit various bugs and vulnerabilities in incorrect solutions. The final system test included all these extra testcases. Your solution failed to pass them.

    I suggest to look at the input data of the 7th test case and try to figure out what exactly killed your solution.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Imagine a test case of $$$t = 10^4$$$ and in each case $$$p1 = 1, p2 = 1000000$$$. In this case your code will run $$$10^6 . 10^4 = 10^{10}$$$

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

Ok so carrot is predicting +79 and i need +81 rating for cm. I dont think my copium can handle this.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will anyone please help me that why my solution for the question is getting tle in the 16th testcase. First I thought that in my code there is some infinite loop. So, to check it I changed my code specifically for case 1)m=1 2)n=1 and since, in this we only have to go in both directions from 'L'= lab until we encounter '#' or we have reached to the end of string. So I Directly use the while loop for that and still, I am getting tle. Its not clear to me whats the problem is. Link to my code.

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

    Just use '\n' instead of $$$endl$$$.

    And a good advice for the future, use $$$endl$$$ only in the case you want a flush, otherwise use \n

    → Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Is this Rated?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Rating is not updated yet. Moreover, previous contest ratings also has been rolled back. What's going on?

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

    Maybe someone in the headquarters was sleepy and instead of clicking on rating update he clicked on rating roll back . ( Not trying to disrespect anyone )

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

    You have been around long enough to know the drill. The only missing thing is a banner at the top of the site with a notification about temporary rating rollbacks.

    Looks like the plagiarism checks for the earlier Deltix round are almost complete and the scoreboard will be finalized soon with recalculated ratings. And then preliminary rating updates for the current round will become available too (followed by a rollback and finalization at a later date).

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

Rating ??

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

Kindly Update Ratings

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Div. 1 participants got a delta rating as well xD

→ Reply
»
3 years ago, # |
  Vote: I like it +50 Vote: I do not like it

Educational Codeforces Round [Rated for Div1 + Div2]

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Hurray! new rating!

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess there's something wrong with rating changes cause I should've got +147 delta according to cf-predictor but only got +71

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

    as you said , it is "predictor"

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

      looks like this trouble is not only mine so I believe predictor works fine with possible plus minus 15 delta diff

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is Mike high today?

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

    He just pressed some wrong buttons ig. Come on, everyone loves to play with buttons

    → Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Why aren't the problems still allotted to their difficulty rating ?

→ Reply