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.
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
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/
not only one problem, there is at least two problems existed in internet
I will post them too
Условия в bronze division на русском языке содержат ошибки:
Задача B:Условие написано не до конца, точнее почти не написано.Задача A:В самом конце в пояснении output перепутали имена.Для еще не сдавщих советую прочитать условия на английском во избежания "лажи" :)
Как начать соревнование? Где что нажать? я там новичек
Если уже можно обсуждать , то как решалась вторая таска в Silverе ?
Не знаю зайдет у меня или нет, но я добавил 2*N точек с пометкой нижняя левая или правая верхняя точка. Сортил точки по x-координате. + у меня еще сделано дерево отрезков по у-координате, (y<=10^6) Потом бежал по массиву. Если точка — это левый нижний угол прямоугольника,то сначала определяем покрашен-ли отрезок Y1_i .. Y2_i (Y1_i — нижняя y-координата текущего прямоугольника, Y2_i — верхняя ), если покрашен, то пропускаем данный прямоугольник(покрашен — значит есть прямоугольник, который начинается по x-кординате раньше и включает наш), если нет то ans++ и красим отрезок Y1_i .. Y2_i. Если точка — это правый верхний угол, если мы красили отрезок Y1_i .. Y2_i , то красим обратно в никакой цвет, иначе ничего не делаем. Я не уверен что будет работать, но мне кажется что будет, тк прямоугольники не пересекаются. Сложность O(N * log 10^6)
When will be results?
Sunday maybe.USACO is usually slow for its 'Results will be posted on this website shortly after the end of the contest.'
Is it over?
Yes. It finished about four hours ago.
so we can discuss the tasks now, right?
Yeah,I think so.
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
Can anyone explain why this solution works?
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 ).
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.
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.
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...
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.
Слабый я какой-то в этой раз, но не подскажете полные решения по B и C Gold? C вроде какое-то дп, причём не совсем оригинальное. Особенно интересна B.
B, по идее, должна бы решаться свиплайном по горизонтали снизу вверх. Key observation №1: отрезки нужно только добавлять, но не удалять. Key observation №2: так как отрезки не пересекаются, то, если у нас есть два отрезка, у которых пересекаются проекции на Ox, то мы можем из них однозначно выбрать «высший». Каждый раз, когда свиплайном встречаем нижнюю левую точку какого-то отрезка, добавляем в дерево отрезков отрезок (x1, x2 — 1). Если вдруг начало очередного добавляемого отрезка выше, чем конец того отрезок, на котором сейчас стоит корова, то одним запросом к дереву отрезков узнаём, на какой отрезок корова упадёт (это то же самое, что и «высший отрезок, добавленный до сих пор, который включает точку x», где x — конец отрезка, на котором корова сейчас).
Someone can tell how solve all tasks in gold division?
.. 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 ..
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?
I wonder why N is not 10^5 then :)
Because they do not know either sulution, or it's proof :p
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.
My solution gives 502 for this test case as you can see. What's your answer?
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
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.
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...
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
My solution gives 4 ..
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...
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
кто-нибудь может рассказать условия gold-дивизиона?
A
B
C
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
btw, there is a nice explanation of the Necklace problem here:
http://apps.topcoder.com/forums/?module=Thread&threadID=669371
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!
Someone please explain how you solve bronze division 3-rd problem.
Just brute-force 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.
I did have the same idea, but had difficulties implementing it and ended up doing a brute-force.
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 :)
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.
Yes I did the same thing but I think my code fails for n=15 or maybe even n=14.
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.
I never understood why USACO insists on hiding one's personal results for too long.
When will the results come out.
Probably early on Sunday. Last two contests were released by that time.
Thanks:)
find results here : http://www.usaco.org/index.php?page=mar13results
They published RESULTS!! You can see your score, but solutions for some problems aren't published yet(
can anyone give me solution for problem B in silver division ?
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.
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.
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.
This doesn't include hill 0 right?
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
Ah yes, I thought there was something off about those first ones. Thanks.