chaosagent's blog

USACO First (December) Contest
By chaosagent, history, 8 years ago, In English

The first USACO contest of the 2016-2017 season is going to run from 12/16 (Friday) to 12/19 (Monday). Let's discuss the contest and the problems here after the contest :)

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

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

I guess Mexicans aren't allowed to participate.

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

    The firewall hasn't been built yet.

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

Problems in English only? or ? :)

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

    There already problems in en, ru, fr.

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

can anyone explain for me why the input of problem 3 — silver is 3 :(( .The 4th cow can't be reached so i think the answer is 2 @@@

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

    deleted. I think that my comment doesn't give any hint to this problem. Anyway, excuse me)

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

      Please do not discuss problem specifics DURING the contest >.<

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

How to solve the first Platinum Division problem? (Lots of triangles)

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

    My solution: Angular sort, radial sweep, range query.
    Complexity: O(n3log(n)).

    Is there O(n3) solution or better exists?

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

      And my solution TLEd -_- (I used angular sort + count number of inversions). However, I heard from minimario that an O(n3) solution exists.

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

      O(3004  /  6) solution is kinda obvious. you can optimize it to O(3004  /  (6  *  64)) by using a bitset. which is better than O(3003) .

      code: https://hastebin.com/cuduvepuqu.cpp

      UPD: sorry, bciobanu answered that before me

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

      Yes.

      1. if we pick triangle with point A, B, C. we remove points that is outside of line A-B, B-C, C-A (precompute this in N^3) Unfortunately this removes some points two times. So, we precalculate rangePoint[X][P][Q] = num of points y s.t ccw(X, P, y) > 0 and ccw(X, y, Q) > 0, and add them. With N^3 precomputation we get O(1) per query.
      2. precomputate DP1[X][Y] = number of points p s.t ccw(X, Y, p) > 0 and X.x <= p.x <= Y.x. (also with ccw(X,Y,p) < 0) Now we can get O(1) per query. Careful with elements with same X coordinate.....

      In contest, I didn't realized such exists, and coded n^3lgn solutions. (angular sort + bit) I got TLE, so I precomputed angular sort for n^2lgn, and get AC. (I know this is dirty :D)

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

    You can pick a point say the point leftmost of all points (point P) and fill a pre_process array dp[i][j] that means in the triangle with vertices P,i,j how many dots are there we can fill this array naively O(n^3) and then for any triple (a,b,c) we can easily find out the number of dots inside it O(1) for example the number of dots inside(a,b,c) can be equal to : dp[a][c] — dp[a][b] — dp[b][c] — 1 OR dp[a][b] + dp[b][c] — dp[a][b] (if b is between a,c if we look at it from P) so the overall complexity will be O(n^3)

    (filling up the array and finding out which point is in between to other points by looking at it from P can be easily implemented by cross product)

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

    Let's use trapezoidal decomposition. Loop through all segments and compute the number of points inside the trapezoid formed with the x-axis. Now, for any query triangle, lets pick the longest segment forming it and look at the third point not forming this segment. Depending on which side of the segment this third point is, we either add 2 trapezoids and subtract 1, or subtract 2 trapezoids and add 1. Either way, it's O(n3).

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

How do you solve gold 2 and gold 3?

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

    You can solve third problem by bfs. Here is the code.

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

      Can you describe your algorithm with words?

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

    gold 2 ==> DP[1000][1000][2]

    wtf of down?! :/

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

    About problem 2 gold :

    I decide to go to through the all options and get the best answer.

    Situation (x, y, k) :

    . k = 1 — Holsteins cow, 2 — Guernseys cow.

    . the last Holsteins cow was Holstein cow by number x,

    . the last Guernseys cow was Guernsey cow by number y,

    and we now near cow type k.

    The ansewr for situation (x, y, k) it's minimum energy which we need fo going from (x, y, k) to (h, g, 1)

    Let calculate answer for situation (x, y, k) and we want go to the (h, g, 1)

    So where we can go from there ?

    1) if x == h and y == g

    . a) k == 1 then nowhere ( ans = 0 )

    . b) k == 2 then go to the h-th Holsteins cow.

    2) if k == 1

    . a) we can go to ( x + 1, y, 1)

    . b) if y < g we also can go to ( x, y + 1, 2 )

    3) if k == 2

    . a) we can go to ( x + 1, y, 1 )

    . b) if y < g we also can go to ( x, y + 1, 2 )

    One point : if we walked out from [1; n][1; m] then the answer will be BIG NUMBER.

    So we will calculate the answer for (1, 0, 1), and it will be the answer for the problem.

    First I just write recursion "go through the all options" ( and got 2/10 AC)

    Then I saw that some positions (x, y, k) we calculated several times, and decided to use map for optimization ( we calculated answer for each position one time and save the answer, and each another time we will use saved answer ). ( it got 5/10 AC ).

    And I decided to change map to the array because the problem has no big limitations [1000][1000][2]

    ( it got 8/10 AC ).

    This problem helped me to understand how to convert some DFS solutions in to the BFS solutions, and I convert my DFS solution in to the BFS solution and got 10/10 AC.

    I think this problem was very interesting and useful for me.

    If you are interesting here is my DFS and BFS solutions.

    Thank you for attention. And sorry for my bad English.

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

      Please if it was useful put "+" here.

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

      Please if it wasn't useful put "-" here.

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

