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

Автор P_Nyagolov, история, 9 лет назад, По-английски

Hello everybody!

This morning I realized that I was about to miss the contest since I completely forgot about it so just a quick reminder. It can be done from 11th to 14th this month :)

PS: According to usaco.org, this year there is going to be a new Platinum division :)

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

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

Should we discuss the problems here after the contest?

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

Be sure to read the clarifications for the problems!!!

I spent almost an hour trying to debug a correct solution because the statement wasn't clear enough. Got it working on all tests after reading the clarification.

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

In 2 hours of the contest, I only tested the solutions to understand questions ! I think problems have unclear statement.

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

Is that green box after submit containing full test case or pretest only?

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

Went from silver to platinum this contest :D

Hopefully I can make some time to do platinum, but I'm a bit tired...

P.S. How do we do Platinum #1? I tried adding 1 to all parent nodes of a and b up to the LCA of a and b but that's only O(n^2).

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

    are the results out?

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

      No; they usually come out a few days after the last day of the contest, which is probably going to be Wednesday or Thursday. I got 1000/1000 on both silver and gold so I got two promotions during the contest (you get an in-contest promotion if you get a perfect score).

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

Who have used the entire time to do Silver division?

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

what's wrong with USACO? As I remember 2-3 years ago there were VERY hard and interesting problems in GOLD division.

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

Why USACO is so easy now ? It was much harder 2-3 years ago.

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

    " The old bronze, silver, and gold divisions will be scaled down in difficulty accordingly, so that bronze contests will provide an easier entry-level experience for our new competitors (we've received overwhelming feedback requesting this) and so it will be less of a discontinuity for students to compete in higher divisions after promotion. Platinum-level contests will be roughly comparable to the difficulty level of prior-year gold contests. "

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

      True, but Gold was painfully easy. I was distracted, half-watching TV and coding and still finished the problemset in 40-50min. At least they had insta-promotion option so I could have some fun in Platinum.

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

        Have fun with RMQ and LCA? :(

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

        platinum was not much harder :/ and too standard

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

        Yes, after looking forward to it for the past week, I must say I've been let down :( Is USACO experiencing some structural changes to the training staff?

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

        Yeah, the only difficult part of the Gold contest was the unclear statement of the 3rd problem. I spent almost an hour debugging it until I realized there was a clarification on the main page.

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

          What's your solution for the third problem (Bessie's Dream)?

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

            You can do a simple BFS by just expanding the graph to [N][N][2][4] to keep your position, whether you smell of oranges and the direction from which you came from. Complexity is around O(32*N^2).

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

              Wow, does BFS really work? If we slide from A to B, then from B to C and then from C to D, we have an edge from A to D with weight 3 but no edge from A to B or from A to C so I thought we should use Dijkstra since the edges have different weights, also I got WAs with BFS and AC after changing it to Dijkstra. Perhaps I have messed something up during the contest but really, why does it work?

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

                If you do the sliding in one single step, then simple BFS will fail, but you can still get it AC if you check every time if the new distance is less than the current one.

                But the thing is that you can do one single move at a time by checking at the beginning of each iteration if the tile you're currently on is purple. That's why you save the direction for each state.

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

                You don't have to do the sliding in one step. You keep the direction you came from so in case you are currently on a purple tile you know where you'll continue sliding. This way you don't have to do any precalculations and BFS is fine since all edges are 1-weighted.

                So basically in your siliding sample you'll have A->B ; B->C and C->D edges, not A->D edge

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

                  In my solution I expand the graph in exactly the same way but after getting WA I thought it's wrong and it got AC with Dijkstra. Now I understood why it's correct so I must have had some little bug (I know it sounds funny to have a little bug in BFS but it happens :D), thank you! :)

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

IMO, platinum problems should have been gold ones, because they are too easy for the highest division.

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

Just finished Platinum contest!

The problems were indeed much easier than I expected, but I enjoyed every single one of them (specially the first one, it was pure magic!). As usual, it was a pleasure taking part in the USACO contest! :)

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

From Bronze to Platinum :)

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

I wanted to participate in Platinum during last hours of the contest and now it turns that usaco.org is down T_T

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

    I was in the middle of the contest, not sure what to do now.

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

    I can enter to Usaco, by the way the connection is very slow ,but when I submit, it says, "Waiting for Available Grading Server".

    Edit: 15 minutes passed still nothing

    Update: The Grader works fine at the moment

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

      After an hour since my submission I got a response that I forgot to include input/output files :)

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

      Same Problem here !

      Is there any one have any solution for this PROBLEM !!! :|

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

