When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

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

Hello Codeforces!

On May/23/2022 17:35 (Moscow time) Educational Codeforces Round 129 (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!

UPD: Editorial is out

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

| Write comment?
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Educational Round are the best for me, good luck for all participant <)(>.

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

Goodluck all participants <3

»
22 months ago, # |
  Vote: I like it -11 Vote: I do not like it

hope I become a specialist today !!!! :)

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

    Solve 3 problems in less than 30 minutes of time.

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

      don't expose the secret technique of speed-solving experts :)

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

Can anyone guess what the rating range problem C would be??

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

    1400-1600

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

      I mean there has been Cs with 2000 rating like robot collision from Edu round 109, so trying to generalize ratings of problems could get you stuck trying to solve a problem that is way harder than what you think.

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

    I think it's like around 1200. Question difficulties have increased significantly to account for rating inflation.

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

Hope problems are less Ad-hoc and more algorithmic this time :/

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

Always love educational round.

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

I can not thank you guys enough. Thankyou so much for your efforts.

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

Educational rounds seems brainstroming to me. Does this happens to others also? But, Happy to attend these contest thinking one day these hard problems would be easy for me. Best of luck guyzz.

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

For the love of back to back rounds. <3

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

Hope that I will not mess everything up again.

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

    Hope you to become master and I can get specialist this round :>

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

    Considering your rating history, I don't understory what you mean by "again"

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

      Because of stupid mistakes like not opening correct array sizes or mistaking C for D,I lost 150+ points.

      I might have got top 100 if I didn't.

      TAT

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

    Your messing up is equivalent of my best performance

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

    I just lost my color.

    HackingForces

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

Thank you for the contest

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

