xiaowuc1's blog

USACO 2016-2017 February Contest
By xiaowuc1, history, 8 years ago, In English

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!

  • Vote: I like it
  • +60
  • Vote: I do not like it

Comments Comments (50)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the contest over? Anyone minds to share any problem's solution for silver division?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's not over.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What were the problems for silver?

    → Reply
»
8 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Hints for Platinum division:

  1. BIT
  2. Segtree
  3. 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 :( ).

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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))).

      → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    2D range tree --> MLE on test case 10 :( :(

    One testcase wrong oops.

    Passed with O(n2) on #2 somehow!

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 ?

          → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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!

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Me using segment tree with AVL tree and only passed 7 cases, I thought O(N log N) is need :'(

          → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :(

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is the site still stating that the contest is running?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

@xiaowuc1 Is there a better solution than 2D range tree or Sqrt decomposition + fenwick in better order?

→ Reply
»
8 years ago, # |
  Vote: I like it +89 Vote: I do not like it

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?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    #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).

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +34 Vote: I do not like it

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_queue as 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.

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +31 Vote: I do not like it

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?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    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

    → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +47 Vote: I do not like it

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?

→ Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

So why exactly did the cow cross the road?

→ Reply
»
8 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Results are out: http://usaco.org/index.php?page=feb17results

→ Reply