chaosagent's blog

USACO US Open
By chaosagent, history, 9 years ago, In English

The USACO US Open contest for the 2015-2016 season is going to run from 4/1 to 4/4. Let's discuss the contest and the problems here after the contest :)

(Hopefully I can make camp this year but that's really doubtful :()

Edit: The contest is live, and it turns out the contest window is 5hours for this contest :)

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

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

It's going to be a fun contest!

I believe in you chaosagent. You can make camp. ez.

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

    @chaosagent would need some pretty buff score here. Probably a 800 to even be in contention to be picked for camp.

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

      That's assuming the contest is super easy... The US Open is generally more difficult than the other contests.

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

      Welp got a 555 :(

      now i have to wait a whole year to try again :(

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

        That's not bad. Probably better than what I will get (OK, I got a 494, my prediction was right) FYI, I don't think you're supposed to discuss your scores until the contest is over. I'm assuming you got #1 but didn't have good solutions on #2 and #3 (right?).

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

          Yeah I got #1, did the counting thing for #2 and got 5/10 cases and did something random for #3 and got 2 cases.

          In hindsight, I'm actually pretty sure I was capable of doing #3 if I sat down and calmly thought about it for a while...

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

            Wait, you got 5 cases? :( I only got 4 cases by counting lol.

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

        Please do not discuss the contest while it's still live.

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

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

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

Problems were really nice, but I spent more than 20 minutes trying to understand 2nd problem (platinum), wrote a solution (about 40 minutes) and then it turned out that I misunderstood the problem :D

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

I don't know what's happening in p2 of platinum. I coded it according to the limits written in description — and failed. Of course, this affected other problems. I finished the contest and went to bed.

Today, I found out that the description and limits was changed — since my code depends on the limit, it might changed my verdict (and I'll be disappointed if it changed my verdict.,) But still, something is strange.

  • ...so they are giving 25MB in a single input? did they?
  • they say, "This has been corrected in the English text". But it's not corrected in actual problem. So they changed the statements and didn't even checked for it?

Whatever, it's a pity that usaco is consistently getting their data / limits "wrong".

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

Contest is over, can we discuss problems?

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

    Contest is not over, I still have 3 hours hahaha.

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

    Yes. Please discuss.

    1-picture summary of platinum:

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

Problem 1 was pretty easy (greedily scan around 60 times). I couldn't figure out legit solutions to #2 and #3 (I misread #2 at first). This seemed a lot harder than the February contest :( It'd be nice if someone could post their solutions to #2 and #3.

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

    You could solve problem 1 by "collapsing" everything left and then right using a dfs or a stack and taking the best.

    Proof (kinda): the winning merge will come from either left or right. By collecting everything in one direction, you pull all possibly used bars into the winning bar (if you skip a bar when it can be merged, it'll become "stuck", and that's not optimal).

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

    I solved problem 3 by using a greedy approach, so basically my code was 10*NlogN worst case, I'll explain why.

    Think about every unit you are off as a value that has a cost, there are two types of values, values that you need to remove, and values you need to add.

    We will treat them separately, yet we will use the same logic, so I will only explain what I did for one and you can do it for the other one.

    Let's solve for the case where we have more dirt than we are supposed to, we only have two options, remove the dirt with a cost Y or move it somewhere else with a cost |j-i|*Z.

    First let's suppose we don't have anywhere to move the dirt, so we remove it and we want to have a priority queue that tells us the cost we paid for a unit minus the position it currently is in, so in the beginning we would push -Y-i*Z, why do we take away the position times Z? Because the cost of moving it somewhere else would be (j-i)*Z, so when we find a position where we could move that piece of dirt, if it's better to move it instead or removing it, we would like to get our Y units back, and we would like to pay (j-i)*Z units instead, so we did some simple math and expanded the term to j*Z-i*Z. We don't know yet the value of j, but we will eventually find it (if it exists), that's why we push -Y -i*Z, to make sure we regain what we had temporarily invested and we take away i*Z because that way we don't need to know our position for this particular piece of dirt (it makes it easier later on, once we know j).

    So now lets go to the generalized case, its the same as the one described above, its just that instead of pushing -Y-i*Z we would push -cost-i*Z, where cost is the cost we would be paying to do that move (notice that cost can be negative), in other words cost is the minimum between firstInQueue+j*Z and Y. Notice how if we are going to take the first in the queue we have to add j*Z, that's because we expanded the term (j-i)*Z. Again we push -cost to make sure that if we want to undo that move we would get our money back.

    And that's it, it's the same to add, just with X instead of Y, so I had two priority queues, one for adding and other for removing, so the time complexity is 10*N*logN, because we have maximum 10 units of dirt in each pot.

    You can look at my code here, it passed all tests. http://pastebin.com/ccCEMt6s

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

      Can I use Cost flow with lower and upper bounds to solve the problem?In the test,I tried,but Time Limit Exceeded

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

        If by cost flow you mean the logic I wrote there, then it should work, but why do you want to do lower and upper bounds? You want to take the minimum cost always, and having a data structure that can handle lower and upper bounds usually has a bigger constant involved (for example sets in C++ can be up to 5 times slower than a priority queue), if you don't use a structure that allows insertions in logN it would become N, as such overall N^2, which would be time limit exceeded.

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

I gave the platinum version of the contest and I'm probably going to score ~425 points.

The problems were pretty nice I would say, interesting, especially problem 3,Landscaping. I think it has a greedy solution(more on this later).

First thing, problem 2 is really weird. I don't know if it was only me, but some things didn't make a lot of sense about the problem statement, such as "Each piece will be horizontally/vertically connected" and the limits of course seemed weird. I thought of using hashing to do it, but around 30 minutes into solving it I didn't feel like writing it so left it.

Problem 1, for this I have a brute force solution that takes O(n * answer) time and memory. The only thing one had to figure out/prove in this problem was that answer ≤ 40 + log2(n). After this, another simple observation is that if we want to make value k for range [L, R] for fixed L the R is also unique and fixed. This is simple to observe, as if we get value k from range [L, R] and try to increase its length to [L, R + 1] if A[R + 1] is equal to k, then we'll get k+1, otherwise we can't even merge. This can be used to easily solve the problem using simple arrays. I used limit of answer = 65. This was my submission.

For problem 3, I tried to use a greedy solution, which was to basically maintain one set of fields such that A[i] < B[i] and then iterate over all those with A[i] > B[i] and find the closest field in the set to this field, check if cost of transfer(z * abs(i - j)) is less than cost of adding and subtracting one individually(x + y). After this, just change the values to the final values by using only add or remove type of moves. But this got WA. I also tried doing the inverse of this, and combining the results, but even that got AC on only 3-4 test cases :'(

Can someone please explain there solutions to P3?

Also, side note, does USACO consider our best submission(max score) or the last submission made in contest?

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

    USACO considers the last submission. For #3 I tried using graphs but it epically failed (1 AC). I thought it might be some kind of bipartite matching between the fields with a[i]>b[i] and a[i]<b[i]. I probably should've put more effort into thinking of a simple DP solution. By the way, on problem #2 you could've gotten 4/10 test cases by simply counting the number of colors in each piece and checking if the total colors are the same :D

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

Any solutions to P3 that got > 4 test cases? I tried looking into faster edit distance algorithms, but unfortunately all of the research papers are over my head :P

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

The code here gets AC on A:

http://ideone.com/Dnz3Nu

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

    Your code fails on this test:

    5
    2 1 2 1 2

    The correct answer is 2 but your code outputs 4.

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

      (I think he was trying to make a point about USACO's limited/weak test cases)

      btw, 3 2 1 2 is enough to break it ;)

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

What did you guys think about the Silver Division? I though the field closing one was easy and the other two were very hard. I thought my solutions were fast but they barely got 4 test cases on both the other two problems.

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

    Problem 3 was a very simple DFS. Here's my code that got all test cases: http://ideone.com/CRfppf

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

      Yes I know, I did bfs and got 10/10 on my first input file. The other two problems killed me though. I only got 4/10 on p1 and 4/10 on p2. I really am hoping that the cut off for gold is 550 instead of the usual 600. This may be the second time I missed promotion by 1 input case.

      How did you do #1 and #2? I tried everything but my program was too slow and sometimes wrong.

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

        Problem 1: Given a set of points, we can find area of the minimum enclosing rectangle in O(N) by looping to find the maximum and minimum x and y values. Observe that only removing 3 points with minimum or maximum x or y values will decrease the area. There are only about 35 ways to do this, so we can just try them all. Runtime  -  O(N) with large constant.

        Problem 2: Sort all diamonds. For each diamond Di we will calculate size[i], the maximum number of diamonds that can go in a case with Di if Di is the minimum diamond in that case. We can do this by binary searching for the maximum j such that Dj - Di <  = K. Then, size[i] = j - i + 1. Now let maxsize[i] = max(size[i], size[i + 1], ..., size[n - 1]). The answer will be the maximum of size[i] + maxSize[i + size[i]] over all i. Runtime  -  O(NlogN).

        I hope this helps!

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

Results are out, but only for gold, silver and bronze. Why aren't platinum results out?

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

    They probably want to hide the bottom [10:] of the leaderboard to not give people false expectations/hope of making camp...

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

    Last year they only posted perfect scores for the open in the gold division.

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

    i really think they should release the final results after the camp selection at least. Because these lists are an extremely good way of comparing performance in IOI like contests, especially because unlike COCI and others, it has long window allowing more competition.

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

      If they do, they'll have a bunch of salty kids and their parents spamming them about why they didn't make camp when they were in the top 24...

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

        Valid but I think the page makes it pretty clear that their policy is not solely on the basis of US open even though it is majorly considered. This clearly mentions that.

        One thing that I do think should be done though, is introduction of some kind of honorable mention for those students who had great performance but missed the camp selection. India did it this year in INOI. It is motivating as well as satisfying for those students.

        Anyways, best of luck to you for the results. :)

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

          Personally, I think it feels much better to not know what happened than to know you missed by a small margin (especially when the next time I get to try again is next year)...

          Also, salty kids and parents are the world's most formidable force. Never underestimate the tryhard high schooler trying to get into MIT ;)

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

I think that test cases of Platinum problem 262144 are too weak. You only need to push the numbers to the stack from the beginning to the end (and vice versa) and just replace the equal two x numbers with the x+1 and get the maximum value. You get full points with this approach. :D

→ Reply