Any hints for problem C in platinum division?

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

    From what I have heard, the problem is a harder version of Problem A in this competition: http://cs.stanford.edu/group/acm/slpclive/problems/problems_2016.pdf

    I've also heard that one can use Eppstein's algorithm to solve it.

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

    My solution is O(nlg^2n). I will only explain some key ideas, since the full algorithm is hard to explain....

    • Let's run some sort of Dijkstra here. we start from (0, 0, 0, 0 ....), and increase one element from each of N entry. This is NKlgN and I remember it didn't rewarded much.
    • Observe that Kth pick differs for at most lgK elements from the 1st pick.
    • We want to reduce state to N entry -> K entry, but it's not clear till now.. So, dismiss all rows with one elements, and sort every rows by order of M[1] — M[0].
    • Still it's not clear, so let's fix the number of changed elements (say C), and solve each problem independently.
    • Now think about the two ways of state transition.

    In contest, I was short of time, and I just submitted optimized O(nlg^3n). This misses two TC as TLE. (956/1000) This is my code. http://ideone.com/s08eao

    Also, ainta told me that there is nlgn solution. I think it won't be really hard to optimize mine to nlgn...

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

    Link to my solution of C (it got AC). It's an easy to understand DPlike bruteforce which runs in .

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

      Can you explain the code?

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

        So let's begin with some facts.

        1) We can binary search on the maximum number we will get.

        2) If we sort the numbers in each row, we must get at least the minimum number in each row. So we subtract from each number the minimum in its row. We do this so that we can ensure that our transitions in the following DP will be O(K).

        3) How to do the check in the binary search? If we do a DP[add_sum] = number of ways to increase the minimum sum with add_sum, then we can notice that in each transition of the DP our count of numbers increases with at least 1. So we can maintain a global counter of all possible sums less than the current minimum that leads us to at most O(K) DP transitions (if our global counter reaches K we just return true). The complexity of the check is because of the map, but it can be improved using a hash table.

        4) after we find the maximal number the sum can be found in a similar manner.

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

    My solution is O(n log n) and it's really simple to code:

    1. Let's sort pairs (value, row) for all elements in all rows (except for the smallest ones), where value is the differences between the element and the smallest element in its row.

    2. Let's say that a state is a vector of positions (in the sorted array) and run Dijkstra's algorithm (starting from an empty vector). We need only two transitions: creating a new position immediately after the last one and increasing the last position by one.

    3. There's one problem here: we can take two elements from the same row. It's bad. Let's fix it by moving the last element until all rows are unique (we touch only the last element, so it's the only one that could break). That's it.

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

You know, people can compete in this competition until 4h after the official finishing time. I have 30 min left and I'm seeing a lot of spoilers.

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

This is pathetic. Officially, anyone can start USACO contest at Dec 19, 23:59 UTC time and start for 4 hours. You guys are discussing problems just after the time for the official start of the contest is over instead of four hours after it__. Even I started the contest 2 minutes before it officially ended and although I did not use any outside help, I came here after the contest to be the first guy to talk about it. Now, I am disgusted to see that three hours before the contest ended for me, some other people had already started discussing stuff. This is pathetic.

P.S. Feels fun to get promoted to platinum!

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

    And the people discussing it early are probably the ones downvoting you.

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

Results are available here!

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

My solution for problem C was as follows:

First, notice that the approach with the priority queue has two problems: it is O(NK) and it generate duplicates. In order to solve both of these problems, notice that once we have an element in the queue (I.e., an array of indices for each of the N components), we have two options: Either we take the next best possible difference (let's call the corresponding position pos), or we completely stop adding differences from pos. You can see that, by doing that, the decision splits the solution space into two disjoint parts.

The minimum, as well as all the operations, can be simulated in O(log(n)) with persistent segment trees. Hencr, total complexity is O((N + K)log(N + K)) Here is the code:

http://pastebin.com/xHn88B3d

Note: I did not notice that the cases were disjoint in contest-time, that's why I also have hashes comparison. They are useless in the code.

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

    Can you please explain your method with more details ? Thanks in Advance.

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

For Platinum P3 "Robotic Cow Herd", shouldn't the worst case complexity of the (official solution) which is a brute force, be more ? Shouldn't the enumeration run in O(M1*M2...Mn) in the worst case ?

→ Reply