### xiaowuc1's blog

By xiaowuc1, history, 14 months ago, ,

Hi all,

The third contest of the 2016-2017 USACO season will be open from February 10th to February 13th. This will be our last contest before the US Open. Feel free to discuss the problems here after the contest is over!

•
• +60
•

 » 14 months ago, # |   0 Is the contest over? Anyone minds to share any problem's solution for silver division?
•  » » 14 months ago, # ^ |   0 It's not over.
•  » » 14 months ago, # ^ |   0 The people who started the contest during the last possible moment are still competing until 16:00 UTC. There's a bit less than 3 hours left.
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 I couldn't solve the first one completely but I got 5 test cases with a dumb greedy algorithm. I sorted the intervals by starting time, and sorted the other time list. Then just greedily matched intervals to times. Would love an approach for this one.For the second one, just make a huge array of ints of size N and initialize everything to zero. Set all broken ones to 1. Select the k length subarray with least sum (using sliding window/cumulative sum).For the third one I imagined the whole grid as a graph with complete connectivity initially. The roads were edges we could not take. Then on this new graph, I ran component division using DFS and inside the main loop I checked if the edge being considered is in the "forbidden" edge list or not. So the DFS takes O(N2 R) time which passes time limit. This can be optimized using hash table/BST. Now that we have marked connected components with different numbers, we just try all pairs in the K cow list and check if they are in the same component. If they are not, add one to the counter and finally print the counter. This was a cute one.Will I get to gold with this performance?EDIT: Fix math notation
•  » » » 14 months ago, # ^ |   0 The highest promotion boundary cut-off over the past couple years looks like 800, so unless the promotion boundary is higher than that, you should be promoted to gold.
•  » » » 14 months ago, # ^ |   0 I did the same thing that you did for #1, but i sorted the intervals by ending time. Code: (it's in java) http://pastebin.com/CvzvfXR6
•  » » 14 months ago, # ^ |   0 What were the problems for silver?
•  » » » 14 months ago, # ^ |   0
•  » » » » 14 months ago, # ^ |   +3 ...you can't access those unless you are silver.
•  » » » » » 14 months ago, # ^ |   0 Didn't know that. Here's a paste. Sorry for the inconvenience.
•  » » » » » » 14 months ago, # ^ |   0 Silvers: DP(i,j), where i and j are positions of where we "start" looking from, therefore there will be n^2 states
•  » » » » » » » 14 months ago, # ^ |   0 Assuming you are talking about Problem 1, wouldn't that time out as N = 2e4?
•  » » » » » » » » 14 months ago, # ^ | ← Rev. 2 →   0 Oh wait, that's the different problem, sorry.For that problem you can sort the intervals by their Right point, then, you can look for a lowest point(in "Chickens" array) where it can still be placed. You can do that using binary search and using a set or, as I did, a full search in O(n) time, which did result in O(n^2), but passed TL :/Usually, the TLE is when the number of operations is >= 1e9, in this case, however number of operations were less
•  » » » » » » » » » 14 months ago, # ^ |   0 1e9 is an overstatement. 1e8 is nearly always safe.
 » 14 months ago, # |   +21 Hints for Platinum division: BIT Segtree 2d range tree. Needed a few optimizations to fit into ML. There's probably a faster way. I derped on the first one because I didn't realize that rotating just one side wasn't enough — you had to check rotating both (in addition, I solved #3 first, so I copied my 2D range tree code from it instead of just using a simple 1D BIT, greatly overcomplicating the problem :( ).
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 We can also use a BIT for Number 2 and a kind of 2D BIT for the Number 3 (although I am not sure if it works). Also, how did you optimize the 2D range tree? I tried that for more than 2 hours but could only get it to pass 10 test cases. I had 5 minutes left when I figured out the BIT solution, but when I submitted it (with seconds to spare), it only solved 3 test cases due to a small bug.
•  » » » 14 months ago, # ^ |   0 I used a bit with an implicit segtree in each node; passed all cases. Code: http://ideone.com/sfKpb4
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   0 I used almost the same code, but it failed 5 cases. Was it because I was declaring the new nodes on the spot?
•  » » 14 months ago, # ^ |   0 I've used Mo's algorithm with Fenwick tree in the third problem. Although my solution is O(N * sqrt(N) * log(N)), it passes all the tests within a second.
•  » » » 14 months ago, # ^ | ← Rev. 2 →   0 I also used sqrt bucketing with Fenwick but initially didn't AC. Messed with the bucket size a little and then it passed. Interestingly if you make bucket sizes equal to sqrt(N * log(N)) then you can bring it down to O(N * sqrt(N * log(N))).
•  » » 14 months ago, # ^ | ← Rev. 3 →   0 2D range tree --> MLE on test case 10 :( :(One testcase wrong oops.Passed with O(n2) on #2 somehow!
•  » » 14 months ago, # ^ |   0 For 3rd I wrote a 2D BIT on a smart hashmap. http://pastebin.com/DPemaJeWIt is O(n·log2n) time and memory, and I was actually a bit surprised it passed within a second.
•  » » 14 months ago, # ^ |   +15 Here is an interesting solution, which doesn't involve 2D. Maybe it works, maybe it doesn't, because I haven't gotten a chance to submit: mooLet's call the left cows ai and the right cows bi. Now, let pi = abi. Our goal is to count the number of pairs i < j such that pi > pj and |bi - bj| > k.We use divide and conquer. At some step, we consider some pairs such that l ≤ i < j ≤ r. Now, from conquer we only need to count the pairs where and . Let's sort all the indices from l to r by b value, and process them least to greatest. Maintain 2 BIT's storing the p values (one for [l, mid] and one for (mid, r]) and query appropriately.
•  » » 14 months ago, # ^ | ← Rev. 3 →   +5 Did anyone else get time limit exceeded for platinum question 3 using an O(nlog2(n)) solution? I used a segment tree containing a binary search tree (AVL tree) at every node and it took about 4 second for a large test case on my machine. Obviously it was badly over the time limit on the judge's server.
•  » » » 14 months ago, # ^ |   0 If you didn't optimize the constant, then you got TLE. An easy way to optimize the constant is by using a Fenwick tree for the first dimension.
•  » » » » 14 months ago, # ^ |   0 Apparently, using a Fenwick tree for the first dimension is not sufficient. I got TLE and MLE using it. Also, I think we can make the solution use O (N logN) memory by compressing the values for the lower dimension.
•  » » » » » 14 months ago, # ^ |   0 What do you mean about compressing the values for the lower dimension ? Isn't using segment tree contain a BST is already having O(N log N) memory ?
•  » » » » » » 14 months ago, # ^ |   0 For each lower level tree, we can calculate the update values in N log N time. Then we can sort them and binary search before each update/query. (I am talking about the 2D range tree/BIT solution)
•  » » » 14 months ago, # ^ |   0 My solution is simply and it passed all the cases within the time limit (the worst case runs in 881ms)Here are the submission verdicts: And here is the detail of my approach: Click Me!
•  » » » » 14 months ago, # ^ |   +7 I'm not having trouble solving the problem, I replaced the AVL tree with a splay tree and my solution takes < 200ms. I was just wondering if anyone else had to struggle to optimise an O(nlog2(n)) solution. If it is the intended complexity, then it seems a bit tight.
•  » » » » » 14 months ago, # ^ |   +8 Me using segment tree with AVL tree and only passed 7 cases, I thought O(N log N) is need :'(
•  » » 14 months ago, # ^ |   0 What's a range tree?
•  » » 14 months ago, # ^ | ← Rev. 2 →   +3 My solution passed for problem 3.(1099ms on max test)The core idea:Within each block,instead of a BIT,consider a data structure that supports update and O(1) query. UPD: It's actually 1470ms on max test,sorry.
•  » » 14 months ago, # ^ |   0 Apparently if you only check rotating the bottom, you get 3/10 test cases (1, 4, 5), but if you check rotating the top, you get 8/10 test cases (miss 4 & 5). My luck is real :(
 » 14 months ago, # |   0 Why is the site still stating that the contest is running?
 » 14 months ago, # |   0 @xiaowuc1 Is there a better solution than 2D range tree or Sqrt decomposition + fenwick in better order?
