gepardo's blog

XXI Open Cup, Grand Prix of Belarus
By gepardo, history, 4 years ago, In English

Hello everyone :)

We are happy to announce that XXI Open Cup, GP of Belarus will take place on February 14, 2021 at 11:00 MSK.

The authors of the problems are gepardo, kimden, Mediocrity, 244mhq, Wind_Eagle, and PuRpLe_FoReVeR. Also greencis, aleex, RED_INSIDE, programmer228, mrboorger, Chmel_Tolstiy, and gosuto took part in preparing the contest.

This contest was in Petrozavodsk, so if you have been there and have seen the problems, do not solve it now.

Links: Div. 1, Div. 2. You need an Open Cup login to participate.

You can discuss the contest here after it's over.

Good luck everyone and I hope you'll enjoy the problems!

UPD: Editorial

UPD 2: The contest is added to gym now.

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

Comments Comments (20)
| Write comment?
»
4 years ago, # |
  Vote: I like it +63 Vote: I do not like it

Hope you will enjoy the problems!

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

How to solve H, K, L?

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

    For H, I tried the following (but got WA6; possibly due to a bug, not sure though)

    If we have to go say south-east from (x1,y1) to (x2,y2), then we should take south as long as the x-coordinate is smaller than the y-coordinate. After we get to (k,k) cooodinates, we should keep alternately increasing x and y until we hit x2 or y2. Then, we increase the other coordinate.

    I computed all the series by abusing wolfram alpha (though it was doable by hand) and directly wrote the final expressions.

    I did casework for all similar cases; in another case, it turns out to be x <= -y.

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

      The model solution is very similar (we consider many cases and use the optimal strategy for each of them), but there is one observation which makes the calculation much simpler. See the editorial for details.

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

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

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

problem I nice solution)

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

Fun fact: F can be passed by $$$O(n^3)$$$ brute force.

code

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

    Another fun fact: in B — $$$O(n^4)$$$ can get AC.

    code

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

    Our TLE solution was using bitset similarly but with ? and : instead of if in the deepest loop. orz...

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

      Maybe the key is #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops")

      It may speed up your program 1.5x as I remember.

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

        maroonrk have written pragmas as if it is a common sense :)

        We actually observed a speed up by changing e.g. c = bs[k] ? c : 0 into if (bs[k]) c=0; somehow, so thanks for sharing your code...

        We have experienced that sometimes (in particular, some implementation of FFT) if is slower than ?, that's why we used ? today.

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

        Here's (a simplified version of) my TLE code. I believe it's very similar to your code, but still, yours runs 1.5x faster than mine on my computer. I really need help from a master of constant optimizations...

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

          Changing "-unroll-loops" to "unroll-loops" gets your solution accepted in 5.88s (it is the wrong way to turn that pragma on, compiler warns "bad option -unroll-loops").

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

            OMG I've been using this pragma for more than a year. Thank you so much!

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

For the sake of completeness, here is the editorial of Division 2 only problems.

Problem N (Div. 2). Bad Sets Usage. For pieces of each color and rank, check if there are enough of them in the first set. If not, borrow some pieces from the second set and remember them before printing. If there are still not enough, it is impossible to complete the first set.

Problem O. Blots Spilled Unluckily. This problem is an exercise in implementing a depth-first search or a breadth-first search on a grid.

Problem P. Bored Serving Users? We obviously prefer hubs with more sockets. Sort the hubs in non-increasing order by the number of sockets and find the least $$$i$$$ such that the first $$$i$$$ hubs are enough. Remember that connecting $$$i$$$ hubs requires $$$2(i-1)$$$ sockets, thus we have to check that $$$(\sum_{j=1}^{i} k_j) - 2(i-1) \ge N$$$. Also, we should store the indices $$$j$$$ of the hubs along with the values of $$$k_j$$$ to restore the answer.

Problem Q. Base Structure Under... Convert the years $$$A$$$ and $$$B$$$ into AUC, then iterate over all years in the range, represent them in the Roman number system, and find the length of the longest representation.

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

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

→ Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it -16 Vote: I do not like it

Can any author confirm that why the Editorial link is not working ?

UPD:- Mentioning authors gepardo, kimden, Mediocrity, 244mhq, Wind_Eagle and PuRpLe_FoReVeR.

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

    Does the problem still persist? The editorial link works for me.

    If you still have an issue, I may try to re-upload it somewhere else.

    → Reply