### chaosagent's blog

By chaosagent, history, 3 years ago, , The first USACO contest of the 2016-2017 season is going to run from 12/16 (Friday) to 12/19 (Monday). Let's discuss the contest and the problems here after the contest :) Comments (45)
 » I guess Mexicans aren't allowed to participate.
•  » » The firewall hasn't been built yet.
•  » » » Trump: "I will build a firewall and make China pay for it".Later...USA team got 1 bronze medal and 3 honorable mentions at the IOI (and China didn't pay for the firewall).
 » Problems in English only? or ? :)
•  » » There already problems in en, ru, fr.
 » 3 years ago, # | ← Rev. 2 →   can anyone explain for me why the input of problem 3 — silver is 3 :(( .The 4th cow can't be reached so i think the answer is 2 @@@
•  » » 3 years ago, # ^ | ← Rev. 2 →   deleted. I think that my comment doesn't give any hint to this problem. Anyway, excuse me)
•  » » » Please do not discuss problem specifics DURING the contest >.<
 » Can i ask for a clarification in Silver Contest Problem 3 Mooncast?
 » How to solve the first Platinum Division problem? (Lots of triangles)
•  » » My solution: Angular sort, radial sweep, range query. Complexity: O(n3log(n)).Is there O(n3) solution or better exists?
•  » » » And my solution TLEd -_- (I used angular sort + count number of inversions). However, I heard from minimario that an O(n3) solution exists.
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   My O(N4  /  64) with bitsets fit in the time limit.
•  » » » » I went from only 3 tests to full score by just removing constant factors from my complexity :D :D
•  » » » » » I don't really mind the downvotes but just in case someone thinks I was lying: O(N^3logN)\$ — 3/10, O(N^3logN) — 10/10.
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   The problem is technically a subproblem from codechef problem CHEFPOLY.To solve in O(n3), do inclusion exclusion. Choose any point that is at extreme bottom left, now, for all O(n2) triangles made by this point, check points lying inside in O(n). Note how all original triangles can be defined as some addition of two of these triangles and subtraction of one. Now you can process each triangle in O(1). Also the bitset solution is described here.
•  » » » 3 years ago, # ^ | ← Rev. 4 →   O(3004  /  6) solution is kinda obvious. you can optimize it to O(3004  /  (6  *  64)) by using a bitset. which is better than O(3003) .UPD: sorry, dogewizard420blazeit answered that before me
•  » » » 3 years ago, # ^ | ← Rev. 3 →   Yes. if we pick triangle with point A, B, C. we remove points that is outside of line A-B, B-C, C-A (precompute this in N^3) Unfortunately this removes some points two times. So, we precalculate rangePoint[X][P][Q] = num of points y s.t ccw(X, P, y) > 0 and ccw(X, y, Q) > 0, and add them. With N^3 precomputation we get O(1) per query. precomputate DP1[X][Y] = number of points p s.t ccw(X, Y, p) > 0 and X.x <= p.x <= Y.x. (also with ccw(X,Y,p) < 0) Now we can get O(1) per query. Careful with elements with same X coordinate..... In contest, I didn't realized such exists, and coded n^3lgn solutions. (angular sort + bit) I got TLE, so I precomputed angular sort for n^2lgn, and get AC. (I know this is dirty :D)
•  » » You can pick a point say the point leftmost of all points (point P) and fill a pre_process array dp[i][j] that means in the triangle with vertices P,i,j how many dots are there we can fill this array naively O(n^3) and then for any triple (a,b,c) we can easily find out the number of dots inside it O(1) for example the number of dots inside(a,b,c) can be equal to : dp[a][c] — dp[a][b] — dp[b][c] — 1 OR dp[a][b] + dp[b][c] — dp[a][b] (if b is between a,c if we look at it from P) so the overall complexity will be O(n^3)(filling up the array and finding out which point is in between to other points by looking at it from P can be easily implemented by cross product)
•  » » » Code here: http://paste.ubuntu.com/23662295/
•  » » Let's use trapezoidal decomposition. Loop through all segments and compute the number of points inside the trapezoid formed with the x-axis. Now, for any query triangle, lets pick the longest segment forming it and look at the third point not forming this segment. Depending on which side of the segment this third point is, we either add 2 trapezoids and subtract 1, or subtract 2 trapezoids and add 1. Either way, it's O(n3).
 » 3 years ago, # | ← Rev. 3 →   How do you solve gold 2 and gold 3?
