BledDest's blog

By BledDest, 23 months ago, In English

Hello Codeforces!

The Southern and Volga Russian Regional Contest was held in Saratov State University on 22nd of November. This contest was used to qualify the teams from Southern Russia and Volga region to the Northern Eurasia Finals.

On Nov/27/2022 13:35 (Moscow time), we will conduct the online mirror of this contest. It will last for 5 hours and is best suited for teams of three people, although it is not forbidden to participate in teams of smaller/larger size. The mirror will use ICPC rules, the same as the offline contest.

I would like to express my gratitude to all other jury members: awoo, Neon, vovuh, adedalic, DmitryKlenov, dmitryme, DStepanenko, elena and kuviman. Also, big thanks to the contest testers: IlyaLos, Oleg_Smirnov, ashmelev, pashka, and especially MikeMirzayanov not only for testing the problems, but also for his excellent Polygon system, without which it would be almost impossible to prepare the competition.

As a chief judge of the contest, I hope you enjoy the problems!

Of course, the contest will be unrated.

upd: The editorial can be found here.

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

| Write comment?
»
23 months ago, # |
  Vote: I like it +41 Vote: I do not like it

Would the Southern and Volga Russia regional consider uploading test data for this year's (and also previous years') contests? The regional page is missing a lot of details.

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

    Unfortunately, I don't have any access to editing that page. I will try to find out who I should contact to upload that information for the current Regional and the 2021-2022 one (I wasn't the chief judge during the earlier seasons, so I also need to consult with the previous chief judge).

    As a temporary solution, I can upload the editorials and the tests as the contest files after we conduct the mirror.

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

Is $$$\mathcal{\color{red}{Hack}}$$$ available?

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

How challenging are the problems? Should I attempt to participate if I'm green?

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

    You definitely should

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

    For a lone green participant, the problemset can be very challenging. I advise you to play this contest with a team.

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

      What about a lone blue one?

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

        Much more suitable than for a lone green one, but there will be several problems which are not expected to be solved by anyone who is in the second division.

        The problems are very different in terms of difficulty, you will surely find several ones to solve.

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

excited

»
23 months ago, # |
  Vote: I like it +181 Vote: I do not like it

As a tester, I think that this is a really good set of problems. It will be of interest to a wide range of participants.

I'll add more. That, as a former chef judge, I highly appreciate the problems and think that the guys did a great job. Kudos!

»
23 months ago, # |
  Vote: I like it -120 Vote: I do not like it

It would be nice to finally fix language selector issue and remove excessive use of flags.

Sources with supporting arguments:

Codeforces Language Picker -- chrome extension to see how fixed codeforces language picker would look like.

Please support the initiative and stop reinforcing poor UX practices.

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

    Please use your plugin and don't bother us all.

»
23 months ago, # |
  Vote: I like it -52 Vote: I do not like it

Is this contes rated?

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

    Literally the last line of the blog answer your question

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

Interesting provlems. Thx

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

What is test 72 of problem I?

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

How to solve problem A ?

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

    Just https://e-maxx.ru/algo/path_cover (in Russian).

    Docs form a DAG. Duplicate the vertices, for each edge of DAG add the edge (i, j+n) to a new bipartite graph. Find the maximal matching. Edges chosen for matching form a path cover. Each path is then solved independently, and it is easy.

    Bad problem: it is not easy but at the same time it is just a copypaste from e-maxx.

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

      How do you deal with duplicate vertices? I was able to figure out the DAG part and then googled my way into the mcbm solution, but I am currently unable to solve when some documents have the same permissions.

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

        If two vertices are absolutely identical (the columns in the input are equal), just remember that one of them is the clone of the other and drop it from the rest of the solution except printing answer.

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

          hmmm that's what I did initially, guess it must be something else that's wrong lol. thanks

          EDIT: Ok i think my problem was decomposing the graph improperly (if $$$(i,j)$$$ is an edge and $$$(j,k)$$$ also an edge, I removed $$$(j,k)$$$ from the graph). :facepalm:

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

          There's an interesting way to handle identical documents (credit to ashmelev): use the document index as the tiebreaker. The method you described works just fine, but this one is a bit more elegant in terms of code.

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

