mr146's blog

Ural Championship — 2016
By mr146, 9 years ago, translation, In English

Hi everyone!

May 2, 11:00 (MSK) the mirror of XX Ural Championship will take place for Open Cup participants on Yandex.Contest system.

Contest is not stage of Open Cup, but it's winner will be awarded Internet-Ural Champion's Cup. Authors are — winger, Kurpilyansky, Stigius, Erop, AlexFetisov and other Ural (and not only) veterans. Thanks to GlebsHP, TeaPot and SirShokoladina for testing and useful advices, and thanks to MikeMirzayanov for Polygon.

UPD

Contest link: https://official.contest.yandex.ru/contest/2486/enter/

UPD2

BREAKING NEWS: If you don't have login for Open Cup, you can register here: https://contest.yandex.ru/contest/2486/enter/?lang=en

UPD3

Teams without login for Open Cup should enter the contest via link above, teams with login for Open Cup — via https://official.contest.yandex.ru/contest/2486/enter/

Statements: https://www.dropbox.com/s/nrdu4jaqamqnjdp/chu-statements-en.pdf?dl=0 https://www.dropbox.com/s/xg18wiej9xm8yqw/chu-statements-ru.pdf?dl=0

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

Comments Comments (24)
| Write comment?
»
9 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Will the contest be standard ICPC format? (5 hours and teams of 3 people)

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

Where can I find the link to the mirror contest?

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

    Now you can find link in the post.

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

The problem statements of mirror contest are not available.

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

What is the solution of G?

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

    My solution is O(nx3). It is obvious, that we should start by solving tasks, that will add 0 to utility. Only after that we will start solving other ones. The order doesn't matter for the first part and for the second part we should solve the one with higher a. Now, let's just iterate over the debt X after first part and calculate the best result with DP[i][j][k] — best utility that we can get by solving tasks starting with i, so that we reduce debt for the first part to j and to k for the second part having the debt after the first part exactly X.

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

      I'm not sure that I understand you correctly. The set of tasks that add zero utility may change while you start taking them. Consider the following test:


      a1 = 5, b1 = 100
a2 = 10, b2 = 110

x = 100
order [1,2] -> 5 + 25 = 30 
order [2,1] -> 20 + 15 = 35 (better)

x = 105
order [1,2] -> 0 + 20 = 20
order [2,1] -> 15 + 10 = 25 (better)

x = 110
order [1,2] -> 0 + 15 = 15 (same)
order [2,1] -> 10 + 5 = 15 (same)

x = 115
order [1,2] -> 0 + 10 = 10 (better)
order [2,1] -> 5 + 0 = 5

      For x = 105 taking the task with zero utility add will not be optimal. Does your program proceed all these tests correctly? Those tests failed all solutions we tried. (Yes, those numbers violate the constraints, you can just divide all numbers by 5).

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

        Yes, it works on these tests. They are not hard actually.

        The main idea is that after you decide what the debt Y will be after you pick all with zero utility, the first and second part become nearly independent. What is left to do is to partition all tasks into these two sets such, that debt after processing the first one will reduce from X exactly Y and the sum of utility after processing second one with initial debt Y is maximal. That is what we need DP for. On each step we decide whether we solve the task in first part (it must have zero utility then) or in the second.

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

          This solution can be improved to work O(nx). You should go in order of increasing of a[i] and count dynamics d[i][j] — utility that we lose, where i — number of problems we go through, j — debt we get after solving problems of first type (that we solve with 0 actual utility).

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

            I don't understand this O(nx) approach. Do you have code or can you write 2-3 lines of pseudocode? Thanks.

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

Thanks a lot to authors for the problem I!!! I love to write very stupid solution for the geometry problem, then iterate over all possible epsilons and finally rewrite the solution to BigDecimals to get AC.

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

Solution of F:
Note than if x and y and consecutive Fibonacci numbers, than y2 - xy - x2 =  ± 1. Proof:

So we can find at most four candidates for the answer. (Using discrete logarithm for taking square root easily passes).
For each y, we want to check if there is such n that

We can use baby-step-giant-step again (here we using that period of fibonacci numbers is at most linear in p).

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

How to solve B Memory leaks(xn = (xn−1 + xn−2) mod p,(p is a prime),for a y,to find k (xk=y) or say k doesn't exist)?

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

    This is how I solved.
    F(0) = 0; F(1) = 1; F(n) = F(n — 2) + F(n — 1). Then matrix 2x2:

    F(n — 1) F(n)
    F(n) F(n+1)

    is n-power of matrix:

    0 1
    1 1

    There is property: det(AB) = det(A)*det(B), if A and B — same size square matrixes.
    det([0 1; 1 1]) = -1 => det(([0 1; 1 1])^n) = (-1)^n => F(n)*F(n) — F(n — 1)*F(n+1) = (-1)^n
    We are given p and x. If x = F(n) the we need find F(n + 1) = F(n — 1) + F(n). Assume F(n) = x. Then we've got modular equation:

    a*(a+x) — x*x = (+/-)1 (mod p)
    a*a + a*x = x*x (+/-) 1 (mod p) | *4
    4*a*a + 4*a*x = 4*x*x (+/-) 4 (mod p) | +x^2
    4*a*a + 4*a*x + x^2 = 5*x^2 (+/-) 4 (mod p)
    (2*a+x)^2 = 5*x^2 (+/-) 4 (mod p)

    Now we need find sqrt(A) mod p. This is standart algorithm. This. O(sqrt(p)*log(sqrt(p))).

    This is how we find at most four values for a. Then we need to check whether matrix
    [a x; x (x + a) mod p] power of [0 1; 1 1] mod p. This is standart algorithm too (This. Brute-force says power can be at most 2*p. O(sqrt(p)*log(sqrt(p))).

    So we found all values of a.

    P.S. There are two corner cases: p = 2; p = 5. (Both algorithms works on odd prime p. For p = 5 power can be at most 4*p).
    P.P.S. There is more easy way?

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

Any hints or solution for H?

→ Reply