msg555's blog

By msg555, 11 years ago, In English

USACO's US Open contest is now live at http://www.usaco.org/ through April 8. As USACO's signature end of season contest, playing a significant role in finalist selection, you will have 5 hours from when you start to solve 3 or 4 problems.

Good luck and enjoy the problems!

-Mark

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

| Write comment?
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it just for gold competetors?

»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Interesting Gold problems this time!

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

Bronze was interesting, but the problems were rather mean...

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    How did you do Bovine Ballet? I used a bunch of casework to do it, but I don't feel as though that was the best solution since it took way too long to code and it didn't seem characteristic of USACO to have such a solution for a problem.

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

      I used a similar method to do Bovine Ballet. Took me quite a while to code and debug. I agree with you that this problem should have a shorter solution, as most USACO problems do.

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

I can't believe those problems was for Silver. Silver's problems was really easy. Hope to get full mark. :D

»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

how can I ask for clarification ?

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

    You can email Brian Dean, the contest administrator, for clarification requests.

    Email: [email protected]

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

      not useful, because one will not receive the answer before the time end

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

        I had received an answer before time ended once (there was corrupted html in one task)

»
11 years ago, # |
  Vote: I like it -16 Vote: I do not like it

the first problem in the silver division was so ambiguous.i didn't know whether it's possible to catch the other captain while we are still falling or not...

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

    I have the same problem!

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

    Please don't discuss the problems while the contest is still running. If you have a clarification request you can email the contest administrator, Brian Dean, at [email protected]

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

What is the memory limits for problems from Gold?

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

    "Your program must be less than 1,000,000 bytes in size and must compile in 30 seconds or less. Unless otherwise stated, your programs will be limited to about 64MB of total memory use. " :)