What is the idea for solution problem D?

  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hint
    Solution
»
23 months ago, # |
  Vote: I like it +10 Vote: I do not like it

When will the editorial be published?

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

How to see the failed test cases ? I am not able to see it

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

How to solve problem K ?

  • »
    »
    23 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 3 (+ Answer)
    Solution Code
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Only one type of shifting is available and dp.

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

how can i hack a solution when i can't see the author's code ?

update : problem solved!

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

How to solve Problem N?

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

    First, you have to minimize the number that will appear in the first position of the answer, using as few operations as possible. If you have more operations left, do it again with the second position. Repeat the same process until you run out of operations. I implemented it storing in 10 vectors all the positions of the numbers from 0 to 9, then performing binary search in each position. Be careful with the leading zeros, and also, at the end of the process you might still have operations, if there is no way of making the firsts positions smaller. Example: "1111111111..." Then you can just delete random digits that are still not deleted.

    Hope my explanation was not terrible.

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

      Now I kinda get the concept, though the implementation seems quite complex. I wonder how so many teams solved it.

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

        It's not that complex, but there must be simpler solutions.

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

        If you have to delete $$$k$$$ values then you have to keep $$$n-k$$$ values. Let's try to understand an approach to decide the first digit (leftmost) of the answer. It cannot be a $$$0$$$ and it has to be a value in the range $$$[0,k]$$$ (inclusive). Because if we were to take the $$$k+1th$$$ value then we won't be able to take $$$n-k$$$ values in total. Greedily we choose the smallest value in the range $$$[0,k]$$$ as our first value. Mark this index as $$$l$$$, now to choose our next value we apply a similar technique but we have to choose the least value in the range $$$[l+1,k+1]]$$$. Call this value $$$mn$$$ and update $$$l$$$ to the first occurence of $$$mn$$$ in the range $$$[l+1,k+1]$$$. We can do this naively since our $$$l$$$ pointer moves atmost $$$n$$$ times in total. Now do this approach again by finding minimum of the range $$$[l+1,k+2]$$$ and so on.

        To compute the minimum of the range, I just used a segtree. This makes the implementation quite easy imo — Submission

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

What was the order of problems in the onsite contest? Will you add ghosts?

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

    The order of the problems from the official competition was the following one:

    Spoiler

    I don't know how to add ghost participants, but I'll try to find it out and, if possible, add them.

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

About Problem J :

Spoiler
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
    Spoiler
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +22 Vote: I do not like it
    Another spoiler, now about problem C
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it
      Spoiler for C
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        can you tell a bit more about the solution? i thought keeping the count distribution of the k cards is not enough because the selection algorithm may make the states heavily biased. it may not b the case that the remaining cards are uniformly distributed before the k cards.

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

          We just used linearity of expectation. Note that the contribution only depends on the distribution of the cards. For that you only need a multinomial distribution. For every possible size of your look-back, you can compute the distribution in $$$O(n^3)$$$, leading to an $$$O(n^4)$$$ solution.

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

How do you solve H?

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

    Use a topological sort to find the minimal $$$p_i$$$ for each vertex (basically you want to ensure that $$$p_i \leq p_j$$$ if $$$i$$$ is an ancestor of $$$j$$$). Then for each vertex, you must place all ancestors before it, so just retrieve the ancestors then binary search on the leftmost position you can place it at.

»
23 months ago, # |
  Vote: I like it +13 Vote: I do not like it

How to solve H?

»
23 months ago, # |
  Vote: I like it +57 Vote: I do not like it

I'm kinda surprised so few participants solved L and G. They were much more popular on the official contest (all teams which solved 9 problems had G+H+L+6 easiest problems), and neither L nor G is especially hard.

