phantom11's blog

By phantom11, 7 years ago, In English,

This is to remind you that the USACO December 2012 Contest is going to take place from tomorrow.The duration of the contest is 4 days.You can appear in the maximum of any of the 4 hour window during the contest.

Link to Contest Page .(to be updated before the contest starts )

Your Timezone.

You can use this blog space to discuss problems NOT during the contest but ONLY after the contest is complete.

UPD -> [Results]

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

»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it
»
7 years ago, # |
  Vote: I like it +16 Vote: I do not like it

It's time to help FJ with his cows :)

»
7 years ago, # |
Rev. 3   Vote: I like it -13 Vote: I do not like it

I am getting WA on sample case, the output is 57.5 and I am printing 57.500000. The Sample case is unique or they are testing with another sample case? Thanks. **Ok, I solved it.**

**Can anybody please tell me why I got WA printing 57.500000 when answer is 57.5? I understand negative votes but I really want to know. Thanks.**

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

    Ok, USACO's answer: "Wifi setup: If the answer is an integer, print it as an integer. If it is half-integral (a decimal ending with .5), print it as a decimal with one digit after the decimal point."

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

      It's so funny ! my code always answer with one digit after the decimal point and mybe it will get WA on many tests ! the clarification didn't mention to it ! X-(

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

Is it something wrong with USACO? it doesn't show Remaining time...

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

For how long does Gold contest lasts this time? 3 or 4 hours?

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

In USACO, Is the stacksize increased by default?

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

Can i knew my submittion result during contest?Or only samle tests?

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

    Solutions are checked only on the sample test cases during the contest . They will be evaluated later and you will know your results only when they officially declared.

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

According to the announcement,the contest will be over 15 minutes later(Dec 17,23:59 UTC-12).

UPD:Sorry,actually it will be over at Dec 18,03:59 UTC-12.We can discuss problems after that.

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

    As far as I understand, "starting window" will end at this time, however it's possible to start the contest at this time so we can only discuss tasks 4 hours later.

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

Can the last problem in Gold division be solved if cows are allowed to run not only away from the 1st barn?

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

    I originally understood it that way so I think it could. :) Here's a sketch of an O(n log^2 n) solution: First, let's find the center of the tree C and root the tree at C. Find the list of lengths from C to every other vertex and sort it. Now, for each element a of the list we can easily compute number of other elements b, such that a + b <= L. That way, we are able to find for each vertex v the number of vertices w s.t. the path v-->C-->w is of length <= L. Doing roughly the same thing for length lists limited to every single subtree of C, we can subtract for each vertex v the number of vertices w such that the shortest path from v to w does not go through C. Overally, for each vertex we will know the number of vertices located past vertex C, that are still close enough to be counted. Now all you need to do is to delete edges adjacent to C and recurse on each subtree. Every subtree is at least two times smaller, so the complexity is O(n log^2 n).

    Any idea how to do that in O(n log n)? :)

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

      I don't understand your solution fully, but in a chain every subtree will be two times smaller only when you delete first vertex(i. e. center of a graph).

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

        Deleting edges adjacent to center C is just the same as deleting the center itself (there's no way back from the subtree to C or any other subtree after any of these).

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

          For each subtree(say with root T) do we sort distances from C to all vertices or from T to all vertices?

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

            We always sort the distances from the center of the processed tree. So if out tree is 1--2--3--4--5, in the first call we will find center 3, sort the distances from 3 to 1, 2, 4, 5 and do the processing I described to compute for each vertex the number of other vertices that are past the center and at most L miles away. Once we are done, we delete vertex 3 and run our procedure independently for trees 1--2 and 4--5.

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

              So do we go only one level down and not deeper?

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

                Of course we go deeper, it's a pretty standard divide and conquer. In the top call we consider only paths going through the center C. In subsequent calls we'll consider only paths not going through C, but through centers of the smaller trees ans so on.

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

                  How will it work then on a chain of 200000 vertices?

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

      I think I have a solution in N*log(n) to this problem. Root the tree at node 1. Foreach node, add 1 to every node on its path to the root, if the distace <= L. The last node can be found vial logarithmic jumps(well nḱnown data structures) in O(log(n)) (binary search). How to set one to each node on that path? The answer is a techinque called heavy_light decomposition.

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

        But what about paths that are first up, then down?

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

          Ok, that's true, but I interpreted the statement in a way, that this is not possible. It says: "FJ does know that the cows only run away from the barn". This means to me, that they go away in every step of the path.. Wrong? Maybe my english is not good enough

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

            But this thread is about version of the problem without this condition

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How can i solve third problem from bronze div?

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

    Draw field after coordinate compression, next bfs. May be it's not optimal solution.

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

      How do you compresse the coordinates? Using a global pgcd on the differences between each adjacent points, and consider min_x and min_y as origin? And if so, isn't there some special cases where the compression can't be applied?

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

        I just saved all x's and y's coordinates in big array and compressed. Now all numbers are less than 3000 (on contest I thought that bound is 1500:( ). Also you can make two arrays for x's and y's — bound will be 1500. Of course there is no special cases cos all holes in fence remain holes.

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

    Is there a way how to see the problems of the other divisions, except of waiting some days? :)

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

    You may also try this problem, http://uva.onlinejudge.org/external/119/11918.html, It also requires grid compression, a bit harder than the usaco's one.

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

Can the first problem be solved using some non greedy algorithm?

I used maximum bipartite matching and I was able to find out how many cows from the first group will survive but I found no correct way to output the lexicographically earliest ordering of the cows.

UPD: I'm talking about the gold division.

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

    If you need first lexicographically, you always try to set first element of the sequence the least, that there exist answer starting with this element.

    I did this way. Matching exists if and only if for every group it's not larger than sum of the other groups. So main idea is to choose two elements least lexicographically, and try them put in the first place and check whether you can continue.

    There are several different situations, so you must be accurate when solving them.

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

    I'm not sure I see how to use bipartite matching to solve this. Care to explain?

    I intended for it to be solved greedily.

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

      For how long we should wait for the results?

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

        I really don't have any control over that. Usually the first time I see the results are after they are released. AFAIK everything is ready at this point.

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Is there anyone who know when will they post the result?

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

    I was about to post that:)

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

    They should put more informations on the website about the true status of the contest :/

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

