tourist's blog

XVIII Open Cup: GP of Gomel
By tourist, history, 7 years ago, In English

XVIII Open Cup Grand Prix of Gomel takes place on Sunday, February 18, 2018, at 11:00 AM Petrozavodsk time.

The link to the contest. You need an Open Cup login to participate.

I'm the writer of all the problems. Let's discuss them here after the contest!

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

Comments Comments (46)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it +31 Vote: I do not like it

Do you believe in extraterrestrials? what if they appear and ask you to find ramsey 5,5 number? what will you answer?

After some csacademy rounds, I thought that the best are minimalistic statements, but even tourist can write cute problem stories :)

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

How to solve B?

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

    First note you need to maximize subject to (here xi is the number of ones in f(a, i)). Now increasing a xi by one 'costs' i·2xi. Binary search over the maximum cost that you use.

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

      Is there greedy first binary search for i = 1 find max x1 then max x2 for n — 2xi + 1 and so on...?

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

        No, you binary search over the maximum cost for which you use 'all options'. To check if m is possible, check if (here counts the number of i for which i·2x ≤ m). After the binary search you can use whatever you have left for options which cost exactly one more.

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

Could you share the feeling when you see no Chinese team solved the problem J?

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

    Lol, you guys should write some problems about Mahjong hands evaluation :)

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

    (Note to readers: this contest first appeared at Chinese Winter Camp two weeks ago. 25 teams, 0 submissions for problem J.)

    Well, I anticipated that it could go either way :) Such a scenario was more likely with Chinese teams -- Russian-speaking participants are more familiar with this game, even though this particular modification is made up by myself and obviously not played by anyone.

    If you ask about feelings -- I was slightly worried that the problem statement was difficult to understand. In Petrozavodsk & Open Cup the first correct attempt came in during the first hour, and then a dozen of non-Russian-speaking teams solved it as well, so hopefully it was good enough.

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