On the other hand, A and F were the opposite of that: not solved on the onsite, popular during the mirror. Problem A is understandable, much more participants know the required techniques and can reduce the problem to those techniques; but F was considered one of the hardest problems in the set by me.

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

    When will the editorial be published?

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

    I think F is not difficult to solve it ,but maybe hard to prove it. I solved it by guessing.

    It is easy to find that we need to use DP to solve this problem in O(n^2). And then we guess dp[i]=min(dp[j]+f(j,i)) [1<=j<=i-1], try a try, ac is ok.

    If n<=300 the problem will be more difficult,I think.

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

      Proved by geometry, It actually relates to area below segments.

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

      Just upsolved it. Nothing hard, easier than A and L for sure. There was too much stress during the contest, but now it's much better.

      The problem is, in short: you can buy some points and in the end you gain the area under the top part of their convex hull.

      Solution of F
»
23 months ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

How solving problem E please ? I know this the problem solve math but how ?

»
23 months ago, # |
  Vote: I like it +60 Vote: I do not like it

J is absolutely beautiful. F and G are nice. Cool contest!

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

How to Solve L ?

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

Does anyone know what causes the verdict of hack showing "Unexpected verdict"?

I tried to hack some solutions (which seem to have wrong time complexity) for problem L, but I only got "Unexpected verdict".

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

    The "Unexpected Verdict" happens when the checker returns _fail, and is supposed to happen when a jury solution happens to fail on a valid testcase or a solution finds a better solution than the jury solution. I don't understand why this happens on problem L though, isn't the answer supposed to be deterministic (i.e. there is only one answer for one input)?

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

      Hmmmm, could it be that jury solution neither fits in TL? xd

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

        Polygon will check all the solutions marked as "Correct", and if one of them fails, will return _fail. Authors sometimes add participants solutions, so maybe one of them is slow, or maybe one of jury solutions is slow, which also can happen. Or the model solution is slow :)

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

          Yes, this time our solution (me + pashka) was actually slow. Thanks, YaoBIG. Now tests are better!

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

            Thanks for the fix!

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

            Would be also good to mark uphacked submissions in the standings (maybe change the color of '+'), and to run all contest submissions on new tests to see if they should be marked as uphacked.

            Now someone looking for the code can check top-2 team's solution for L, but it's wrong. Our contest submission is also wrong but as it's not uphacked it may seem it's correct.

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

          Ah I see. I did not know that all solutions marked as "Correct" will be checked and it is good for me to learn this! Thanks for the explanation!

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

How to solve problem H?

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

How to solve G?

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

      Thanks. I now know how to do. Additionally, can I ask when the editorial will be posted?

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

        Hopefully we'll finalize it in about 24 hours. I am sorry for the delay.

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

Nevermind... You don't have to use all contracts...

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

Solution

This is the solution of Torus path (K) . Please help me i am not able to clear all test cases , i have tried with dp.

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

    K is simpler than DP.

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

    You calculate dp in DFS order, it doesn't always find maximum path. Sometimes you can get better value if you go to already visited cell. Example:

    3

    2 2 2

    2 2 2

    1 2 2

    This problem can be solved with dp using the fact that it's impossible to use both vertical and horizontal teleports. If you don't use vertical teleports, you can calculate DP in vertical order and vice versa.

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

      But we cannot visit the same cell twice. It will be great if you can give code please

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

        We cannot visit the same cell twice but your function can visit some cells in one path and block some other paths. For the same reason we can't use DFS for finding shortest paths.

        Solution with vertical and horizontal DP: 183454259

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

          I understood that it's possible to use both types of teleports so this idea is incorrect. But in this problem you don't need it so this solution works.

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

I recognize that for D it is simply to permute $$$a$$$ such that the least pairs $$$(a_i, a_{i+1})$$$ add to over $$$m$$$. To do this I use a simple greedy algorithm: for $$$a_x$$$ starting from smallest $$$a_x$$$, pair it with largest $$$a_y$$$ such that $$$a_x + a_y \leq m$$$. Then arrange pairs as such: $$$a_{y_1}, a_{x_1}, a_{y_2}, a_{x_2}, ...$$$. The remaining elements will always cause pairs that add to $$$\geq m$$$. I came up with this algorithm through intuition (it works). Is can somebody prove correctness?

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

Where can I find the editorial?

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

How to solve problem F ?

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

Not sure why does this solution work? 187063817 (why does this solution doesn't work without line 18: dp[i][j][t] = ans = -INF; should be just ans = -INF; from my knowledge it enters an infinite loop in this case).