| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
Is anyone else with an automatic berth unable to register? I know JoeyWheeler and I got automatic berth and can't register but gongy qualified through round 1C and successfully registered...
How to solve A ? Exponential dp on power of 3 s or something?
Cases.
Basic observations: 1. First of all just look at the exponenets, so we have n pairs of integers, and we can replace two pairs by its max, or min. 2. WLOG our goal is to get (0, 0). // by subtracting goal
Then we divide points in four categories x-axis, y-axis, center, the rest. Now:
If we have ≥ 2 centers then OK
If we have 1 center and sth on some axis then OK
If we have 1 center and maximum of all points in the rest has x, y > 0 or minimum of all points in the rest has x, y < 0 then OK.
If we have sth positive on both axis, or sth negative on both axis then OK
If all points on x-axis are positive, and all pts on y-axis are negative, and we have soem point in the rest with x < 0 and y > 0 then OK.
If all points on y-axis are positive, and all pts on x-axis are negative, and we have soem point in the rest with y < 0 and x > 0 then OK.
In other cases Impossible.
Can you or someone else give more intuition of these cases? How do we go from these properties to the existence of a series of moves that guarantee hitting the target?
Suppose that there is no pts in the center. First of all we have to have sth on both axis — which is clear.
The last move should be min on (+,0) and (0,+) or max on (-,0) and (0,-).
Suppose that there are points of the form P1 = (0, + ) and P2 = ( + , 0). Then replace all the rest by one point in any way, say Q = (a, b). Depending on where the Q is we can either remove Q (i.e. min(P1, Q) = P1 or etc.) or project Q on some axis (i.e. min(P1, Q) = (0, b) etc. )
to obtain two pts of the form (0, + ) and ( + , 0). And we use min on them.
In the same way we can treat the case P1 = (0, - ) and P2 = ( - , 0). (Because there is the symmetry : (x, y) – > ( - x, - y) which swaps min and max).
The remaining case is: all pts on x-axis are (+,0), and all pts on y-axis are (0,-).
When we have some point of the form (-,+) then we can in first move use max((0,-),(-,+)) = (0,+). And use the previous case. So suppose that we have no pts of the form (-,+). So the upper left quarter of plane is empty. Observe that using moves we cannot get into this quarter so it is impossible to get (0,0) (which lies on the boundary of that quarter).
Ok. Now the center can be treated as point on x-axis or y-axis. Using the same arguments we can consider the cases with center too.
I had dp/backtrack with memoization, complexity about O(39) but I don't have a proof that it works. There are 9 groups of elements and I assumed that in each group we don't need more than 2 elements. So, each group contains 0, 1 or 2 elements.
Iterate over all subsets of three numbers. First do gcd operation for all numbers not in the subset, then iterate over all operation sequences for the remaining three operations. If you do not find answer this way, then its Impossible.
Here's a proof I had for casework:
First, there are 9 types of numbers 2^(<a,=a,>a) * 3^(<b,=b,>b). I labeled these numbers below:
For instance 1 is 2^(<a) * 3^(>b), 2 is 2^(=a),3^(>b), 9 is 2^(>a), 3^(<b)
The lcm/gcd can be intepreted as taking two points
and replacing with one of
Or, if we have
We can delete one of the points.
More concretely, we can make rules like (2 and 6) can become 5 or 3. Or (6 and 3) can become 6 or 3. And so on for all 9^2 pairs of input.
Now, for the actual solution. We need (2 or 5 or 8) and (4 or 5 or 6) to be able to reach the target.
For always possible cases:
For other cases:
Thus, only cases we haven't covered are