We spent 40 minutes to understand rule of "Fool's Game".. Do Russian competitors know it already?

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

    Yes, but it's modified. If second has 2 jokers, he loses, otherwise he wins by taking all cards that first tosses until first only has jokers.

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

      Is there any simple proof? We solved J without any proof :(

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

        As I said, if second has at most 1 joker, his optimal strategy is to never cover and always take cards that first tosses at him. This way first always tosses. In the end the first will take all cards from the deck, so he surely will have at least one joker, which he can't toss, so he will lose. If second has both jokers, then if he always takes cards, then first's hand will get empty in the end, and if he covers at least once, first can use similar strategy and only take cards for the rest of the game.

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

    In Russia it's a well known card game called "Дурак" ("durak").

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

    If I were to choose a card game that every single native speaker of Russian knows the rules of, Durak would be my bet.

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

How to solve G and K?

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

    K: Factorize N first. Then, inclusion-exclusion works in O(3k), where k is the number of distinct prime divisors of N. It's first enough.

    The main challenge is the factorization. Check all divisors up to N1 / 3. Then there are three cases:

    • N = p2 (we compute sqrt(N) and check)
    • N = p (use BigInteger.isProbablePrime in Java, not sure if this is intended)
    • N = pq (otherwise this holds, we are not interested in the values of p and q)
    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      Could you explain about inclusion-exclusion more detailed?

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

        Suppose that N = paqb. We want to choose a subset of divisors of N. But there are four things we want to avoid:

        • (1) All numbers in the set are multiples of p.
        • (2) All numbers in the set are divisors of pa - 1.
        • (3) All numbers in the set are multiples of q.
        • (4) All numbers in the set are divisors of qb - 1.

        Now we get an O(4k) inclusion-exclusion.

        To make it O(3k), notice that "choose (1) and not choose (2)" and "choose (2) and not choose (1)" are equivalent (and the same holds for (3) and (4)).

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

          Why N is pa * qb but not p1a1 * ... * pnan?

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

            I assumed that k = 2 just for simplicity, it works for general k.

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

        Here is more or less strict detailed formulation. Assume n = p1a1... pmam.

        All numbers in considered set must be divisors of n. Let's calculate number of subsets g(n) we can take having only equals 1. That means that for each number pi we should take at least one number having pi with only power of 0 in its factorization. let's denote set of all sets that contain at least one such number for pi by Ni. Then we have to calculate intersection of such sets:

        Here denotes set of all sets that do not contain any number having pi with power 0 in factorization. For single number i holds where is simply number of divisors of n.

        Indeed, we shoud choose some divisors of n such that they all are divided by pi, thus we can first divide n by pi, choose arbitrary subset of divisors and multiply them backwards by pi. After that we subtract 1 to vanish empty set. And for intersection of such sets we have:

        Thus answer can be reformulated as Dirichlet convolution using Möbius function:

        Now if we would like additionally calculate number of subsets f(n) having equals n we can write it with quite similar formula:

        Since Dirichlet convolution is associative, we can just calculate

        Where is Dirichlet convolution of Möbius function with itself. It can be found out that is multiplicative function defined in the following way:

        This allows you to solve the problem in .

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

How to solve D and I?

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

    Gaussian binomial coefficient and line graph recognition.

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

      Line graph recognition lol

      Now I'm curious how MSU team solved it. Did they derived it from scratch?

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

        It's not so hard to come up with some process building the answer. Something like "take an edge uv, assign xy and xz to its endpoints, realize which neighbors can have x, y, z and yz labels..". I can share my code which received OK after about one and a half hour of debugging with stress after the contest in Petrozavodsk. Also I can explain the ideas behind my solution if you are still interested, but maybe guys from Red Panda had simpler approach.

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

          Yes, basically I expected the contestants to come up with a similar process. From a fairly large number of submissions, it seems that many teams actually did that.

          Unfortunately, the devil is in the details, and most teams failed on test cases 4 and 5, which are line graphs of graphs with a lot of small connected components. The only team besides MSU Red Panda who managed to get past them was team Ural FU 1 -- they ended up with WA 35.

          One way to deal with ambiguities, which actually only happen in the beginning of the process, is doing a brute force search until the current connected component is large enough. Definitely it's also possible to analyze these ambiguities on paper.

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

    Let q = 1 - p and r = p / q. It's easy to see that f(k) corresponds to the coefficient of Xk of the polynomial PN(X) = (1 + X)(1 + rX)(1 + r2X)...(1 + rN - 1X). So we want to evaluate this polynomial.

    Use the following (and FFT):

    • PN(X) = PN - 1(X) * (1 + rN - 1X)
    • PN(X) = PN / 2(X) * PN / 2(rN / 2X) (in case N is even)
    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      In fact, no FFT or polynomials are needed as there is a simple formula for f(k).

      If we call G(N) = (1)(1 + r)(1 + r + r2)...(1 + r + ... + rN - 1), then .

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

        Why the formula of f(k) looks like this or the one from rng_58's post?

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

          For my formula: simple calculation shows that the probability that the set of people with indices {a1, ..., ak} beats everyone else is ra1 * ... * rak * Ck, where Ck is a constant that depends only on n, k, p. Thus, we are interested in the value of

          If we get sk for each k, we can get f(k) = Cksk.

          sk is the coefficient of Xk in the polynomial above.

          UPD: Now, search "There are analogs of the binomial formula" here.

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

How to solve H and J?

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

    For problem H:

    Assume a < b. If n is even while a, b are odd, then there is no way to complete the journey as you can never travel between two even numbers consecutively by walking or jumping.

    Otherwise: if a is even, a valid path with three jumps is

    a -> 2 FLY a+1 -> b-1 FLY 1 FLY n -> b.

    Similarly, when n is odd, the following is valid

    a -> 2 FLY n -> b+1 FLY 1 FLY a+1 -> b.

    and when b is even, the following is valid.

    a -> 2 FLY b-1 -> a+1 FLY 1 FLY n -> b.

    We will also need to check if there are shorter paths, and deal with special cases like b = a+1, b = n, a = 1, etc. The number of possibilities to check will still be O(1).

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

      I've already posted solution sketches in a separate comment, but I'd just like to make a special note here (for those who don't get to read it) that a solution without case analysis, at least in the implementation part, is possible.

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

How to solve G?

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

Great chance to know about tourist's musical taste

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

I'm kind of curious about case 64 in problem K. Was it designed to break integer factorization in ? (My squfof breaks on it and I could't break it with various random tests.) Did anyone try pollard-rho?

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

    Test case 64 in problem K is 999949000866995087 = 9999833. Yes, I've seen a bunch of accepted solutions using Pollard's rho.

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

      Can you give me please the 33th test? I don't know why but I get TLE on it (in Go) while all others pass in less than 30 ms.

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

        This is the first test case with a lot of distinct prime divisors: 914836017997511610.

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

Please find a brief summary of solution ideas here. Feel free to ask if you have any questions.

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

    Could you explain in problem G how to find intersection of semiplanes in O(n) and tricky moment with "all semiplanes intersect any line x=d at some integer y" more detailed?

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

      In general, half-plane intersection is similar to building convex hull. One possible way to go is to separate half-planes into "upper" (covering point (0; + ∞)) and "lower" (covering point (0; - ∞)), sending "vertical" half-planes into either category (there are none in this problem, though). Then, in each category, sort half-planes by polar angle and perform a scan with stack removing unnecessary half-planes -- this is similar to Graham scan. Finally, we have two polylines and by finding their intersection points we obtain the resulting polygon. Of course, in general case this "polygon" might have infinite area, so additional care must be taken (luckily, it never happens in this problem).

      This algorithm works in due to sorting, but the scan part works in O(n). In this problem, since the half-planes are sorted naturally -- their normals look like (i - 1;1) for i from 1 to n -- there is no need in sorting, so the whole algorithm works in O(n).

      For the second question, when I said "all half-planes intersect any line x = d at some integer y", I actually meant "half-plane borders" not just "half-planes". Consider any half-plane border, for example, a1 + d·(i - 1) = ri. This is equivalent to a1 = ri - d·(i - 1). The right part is integer when d is integer, hence the left part is integer too.

      How does it help in this problem? We have found a polygon representing the intersection of half-planes and we want to find the number of integer points inside it. Let's move with two pointers from left to right and divide it into O(n) trapezoids with legs formed by two of the given half-planes and bases parallel to Oy (well, Oa1). Consider one such trapezoid. Since we are only interested in integer points inside the trapezoid, let's shrink it a bit in such a way that its bases have integer x = d. And now the coordinates of vertices of this trapezoid are all integers -- exactly since both legs intersect line x = d at some integer y. Now, for example, you can use Pick's theorem to find the number of integer points inside the trapezoid, but actually this number is just the sum of an arithmetic progression, since at every intermediate integer x = d trapezoid's legs have integer intersections as well.

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

guys where can i see the problem statements??

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

    The statements will appear here after some time (down on left side in russian is written to choose the stage) but you won't be able to submit problems unless you have an account.

    → Reply