However, most of the other results suggest that this problemset has strongly favored submitting problems in the open, in particular problem C had less than 10% submissions correct. Unfortunately I was one of those caught out by the trick in this problem, and thus couldn't qualify for the final round - good luck to all those who did!
I think problem D was the most beautiful in this set, and it was also quite tricky with just 34% success rate. You were given... nothing, but you could ask questions. In each question, you could name an integer not exceeding 1018 by absolute value, and you were told whether this number is black or white. You also knew that the structure of black/white numbers is very regular: more precisely, there exists a positive integer l not exceeding 1017 such that black/white numbers form alternating blocks of l consecutive numbers each: numbers from a to a+l-1 are white, numbers from a+l to a+2l-1 are black, numbers from a+2l to a+3l-1 are white again, and so on both in positive and negative directions. However, you don't know the values of a and l. Your goal is to determine the value of l using at most 2000 questions.
Problem F in this round was an interesting exercise in researching and gradually gaining an understanding until the solution becomes clear. The research subject is two permutations of 2n objects, called L and R. The permutation L is constructed like this: the first n objects in the old order go to odd-numbered positions in the new order without shuffling, and the last n objects in the old order go to even-numbered positions in the new order, without shuffling. The permutation R does almost the same, but the first n objects go to even-numbered positions, and last n go to odd-numbered positions. You are given three numbers: n, a and b. An object is currently on position a in the permutation of 2n objects, and we want to put it to position b using only operations L and R. Construct any shortest sequence of those two operations that achieves it.
Here are the 120 qualified contestants grouped by country:
Russian Federation - 30: Petr, Merkurev, kuniavski, ariacas, lhic, AMashrabov, ifsmirnov, knightL, Dembel, Egor, UdH-WiNGeR, Burunduk1, Vercingetorix, Kankuro, Endagorion, Um_nik, qwerty787788, VArtem, eatmore, 2rf,Michael_Levin, -XraY-, Enot, pashka, niyaznigmatul, RiaDWaW, HellKitsune, Copymaster, LoRd_TaPaKaH, KalininN
China - 26: jcvb, SanSiroWaltz, maopao, jiry_2, liympanda, jinzhao, edly01, dnvtmf, BSBandme, lxhimo, hzt1, quailty, zhuojie, panjf1987, zyxwvu164, ftiasch, liymsheep, ACRush, Blue.Mary, Herzu, cvcvb_lyp, matthew99a, Ronnoc,xudyh, xyz111, wenhanhuang
Japan - 17: snuke, semiexp, sugim48, rng_58, camypaper, sky58, yosupo, uwi, rickytheta, j_gui0121, chokudai, LayCurse, tozangezan, logicmachine, anta, hogloid, natsugiri
Poland - 12: embe, marek.cygan, dasko, Marcin_smu, fruwajacybyk, tom612pl, Errichto, Swistakk, mnbvmar, Stonefeang, krismaz, dj3500
Ukraine - 8: K.A.D.R, sdya, mgch, Vasyl[alphacom], LeBron, dzhulgakov, MrDindows, Milanin
Taiwan - 5: peter50216, eddy1021, ShikXD, aaaaajack, dreamoon
Belarus - 4: tourist, Arterm, subscriber, Ra16bit
South Korea - 4: ainu7, ainta, jaydoubleuel, Kriii
Australia - 2: izrak, John Dethridge
United States - 2: scott_wu, ksun48
Canada - 2: FatalEagle, azneye
Netherlands - 1: krijgertje
Brazil - 1: ffao
Switzerland - 1: W4yneb0t
Germany - 1: pwahs
Croatia - 1: ikatanic
South Africa - 1: bmerry
Indonesia - 1: azaky
Viet Nam - 1: skyvn97
The solution for the easy problem relied on a cute geometric observation. The problem went like this: you are given 1500 points on the plane. You can move from any point to any other point if there are no more points on the segment connecting them. For all pair of points you need to determine what's the smallest number of moves needed to get from one to the other - and of course to do it faster than the standard O(n3) all-pairs-shortest-paths algorithms.
The hardest problem F forced one to pick a good tradeoff between studying too many cases on paper and implementing more logic in the solution. You were given at most 100000 integers ai, each between -C and C, and a goal d. You needed to find such integers xi, also between -C and C, that sum of ai*xi is equal to d. Additionally, none of xi must be equal to zero.
It's not hard to see that without the "between -C and C, and non-zero" restriction a solution exists if and only if the greatest common divisor of all ai divides d. It turns out that for sufficiently large values of C nothing changes. This problem in particular had C always equal to 1000000, so solving it was a matter of careful reasoning and implementation.
What is the largest value of C for which the condition mentioned above is not sufficient?
The first step is quite usual: instead of finding the point with the smallest asymmetry value directly, we'll learn to check if there are points with asymmetry value below the given value, relying on binary search to then produce the final answer.
Then we notice that when determining the asymmetry value of a given point, we can consider only the lines passing through a vertex of the polygon, and where the longer of the two resulting segments is between the point and the vertex (assuming it's not, we can show that turning the line in one of the two directions will not decrease the ratio).
That observation reduces our problem to the following question: consider the n smaller polygons obtained by compressing our polygon m/(m+1) times towards each of its n vertices. Do they intersect?
An intersection of a few convex polygons can also be thought of as an intersection of all half-planes containing their sides. However, we have n n-sided polygons to intersect here, so we have n2 half-planes, and that's too much.
However, all those n2 half-planes were obtained by shifting one of the n sides towards one of the n vertices. As we see on the picture on the left, instead of looking at all n images of one side, it's enough to consider the one where it's shifted the furthest - in other words, towards the vertex that's most distant from the line containing given side! We can find the most distant vertex for each side once using the rotating calipers algorithm, and then we have only n half-planes to intersect each time.
And that means we have reduced the original problem to a standard one: check if n half-planes have a non-empty intersection in O(nlogn) or faster. This problem has a tedious standard solution and a beautiful randomized solution. Let me describe the latter.
The randomized algorithm inductively builds the answer to the following question: what is the point (x, y) that lies in the intersection of the given half-planes and maximizes the value of ax+by, where a and b are some arbitrary constants, for example the normal vector to the first half-plane's boundary (such pick will make sure that the value ax+by in that half-plane is bounded from above)?
Assume we already know such point (x, y) for some set of half-planes and want to add one more half-plane. There are two possibilities: either the point (x, y) belongs to the new half-plane, or not. In the former case, nothing needs to be done - the old maximum is also the maximum now.
In the latter case, it's easy to see that the new point (x, y) must lie on the boundary of the new half-plane. Knowing that, we can find it by intersecting all previous half-planes with that boundary, and then solving the 1D half-line intersection problem by finding the bottom-most downwards and top-most upwards half-lines.
That's the entire algorithm - we will add all half-planes in random order, and either find a point (x, y) in their intersection or learn that there's no such point.
The interesting part is, of course, its running time. In the worst case, we'll have to solve the 1D problem every time, for the total running time of 1+2+...+n=O(n2). However, since we consider the half-planes in random order, it's unlikely that we will always run into the worse of two cases. More precisely, consider the i-th step of the algorithm. The point (x, y) after this step lies on the intersection of the boundaries of some two of the first i half-planes. This point was also the answer on the previous step i-1 unless the i-th half-plane is one of those two. That means that the probability that we need to solve the 1D problem on the i-th step is at most 2/i. Solving the i-th 1D problem takes O(i), and thus the expected total running time is O(1)/1+O(2)/2+O(3)/3+...+O(n)/n=O(1)+O(1)+...+O(1)=O(n) - linear!
This is the first time I describe this algorithm and I haven't yet implemented it myself, so please correct me if there are any errors or ways to implement it even simpler!
And of course, thanks for reading, and check back soon for more.
And that means we have reduced the original problem to a standard one: check if n half-planes have a non-empty intersection in O(nlogn) or faster. This problem has a tedious standard solution and a beautiful randomized solution. Let me describe the latter.
The randomized algorithm inductively builds the answer to the following question: what is the point (x, y) that lies in the intersection of the given half-planes and maximizes the value of ax+by, where a and b are some arbitrary constants, for example the normal vector to the first half-plane's boundary (such pick will make sure that the value ax+by in that half-plane is bounded from above)?
Assume we already know such point (x, y) for some set of half-planes and want to add one more half-plane. There are two possibilities: either the point (x, y) belongs to the new half-plane, or not. In the former case, nothing needs to be done - the old maximum is also the maximum now.
In the latter case, it's easy to see that the new point (x, y) must lie on the boundary of the new half-plane. Knowing that, we can find it by intersecting all previous half-planes with that boundary, and then solving the 1D half-line intersection problem by finding the bottom-most downwards and top-most upwards half-lines.
That's the entire algorithm - we will add all half-planes in random order, and either find a point (x, y) in their intersection or learn that there's no such point.
The interesting part is, of course, its running time. In the worst case, we'll have to solve the 1D problem every time, for the total running time of 1+2+...+n=O(n2). However, since we consider the half-planes in random order, it's unlikely that we will always run into the worse of two cases. More precisely, consider the i-th step of the algorithm. The point (x, y) after this step lies on the intersection of the boundaries of some two of the first i half-planes. This point was also the answer on the previous step i-1 unless the i-th half-plane is one of those two. That means that the probability that we need to solve the 1D problem on the i-th step is at most 2/i. Solving the i-th 1D problem takes O(i), and thus the expected total running time is O(1)/1+O(2)/2+O(3)/3+...+O(n)/n=O(1)+O(1)+...+O(1)=O(n) - linear!
This is the first time I describe this algorithm and I haven't yet implemented it myself, so please correct me if there are any errors or ways to implement it even simpler!
And of course, thanks for reading, and check back soon for more.
0 komentar:
Post a Comment