P_Nyagolov's blog

USACO First Contest 2015-2016
By P_Nyagolov, history, 9 years ago, In English

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

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

Comments Comments (66)
| Write comment?
»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Should we discuss the problems here after the contest?

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

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.

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

    Yeah, I just finished it, thanks, the statement wasn't clear enough so this helped! :)

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

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

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

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

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

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

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

    are the results out?

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

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

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

Who have used the entire time to do Silver division?

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

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

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +37 Vote: I do not like it

    Yes, even platinum ones are quite easy. Though remember that you improved in this 2-3 years ;)

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

    I personally like USACO problems very much whether easy or hard.

    As a side note does anybody know of any archive where solutions to old problems can still be found?

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

    I absolutely agree! I found one of the Platinum problems hard but I didn't think it a lot, maybe it's easy for better programmers :)

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

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

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

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

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

      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.

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

        Have fun with RMQ and LCA? :(

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

        platinum was not much harder :/ and too standard

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

        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?

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

        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.

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

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

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

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

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

              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?

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

                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.

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

                  Thanks, I was confused, now I see that it really works :)

                  → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                9 years ago, # ^ |
                ← Rev. 2   Vote: I like it +1 Vote: I do not like it

                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

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

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

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

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

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

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

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

From Bronze to Platinum :)

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

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

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

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

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

      You can try e-mail solutions to [email protected]

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

        Thanks, just have to wait and see if I can get credit for problems I solved right after the four hour block ended.

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

    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

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

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

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

        omg haha I did same thing.

        I went to lunch and when I came back, the sad case was seen:D

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

      Same Problem here !

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

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

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

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

    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.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it
    • 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].
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

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

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

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

          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)

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

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

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

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

result are Here

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

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

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

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?

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

    but all of my prevois submissions have beeb saved of each problem...

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

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.

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

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?

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

    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.

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

    Same here! :D

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

    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.

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

    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.

    → Reply