mrgreen's blog

USACO January Contest
By mrgreen, history, 9 years ago, In English

This is a reminder that USACO January contest starts soon on January 15 and lasts till January 18.

UPD: Contest is over. Feel free to discuss the problems.

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by mrgreen (previous revision, new revision, compare).

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

I only solved Fort Moo (Platinum). Geometry is not my thing :-( .

I really couldn't understand the third problem.

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

    The solutions should be up soon.

    I didn't understand the third problem during my block either. Even after, it took me a decent amount of time to figure it out.

    Draw a polygon for yourself (make it at least 10 edges; the sample was far too simple) with labeled edge lengths and see if you can make your way out by "feeling around" -- that is, try to reach the first vertex knowing what the polygon looks like but not knowing where on it you are. The key is just that: to determine your location. Use a separate sheet of paper to map out what you've "felt," and you'll soon see the idea behind the problem.

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

    I really couldn't understand the third problem.

    +1 :)

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

    I personally thought Fort Moo was more of a gold level problem than a platinum. Maybe it was to compensate for the other problems (which I didn't do well on) :L I was surprised that my O((NM)^2) solution ran in the time limit for every test case.

    I got 5/10 test cases of the second problem by bashing with a segtree. The inflated time and memory limit confused me (it suggests an Õ(N^1.5) solution, but I can't think of any. I tried breaking it into blocks of sqrt(N) to no avail)

    The third problem was... weird. I understood it, but decided to focus on problem #2.

    All in all, did you guys think this contest was easier or harder than the last one?

    How do you solve #2 and #3 on Platinum?

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

      Can you elaborate on your attempt on the second problem? I tried doing a line-sweep and counting the intersections that met the requirement by brute force; I only got three or four cases.

      As for the third problem (which I figured out after the contest), the problem boils down to representing the polygon as an array of integers, with a negative sign denoting a concave vertex and a positive sign a convex vertex. To determine where you are on the polygon, explore right or left (try both to determine which is more efficient on average over all possible starting vertices) and narrow down where in the array with each new edge traversed. Once you know for sure where you are -- when the number of possible locations equals one -- either simply continue or go backwards to reach the first vertex.

      Run this algorithm on each vertex and find the maximum difference between the distance traveled in the dark exploring left or right, and the distance with the lights on, which is basically the distance between the starting vertex and the exit.

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

        I don't think your solution works for the third problem. Notice that Bessie needs to have the same strategy for all starting vertices. She can't use a different strategy for different starting vertices. More generally, regardless of where she starts, if Bessie has explored the same layout, she must always make the same move. That is, her strategy must be deterministic.

        My solution (also post-contest) was a dp using the above idea, where state is (hash of explored area, starting position within explored area, which side of explored area Bessie is on). Reference code: https://ideone.com/tnQIzM

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

          It's possible she could use a different strategy depending on the concavity of her starting vertex. For instance, it could be that case that starting right is most efficient for concave vertices and starting left is best on convex ones.

          But yes, her starting strategy must be the same. When I said to run the algorithm on each vertex to find the maximum difference, I meant to say the maximum difference should she start right and left, respectively. Sorry for not making it clear.

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

            I used a segtree with each node containing a set of vertical or horizontal lines. Segtree with horizontal lines is sorted by y coordinate, and segtree for vertical lines is sorted by x. Lets say we are currently testing a vertical line. The vertical line ranges (10,15) to (10,30). Then I queried the horizontal line segtree from (15,30) (but I still had to check for all the intersections because I had only guaranteed that the y value would work). This can still get rid of a lot of possibilities in some cases though (I think). O(N^2) is still worst case. Iterate over the whole array of lines starting at T+1, and each time add the line that is T+1 behind. This probably doesn't make sense, because my solution is so weird I can't find another way to say it. Now that I think of it, std::set with lower_bound probably would've been faster and easier to use :(

            UPD: Tried doing the same thing with a set, got 7/10 test cases (missed cases 7,8,9). I'm guessing a lot of other people used a set, judging by the contest results (lots of people got 7/10 and missed 7-9)

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

How to solve Gold 2nd problem?

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

    You can solve it using dynamic programming. Let f(i, j) be the minimum cost for both people to arrive at their final destination if the first person is going to execute the ith character of his string and the second person is going to execute the jth character of his string.

    Therefore, f(i, j) = min { f(i + 1, j) + cost(i + 1, j), f(i, j + 1) + cost(i, j + 1), f(i + 1, j + 1) + cost(i + 1, j + 1) }.

    We can precompute the positions of the two people by simply traversing each string and from this we can get cost(i, j) in constant time.

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

How was the third Silver problem solvable?? (Build Gates). Were you supposed to graph the directions out and then do dfs?? but that's too slow. . . I did something by adding the directions and counting how many times a rectangle was made and I only got 3/10 test cases :(

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

    I did dfs.

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

      How did you do the dfs? did you iterate through ever unvisited part of the graph represented as a 2D array?? I didn't do that because i though it would take too long. how many test cases did you solve??

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

Interesting. My solution on Lights Out (Gold), which kept getting WA on all tests except the sample, gets AC when resubmitted after the contest.

UPD: I didn't notice a note that the test data contained a bug.

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

The time limits were really long; I got full score on platinum's problem A (Fort Moo) just with simple prefix sums + trying every pair of vertices. Even in problem B, Mowing The Field, the naive solution — for each line, look at lines that come at least T earlier and check if they intersect — got 7 tests out of 10. Also it feels wrong that you can just submit a program that prints "2" (the sample output) and get points for free, even though you didn't really solve anything.

This contest is really missing the "bundled tests" that most contests have — you don't get points for solving individual tests, but for solving all tests out of a "bundle", which makes it much harder to abuse the grader. Also, it doesn't tell you anything about the limits on subtasks which makes it hard to make informed decisions. For example, you know that the solution is O(n) but you have no idea if your O(n^2) solution will get 20% or 70% tests so you don't know if it's worth it to code it.

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

Thank goodness there was a problem with Gold #3. Was getting very worried when, at end of contest, I only had 1 complete AC :P.

Also, what was solution for Gold #1(as of writing this, the solution is not yet up). My idea after the contest was to binary search R, and then inside that binary search again binary search this time for position, and finally to simulate with the given R and position. If all of the left side doesnt explode but the right does, we need to shift the position leftward. If vice versa, shift rightward. If neither side fully explodes, it is an impossible radius. If both sides explode, it is a possible radius.

However, there are actually 3 nested binary searches in this process(1 for R, 1 for position, and 1 during position to find leftmost/rightmost destroyed index). Surely there must be an easier solution?

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

    You can find the smallest R necessary for everything to the left from each position to explode, by binsearching and using the results already computed for everything further to the left. Same for the smallest R to the right.

    Then, you can binsearch the generally optimal R. For a fixed R, try all leftmost exploded points, for which you know the rightmost and can check if this R is sufficient.

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

When you forget that the site takes your last submission on each task... :/ I stopped on the first hour and had 566 but forgot to return back my best solution on the second :D :D :D

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

I personally don't think this contest differentiated much between contestants. A very large number of people solved #1, got part of #2, and missed #3. The standard deviation is super low.

By the way, can someone link me to a good tutorial about using range trees? The USACO solution says 3D queries can be answered in log^3(n) time, but all the tutorials say it's k+log^d(n) (which is too slow).

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

Can anyone elaborate more about how to use a 2D segtree or a 2D BIT (with coordinate compression or something?) to solve Mowing (platinum)? These are different from a quad tree right?

Also, when implementing the naive solution, mowing.java gets 6/10, and mowing.cpp gets 7/10. It might be time to switch to C++, lol

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

How to solve GOLD #1 Angry Cows? I didn't find editorial on it.

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

    How about reading the comments here?

    → Reply