Автор awoo, история, 22 месяца назад, По-русски

Привет, Codeforces!

В 23.05.2022 17:35 (Московское время) состоится Educational Codeforces Round 129 (рейтинговый для Div. 2).

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

Раунд основан на Межвузовской олимпиаде г. Саратова, поэтому просим воздержаться от участия тех, кто уже знаком с задачами.

Удачи в раунде! Успешных решений!

UPD: Разбор опубликован

  • Проголосовать: нравится
  • +45
  • Проголосовать: не нравится

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Goodluck all participants <3

»
22 месяца назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    1400-1600

    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится +23 Проголосовать: не нравится

      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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

»
22 месяца назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Always love educational round.

»
22 месяца назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

For the love of back to back rounds. <3

»
22 месяца назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Hope that I will not mess everything up again.

»
22 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Thank you for the contest

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If the score is more than 2100, why do people with a score of more than 2100 participate in the ranking

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Probably one of the best question sets I've seen this entire year!! However, I made one typo in question C which costed me 20 more minutes and 4 penalty attempts :(

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится

Only solved A-C again :(

Maybe I should have a rest……

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Relatable :(

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +67 Проголосовать: не нравится

    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 месяца назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      How do you prove bfs will not time out though?

      • »
        »
        »
        »
        22 месяца назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

        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 месяца назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится

        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 месяца назад, # ^ |
        Rev. 5   Проголосовать: нравится +40 Проголосовать: не нравится

        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 месяца назад, # ^ |
          Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

          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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяца назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

Educational speedingforces

»
22 месяца назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Dude, really 6500+ people solved C?

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Speedforces

»
22 месяца назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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 месяца назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Proof that this wont give TLE?

      • »
        »
        »
        »
        22 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 месяца назад, # ^ |
          Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

          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 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
    • »
      »
      »
      22 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      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 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        why the limit of 1000 ?

        • »
          »
          »
          »
          »
          22 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          22 месяца назад, # ^ |
            Проголосовать: нравится +7 Проголосовать: не нравится

          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 месяца назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится

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

    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится +27 Проголосовать: не нравится

      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 месяца назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

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

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    No bro, the counter example is given in sample.

    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    test case : 13 42

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяца назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    123456789x9=1111111101 and you're stuck :D

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What's the proof for C???

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What was the idea behind E and F?

  • »
    »
    22 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

    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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve F?

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +44 Проголосовать: не нравится

    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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What's the intuition behind D??

»
22 месяца назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    22 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

      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 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 месяца назад, # ^ |
    Rev. 6   Проголосовать: нравится +105 Проголосовать: не нравится

    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 месяца назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    +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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

158223688

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        22 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          22 месяца назад, # ^ |
          Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          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 месяца назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
22 месяца назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

Why are there orange people in the official standing?

»
22 месяца назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Can we solve F using smaller to larger technique ?

»
22 месяца назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

What a bullshit D.

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

First time solved 4 problems in div 2

»
22 месяца назад, # |
  Проголосовать: нравится +101 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    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 месяца назад, # ^ |
      Проголосовать: нравится +33 Проголосовать: не нравится

    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 месяца назад, # ^ |
        Проголосовать: нравится +61 Проголосовать: не нравится

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

    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится +36 Проголосовать: не нравится

      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 месяца назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится

        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 месяца назад, # ^ |
            Проголосовать: нравится +17 Проголосовать: не нравится

          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 месяца назад, # ^ |
            Проголосовать: нравится +15 Проголосовать: не нравится

          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 месяца назад, # ^ |
              Проголосовать: нравится -19 Проголосовать: не нравится

            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 месяца назад, # ^ |
        Проголосовать: нравится +35 Проголосовать: не нравится

      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 месяца назад, # |
Rev. 2   Проголосовать: нравится +17 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится +99 Проголосовать: не нравится

    samjh nhi aaya pr sunke aacha laga

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяца назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        22 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
22 месяца назад, # |
Rev. 4   Проголосовать: нравится +4 Проголосовать: не нравится

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 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why this recursive solution to problem D doesnt work? link

»
22 месяца назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

try hacking this 158235750

»
22 месяца назад, # |
Rev. 4   Проголосовать: нравится +2 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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 месяца назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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 месяца назад, # |
Rev. 4   Проголосовать: нравится -26 Проголосовать: не нравится

deleted

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
22 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

System test has already passed ?

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I am wonderning too ??

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    same question

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    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 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        22 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why so many downvotes?

»
22 месяца назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

»
22 месяца назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

When you wait for the rating change:
Meme

»
22 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

»
22 месяца назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

My dad has returned with the milk already.

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The blog now has -1 votes , 5m earlier it had 1 upvote.

»
22 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

-1 votes right now, and it keeps decreasing.

»
22 месяца назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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

»
22 месяца назад, # |
Rev. 3   Проголосовать: нравится -25 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

I finally become expert after 1 year . Cheers

»
22 месяца назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

»
8 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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