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!
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!
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
Is the contest over? Anyone minds to share any problem's solution for silver division?
It's not over.
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.
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
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.
What were the problems for silver?
1: http://usaco.org/index.php?page=viewproblem&cpid=702
2: http://usaco.org/index.php?page=viewproblem&cpid=703
3: http://usaco.org/index.php?page=viewproblem&cpid=704
...you can't access those unless you are silver.
Didn't know that. Here's a paste. Sorry for the inconvenience.
Silvers: DP(i,j), where i and j are positions of where we "start" looking from, therefore there will be n^2 states
Assuming you are talking about Problem 1, wouldn't that time out as N = 2e4?
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
1e9 is an overstatement. 1e8 is nearly always safe.
Hints for Platinum division:
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 :( ).
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.
I used a bit with an implicit segtree in each node; passed all cases. Code: http://ideone.com/sfKpb4
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.
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))).
2D range tree --> MLE on test case 10 :( :(
One testcase wrong oops.
Passed with O(n2) on #2 somehow!
For 3rd I wrote a 2D BIT on a smart hashmap. http://pastebin.com/DPemaJeW
It is O(n·log2n) time and memory, and I was actually a bit surprised it passed within a second.
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: moo
Let'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.
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.
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.
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.
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 ?
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!
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.
Me using segment tree with AVL tree and only passed 7 cases, I thought O(N log N) is need :'(
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.
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 :(
Why is the site still stating that the contest is running?
@xiaowuc1 Is there a better solution than 2D range tree or Sqrt decomposition + fenwick in better order?
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
Oh! cool! Can you explain the idea of the solution!?
Same here on C++ :)
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?
#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).
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
Sure, here's my source:
http://pastebin.com/vR1hgnTJ
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.
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 Division
Problem 1. Why Did the Cow Cross the Road
By 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_queueas a heap to do so.Problem 2. Why Did the Cow Cross the Road II
We 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 III
Before 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.
Gold Division
Problem 1. Why Did the Cow Cross the Road
I 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 II
Before 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 III
We 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?
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
Platinum Division
Problem 1. Why Did the Cow Cross the Road
We 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 II
As 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 III
By 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
Conclusions
Actually 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 :D
Last 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?
So why exactly did the cow cross the road?
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
To get to the udder side...
If I am looking at my results, they will die before they get to the other side. :D
for the same reason Why_did_the_chicken_cross_the_road
Results are out: http://usaco.org/index.php?page=feb17results