lsmll's blog

USACO March Contest 2013
By lsmll, 12 years ago, In English

The USACO 2013 March contest is available now. Participation is free, and open to all.

There will be 3 problems and you will have 4 hours to complete them.Supported languages are C, C++, Pascal, Java and Python.

You can take the contest during any contiguous 4-hour block of time you want.

The contest is open until until March 11.Check the deadline to start the contest in your timezone here.

Link to Contest Page

Please don't discuss the contest problems before it ends(deadline + 4 hours).

UPD:Contest is over.Now you can discuss the problems.

UPD2:Official results

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

Comments Comments (53)
| Write comment?
»
12 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

There is one problem that is identical to another I've seen on Spoj :/, same sample test case and limits! When the contest is over I will post the link.

Edit: The problem is http://spoj.com/problems/PSTRING/

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

    not only one problem, there is at least two problems existed in internet

    I will post them too

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

Условия в bronze division на русском языке содержат ошибки:

Задача B: Условие написано не до конца, точнее почти не написано.

Задача A: В самом конце в пояснении output перепутали имена.

Для еще не сдавщих советую прочитать условия на английском во избежания "лажи" :)

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

When will be results?

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

    Sunday maybe.USACO is usually slow for its 'Results will be posted on this website shortly after the end of the contest.'

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

Is it over?

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

    Yes. It finished about four hours ago.

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

      so we can discuss the tasks now, right?

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

        Yeah,I think so.

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

          Well, I participated in the silver division... So, my solution for the first problem is greedy, but I couldn't find an example on which it would be wrong The answer at the beginning is equal to the first value, then I compare every two consecutive elements and if their difference (A[i] — A[i-1]) is positive I add it to the final answer. Their example 5 elements 2 4 1 3 2 2 + (4 — 2) + 0 + (3 — 1) + 0 = 6

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

            Can anyone explain why this solution works?

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

              Well let's say you have found the minimal answer up to this position. In the case 2 4 1 3 2 2 for example we know that the minimal answer up to the second position (including) is 4, because it is better not to take the elements separately. For the third position — the second number of elements is bigger than the third so the optimal answer would be to take all of the third with the second or everything else will lead to a bigger answer. The same way we determine for the forth position — it is better to take some elements (actually 1 and we have already counted it) with the previous and what's left separately (2 ).

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

                The 8th test case on that problem... :( When do you guys recommend using 64 bit rather than 32 bit ints? Don't want my program to be caught off guard again.

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

                  You must look not only for the numbers in the input and output, but also for all the intermediate steps in your program.

                  For example, if you're told that no number A[i] in the input is > 10^5, and you use int's because of that, but there's a part in your program when you do (A[i] * A[i — 1]) % 1000, with A[i] = 99887 and A[i — 1] = 98456, you'll get overflow. Even though the final result will be < 1000, because of the modulo, the intermediate step of A[i] * A[i — 1] will overflow the data type.

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

            Yes, that's the solution I made in Analysis mode too. Only 11 lines of code.

            Consider a sequence of hands you play with K elements A[1], A[2], ..., A[k]. When you add the K+1th element into the game, you have two possibilities...

            • A[k+1] <= A[k]. In this case, you can just include it in the hands you play for A[k], so no extra hands are added.
            • A[k+1] > A[k]. In this case, there's no way you can include it in the hands you already have, because A[k] will become zero before A[k+1]. When A[k] becomes zero, you must make A[k+1] — A[k] extra moves to make A[k+1] become zero as well.

            Since you only need the last two values at any moment, this solution can be done on the fly while reading the input in O(N) time and O(1) memory.

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

Someone can tell how solve all tasks in gold division?

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

    .. The quality is USACO contests got much worse now, some months ago the solution for the only non-trivial problem was easy to find at the USACO site .. This time, 2 problems of 3 are far from new ..


    Problem 1. Google "Grazing on the run" or "Grazing on the run USACO" and you will find much solutions for the same problem. Generally, we do a DP F[L][R][flag] that means that we have visited all the cows from L-th to R-th (yes, you have to do the sort in the beginning) and now we are standing at the position of L-th or R-th cow (flag denotes which cow exactly). You can notice that if you visit the cows in order a1, a2, a3, a4, ... an then the answer is |a1-a2|+|a1-a2|+|a2-a3|+|a1-a2|+|a2-a3|+|a3-a4|+... , according to that you should count the first distance N times the second distance N-1 times, and so on.

    Problem 2. This is the only original (at least, I don't know any similar one) problem here. I have used standard scan line by X approach. I have two type of events: a segment begins at some X-coordinate and the segment ends at some X-coordinate. When the current "active" segment ends we have to find the first segment after it. Any balanced tree will do, maybe even set. I have used treap for it. The main observation is that the relative order of the segments in the set of enabled segments at some time is always the same.
    .. There are some tricky cases, I bet my solution will fail .. >_<

    Problem 3. Google "SPOJ PSTRING" or "SPOJ 704". You can do a DP, F[i][j] means that if you have processed the first i symbols of the string S (string S is the string from which you have to remove the symbols) and the largest prefix of the string T is j, what is the minimal number of symbols to remove. You have to preprocess the value of R[i][j], means that if there is a i-prefix of T (lets call it G), what is the largest suffix of G+j (j is char) that is the prefix of T can be obtained. Prefix function or hashes will do. You will get O(|S|*|T|) complexity for the problem ..

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

      By the way, the first one can be solved using this greedy approach:

      go from 0 to some point i, then turn and go to the end of the other side, then turn again and take all the other points.

      I got AC with this solution on a similar problem a year ago, and tested the same with bruteforce this time. It passed about 8k random small test cases :)

      I wonder, whether there is a proof for this solution?

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

        I wonder why N is not 10^5 then :)

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

          Because they do not know either sulution, or it's proof :p

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

        I'm not sure I understand how your algorithm works. What do you give for the case: 6 1 -1 10 -10 100 -100?

        It seems to me that the optimal path for this case requires several turns.

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

          My solution gives 502 for this test case as you can see. What's your answer?

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

            If you go to the points in the order 1, -1, -10, 10, 100, -100, the total is 492, which is what I give.

            I wouldn't be surprised if you got most or all of the points though, since only very specific cases will break your solution :P

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

      May you please suggest some testcases for Problem 3 ? My DP looks similar to what you describe here , but I'm getting WA on SPOJ.

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

        If you are talking about the cow run I have the same issues. My idea is as they described it and it's the author's solution, but I still get WA. I rewrite the code several times, but I can't find why it fails...

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

      Hillwalk: what is your answer for this test?:

      6

      0 0 6 6

      4 3 10 7

      4 1 8 4

      6 0 12 10

      10 4 13 7

      4 0 7 2

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

      Problem 2 is an easier variation of the segment intersection problem, cuz segments doesn't intersect thus relative order never change. The only trap at least for me is a dangerous overflow given the huge ranges in the coordinates, I first thought to use doubles, but finally I use a custom int128 to do calculations exact, but this is TLE prone, fingers crossed...

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

    Problem 1: The Cow Run This is a dynamic programming problem. And the state is the number of cows above the 0-position, the number of cows below the 0-position, and whether we are on the top or bottom. We only need to keep track of these things because we will always build a halter whenever we reach a cow, since it is instantaneous.

    There are at most N cows above, N cows below, and 2 possible states for being above or below, for a total of 2*N^2 states, making it a O(N^2) algorithm.

    Here is a link to my code: http://pastebin.com/TUaGjtgz

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