What's the solution of High Card Low Card (platinum)?

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

    The contest is still going on for those who started it at the last moment. Wait an hour and I'll tell you my solution.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится
    • First thing to notice is that if we use k cards to win k "high card wins" rounds, we might as well use the k highest cards. Similarly, if we use k cards to win k "low card wins" rounds, we can also use the k lowest cards.
    • Second thing is that we have N cards and there are N rounds, so the sets of cards we use to win each type of round will be disjoint.
    • Knowing those facts, we can build a solution. Let's calculate for every prefix, the maximum number L[i] of rounds we can win if we play with "high card wins" rule for the first i rounds. And let's also calculate for every suffix, the maximum number R[i] of rounds we can win if we play the last N - i + 1 rounds with "low card wins" rule. We can calculate both of these greedily using an ordered set of available cards (start with a set containing all our cards, then to beat a card x, for "high card wins" choose the minimum available card y such that y > x, and for "low card wins", choose the biggest available card y such that y < x; then remove the card from the set).
    • The answer will be the maximum L[i] + R[i + 1] among all i in the range [0, N].
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      That is really a lovely greedy problem. It was rather hard for me to find the solution, even if I already had done the gold version the day before (gold problems were really easy ^^).

      It was more difficult than the 2 others problems for me, they were just simple applications of big techniques (trees and eventually LCA for the first one, lazy SegTrees for the last one)

      Still got 1000/1000 in 3h :D

      But it seems that it's not such an exploit after all...

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

        how do you approach High Card Low Card (Gold)? The only idea i can come up with is bipartite matching. :(

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

          No, it's a greedy one. It uses the same ideas that tenshi_kanade explained for the platinium solution.

          Basically, you use the N / 2 biggest cards for the "high card wins" mode, and the N / 2 lowest cards for the "low card wins" mode.

          Then, each time you have to beat a card from Elsie, you simply use the weakest card that beats it (so the lowest one in high card wins, the biggest in low card wins). If none of the cards you have in your deck beats it, than you don't get this point, and you don't have to remove a card from your deck.

          That's a greedy approach, and you can implement it in with a set (you'll have to use lower_bound and upper_bound)

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

            it .. is .. simple. too bad i didn't get it.

            Thanks for your explanation. I'll try to implement it in the future.

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

result are Here

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

    Никак не могу разобраться с решением. Может кто-нибудь кинет код задачи о лампочках (silver 1) на c++ или fpc. Заранее спасибо всем добрым людям.

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

I submited for the first problem in gold section, and after I deleted my source from the Idle. I went to usaco in 'previous submissions' and there is nothing. Do you know if they gonna publish previous solutions soon or no?

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

I guess I'll mention slightly differing(/slightly simpler?) solutions from the solutions given...

For 'High Card Low Card (Platinum)' we don't need a custom segment tree, we can simply use a set to find the next lowest/highest card available: code.

And for 'Counting Haybales' we don't even need lazy update (although one might prefer either way...), instead we just update ranges as normal and the 'actual value' at a leaf node is the sum of all nodes on the path to the root: code. In my range tree code, the ranges are [inclusive, exclusive), 'l', 'm' and 'r' stand for left, middle and right, 'n' stands for node', 'u' for update and 'q' for query.

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

Anyone else solved Max Flow from Platinum using Heavy-Light Decomposition?

When I read the problem statement, it involved LCA and paths, so I immediately thought of HLD. I didn't bother trying to find a better solution during the contest and went straight into coding. Later I realized it wasn't necessary.

So I was wondering if anyone here did the same thing?

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

    Did Heavy-Light Decomposition too. The site was slow when I was doing the contest (during the final hours) so I thought it was a good idea to simply code HLD rather than try out other ideas, in case other ideas fail tests.

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

    Same here! :D

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

    you can do it with cumulative frequencies. The operation (update from a to b with 1) can be transformed to:
    sum 1 from a to the root
    sum 1 from b to the root
    rest 1 from lca(a,b) to root
    rest 1 from the parent of lca (if exists) to the root.

    so you dont have to do HLD, of course it needs to calculate lca.

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

    HLD passed my mind but I quickly found the easier solution. It's better to think a couple of minutes more than to overkill. I personally take much longer to implement HLD compared to LCA so it turned out good that I didn't jump straight to coding.