Was #3 in silver just a modified djikstra?

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

    State: denotes the length of the shortest path to vertex v with capacity . Compress the capacities in the given input into at most M ranks. Then it suffices to solve the problem using Dijkstra.

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

    I used a modified Dijkstra but I have a doubt if that problem can be solved by network flow.

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

    I solved it by DP.

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

    My approach was Binary search[ on minimum capacity ] + Dijkstra

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

    Well my solution was:

    • Dijkstra returning L for any given lower bound on C (edges with capacity < C are cut off from the graph)

    • the return value of this is non-increasing for increasing C

    • since we're only interested in integer results, it's sufficient to consider only such C, for which (integer division) X/C isn't equal X/(C+1), because if they are equal, then the solution for X/C is obviously better

    • EDIT: for C \ge \sqrt(X), X/C \le \sqrt(X), so there are O(\sqrt(X)) interesting C, and time complexity is therefore O(\sqrt(X)M\lg(N))... not optimal, but hopefully sufficient, haha

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

    SILVER-WIFI_SETUP : I thought that cout << res; will print what was expected. But it prints 1.65947e+06 instead of 1659471. So I lost points of test2,test3,test7. Replaced it with :

    printf("%d",(int)res);
    if (res != (int)res) printf(".5");
    

    and got full points.

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

      I had the same mistake as you and also got WA on those testcases.Fortunately,I got a total of 667 points,just enough to get a promotion to Gold division.What about you?

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

      Using real valued variables is often not a good idea — their behavior can get messy sometimes. Besides, since the answer is an integer or half-integer, you could've just computed 2*answer and treat both cases separately on output.

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can you go to lower division if your results are bad?

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

    No, it's impossible, even if your result is 0.

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

finally the results has been published. :)