•  » » 3 years ago, # ^ | ← Rev. 4 →   You can solve third problem by bfs. Here is the code.
•  » » » Can you describe your algorithm with words?
•  » » » » I just did coordinate compression for P3 Gold, then did normal BFS with a global visited array. It passed all tests
•  » » 3 years ago, # ^ | ← Rev. 4 →   gold 2 ==> DPwtf of down?! :/
•  » » » Please if it was useful put "+" here.
•  » » » Please if it wasn't useful put "-" here.
 » Any hints for problem C in platinum division?
•  » » From what I have heard, the problem is a harder version of Problem A in this competition: http://cs.stanford.edu/group/acm/slpclive/problems/problems_2016.pdfI've also heard that one can use Eppstein's algorithm to solve it.
•  » » 3 years ago, # ^ | ← Rev. 6 →   My solution is O(nlg^2n). I will only explain some key ideas, since the full algorithm is hard to explain.... Let's run some sort of Dijkstra here. we start from (0, 0, 0, 0 ....), and increase one element from each of N entry. This is NKlgN and I remember it didn't rewarded much. Observe that Kth pick differs for at most lgK elements from the 1st pick. We want to reduce state to N entry -> K entry, but it's not clear till now.. So, dismiss all rows with one elements, and sort every rows by order of M — M. Still it's not clear, so let's fix the number of changed elements (say C), and solve each problem independently. Now think about the two ways of state transition. In contest, I was short of time, and I just submitted optimized O(nlg^3n). This misses two TC as TLE. (956/1000) This is my code. http://ideone.com/s08eaoAlso, ainta told me that there is nlgn solution. I think it won't be really hard to optimize mine to nlgn...
•  » » » 3 years ago, # ^ | ← Rev. 2 →   Oops, sorry :(
•  » » Link to my solution of C (it got AC). It's an easy to understand DPlike bruteforce which runs in .
•  » » » Can you explain the code?
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   So let's begin with some facts.1) We can binary search on the maximum number we will get.2) If we sort the numbers in each row, we must get at least the minimum number in each row. So we subtract from each number the minimum in its row. We do this so that we can ensure that our transitions in the following DP will be O(K).3) How to do the check in the binary search? If we do a DP[add_sum] = number of ways to increase the minimum sum with add_sum, then we can notice that in each transition of the DP our count of numbers increases with at least 1. So we can maintain a global counter of all possible sums less than the current minimum that leads us to at most O(K) DP transitions (if our global counter reaches K we just return true). The complexity of the check is because of the map, but it can be improved using a hash table.4) after we find the maximal number the sum can be found in a similar manner.
•  » » 3 years ago, # ^ | ← Rev. 3 →   My solution is O(n log n) and it's really simple to code: Let's sort pairs (value, row) for all elements in all rows (except for the smallest ones), where value is the differences between the element and the smallest element in its row. Let's say that a state is a vector of positions (in the sorted array) and run Dijkstra's algorithm (starting from an empty vector). We need only two transitions: creating a new position immediately after the last one and increasing the last position by one. There's one problem here: we can take two elements from the same row. It's bad. Let's fix it by moving the last element until all rows are unique (we touch only the last element, so it's the only one that could break). That's it.
 » You know, people can compete in this competition until 4h after the official finishing time. I have 30 min left and I'm seeing a lot of spoilers.
 » How long do results take to publish? Will it be out by tomorrow?
 » This is pathetic. Officially, anyone can start USACO contest at Dec 19, 23:59 UTC time and start for 4 hours. You guys are discussing problems just after the time for the official start of the contest is over instead of four hours after it__. Even I started the contest 2 minutes before it officially ended and although I did not use any outside help, I came here after the contest to be the first guy to talk about it. Now, I am disgusted to see that three hours before the contest ended for me, some other people had already started discussing stuff. This is pathetic. P.S. Feels fun to get promoted to platinum!
•  » » And the people discussing it early are probably the ones downvoting you.
 » Results are available here!
 » My solution for problem C was as follows:First, notice that the approach with the priority queue has two problems: it is O(NK) and it generate duplicates. In order to solve both of these problems, notice that once we have an element in the queue (I.e., an array of indices for each of the N components), we have two options: Either we take the next best possible difference (let's call the corresponding position pos), or we completely stop adding differences from pos. You can see that, by doing that, the decision splits the solution space into two disjoint parts.The minimum, as well as all the operations, can be simulated in O(log(n)) with persistent segment trees. Hencr, total complexity is O((N + K)log(N + K)) Here is the code:http://pastebin.com/xHn88B3dNote: I did not notice that the cases were disjoint in contest-time, that's why I also have hashes comparison. They are useless in the code.