»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Could I ask questions about tasks now? If I can, how to solve A,B,C Gold :)

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    Yep :) We're working on analysis but I'll give you a brief overview of the solutions. (and of course, anyone else can write about their own solution)

    Figure Eight

    The implementation of this problem is a bit tricky. Basically you try all O(N^3) possibilities for the middle line of the eight (connecting the top and bottom loops) and use some clever accounting so you can find the maximum area bottom and top loop coming from it.

    Yin and Yang

    For each subtree you maintain two data structures that indicate the number of nodes that have a given difference of cow types on the path to the root of the subtree. One data structure counts this for nodes with no intermediate nodes with equal types and the other counts nodes that do. To make this efficient merging results from subtrees should be done in a "heavy light" fashion; merging the smaller structure into the larger.

    Photo

    Believe it or not this problem can be solved with Dijkstra's. However that's not the intended solution. Instead you formulate an O(N^2) DP where the state is where the last spotted cow was located. The maximum extent of ranges that start before this cow give the earliest you could place the next cow. The minimum extent of ranges that start after this cow give you the latest you could place the next cow. To make this all efficient you need to quickly compute the ends of this range and then quickly compute the maximum valued state in this range. (or if the range is empty a cow cannot be placed here).

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

      I came up with that solution to Photo, but I didn't do it because there's no way it'll work, even with intermediate cases of N = 15000~20000. Let alone for N = 200000...

      Even if you compute the ranges efficiently and you code it so that the constant factors are low, you will still have an O(N^2) algorithm for a problem where N <= 200.000.

      • »
        »
        »
        »
        11 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        You can calculate the ranges, with O(N) precomputation, in O(1). Computing the maximum valued state in that range can be done in O(log N) (a Fenwick tree suffices). Overall the algorithm is O(N log N).

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

          And you can solve the whole problem in O(N) time if you use just the right data structures.

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

            I think you can also implement the dp without range query structures if you relax the state to just be a prefix of the cows (not requiring a cow to be placed right at the end). You can then just track the set of intervals containing your current position, querying it for the earliest starting point when you try placing a cow at your current position.

            http://pastebin.com/Pr7hYj2S

            I haven't really tested this, but it seems to work, and seems somewhat simpler to implement if you have access to heap or BST, such as that from the STL.

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

      What about MLE in Figure Eight? N^3 is too much more than 64 MB

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

      Yin and Yang can be solved in O(NlogN) without any data structures. We can use divide-and-conquer technique on a tree and on each iteration we only need to run DFS several times.

      I'm wondering how to detect negative cycles with Dijkstra algorithm quickly. I used some heuristics to do this, but the main one is to output "-1" if the program is already running for 1.8 seconds. Are there any test cases against this?

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

        Empirically I've found that reporting -1 when a vertex gets popped more than twice is sufficient. I don't have a proof, however.

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

        Could you give more details about your Yin and Yang solution?

        • »
          »
          »
          »
          »
          11 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Edit: Wow, I answered something completely different then what you asked, sorry. I'll have more details in the editorial.

          The solution is based on the dual form of the shortest path linear program.

          See http://en.wikipedia.org/wiki/Shortest_path_problem#Linear_programming_formulation

          Still, since there are negative edges, it's not obvious that Dijkstra's applies (and I don't have any proof of its efficiency, sorry).

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

          Suppose that our tree is rooted and we are only interested in those balanced paths which contain the root. In this case we can solve a problem with DFS that counts the number of paths starting from the root with each possible balance between 0-edges and 1-edges. Note that we need to store these values for each subtree of the root separately. After that it's quite obvious how to calculate the total number of balanced paths passing through the root.

          We can solve the initial problem in the following way. Let's fix some node and call it a root. After counting all balanced paths passing through it we can remove this node from the tree and calculate the answer for each remaining connected component separately. This is where divide-and-conquer approach comes into play. However, we can't simply choose an arbitrary node as a root, because the tree can be split into uneven connected components after its removal. One can prove that there always exists a node that at least halves the size of the largest connected component remaining after its removal.

          The overall complexity is O(NlogN), because we have O(logN) levels of recursion and on each of them we perform O(N) operations.

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

      It would be interesting if you shared the Dijkstra's solution for photo...

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

      Hi, do you have some link/reference where I could learn more about the merging of the data structures (balanced trees?) fast in a "heavy light" fashion? (merging the smaller structure into the larger). I once faced it here in this problem: Safe Travel and I could not understand much the details about it (because the editorial didn't explain much how to do it and how to reach the right final complexity). Thank you!

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

If the contest is over. can anyone give any ideas on Silver division 3rd task (Luxury River Cruise) ?

  • »
    »
    11 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I've solved it this way: Let's precalculate for each vertex v — go[v] = u, where u is the vertex, where we finish our route, if we start to simulate M steps from v. Now we can solve the problem in O (K) time this way :

    v = 1
    
    while (k--)
    {
        v = go[v];
    }
    
    print (v)
    

    But for k <= 10 ^ 9 it will be too slow. Now we can precalculate next[v][i] = u, where u is the vertex, where we finish our route, if we start to similate M steps from v for 2 ^ i times. Now we can just find all the '1' bits in binary representaion of K and for each bit do this way :

    v = 1
    
    for each bit '1' in K :
        v = next[v][deg[i]], where deg[i], is degree of 2 of i'th bit in K
    
    print (v)
    

    Total complexity O (NM + log(K))

    • »
      »
      »
      11 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      K<=1000000000 ...

      UPD: ok, thanks for explanation. Did you solve 2?

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

        Nope, you?

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

          Yes, I've used dynamic programming to solve it, I didn't prove that my solution is right, but it works for the sample case.

          On each station I fill the tank up to G units of fuel, for example, for the sample case, on the first station we will have 1 unit of fuel, and we can buy 9 units of fuel to fill the tank, the cost will be 9*40=360. then, for the next station, we see that the cost is lower, and we could buy less fuel on the previous station, we needed fuel only to reach the current station. so, we could buy only 2 units of fuel to reach the second station, cost=cost-7*40; cost= 80. then we fill the tank in the second station and so on. I would appreciate if someone suggested a case where my solution fails.

          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
            Rev. 4   Vote: I like it 0 Vote: I do not like it

            What if your capacity is 10, you start with 5 units and the destination is at distance 16. The prices and positions of the stations are as follows...

            80 5

            100 7

            60 10

            If I understood correctly, your program would fill the tank in every station, when actually the optimal solution is to get 5 units from station 1 and 6 units from station 3 for a total cost of 80*5 + 60*6 = 760.

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

              yes, my solution failed :/

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

                Did anyone solve it correctly?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 years ago, # ^ |
                  Rev. 4   Vote: I like it 0 Vote: I do not like it

                  This was a DP problem. Note that the minimum to reach a certain location would result in that location having 0 gallons left that way we don't use any extra payment. So the min[i] = min[i — 1] + distanceAtMinimumCost(i, i — 1). Now the trouble is Distance at Minimum cost. So we notice that our tank can only hold D gallons so we only have to search the stations within D of the i — 1 th station and take out gallons at minimum cost keeping a deltas array to keep track of how much we can take out from each station. You can keep a dummy station for your start location and end location.

                  I forgot to use a 64-bit int :(

  • »
    »
    11 years ago, # ^ |
    Rev. 11   Vote: I like it 0 Vote: I do not like it

    I came up with a different solution, which should be able to run within the time limit of 2 seconds, I believe...

    The solution is to simulate the moves, until either all K moves have been simulated or we end up at a node we've ended up before. Let's say we're on the ith simulation and we end up at the same node we ended up on the jth simulation. Then, if Node[x] is the node we end up on the xth simulation, our answer will be

    Node[j + (K - i) mod (i - j)].

    Complexity:

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

Bronze power <3

Seriously you guys need to be more bronze.

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

Do you know when results will come out?

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

    usaco needs some time, please give him some time and you will get the result

»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Results are out: 2013 US Open Results. Congrats to those who did well.

»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

In silver division problem fuel:I saw the test cases and i think some of them weren't logical.because Farmer John starting fuel was more than his truck can hold.