Блог пользователя phantom11

Автор phantom11, 12 лет назад, По-английски

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]

  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
»
12 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится -13 Проголосовать: не нравится

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.**

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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."

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      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-(

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

In USACO, Is the stacksize increased by default?

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
12 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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)? :)

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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).

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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).

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

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

              • »
                »
                »
                »
                »
                »
                »
                »
                12 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How can i solve third problem from bronze div?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    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.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    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.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      For how long we should wait for the results?

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Was #3 in silver just a modified djikstra?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I solved it by DP.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
12 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

finally the results has been published. :)