### P_Nyagolov's blog

By P_Nyagolov, history, 5 years ago,

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 :)

• +73

 » 5 years ago, # |   +7 Should we discuss the problems here after the contest?
•  » » 5 years ago, # ^ |   +9 sure what a wonderful idea
 » 5 years ago, # |   +33 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.
•  » » 5 years ago, # ^ |   +4 Yeah, I just finished it, thanks, the statement wasn't clear enough so this helped! :)
 » 5 years ago, # | ← Rev. 2 →   +12 In 2 hours of the contest, I only tested the solutions to understand questions ! I think problems have unclear statement.
 » 5 years ago, # | ← Rev. 2 →   0 Is that green box after submit containing full test case or pretest only?
•  » » 5 years ago, # ^ |   +8 Full
 » 5 years ago, # | ← Rev. 2 →   0 Went from silver to platinum this contest :DHopefully 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).
•  » » 5 years ago, # ^ |   0 are the results out?
•  » » » 5 years ago, # ^ |   0 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).
 » 5 years ago, # |   +5 Who have used the entire time to do Silver division?
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 it does not matter
 » 5 years ago, # |   +44 what's wrong with USACO? As I remember 2-3 years ago there were VERY hard and interesting problems in GOLD division.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +37 Yes, even platinum ones are quite easy. Though remember that you improved in this 2-3 years ;)
•  » » 5 years ago, # ^ |   +3 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?
•  » » » 5 years ago, # ^ |   +3 dl.gsu.by
•  » » » 5 years ago, # ^ |   +16 Here you can find: http://contest.usaco.org/ After slash write month and year. Example: http://contest.usaco.org/DEC06
•  » » » » 5 years ago, # ^ |   0 How do I see problem statements? When I click on the problem name it shows the test data.
•  » » » » » 5 years ago, # ^ | ← Rev. 3 →   0 I don't know that, I think it only contains analysis and test data, but you can find statements on dl.gsu.by.
•  » » 5 years ago, # ^ |   0 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 :)
 » 5 years ago, # |   +3 Why USACO is so easy now ? It was much harder 2-3 years ago.
•  » » 5 years ago, # ^ |   0 " 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. "
•  » » » 5 years ago, # ^ |   +18 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.
•  » » » » 5 years ago, # ^ |   -65 Have fun with RMQ and LCA? :(
•  » » » » » 5 years ago, # ^ |   +20 The contest is still on...
•  » » » » 5 years ago, # ^ |   +4 platinum was not much harder :/ and too standard
•  » » » » 5 years ago, # ^ |   -29 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?
•  » » » » 5 years ago, # ^ |   +5 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.
•  » » » » » 5 years ago, # ^ |   0 What's your solution for the third problem (Bessie's Dream)?
•  » » » » » » 5 years ago, # ^ |   +3 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).
•  » » » » » » » 5 years ago, # ^ |   0 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?
•  » » » » » » » » 5 years ago, # ^ |   +4 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.
•  » » » » » » » » » 5 years ago, # ^ |   0 Thanks, I was confused, now I see that it really works :)
•  » » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   +1 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
•  » » » » » » » » » 5 years ago, # ^ |   0 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! :)
 » 5 years ago, # |   +27 IMO, platinum problems should have been gold ones, because they are too easy for the highest division.
 » 5 years ago, # |   +19 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! :)
 » 5 years ago, # |   +5 From Bronze to Platinum :)
•  » » 5 years ago, # ^ |   +1 In just one day. :)
 » 5 years ago, # |   +14 I wanted to participate in Platinum during last hours of the contest and now it turns that usaco.org is down T_T
•  » » 5 years ago, # ^ |   +3 I was in the middle of the contest, not sure what to do now.
•  » » » 5 years ago, # ^ |   +11 You can try e-mail solutions to bcdean@clemson.edu
•  » » » » 5 years ago, # ^ |   0 Thanks, just have to wait and see if I can get credit for problems I solved right after the four hour block ended.
•  » » 5 years ago, # ^ | ← Rev. 3 →   +6 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 nothingUpdate: The Grader works fine at the moment
•  » » » 5 years ago, # ^ |   +8 After an hour since my submission I got a response that I forgot to include input/output files :)
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   0 omg haha I did same thing.I went to lunch and when I came back, the sad case was seen:D
•  » » » 5 years ago, # ^ |   0 Same Problem here !Is there any one have any solution for this PROBLEM !!! :|
 » 5 years ago, # | ← Rev. 3 →   +6 What's the solution of High Card Low Card (platinum)?
•  » » 5 years ago, # ^ |   +14 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.
•  » » » 5 years ago, # ^ |   +5 Oops, I didn't realize it. Thank you!
•  » » 5 years ago, # ^ |   +25 First thing to notice is that if we use k cards to win k "high card wins" rounds, we might as well use the k highest cards. Similarly, if we use k cards to win k "low card wins" rounds, we can also use the k lowest cards. Second thing is that we have N cards and there are N rounds, so the sets of cards we use to win each type of round will be disjoint. Knowing those facts, we can build a solution. Let's calculate for every prefix, the maximum number L[i] of rounds we can win if we play with "high card wins" rule for the first i rounds. And let's also calculate for every suffix, the maximum number R[i] of rounds we can win if we play the last N - i + 1 rounds with "low card wins" rule. We can calculate both of these greedily using an ordered set of available cards (start with a set containing all our cards, then to beat a card x, for "high card wins" choose the minimum available card y such that y > x, and for "low card wins", choose the biggest available card y such that y < x; then remove the card from the set). The answer will be the maximum L[i] + R[i + 1] among all i in the range [0, N].
•  » » » 5 years ago, # ^ |   +3 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 :DBut it seems that it's not such an exploit after all...
•  » » » » 5 years ago, # ^ |   0 how do you approach High Card Low Card (Gold)? The only idea i can come up with is bipartite matching. :(
•  » » » » » 5 years ago, # ^ |   +9 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)
•  » » » » » » 5 years ago, # ^ |   +8 it .. is .. simple. too bad i didn't get it.Thanks for your explanation. I'll try to implement it in the future.
 » 5 years ago, # |   -12 Как решается первая задача из silver (о лампочках). Спасибо.
 » 5 years ago, # |   +9 result are Here
•  » » 5 years ago, # ^ |   0 Никак не могу разобраться с решением. Может кто-нибудь кинет код задачи о лампочках (silver 1) на c++ или fpc. Заранее спасибо всем добрым людям.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Here you are :)
 » 5 years ago, # |   0 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?
•  » » 5 years ago, # ^ |   0 but all of my prevois submissions have beeb saved of each problem...
 » 5 years ago, # | ← Rev. 3 →   +8 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.
•  » » 5 years ago, # ^ |   +8 Shorter code for the nonlazy segment tree.
 » 5 years ago, # |   0 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?
•  » » 5 years ago, # ^ |   0 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.
•  » » 5 years ago, # ^ |   0 Same here! :D
•  » » 5 years ago, # ^ |   -6 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.
•  » » 5 years ago, # ^ |   0 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.