dalex's blog

By dalex, 2 months ago, translation, In English,
 
 
 
 
  • Vote: I like it
  • +51
  • Vote: I do not like it

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

Is there going to be any Editorial?

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

Reminder: it starts in 1 hour 30 minutes 10 minutes 1 minute.

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

How to solve L? I tried to write inclusion, exclusion dp just like knapsack using recursion. But couldn't implement it right.

Can you briefly tell what you did? Thank you!

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

    Sort the array $$$a$$$ in decreasing order. Obviously, if you choose to fight exactly $$$k$$$ dragons, it is optimal to take the $$$k$$$ largest amounts of gold, and you will lose $$$k * (k + 1) / 2$$$ on repairs. Now you just have to find the maximum over all $$$k$$$.

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

      Thanks a lot!

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

      It should be also mentioned that

      Problem L, important statement
      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it
        Can anyone tell me why this piece of code is giving WA in L.
        
        Code
»
2 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

I'll describe just the hardest problems. Others are too easy and everyone should have solved them. Anyway, if you have questions, ask them and someone will answer (hope not me).

The hardest problems

Oh, and this is the video of unfreezing and the editorial in Russian by Slamur: https://www.twitch.tv/videos/578322224

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

    Hi,can u explain this line " Why from n, not from 1? We do that, so that there always be only one next vertex when we will go from 1 to n in the next part of solution". and provide the source code to understand it better and some similar problem or topic. Thanks.

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

      I updated it, and this is the solution: https://pastebin.com/mzSvFaVp

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

        Thanks for providing solution, can u explain this "**Why from n, not from 1? We do that, so that there always be only one next vertex when we will go from 1 to n in the next part of solution**"

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

            Thanks, now i understand it.

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

            In this example vertex (4,3) was put in same layer but vertex (1,2) put in same layer or not as this property{ the i-th layer contains all vertices y, such that for all vertices x from the layer (i-1) the equality d[x] == d[y] + 1 holds.} condition is not satisfied. so can u tell how layers are formed in this example. Thanks.

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

              d[1] = 2 (path 1-3-5), d[2] = 2 (path 2-4-5), so the edge 1-2 is not processed at all — it doesn't lie on any shortest path.

              And three layers are just {1}, {3} and {5}.

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

    "How to deal with TL? There are three parts of solution which give log^2: coordinates compression, events sorting and Fenwick tree. We will get rid of the first two, leaving only log^2 from Fenwick"

    What is the point of making constant optimizations ? The difficulty of the problem is not how wtf it would fit in 2 seconds, instead of write some decent $$$O(n $$$ $$$log (n)$$$ $$$log (4*10^8))$$$

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

      Because they give x7-x8 boost all together. My first solution worked a bit more than 4 seconds, and the last solution with all these improvements — 0.5-0.55 seconds. This is a huge speedup, deserving to be kept.

      You will still get accepted without doing all of them. One of those two optimizations is enough. Some participants wrote another (better) approach to process events, it doesn't require additional log and passes too.

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

        Just my opinion: I think that the main purpose of the time limit in a problem is to differentiate a $$$log^3$$$ from $$$log^2$$$ or $$$log$$$ from $$$log^2$$$ etc... not force the contestant to do constant optimizations...

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

          If I kept my first solution, with TL = 2 * author TL = 8 seconds, who knows what trash could have passed. It would be too much.

          + I find these optimizations very beautiful.

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

            ok, put 3 or 4 seconds not 2

            I have another completely different beautiful solution with same complexity, but I need two fenwick instead of one and that's why I got TLE, so after many many many optimizations finally I got AC with the monster that my solution became 75647531

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        it doesn't require additional log

        Is that overall $$$O(n\log)$$$? I couldn't find a solution with such complexity on CF, can you explain it?

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          No, in those solutions the preparation of events and iteration over them takes NlogN, but Fenwick and lower_bounds in compression still take Nlog^2. Example: 75556991. This is the fast one, there are others with typical running time 1000-1500 ms.

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

How to solve problem J?

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

    This is one of many possible solutions (Found it by brute force)

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

How to do K? I got WA on test 18.

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

      Interesting result. I kept on trying to solve 4 cases where each case had different number of distinct elements.

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

      why we sort the heights.

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

        Why not? It doesn't affect anything (jury could give us the sorted test, and the answer would be the same), and it gives the opportunity to make more assumptions.

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

          thanks, so answer is same if we take points in random order?

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

can someone explain B ? binary search was giving me a wrong answer on test 29

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

    This test case may help

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

      how to solve I.

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

        Split the array by colors, each resulting array must be sorted

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

      yeah it worked that was a tough observation thanks!!

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

        Don't know what is your observation, but the solution is simple and well-known:

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

Can someone explain Problem-H Tree Painting ?? Thanks in Advance... And also can anyone post the link of editorials??

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

    First of all, it is not a rated round, and we don't have to provide editorial. It requires some time, you know. There is a video editorial we recorded just after contest, but for obvious reasons it is not in English. I think people can help each other in comments without any editorial.

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

Getting wrong ans on testcase 70 in problem G, any hints??

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

    You exceed query limit.

    Hint

    See more in my comment above.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain why this solution to problem B gives WA Submission

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

    A couple of things I can see is that:

    1. In main(), you have two for loops using the same variable i, so that would lead to overshadowing (but that won't cause a problem unless you use the outer variable in the inner loop).

    2. On line 62, it says a[i — 1] where i may be 0.

    3. On line 62, shouldn't you be checking if a[i] >= 0 instead of > (and same on line 69 — or you can simply remove line 69, as it changes nothing)?

    The algorithm I used is:

    My Algorithm

    Here is my submission: 75994294

    My submission was accepted — open at your own risk ;)

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could somebody explain how to solve problem D without Memory Limit Exceeded? My code reached test 32 but MLE was the problem (used Dijkstra's shortest path).

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

    Because strings in your Node struct can be O(N) length, so they eat O(N^2) memory in total.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, I thought so. Thank you. So then I would need to split it into two parts — finding the distance and then finding the lexicographically smallest path of that distance.

»
7 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Does anyone have the tutorial for problem D with a c++ solution? I tried dijkstra but exceeded the memorty limit.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Im new to Code Forces. Can anyone give the solution to Problem A , as I had tried it a lot..