USACO March Contest 2013

12 years ago, # |

Is it over?

→ Reply

atpec

12 years ago, # ^ |

Yes. It finished about four hours ago.

→ Reply

12 years ago, # ^ |

so we can discuss the tasks now, right?

→ Reply

atpec

12 years ago, # ^ |

Yeah,I think so.

→ Reply

12 years ago, # ^ |

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

Jamik

12 years ago, # ^ |

Can anyone explain why this solution works?

→ Reply

12 years ago, # ^ |

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

thisisjustm3

12 years ago, # ^ |

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, # ^ |

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, # ^ |

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

Sultan

12 years ago, # |

Someone can tell how solve all tasks in gold division?

→ Reply

CherryTree

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

→ Reply

Rubanenko

12 years ago, # ^ |

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

CherryTree

12 years ago, # ^ |

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

→ Reply

Rubanenko

12 years ago, # ^ |

← Rev. 2 →

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

→ Reply

scott_wu

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

→ Reply

Rubanenko

12 years ago, # ^ |

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

→ Reply

scott_wu

12 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

→ Reply

Pancake

12 years ago, # ^ |

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, # ^ |

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

P___

12 years ago, # ^ |

← Rev. 3 →

Hillwalk: what is your answer for this test?:

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

CherryTree

12 years ago, # ^ |

My solution gives 4 ..

→ Reply

mukel

12 years ago, # ^ |

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

http://apps.topcoder.com/forums/?module=Thread&threadID=669371

12 years ago, # ^ |

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

kingofnumbers

12 years ago, # |

← Rev. 2 →

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

brunoja

12 years ago, # ^ |

btw, there is a nice explanation of the Necklace problem here:

→ Reply

PeterNaut

12 years ago, # |

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

sparik

12 years ago, # |

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

→ Reply

egor-belikov

12 years ago, # ^ |

Just brute-force it.

→ Reply

12 years ago, # ^ |

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

sparik

12 years ago, # ^ |

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

→ Reply

Jarekczek

12 years ago, # ^ |

← Rev. 2 →

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

swarmer

12 years ago, # ^ |

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

sparik

12 years ago, # ^ |

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

→ Reply

guliashvili

12 years ago, # ^ |

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

Pancake

12 years ago, # |

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

→ Reply

Nodir.Daminov

12 years ago, # |

When will the results come out.

→ Reply

12 years ago, # ^ |

Probably early on Sunday. Last two contests were released by that time.

→ Reply

Nodir.Daminov

12 years ago, # ^ |

Thanks:)

→ Reply

guguli

12 years ago, # |

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

→ Reply

Jamik

12 years ago, # |

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

→ Reply

guguli

12 years ago, # |

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

→ Reply

12 years ago, # ^ |

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, # |

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 →

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, # ^ |

This doesn't include hill 0 right?

→ Reply

12 years ago, # ^ |

← Rev. 3 →

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