dalex's blog

Gym — XIII Samara Regional Intercollegiate Programming Contest
By dalex, 5 years ago, translation, In English

Hello everyone,

At March 29 there was an annual programming contest in Samara University (online, of course), and yet again we copy it into Codeforces Gyms. The gym contest takes place on Sunday, April 5, at 11:00 MSK.

Contest link
Virtual participation link

Fifth time in a row it is a personal contest. So we ask everyone to participate solo. The skill of competitive programmers in the university became significantly lower, so the contest is the most interesting for blue and cyan coders, but we have something for violets and oranges too.

The list of our previous contests
  • Vote: I like it
  • +51
  • Vote: I do not like it

Comments Comments (65)
| Write comment?
»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Is there going to be any Editorial?

→ Reply
»
5 years 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.

→ Reply
»
5 years 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!

→ Reply
  • »
    »
    5 years 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$$$.

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

      Thanks a lot!

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

      It should be also mentioned that

      Problem L, important statement
      → Reply
      • »
        »
        »
        »
        5 years 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
        → Reply
»
5 years 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

→ Reply
  • »
    »
    5 years 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.

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

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

      → Reply
      • »
        »
        »
        »
        5 years 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**"

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Counter test
          → Reply
          • »
            »
            »
            »
            »
            »
            5 years 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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years 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}.

              → Reply
  • »
    »
    5 years 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))$$$

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
      • »
        »
        »
        »
        5 years 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...

        → Reply
        • »
          »
          »
          »
          »
          5 years 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years 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

            → Reply
      • »
        »
        »
        »
        5 years 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?

        → Reply
        • »
          »
          »
          »
          »
          5 years 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.

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

How to solve problem J?

→ Reply
  • »
    »
    5 years 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)

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

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

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it
    Problem K
    → Reply
    • »
      »
      »
      5 years 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.

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

      why we sort the heights.

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
»
5 years 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

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

    This test case may help

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

      how to solve I.

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

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

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

      yeah it worked that was a tough observation thanks!!

      → Reply
      • »
        »
        »
        »
        5 years 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
        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          yes

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

          Saying that it's well-known makes me kinda upset :(

          Can you explain what do you mean cause i didn't get it?

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Spoiler
            → Reply
»
5 years 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??

→ Reply
  • »
    »
    5 years 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
    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    You exceed query limit.

    Hint

    See more in my comment above.

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

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

→ Reply
  • »
    »
    5 years 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 ;)

    → Reply
»
5 years 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).

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
»
5 years 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.

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

About the problem G — Nuts and Bolts — I saw in the comments that the problem + solution is described on a book, but I didn't find anything there about the motivation behind the $$$5 \log_{2}n$$$ operations. Why $$$5$$$ and not $$$3$$$ or $$$7$$$?

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

Do you guys prepare these problems yourselves or are they previous CodeForces Problems, dalex?

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

    Some of them are future Codeforces problems

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

WA on test 8 in D any help?

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

    It's a small test. Just write stress (there is easy bruteforce solution).

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

I

→ Reply