•  » » 14 months ago, # ^ |   +8 I had a solution using a merge sort tree with fenwick trees in each node. It uses O(n log n) space and takes O(n log^2 n) time. You can see my code here: http://pastebin.com/N1EeqNRS
•  » » » 14 months ago, # ^ |   0 Oh! cool! Can you explain the idea of the solution!?
•  » » » 14 months ago, # ^ |   0
 » 14 months ago, # |   +89 The problems in platinum division showed a lot of creativity. Like why the hell would someone think that putting 3 DS problems in a single problemset of 3 problems is cool?
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 #2 can be solved with nothing more than DP and arrays. I do think it's a bit much to have DS questions for both 1 and 3 though (unless they also have better solutions).
•  » » » 14 months ago, # ^ | ← Rev. 3 →   +8 Can you share your code, please? And still, the fact that there is a solution which differs from an obvious one with a tree doesn't make the round less boring. As I can see kliu31415 and percywtc used trees, too :)UPD: lol why did percywtc appear purple :D
•  » » » » 14 months ago, # ^ |   0 Sure, here's my source:http://pastebin.com/vR1hgnTJ
•  » » 14 months ago, # ^ |   +3 And more is that, the trick I used to solve Problem 1 and Problem 3 are both involving Number of Inversions.I think the problems each is interesting, but when the authors intend to put series of problems with similar background(cow crossing roads?). Although the solutions themselves are not the same, it is very easy that those problems involves similar tricks or approaches because the background of them limited the range of possible topics.Still, I appreciate the author brilliant idea of preparing problems with similar background and same title(is it same for Bronze as well?). It is not that easy to come up with a large number of problems that all of them can share same background. The first moment when I realized the names of problems in next division were all same as the previous division, I was just expecting problems with greater constraints, stricter limitations to increase the difficulty of the problems, but it turns out to be in 9 of the problems, only two of them overlaps, which is quite a small number than I expected.
 » 14 months ago, # | ← Rev. 2 →   +34 This contest is really memorable to me. As I long time did not participate USACO, my previous division was Silver. As a result, I participated in the Silver contest, and got in-contest promotion to the Gold division, and participated in the Gold contest, and got in-contest promotion again to the Platinum division, and finally, participated in the Platinum contest.So I decided to share all my solutions and ideas to the contest from Silver division to Platinum division.As the solutions are quite long, I decide to split the solutions into 3 parts according to their divisions. This can also let us discuss the solutions for different divisions without colliding on the same comment.Silver DivisionProblem 1. Why Did the Cow Cross the RoadBy getting maximum number of pair (i, j) such that Aj ≤ Ti ≤ Bj, we can greedily match each j to some i. We can perform this by starting from the chicken with smallest Ti, greedily match this chicken to the cow (that fulfill Aj ≤ Ti ≤ Bj) with the maximum Bj. I used priority_queue as a heap to do so.Problem 2. Why Did the Cow Cross the Road IIWe can just pre-compute the prefix sum so that we can calculate the number of damaged signals with range i..i + K - 1. And thus we can iterate through all possible i to find the answer.Problem 3. Why Did the Cow Cross the Road IIIBefore looking for the answer, we can first find the groups of cows that they can visit each other without crossing any road. This can be done by simply DFS, we can go from (x, y) to (x', y') only if there are no roads between them and they are adjacent grids.At last, we can compute the answer by knowing the fact that the cows in seperated groups are distant with each other. Therefore, if we have M groups in total, and the i - th group consists of Gi cows, the answer is G2 × G1 + G3 × (G1 + G2) + G4 × (G1 + G2 + G3).... We can quickly calculate the answer with the aid of calculating the prefix sum of Gi.
 » 14 months ago, # | ← Rev. 3 →   +31 Gold DivisionProblem 1. Why Did the Cow Cross the RoadI solved this with Dijkstra(this is my first thought after reading the problem, I am quite sure there are easier solutions). Let us denote dist[x][y][k] as the minimum cost to reach (x, y) such that this is the (k mod 3)-th step from the starting point. We will only add the cost Gi, j if the previous k is 2, otherwise, the additional cost is zero. Problem 2. Why Did the Cow Cross the Road IIBefore talking about the solution to this problem, I have to state that this is the easier version of the Problem 2 in Platinum Division.Okay, I used 2-dimension DP to solve this problem. Here, we denote dp[i][j] as the maximum number of crosswalks that can be drawn if we just consider the first i cows on one side of the road and the first j cows on the other side of the road.Then we can use this transition formula to compute the whole dp[][] array: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]), And when |a[i] - b[j]| ≤ 4, we also have to consider: dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1).So the answer would be dp[n][n]Problem 3. Why Did the Cow Cross the Road IIIWe can observe that pair (a, b) is a "crossing" pair if and only if the pattern a, b, a, b appears in the circle. In other words, we can just consider the pattern a, b, a and b, a, b in the input (not a circle but a straight line).I calculate the number of occurrence of that two patterns with the aid of Mo's algorithm, and the time complexity of the whole solution is . I think there should be faster solutions?
