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 :)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 173 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 160 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
Should we discuss the problems here after the contest?
sure what a wonderful idea
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.
Yeah, I just finished it, thanks, the statement wasn't clear enough so this helped! :)
In 2 hours of the contest, I only tested the solutions to understand questions ! I think problems have unclear statement.
Is that green box after submit containing full test case or pretest only?
Full
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).
are the results out?
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).
Who have used the entire time to do Silver division?
it does not matter
what's wrong with USACO? As I remember 2-3 years ago there were VERY hard and interesting problems in GOLD division.
Yes, even platinum ones are quite easy. Though remember that you improved in this 2-3 years ;)
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?
dl.gsu.by
Here you can find:
http://contest.usaco.org/
After slash write month and year.
Example:
http://contest.usaco.org/DEC06
How do I see problem statements? When I click on the problem name it shows the test data.
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 :)
Why USACO is so easy now ? It was much harder 2-3 years ago.
" 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. "
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.
Have fun with RMQ and LCA? :(
The contest is still on...
platinum was not much harder :/ and too standard
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?
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.
What's your solution for the third problem (Bessie's Dream)?
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).
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?
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.
Thanks, I was confused, now I see that it really works :)
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
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! :)
IMO, platinum problems should have been gold ones, because they are too easy for the highest division.
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! :)
From Bronze to Platinum :)
In just one day. :)
I wanted to participate in Platinum during last hours of the contest and now it turns that usaco.org is down T_T
I was in the middle of the contest, not sure what to do now.
You can try e-mail solutions to [email protected]
Thanks, just have to wait and see if I can get credit for problems I solved right after the four hour block ended.
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
After an hour since my submission I got a response that I forgot to include input/output files :)
omg haha I did same thing.
I went to lunch and when I came back, the sad case was seen:D
Same Problem here !
Is there any one have any solution for this PROBLEM !!! :|
What's the solution of High Card Low Card (platinum)?
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.
Oops, I didn't realize it. Thank you!
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...
how do you approach High Card Low Card (Gold)? The only idea i can come up with is bipartite matching. :(
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)
it .. is .. simple. too bad i didn't get it.
Thanks for your explanation. I'll try to implement it in the future.
result are Here
Никак не могу разобраться с решением. Может кто-нибудь кинет код задачи о лампочках (silver 1) на c++ или fpc. Заранее спасибо всем добрым людям.
Here you are :)
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?
but all of my prevois submissions have beeb saved of each problem...
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.
Shorter code for the nonlazy segment tree.
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?
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.
Same here! :D
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.
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.