Probably one of the best question sets this year!! However, I made a typo on question C which costed 20 minutes and 4 penalty attempts :(

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

Only solved A-C again :(

Maybe I should have a rest……

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

    Relatable :(

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

    D is just such a frustrating problem I hate it so much. Eventhough I solved it took me an entire hour to realize it is just a stupid bruteforce. it was not fun at all. so it's not your fault

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

      How do you prove bfs will not time out though?

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

        I did a bfs, but only took the 10000 highest numbers after each step. Have no proof that this yields always the correct answer (although I have a strong feeling that it does), but for sure this won't time out. (And just now I noticed, that I forgot to erase duplicate numbers. Uh-Oh...) 158202121

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

          It even works if we take just the top 5 numbers after each step. I am a little surprised.

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

        That was my problem the entire time! but after proofing by AC I think you can prove it this way: so because multiplication is commutative (i.e. 5*3 =3*5) then the order of the digits you use doesn't matter. How many numbers you can multiply by so that the result doesn't exceed 10^n? not that many as you are only using digits between 0 and 9

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

        Numbers which will increase x are from 2 to 9 in which prime numbers are 2,3,5,7.

        So x will eventually turn into x*( 2^a * 3^b * 5^c * 7^d ) after some number of operations.

        As we all know 2^63, 3^39, 5^27, 7^22 are all close to 10^19.

        So 64 * 40 * 28 * 23 = 1648640 are the number of different numbers that can be made.

        In this I have considered all the numbers which can be made using these combinations of prime to the power of some number. Which will not be the case in the real brute force implementation. It will close out at about 1e5 or so.

        There's your proof.

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

          Great! I think there is a tighter upper bound.

          If we simply see that (a + b + c + d) <= 64 (considering a = 64, b=c=d=0). So, the numbers possible is found from this formula — (N+R-1)C(R-1) i.e (64 + 4 - 1)C(4-1) which approximates to 47905.

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

    I think it's just the fact that it's Educational round. You can see my contest history, and literally from each educational round I consistently have negative delta. And they also have an "individual" feature of FSTing and a lot of hacks each time.

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

Educational speedingforces

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

Dude, really 6500+ people solved C?

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

    Yeah, coz n^2 is also allowed

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

      I fiddled like half an hour on a nice solution before realizing that stupid bubble sort also works.

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

        lmao just realized this. I wrote a solution that uses a n queries at most. It was not much write though

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

        actual selection sort.

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

Speedforces

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

What was the approach for D? Weren't we supposed to multiply the number by its biggest digit each time or I am wrong?

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

    I solved it using maps and DP, not sure if there is a greedy solution for it

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

      Proof that this wont give TLE?

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

        Well, this will require a lot of thinking and tracing, and honestly, I'm not very convinced but I would say that since I'm starting with one number for example 123 and I want to try to multiply it by 2 or 3, no matter what is the result they will all be divisible by 123 so the chance of duplicates is very high.

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

          no how does this matter? You can have so many numbers that are divisibl by 123 up to 10^19. it's \floor{10^19}/123>= 1e^16. I think it has to do with the fact that you only use digits and that you multiplication is commuitative1. __

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

      I thought about DP, but wrote greedy which works in $$$O(2^n)$$$. (On every step choose from 2 different maximum digits). Surprisingly it got AC.

      EDIT: Hacked :D

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

        why the limit of 1000 ?

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

          Just a number which is bigger than possible maximum answer (if we take 2 on every step, there will be maximum $$$log_{2}(x)$$$ steps.

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

        lul.. that's why you should never reveal anything "surprising" about your approach while the hacking round is still going on.

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

          No. My main mistake was to think about E/F tasks instead of resolving D in proper way, while I had a feeling my intuitive solution is wrong. Someone proved this, and it's good, I don't really care about color.

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

    If you always multiply by the biggest number then you might exceed n

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

      No this will never happen as each time you can at most increase the size by one. The problem with the greedy approach is that it might lead you to a number that has digits of low values, so it is the same problem with "good localy, bad globaly"

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

    you can't even pass given testcase by that greedy approach..

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

    No bro, the counter example is given in sample.

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

      Yeah thats what I am saying. However Im asking about the logic overall.

      In my head we get the best result while multiplying number by its biggest digit. Isnt it correct?

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

    test case : 13 42

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

    6 -> 7 is better than 9 -> 3 so you might multiply by a lower number at first in order to gain better number in the future

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

    123456789x9=1111111101 and you're stuck :D

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

What's the proof for C???

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

    it's a swap so between any two indices so it won't take more than n steps. (unless I get hacked)

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

    first forget about the values, after some swaps you'll attain a permutation of the indices so any permutation that works for both a and b is good, let us sort a first and then check if we can sort b without ruining the first sort(only moving elements with the same value), this process produces a new permutation and what's left is to check it

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

I think today's contest was easy as compared to normal Div2 rounds

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

I spent 30 minutes thinking that C could be solved greedily, then I said let me just try to perform the K swaps no matter what, and it passed LOL

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

What was the idea behind E and F?

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

    I used binary lifting in E. We just maintain the dp array of $$$jmp_{i,j,k,l}$$$ which represents the minimum distance moving $$$2 ^ j$$$ from the ith section first using the kth door of the ith section and ending up at the lth door of the $$$i + 2 ^ j$$$ section

    EDIT: Sorry for being ambiguous in the original response

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

      Binary lifting what, and in which problem?

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

        You can use binary lifting for E, it's similar to the idea for BOI 2017 Toll.

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

      Can you elaborate how do you count the binary lifting array?

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

    In E binary-lifting or $$$SQRT$$$-decomposition can be used. I tried the second but failed to make it accurate and correct (as usual).

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

God damn it! So everyone knew how to solve F except me. I lost my chance to became Master.I'm so sad now....................

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

    similar nickname,same hacked on Problem D :(

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

Can anyone hack me? Unordered map Your text to link here...

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

How to solve F?

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

    You can consider each $$$x$$$ separately. You can compress nodes connected by non-$$$x$$$ edges to get a new tree for each $$$x$$$. A pair of nodes $$$u, v$$$ has $$$x$$$ as a unique occurrence only if $$$u$$$ and $$$v$$$ belong to adjacent nodes of the new tree of $$$x$$$.

    To build the tree efficiently, iterate through all original tree nodes in decreasing order of depth and simultaneously build all the new trees. When you encounter a node $$$u$$$ for which the edge connecting it and its parent has value $$$x$$$, search for all components of $$$x$$$ already existing within the subtree of $$$u$$$, and join them to get a new component of $$$x$$$.

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

What's the intuition behind D??

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

In task D, How to know that memorization in a map will not exceed time limit?

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

    I also used the map, but it passed the pretest. I hope it will also pass the system test

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

    Even if you multiply by 2 everytime you will reach n digits extremely fast. This along with the fact that you can multiply by only 8 distinct number assures that the number of states transitions are actually quite small.

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

      no it does not. If you can multiply 8 distinct digits to get 8 distinct products, that has a very high upper bound. The map solutions have passed as the number of "distinct" numbers encountered, the "X"s are limited. That is different from what you meant to say.

      Edit: Explanation below makes more sense.

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

        You're right. I believe the 8 numbers fact is more prominent in a way that it limits the number of transitions from one state greatly.

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

    Just notice that any value $$$y$$$ that will be reached can be represented as $$$y = 2^{\alpha}3^{\beta}5^{\gamma}7^{\delta}x$$$ and realize that the total possible combination of the quadruple $$$(\alpha, \beta, \gamma, \delta)$$$ is loosely upperbounded to $$$log_{2}z * log_{3}z * log_{5}z * log_{7}z = 60 * 40 * 26 * 21 \approx 1.5 \times 10 ^ 6, z = 10 ^ {n - 1}$$$, but obviously didn't prove during contest

    EDIT: Made the explanation a bit clearer.

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

Trash E.

It only takes me 5 minutes to manage out a way to solve it using something like Matrix multiplication and Segment Tree or binary lifting.

But there are TOO MANY GOD DAMN DETAILS that I failed to accept it before the contest ends.

I hope there will be more brain-consuming problems (maybe greedy or constructive ? ) instead of such complex and meaningless ones.

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

    +1, the detail are nightmare to follow, I kept getting WA on test 5 :(, but since it's and edu round it completely deserves to be their.

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

I use DFS to solve problem-D, but get TLE. :D

158223688

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

    You need to use memoization to avoid visiting the same values multiple times (which can happen).

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

      yes, it should use memoization, so BFS + memoization, not DFS + memoization.

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

        I used DFS + memoization. Worked ok. I guess you could try to hack me :)

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

          oh! I get AC with DFS + memoization 158229644, but I think BFS is more better, because if DFS always meets bad answer firstly, then memoization does't work.

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

            Well, as I say, I used memoizaton and haven't been hacked yet. Why do you think it doesn't work?

            I simply called a 'bad' answer very big (1e9) and then said if my final answer was >= 1e9, then output -1.

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

      Hi @jimm89. I tried DFS too. Got TLE. Used memoization and it worked. Its kinda weird that you need memoization for this. I initially thought the probability that you will encounter a value you encountered before is so low. I thought the overhead for using a map would harm more than it will help but it is the other way around :-) I was just curious if I will need memoization for BFS as well.

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

        I expect you would not need memoization for BFS.

        I saw that tourist submitted a DFS solution with no memoization, but with sufficient pruning so as not to TLE. I suspect he knew it would not TLE, but did also wonder whether that was due to instinct from vast experience or whether there was some underlying (very fast) deeper thought process. Effectively the solution tries 'higher digit' paths first and then also eliminates any path which could be longer than the current best answer.

        For that reason, I am confident that BFS is fine without memoization, since you will only visit paths shorter than or equal to the best answer.

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

Can someone share the approach for problem F ,how to solve it using disjoint sets

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

    you may google "dynamic connectivity problem (offline)"

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

Why are there orange people in the official standing?

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

Can we solve F using smaller to larger technique ?

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

What a bullshit D.

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

    If I solved that shit, I would achieve performance of IM because I solved ABCF before. But now I even lost my rating.

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

First time solved 4 problems in div 2

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

What the meaning of D? I can't imagine the reason to put a rubbish standard dfs in the place of D.

Is it so hard for you to simply delete this problem? I can come up with hundreds of problems like this.

And for the difficulty, many people can't solve it just because they aren't dare to use such a stupid method in fourth problem. Why not put it in the place of A?

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

    that's sums up my feelings. If this was C, people would have done it faster and lots more people would have solved this.

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

    The point of D is to be a problem on implicit BFS/DFS/dynamic programming where it's not so obvious (but easy to prove) that the solution is fast enough. I don't think that your claim "they don't dare to use such a stupid method" is correct; proving that it works is not difficult.

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

      I would guess that most the people who solved it didn't actually prove that the number of states is small enough.

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

      It is true that the dfs solution can be proved to be fast enough. However, this is a programming contest, not a math contest. Most people who passed this problem during contest didn't think about what the complexity will be, they just tried dfs and it worked. The aim of the problem is to separate people who can come with a method and who can't, not "Here is an easy way to solve the problem. Can you prove it?" This way it will be more like a math problem. The proving part is important but that's not something that should be asked in contest.

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

        You say "Here is an easy way to solve the problem" as if it's written in the problem statement that you should use DFS/BFS/something other there. I agree that this problem is on the easy side for ER D, but I don't think it's C level.

        I don't see anything wrong with some participants guessing that the method works without any actual proof. This is fairly common even on high-level contests. As long as the proof doesn't take five full pages of formulas (I mean, it's definitely possible to come up with the proof in a short period of time), it should be fine, in my opinion.

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

          I am not familiar with what the difficulty of ER D should be, maybe some of my opinions are biased. I am just expressing my confused feeling after solving this problem.

          Actually, I would really appreciate if the problem is changed to "Count how many different numbers $$$\le N$$$ could be reached by using this function."

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

          By the way, I do think that the problem statement directly points to the dfs solution because that's just something everyone will come up with after seeing the problem.

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

            Judging by the results of our local competition where I used this problem yesterday, it's not the case. Some of our students definitely recognized a graph problem fairly quickly, but not all of them, even those who are kinda familiar with DFS/BFS.

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

      In fact I used pruning instead of memoization. 158184259

      This shows another problem: you can get accepted using whatever approach you want as long as you dare try the easiest dfs.

      So, I think his claim "they don't dare to use such a stupid method" is totally correct since I don't think a lot of people actually proved it. The people who solved it are probably just like "okay, let's try dfs. Test 19 42 and the answer came out immediately so submit!"

      This way of thinking is definitely not good for ER D.

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

Kind of sad that $$$O(N (\log{N})^2)$$$ approaches passed in F.

I initially had an interesting $$$O(N^2 \log{N})$$$ solution where I run a re-rooting DP on each edge weight separately, to calculate contributions of that edge weight (a range sum data structure was used for this, thus the log factor). I sped this to $$$O(N \log{N})$$$ by using the DFS times for each node and simulating the DFSs for each edge weight by just looping along occurrences of each edge weight in the DFS order, using only $$$O(\text{occ}(x) \log{N})$$$ for each weight $$$x$$$, where $$$\text{occ}(x)$$$ is the number of occurrences of $$$x$$$.

Edit to add:

Since people seem confused, I will explain my solution in some more detail. Firstly the $$$O(N^2 \log{N})$$$ idea. First root the tree arbitrarily. Now, we find the contribution for each edge weight separately. I will describe how to calculate the contribution of edge with weight $$$x$$$.

Notation:

$$$\text{comp}(u, x)$$$ is the size of connected component of if only edges with weight not equal to $$$x$$$ are considered, $$$\text{sz}(u)$$$ is the size of subtree of $$$u$$$, $$$\text{par}(u)$$$ is the parent of node $$$u$$$, $$$\text{anc}(u)$$$ is the set of proper ancestors of $$$u$$$, $$$\text{sub}(u)$$$ is the set of nodes in subtree of $$$u$$$.

Define $$$\text{dp1}[u] = \text{comp}(u, x)$$$ if the parent edge of $$$u$$$ has weight $$$x$$$ and $$$0$$$ otherwise. Similarly, define $$$\text{dp2}[u] = \text{comp}(\text{par}(u), x)$$$ if the parent edge of $$$u$$$ has weight $$$x$$$ and $$$0$$$ otherwise.

How to compute $$$\text{dp1}[u]$$$? Some careful thought yields:

$$$ \text{dp1}[u] = \text{sz}(u) - \sum_{v \in \text{sub}(u), v \neq u} \text{dp1}[v] $$$

and

$$$ \text{dp2}[u] = n - \text{sz}(u) - \sum_{v \in \text{anc}(u)} \text{dp2}[v] - \sum_{v \notin \text{anc}(u), v \notin \text{sub}(u)} \text{dp1}[v] $$$

With these expressions, $$$\text{dp1}[u]$$$ can simply be computed with DFS and a range sum data structure (on the Euler tour of the tree). After computing all values of $$$\text{dp1}$$$, the $$$\text{dp2}$$$ values can be computed with DFS and a range sum data structure, noting that $$$dp2$$$ value of a node $$$u$$$ will be used when $$$u$$$ is an ancestor and $$$dp1$$$ otherwise. So, these values can be switched in the range sum data structure during DFS.

Contribution of weight $$$x$$$ is simply $$$\sum \text{dp1}[u] \cdot \text{dp2}[u]$$$.

How to make this $$$O(N \log{N})$$$? Well, since only particular $$$dp$$$ values are ever non-zero for a weight $$$x$$$, we can simulate the entire process by just looping over the positions of these nodes in the DFS order.

Code: 158206764

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

    samjh nhi aaya pr sunke aacha laga

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

    I initially had an interesting $$$O(N^2 logN)$$$ solution where I run a re-rooting DP on each edge weight separately, to calculate contributions of that edge weight (a range sum data structure was used for this, thus the log factor).

    You can improve this solution to $$$O(N)$$$.

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

    I am trying to Solve Problem F using centroid Decomposition.

    Timecomplexity should be : $$$O(N(\log(N)^2)$$$,But I am getting TLE on TestCase 45.

    MySolution:158262510.

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

    I have $$$O(n)$$$ solution of F

    For each value of $$$w$$$ from 1 to $$$n$$$, break all edges which have weight $$$w$$$. The tree will break into connected components. Now for each pair of "adjacent" connected components(i.e. components which were connected by the broken edge) you need the number of paths starting from one component and going to other. If we store everything in dfs order, then this can be accomplished in $$$O(n)$$$. It is not that painful but my implementation is a bit messy.

    https://codeforces.com/contest/1681/submission/158273456

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

Problem D was so frustrating. Still can't figure out why DFS would work?

Also, can anyone point out what is the issue with the idea of always multiplying with the largest digit in X? This should give the largest possible number in some number of moves, right?

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

    I initially applied DFS but it was giving WA on test 3. Tried BFS and it worked

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

      But why did it work? From what I can think of, we have 10 different possible states to go from each number. Talking in terms of Tree DS, we have a rooted tree of depth ~20 and each node has 10 children. This leaves us with around 10^20 leaf nodes.

      Is that even possible to solve?

      Is there any special structure to the problem which is not considered in my analysis?

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

        I donot know how to prove it but it got ac. I think some values will repeat in sequence so you do not need to process them, and hence the solution will pass in time. I tried to test it, at max only "4833" values were inside my queue when it reached level 19.

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

158229061 what should I add for this D problem submission so it will work? Or at least give TLE..

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

    Note that it is not always optimal to multiply by the largest digit every time.

    See this comment (and maybe work it out on paper too).

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

      But that’s basically what dupl vector and for loop is for. Am I wrong?

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

        Yes -- it looks like you are keeping track of what digits appear in a single current number and then picking a digit to multiply by based on what maximizes the next number.

        What I am saying is that this decision of taking the largest of the results is not globally optimal.

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

The contest is nice but there are plz skip them ... bcz problems A B and C are in Youtube !

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

I think I solved E during contest but was lazy to implement (though might TLE in theory). Tell me what you think.

I looked at the doors as a layered graph. Each layer has 2 nodes (doors), and there are only edges between nodes of adjacent layers (the distance in the matrix between the doors of consecutive layers). So in total there are 4 edges between 2 layers.

Now for the preprocessing, I want to calculate the distance between the doors of special layers (0 with 300, 300 with 600, 600 with 900). I'm using 300 but actually I would take sqrt(10**5).

This is a simple DP such that in the end each node in each layer has a pair (d1,d2), where d1 is the distance from the first node (corresponding to top door) in the previous special layer, and d2 is the distance from the second node (corr. to right door) in the previous special layer.

Observe there is never any need to travel back and forth between layers. Only one direction.

So now, assume I get a query (x1,y1), (x2,y2). Suppose the first is in layer i, and the second in layer j. All I need is to calculate the distance from x1,y1 to both doors in layer i, then. Then use my preprocessing to calculate the distance from doors of layer i to both doors of layer j (4 distances), and then calculate the distance from both doors of layer j to (x2,y2).

This could take up to 900 operations per query (300 for layer i to special naively, 300 for special to special using preprocessing, and 300 for special to j naively). But notice that if you do the preprocessing in both directions, this can be done in 302 operations per query (the distance to the next/previous special layer can be done in one operation).

Of course this isn't really 302, but more like 302 * 4? (because every calculation I consider 2-4 different options?). So it might be TLE, but it might just work. I'll probably try to implement later and see ^_^

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

    Yes, it is called SQRT-decomposition and should work with $$$10^5$$$, but as you noticed, it depends on realization.

    It's better to make some const $$$X = 300$$$ and use this value for pre-calculating, calculating an answer. Then you will be able to play with this number to get the best result (usually it's less than $$$\sqrt{N}$$$, about 250).

    P.S. I think $$$6s$$$ time limit was done specially to pass such solutions.

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

      Oh didn't notice the 6 seconds! Thanks for advice :)

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

Is it possible to solve $$$F$$$ using centroid decomposition? I tried to write it, but couldn't do it in time and don't know, will it work.

Also, has anyone noticed, that during contest "cses.fi" went down? I only loaded my submission there for a centroid decomposition problem, and after several minutes the site stopped working.

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

I can't control myself to complain the weak pretests of problem D. A way to express this feeling is to hack myself :(

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

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

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

please try to hack this one , my solution is already hacked , i just want to confirm whether my new solution is correct or not. link-158229941 thanks in advance.

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

For D why a DFS with memoization works? From any starting number x you just multiply it with {2, ..., 9}, and there are only 4 prime numbers in that set: 2, 3, 5, 7.

That means you actually just multiply x with those four prime numbers and in the worst case you start from 1 and use 64 multiplications with 2. But some of those 64 multiplications can be 3, 5, 7 as well. So that is really at most 64^4 (imagine you divide 64 positions into four segments for 2, 3, 5, 7). The real number will be much smaller because for 3, 5, 7 you probably don't need 64 multiplications.

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

SpeedForces, in two consecutive days QAQ SPEED IS NOT MY FORTE It's shocking that a D problem can be solve by brute force?? I'm trying to do recursion or dp, without even thinking that this problem can be sooooo easy! and I am sad that I mistake $$$bj$$$ to $$$bj_{th}$$$ in problem B.

and I am sad that because my func for sort() returns false when two elements are equal, I received 3 Runtime Error..

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

My only bug on E was forgetting to initialized my binary lifting array with INF...easily the stupidest bug I've made out of not solving one of the hardest problems in a contest

I also find it kind of funny that samples didn't even catch this bug

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

I solved problem D using recursion + memoization. only prime numbers which will be multiplied by x are only 2,3,5 and 7 and each prime number occurrence will not be more than 60,40,24,28 respectively. so we can memoize the count of each prime number.

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

awoo my 1st submission on D is wrong on sample test case 2, then why I am getting a penalty when my solution is wrong on the sample case? Isn't sample test cases free of penalties?

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

Can solve F more directly using a dynamic tree supporting subtree aggregates, such as this. Just cut/compute/link the edges for each color.

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

I solved problem D with a dp approach. https://codeforces.com/contest/1681/submission/158204160 dp[size of number][mask][distance from the original X] = max number with this mask.

I have a mask of all of the digits that are present in the number.

So if I have a number 1434, digits 1 3 4 are present and current mask is equal to 2^1 + 2^4 + 2^3 = 26

I used an assumption that if we consider all of the numbers with the same size and mask, we should always pick the biggest one. I am not sure about this assumption, I was not able to prove that is really always profitable to always pick the biggest number.

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

    My approach was similar to you; however, I didn't used mask but one of the digits existed in that number. "Wrong Answer on test 13 T_T"

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

why this recursive solution to problem D doesnt work? link

»
22 months ago, # |
  Vote: I like it -21 Vote: I do not like it

from a rank of 2000. to a rank of nearly 6500. after a solution get hacked is worst feeling ever for a coder. why don't they make proper pretest

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

used 3 hours to solve F with smaller to larger technique and get passed 2 hours after the contest. Made so many mistakes to count the number and contribution. Anyway, next time I might be better. How will you rate E and F?

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

try hacking this 158235750

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

Me: struggle with all my might in yesterday's round #793, solving one task for the entire contest, -131 rating

Also me: solve ABCD in the first 26 minutes today and run away to work because I didn't have time for this shit from the very beginning. Predicted rating +203

I'm stable like a stablecoin

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

    Interesting. Perhaps you should always do contests before your work, so you can push yourself to solve problems very fast and then you can run away to work :)

    (of course, just kidding)

»
22 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Question D, if you use dfs to solve this problem, pay attention to this, if the front is 2 and the back is 4, the number of steps *2*2 will be more, but *4 cannot enter because it has already accessed this number

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

Nice tests on E without int overflow, did some hacks with it.

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

Can somebody please explain C ?? also, i wasn't able to solve 'column swapping' in Round #794 (div1 + div2) , these are similar, right?? i think just saving the swapped elements in arr / vector was the difference.

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

I really amazed about problem D! how a single bfs with visit array make this code accepted without TLE, what is the time complexity of the previous code? or there is a failing test case which make it TLE?

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

deleted

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

I think D problem in this round is most hacked problem I have ever seen till now. It has changed so many rankings up and down. As I have also hacked 7 submission of D problem.

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

System test has already passed ?

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

    I am wonderning too ??

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

    same question

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

    I'm not sure if my assumption is correct, but if the new test cases will be added to the original ones then the answer is no because problem D is still showing 66 test cases, which is the number of the original test cases.

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

      why you think new test cases won't included and no re-run the system test again.

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

        What I meant is that if the new test cases will be added to the original ones this means that we will have a number > 66 test cases for problem D and I can still see that problem D has 66 test cases, and if I'm not mistaken then they didn't run the system test yet.

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

Is rating calculation still going on or it has been decided to become unrated even for Div. 2?

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

    After participating in almost 5 educational rounds you haven't realized that this series of contests rating always come late??!

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

      Yeah it was late on previous contest but I didn't check the graph on those contest.

      Since it displayed as "unrated" on my graph so I was wondering if some new announcement was made.

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

When will the tutorial open? The hacking phase is over ig

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

Why so many downvotes?

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

    I think it's because peoples are waiting tutorial/uprate too much

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

Even my grandma runs faster then the rating update system. Lol XD

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

When you wait for the rating change:
Meme

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

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

    Me who is going to become expert right now. Having a lot of adrenaline rush. Can't wait anymore now .

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

      Me too.

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

        Bro Your graph and solve count is so inspiring . You must be my friend . I have made you my friend . :_:

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

        I think your graph is so inspiring, too.

        If someone is going to be an expert, it must be you. XD

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

          I didn't like my graph at all because I got stuck in gray and green for long period. But seeing you guys saying that my graph is inspiring really made my day! Thanks!

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

        Me as well. :)

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

        yeah, holy crap. Lots of effort, you definitely deserve expert!

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

My dad has returned with the milk already.

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

-1 votes right now, and it keeps decreasing.

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

MikeMirzayanov awoo submission 158171922 and submission 158186561 are nearly same and its a pure co-incidence neither i know the person nor i used any online IDE and question was pretty brute force so its obvious to have same kind of solution and further more I have no history of such offence and i personally hate cheaters . This kind of things demotivates a lot please look into the matter.

»
22 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Idk why ppl are downvoting this contest . I find Task great . Just because of fst ??

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

I got my ans similar of C to somewhat 100 people; tell me it isn't possible that too many people do the question with the same approach? IDK why my answers are being skipped. I did not use an online IDE or something that would leak my code. It's too bad; after 2 hrs of brainstorming, you just skipped my question, with no-fault. It is a correct ans, and that's why so many people have the same approach. awoo MikeMirzayanov adedalic BledDest

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

    Exactly its a simple solution and many people can have it

»
22 months ago, # |
  Vote: I like it -14 Vote: I do not like it

Codeforces is considering me responsible for the mistake that I have never made.Actually I was sitting in a public library while competing in this round.I guess someone has copied my solutions by continously peeping into my laptop without informing me. I have not indulged myself in any such activities and I always beleive in right conduct.For reference you can check my submission timings and code. I beleive codeforces won't do injustice to me.

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

    aren't you responsible for keeping your code safe?

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

I finally become expert after 1 year . Cheers

»
22 months ago, # |
  Vote: I like it -10 Vote: I do not like it

How on Earth did I pass pretest with accidentally typing "int" in memoization for D task?

»
22 months ago, # |
  Vote: I like it -9 Vote: I do not like it

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

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

Can anyone tell why I haven't received the ratings for this contest yet... I am in div 2 (920 ratings)

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

    Your Last rating change was +13, after this round. So, you're

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

Well, finally i got my color back. Now i need to get back my rating! xD

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

awoo MikeMirzayanov Yestarday, I recieved a letter from Codeforces System in which it was written that my solutuion 158183564 is similar to Boboge's solution 158175797. We weren't communicating with each other. It's just an coincidence. Both of us used simple implementation of classic bubble sort and well-known C++ STL functions. Please, review your verdict P.S. I didn't use any online IDE, just CLion.

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

Could anyone help me to figure out what's wrong in this submission for the problem D?