•  » » 14 months ago, # ^ |   -8 For gold 3rd I sorted all the segments and then processed then one by one starting from the "shortest" one, then used BIT with the sums, because the smaller intervals have been processed, their value in BIT array will be set to zero
 » 14 months ago, # | ← Rev. 3 →   +47 Platinum DivisionProblem 1. Why Did the Cow Cross the RoadWe can transform the problem into counting the number of inversions on one side if we keep shifting the sequence on the other side. For instance, the sample can be transformed into considering the second sequence as 3, 4, 5, 1, 2 (if we decide to shift the second sequence).We can maintain the number of smaller elements that came after the element i for each i with Segment Tree. For simplicity, we denote this number as counti. The number of inversion of the permutation will be the sum of counti. And each time we move the first element k to the back, the value countk becomes 0, and all counti with i > k will increase 1. Maintaining the values of counti with Segment Tree, we can easily update and calculate the number of inversions with O(logN)Problem 2. Why Did the Cow Cross the Road IIAs I mentioned above, this problem is an harder version of Problem 2 in Gold Division. I just improve my solution to O(NlogN) instead of O(N2).We can observe that for every abs(ai - bj) ≤ 4, dp[i][j] is the maixmum of all dp[x][y] with x < i and i < j. Therefore, by iterating i, we can reduce the dp[][] array to one-dimension, dp[], where dp[j] denotes the number of crosswalks for just the first i and first j elements on two sides with abs(ai - bj) ≤ 4. We can maintain this dp[] with Segment Tree. For every i, we should pre-compute all the values j such that abs(ai - bj) ≤ 4. Then, when we iterate i from 1 to n, we can update dp[j] as the maximum value among dp[1..(j - 1)] plus one.Problem 3. Why Did the Cow Cross the Road IIIBy renumbering the input so that the first n numbers A1..n are 1, 2, .., n. We can just consider the second set of n numbers B1..n, and thus simplify the problem as calculating the number of pairs (i, j) such that Bi > Bj and A[Bi] - A[Bj] > K.Recalling that during the process of merge sort, we can calculate the number of inversions as well. Here I used this trick and handle the rule Ai - Aj > K as well. Every time we merge the two sorted sequences, let's say S and T, we can maintain a Segment Tree which can help us that for each element Si, after finding the maximum j such that Si > Tj, we can calculate the number of elements in T1..j that A[Tx] + K < A[Si] or A[Tx] - K > A[Si]. So, every time we increase j, we can update the ranges 1..(A[Tj] - K - 1) and (A[Tj] + K + 1)..N.Thus, the time complexity of my whole solution should be ConclusionsActually this is my first time sharing solutions of many tasks of one contest, and also as I participate quite early in the 4 days window, my memory to the problems are not very fresh. I apologize for any mistakes or stupid things I have made in this text.I would be appreciated if you could share your thoughts to my solutions as well :DLast but not least, the only problem I can't solve during the whole contest (may someone help me?) — Why did the cow cross the road?
 » 14 months ago, # |   +10 So why exactly did the cow cross the road?
•  » » 14 months ago, # ^ | ← Rev. 2 →   +27 We may never know the full reason, but it is certain that Farmer John's cows do end up crossing the road quite frequently :D
•  » » 14 months ago, # ^ |   +19 To get to the udder side...
•  » » 14 months ago, # ^ |   +11 If I am looking at my results, they will die before they get to the other side. :D
•  » » 14 months ago, # ^ | ← Rev. 4 →   +3 for the same reason Why_did_the_chicken_cross_the_road
 » 14 months ago, # |   +28 Results are out: http://usaco.org/index.php?page=feb17results