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
Will the contest be standard ICPC format? (5 hours and teams of 3 people)
Yes.
No.
Where can I find the link to the mirror contest?
Now you can find link in the post.
The problem statements of mirror contest are not available.
Everyone here is experiencing the same problem.
Now post the in links
What is the solution of G?
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.
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:
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).
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.
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).
I don't understand this O(nx) approach. Do you have code or can you write 2-3 lines of pseudocode? Thanks.
deleted
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.
BTW, it can be solved using only integer arithmetics.
So you solved it after freeze?
Yes.
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).
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)?
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?
Any hints or solution for H?
Problem link : http://acm.timus.ru/problem.aspx?space=1&num=2085