Discussion on all other matters, maybe unrelated to the COJ.
Forum rules
Discussing politics is not allowed. Any posts containing political comments will be penalized.
Post Reply
User avatar
Posts: 38
Joined: 8 years ago
Location: Santiago de Cuba
Gender: None specified


Post by ReynaldoGil » 8 years ago

I have a question, does anybody know where to find the acm-icpc finals data tests, because I can only find the 2011's one. And my other question is if there is some kind of official solution for the same competition??

User avatar
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified

Re: ACM-ICPC Finals

Post by ymondelo20 » 8 years ago

In this Site >
You can find the official problems from past ACM-ICPC world competitions.

In the Forum >
Some discussions about the problems of past World Finals.

Also, I let you this comments by Petr Mitrichev about the problems of the 2011 World Finals of ACM-ICPC :)
K is classical: find the two parallel lines closest to each other that will fit the given polygon (maybe rotated) between them. It's not hard to see that the line must be parallel to the line connecting some pair of vertices, so you can just try them all. For even faster solution, we should just check adjacent vertices of the convex hull.

C is quite straightforward as well. You are given 6 pictures of hieroglyphs, and need to write an OCR that will recognize them. The constraints say that the hieroglyphs in input may be distorted by the shape will be "topologically equivalent" to one of the 6 given pictures. The pictures are chosen such that one can just check the number of connected components of the white pixels (kudos to andrewzta for noticing that).

E is: given at most 500K points on a 1000x1000 grid, and at most 20 queries X, find the X by X square in (x+y, x-y) coordinates that has the most points inside. The constraints are so low that I believe the straightforward solution should pass: using inclusion-exclusion we can find the number of points in each square in O(1), then we can just check 20 million squares.

J, which several teams have attempted but failed, is: given a number C, represent it as a sum of numbers of form a_i=i*(i+1)*(2i+1)/6, b_i=4*i*(i+1)*(2i+1)/6, c_i=a_(2i+1)-b_i (sums of squares, sums of even squares, sums of odd squares). Each a_i, b_i, c_i may be used at most once. If there are several representations, choose the one with the smallest number of addends. If there are still several ones, pick the lexicographically largest one. I would expect that simple backtracking (trying all possible choices for the next number in decreasing order, and truncating the search when current best answer is less than remaining sum divided by the maximum possible value for the rest) works for J, since the numbers are quite dense and thus the be split will always be found very quickly.

A, which is the only remaining problem that has attempts on it, is the following: given two numbers a and m, and two segments [p, q], [r, s], one must create such sequence of operations +a and *m that will transform every number in [p, q] into some number in [r, s]. moreover, one should output the program of minimum length, and smallest lexicographically among those with minimum length. here's one idea: even if we add before we multiply, we still add a multiple of a. So in order to check what is the minimal number of steps required to transform a given segment [q, w] to become a segment inside [r, s], we can just iterate over how many times k we multiply, check that there's a multiple k*a of a that, after being added, will move the result inside [r, s], and the number of steps will be the number of multiplications plus the sum of digits in k when written in m-ary system (roughly). So in order to solve this we must solve a sub=problem: given a segment [l, r], what is the number with the smallest sum of digits (in m-ary system) inside that segment? That is a standard problem that is solved by considering the number of digits of that number that coincides with corresponding digits of l (or r). he above solution yields the lexicographically smallest representation as well if implemented carefully. This looks quite tricky to implement, though.

G is: you are given N segments connected in one row via flexible joints, and you need to assemble one or more polygons in such a way that every segment is a side of at most one polygon and the segments are not allowed to intersect except at endpoints. Your goal is to maximize the total area of the polygons. There are at most 500 segments in problem G. I guess the first question is does it ever make sense to form more than one polygon? Yes, obviously it does. Suppose one middle segment is much, much longer than the others so no polygon can be formed using it. In this case, the segments to the left and to the right of this segment should be treated independently. We can then build similar examples in each part to have the best answer include even more polygons. What doesn't make sense is to have one polygon have non-consecutive set of segments as its sides - we obviously can increase the total area by joining this polygon with the adjacent one then. So it seems that the solution should be: for every [l, r] part of the given sequence of segments, find the best polygon (this is a standard problem). Then, run a standard DP to find the best total area. The only trick I guess is to solve the "standard problem" for so many cases. The standard solution, as Google tells us, is that the optimal polygon with the given sides is a polygon inscribed in a circle, and we can find the radius of the circle by binary search. But that gives a running time of O(n^3*log(precision)) which may be too big. I would expect that it is fast enough, since n^3 is divided by 6 (the number of segments is n^2/2, and the average length of one is n/3). With the super-fast computers, that should be fast enough.