if you read the statment of the cow run carefully you can see:

Problem 1: The Cow Run [Chris Tzamos, 2006]

this is obviously an old problem but I could only find a similar problem in internet the only difference is this problem don't deal with negative positions.

also problem Necklace can be found in spoj here

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

Can somebody give a case for the problem of Necklace (gold) with its output so I can check my solution please. A small case but not with trivial answer. Thanks!

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

Someone please explain how you solve bronze division 3-rd problem.

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

    Just brute-force it.

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

      Yes, though I believe some pruning might be necessary. Maybe I'm wrong, but I think pure brute force would yield a complexity of O(K*3^N), which in the worst case is 717M.

      I think the best way would be to do, for each cow, make a list of different/same rules (with a vector or something). Then do recursion, at each step seeing if assigning breed 'b' to the current cow is in contradiction with some of this cow's rules.

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

        I did have the same idea, but had difficulties implementing it and ended up doing a brute-force.

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

        You can divide the complexity by 3 if you notice, that the actual breed names don't matter. Just assign an arbitrary breed to the first cow and iterate only the others. Finally multiply the result by 3.

        Otherwise I'm afraid a switch to Java is needed to gain extra 2 seconds :)

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

        I wrote 2 solutions: recursive backtracking and lexicographic bruteforce. Guess what, I decided to submit backtracking and got 2 TLs but dumbest bruteforce passed all the tests.

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

      Yes I did the same thing but I think my code fails for n=15 or maybe even n=14.

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

        worst case is 717M is impossible if you will write good brute-force. As K increases there will be no 3^N variants but much less.

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

I never understood why USACO insists on hiding one's personal results for too long.

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

When will the results come out.

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

find results here : http://www.usaco.org/index.php?page=mar13results

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

They published RESULTS!! You can see your score, but solutions for some problems aren't published yet(

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

can anyone give me solution for problem B in silver division ?

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

    We only need the X coordinates to know where the rectangle starts & ends. So we separate the rectangles in two segments (y and y1) and keep where they appear (on the x coordinate and the x1) and mark which one is the beginning (x) and which one is the end (x1). Then we sort by the X coordinate and for each element check whether it is a beginning or an ending. If it is a beginning and we don't have any segments in the range (y ; y1) (I personally do it with an index tree) then we add this rectangle to the answer. I'm not sure I explained it clearly so if you want my code — pm me.

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

Could someone tell me the line segments that Bessie walks on in "Hill Walk" (Gold) for test case #6? I'm having a hard time figuring out the bug in my code and some help would be appreciated. Thanks.

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

    The hills she walks (0-indexed) are, in order...

    200-196-211-247-236-261-268-296-283-326-359-374-401-440

    424-550-549-564-552-588-593-582-560-693-697-748-763-828

    870-881-912-910-957-952-1019-1062-1083-1115-1127-1120

    1151-1161-1176-1199-1213-1262-1268-1303

    49 in total.

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

      This doesn't include hill 0 right?

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

        I forgot to say, those are the indexes of the coordinates after being sorted by x1, then by y1 in case of ties. Of course, the first hill she walks is number 0, which I didn't include there.

        If you need the original number in which the hills appear in the input, then she walks these, in order...

        0-5116-163-4672-1382-1708-6495-1944

        4449-6218-784-1580-2407-4451-4612-2802

        5101-5823-1668-5463-1620-191-3316-5733

        2045-5784-4658-5278-4134-5714-4411-2261

        2013-272-2818-1017-6460-6133-3960-651

        3789-5446-2345-918-5941-4281-3179-4482-3453

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

          Ah yes, I thought there was something off about those first ones. Thanks.

          → Reply