### lsmll's blog

By lsmll, 7 years ago, ,

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

• +13

 » 7 years ago, # | ← Rev. 3 →   +1 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/
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 -snip- never mind, wait till contest is over for EVERYONE!!
•  » » 7 years ago, # ^ |   0 not only one problem, there is at least two problems existed in internetI will post them too
 » 7 years ago, # |   +4 Условия в bronze division на русском языке содержат ошибки:Задача B: Условие написано не до конца, точнее почти не написано.Задача A: В самом конце в пояснении output перепутали имена. Для еще не сдавщих советую прочитать условия на английском во избежания "лажи" :)
 » 7 years ago, # |   0 When will be results?
•  » » 7 years ago, # ^ |   +6 Sunday maybe.USACO is usually slow for its 'Results will be posted on this website shortly after the end of the contest.'
 » 7 years ago, # |   0 Is it over?
•  » » 7 years ago, # ^ |   0 Yes. It finished about four hours ago.
•  » » » 7 years ago, # ^ |   +3 so we can discuss the tasks now, right?
•  » » » » 7 years ago, # ^ |   0 Yeah,I think so.
•  » » » » » 7 years ago, # ^ |   0 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
•  » » » » » » 7 years ago, # ^ |   0 Can anyone explain why this solution works?
•  » » » » » » » 7 years ago, # ^ |   0 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 ).
•  » » » » » » » » 7 years ago, # ^ |   0 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.
•  » » » » » » » » » 7 years ago, # ^ |   0 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.
•  » » » » » » 7 years ago, # ^ |   0 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.
 » 7 years ago, # |   +1 Someone can tell how solve all tasks in gold division?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +19 .. 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 ..
•  » » » 7 years ago, # ^ |   0 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?
•  » » » » 7 years ago, # ^ |   0 I wonder why N is not 10^5 then :)
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   +6 Because they do not know either sulution, or it's proof :p
•  » » » » 7 years ago, # ^ |   +16 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.
•  » » » » » 7 years ago, # ^ |   +1 My solution gives 502 for this test case as you can see. What's your answer?
•  » » » » » » 7 years ago, # ^ |   +13 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
•  » » » 7 years ago, # ^ |   0 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.
•  » » » » 7 years ago, # ^ |   0 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...
•  » » » 7 years ago, # ^ | ← Rev. 3 →   0 Hillwalk: what is your answer for this test?:60 0 6 64 3 10 74 1 8 46 0 12 1010 4 13 74 0 7 2
•  » » » » 7 years ago, # ^ |   0 My solution gives 4 ..
•  » » » 7 years ago, # ^ |   0 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...
•  » » 7 years ago, # ^ |   0 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
 » 7 years ago, # | ← Rev. 2 →   +3 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
•  » » 7 years ago, # ^ |   +2 btw, there is a nice explanation of the Necklace problem here: http://apps.topcoder.com/forums/?module=Thread&threadID=669371
 » 7 years ago, # |   0 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!
 » 7 years ago, # |   +3 Someone please explain how you solve bronze division 3-rd problem.
•  » » 7 years ago, # ^ |   0 Just brute-force it.
•  » » » 7 years ago, # ^ |   +3 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.
•  » » » » 7 years ago, # ^ |   0 I did have the same idea, but had difficulties implementing it and ended up doing a brute-force.
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 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 :)
•  » » » » 7 years ago, # ^ |   0 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.
•  » » » 7 years ago, # ^ |   0 Yes I did the same thing but I think my code fails for n=15 or maybe even n=14.
•  » » » » 7 years ago, # ^ |   0 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.
 » 7 years ago, # |   +4 I never understood why USACO insists on hiding one's personal results for too long.
 » 7 years ago, # |   0 When will the results come out.
•  » » 7 years ago, # ^ |   +3 Probably early on Sunday. Last two contests were released by that time.
•  » » » 7 years ago, # ^ |   0 Thanks:)
 » 7 years ago, # |   +3 find results here : http://www.usaco.org/index.php?page=mar13results
 » 7 years ago, # |   0 They published RESULTS!! You can see your score, but solutions for some problems aren't published yet(
 » 7 years ago, # |   0 can anyone give me solution for problem B in silver division ?
•  » » 7 years ago, # ^ |   0 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.
 » 7 years ago, # |   0 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.
•  » » 7 years ago, # ^ | ← Rev. 4 →   +1 The hills she walks (0-indexed) are, in order...200-196-211-247-236-261-268-296-283-326-359-374-401-440424-550-549-564-552-588-593-582-560-693-697-748-763-828870-881-912-910-957-952-1019-1062-1083-1115-1127-11201151-1161-1176-1199-1213-1262-1268-130349 in total.
•  » » » 7 years ago, # ^ |   0 This doesn't include hill 0 right?
•  » » » » 7 years ago, # ^ | ← Rev. 3 →   +1 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-19444449-6218-784-1580-2407-4451-4612-28025101-5823-1668-5463-1620-191-3316-57332045-5784-4658-5278-4134-5714-4411-22612013-272-2818-1017-6460-6133-3960-6513789-5446-2345-918-5941-4281-3179-4482-3453
•  » » » » » 7 years ago, # ^ |   0 Ah yes, I thought there was something off about those first ones. Thanks.