H is: given a graph, you need to mark the smallest number of its vertices in such a way that after removal of any vertex, there's a path from any vertex to some marked vertex. Unless I'm missing some corner case, this is reasonably straightforward (suggested by Burunduk1): first, we find the tree of biconnected components of the graph, then we choose one vertex in each of the leaves of this tree (in each biconnected component that is a leaf, we must choose a vertex that is not the articulation point that connects this component to the rest of the graph). In case the entire graph is biconnected, we must mark any two different vertices. This is obviously less than the optimal answer since all those marks are required (what happens if we disconnect a leave of the biconnected component tree?), and it's not hard to see they are sufficient.

D: you are given a 40x40 grid of ".", "/" and "C" letters. Your goal is to replace as many "."s by "W"s as possible in such a way that: the total number of "C"s and "W"s in each row and column is at most the given fraction of total number of "C"s and "W"s, and the total number of "C"s and "W"s in the first row is equal to the total number of "C"s and "W"s in the first column, the same for second row and second column, and so on.

F: you are given 100000 machines, each described by the day it appears on (D_i), the price to buy it (P_i), the money you get when you get rid of it (R_i), and the profit it brings on each day (G_i). You may own at most one machine at a time, you can get rid of an old machine and buy a new one in one day, a machine brings profit only on days between the one when you bought it and the one when you got rid of it (exclusive). You can only buy a machine exactly on the day it appears on, and you start with the given amount of money C. What is the maximum possible profit? this actually looks solvable: first, let's start with straightforward N^2 DP: we solve the problem "what is the most money we can earn from the previous machines if we buy k-th machine on the day it appears" by iterating over which machine will we buy before k-th. Then, we will optimize the solution to work in O(N*polylog(N)). More specifically, suppose the previous machine is m-th. Then the maximum profit to get before buying k-th machine is ans[m]-P_m+R_m+G_m*(D_k-D_m-1), and we can only do this if ans[m]+C>=P_m. The second condition doesn't depend on k at all, and the first only depends on D_k. So essentially when choosing the best m for the given k we're choosing the highest among several linear functions of D_k. We can find that quickly, for example, by keeping track of the convex hull of the existing functions.

B is: you are given integer coordinates of 3 points before and after the following transformation: first, you rotate the plane such that Ox axis passes through an integer point on the border of [-10,10]x[-10,10] square. Then, you round the coordinates (up in absolute value if the fractional part is 0.5). Then, you multiply all coordinates in each axis by a non-zero integer (different for different axes). And then, you add an integer constant to all coordinates in each axis (different for different axes). You're asked whether there exists such transformation for the 3 given points, and if yes, whether those transformations transform each integer point in the same way. It looks like one can just iterate over all possible rotations, then find scaling and translation numbers based on linear equations, and then check the resulting transformation. The biggest difficulty I guess would be handling corner cases where all points have the same coordinates and suchlike.

I is: you are standing in a cell of an infinite plane, and you have 100000 mummies going after you. Each mummy stands in some cell. You make moves in turn: first, you can move to any 8-adjacent cell. Then, each mummy moves to a 8-adjacent cell that is closest to you. You lose if at any point a mummy is in the same cell as you. What is the maximal number of moves you can survive? problem I solution together with FedorTsarev: first, let's assume that once the mummy catches us, it follows all our moves. It means that we need to find the largest time X such that we can be in a point distinct from all mummies at time X, and that can be done by binary search. To check a specific X, we believe the following proposition works: we take a 2X+1 times 2X+1 square with center in our position, and check if it's completely covered by 2X+1 times 2X+1 squares centered at mummies'. This relies on assumption that the way the mummies move in the problem statement is "optimal", but this is kind of obvious, since their move always provide strictly optimal distance to us both by x and by y. And checking if a square is covered by other squares can be done in O(NlogN) using the sweeping line method and keeping an interval tree that stores how many times each cell is covered.
"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

Post Reply

Return to “Off topic”