USACO First Contest 2015-2016

9 лет назад, # |

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

→ Ответить

9 лет назад, # ^ |

Yeah, I just finished it, thanks, the statement wasn't clear enough so this helped! :)

→ Ответить

aliasadiiii

9 лет назад, # |

← Rev. 2 →

+12

In 2 hours of the contest, I only tested the solutions to understand questions ! I think problems have unclear statement.

→ Ответить

king_of_math

9 лет назад, # |

← Rev. 2 →

Is that green box after submit containing full test case or pretest only?

→ Ответить

AlexandruValeanu

9 лет назад, # ^ |

Full

→ Ответить

chaosagent

9 лет назад, # |

← Rev. 2 →

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

→ Ответить

shelob

9 лет назад, # ^ |

are the results out?

→ Ответить

chaosagent

9 лет назад, # ^ |

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

→ Ответить

Infused

9 лет назад, # |

Who have used the entire time to do Silver division?

→ Ответить

Bekmyrat.A

9 лет назад, # ^ |

← Rev. 2 →

it does not matter

→ Ответить

Furko

9 лет назад, # |

+44

what's wrong with USACO? As I remember 2-3 years ago there were VERY hard and interesting problems in GOLD division.

→ Ответить

Egor

9 лет назад, # ^ |

← Rev. 2 →

+37

Yes, even platinum ones are quite easy. Though remember that you improved in this 2-3 years ;)

→ Ответить

Matjaz

9 лет назад, # ^ |

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?

→ Ответить

greedyTaiga

9 лет назад, # ^ |

dl.gsu.by

→ Ответить

AClover

9 лет назад, # ^ |

+16

Here you can find:

http://contest.usaco.org/
After slash write month and year.

Example:
http://contest.usaco.org/DEC06

→ Ответить

cadenza

9 лет назад, # ^ |

How do I see problem statements? When I click on the problem name it shows the test data.

→ Ответить

9 лет назад, # ^ |

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

→ Ответить

greedyTaiga

9 лет назад, # |

Why USACO is so easy now ? It was much harder 2-3 years ago.

→ Ответить

determinism

9 лет назад, # ^ |

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

→ Ответить

9 лет назад, # ^ |

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

→ Ответить

kalimm

9 лет назад, # ^ |

-65

Have fun with RMQ and LCA? :(

→ Ответить

rnsiehemt

9 лет назад, # ^ |

+20

The contest is still on...

→ Ответить

sparik

9 лет назад, # ^ |

platinum was not much harder :/ and too standard

→ Ответить

kenning9

9 лет назад, # ^ |

-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?

→ Ответить

9 лет назад, # ^ |

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.

→ Ответить

gautam94

9 лет назад, # ^ |

What's your solution for the third problem (Bessie's Dream)?

→ Ответить

9 лет назад, # ^ |

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

→ Ответить

9 лет назад, # ^ |

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?

→ Ответить

9 лет назад, # ^ |

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.

→ Ответить

9 лет назад, # ^ |

Thanks, I was confused, now I see that it really works :)

→ Ответить

9 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

9 лет назад, # ^ |

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

→ Ответить

ha1vanka

9 лет назад, # |

+27

IMO, platinum problems should have been gold ones, because they are too easy for the highest division.

→ Ответить

9 лет назад, # |

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

→ Ответить

Raywzy

9 лет назад, # |

From Bronze to Platinum :)

→ Ответить

tweety

9 лет назад, # ^ |

In just one day. :)

→ Ответить

Rubanenko

9 лет назад, # |

+14

I wanted to participate in Platinum during last hours of the contest and now it turns that usaco.org is down T_T

→ Ответить

universe-

9 лет назад, # ^ |

I was in the middle of the contest, not sure what to do now.

→ Ответить

Egor

9 лет назад, # ^ |

+11

You can try e-mail solutions to [email protected]

→ Ответить

universe-

9 лет назад, # ^ |

Thanks, just have to wait and see if I can get credit for problems I solved right after the four hour block ended.

→ Ответить

KayacanV

9 лет назад, # ^ |

← Rev. 3 →

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

→ Ответить

Rubanenko

9 лет назад, # ^ |

After an hour since my submission I got a response that I forgot to include input/output files :)

→ Ответить

KayacanV

9 лет назад, # ^ |

← Rev. 3 →

omg haha I did same thing.

I went to lunch and when I came back, the sad case was seen:D

→ Ответить

Tparsa

9 лет назад, # ^ |

Same Problem here !

Is there any one have any solution for this PROBLEM !!! :|

→ Ответить

determinism

9 лет назад, # |

← Rev. 3 →

What's the solution of High Card Low Card (platinum)?

→ Ответить

9 лет назад, # ^ |

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

→ Ответить

determinism

9 лет назад, # ^ |

Oops, I didn't realize it. Thank you!

→ Ответить

9 лет назад, # ^ |

+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].

→ Ответить

damien_g

9 лет назад, # ^ |

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

→ Ответить

monyet

9 лет назад, # ^ |

how do you approach High Card Low Card (Gold)? The only idea i can come up with is bipartite matching. :(

→ Ответить

damien_g

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 $\text{[math]}$ with a set (you'll have to use lower_bound and upper_bound)

→ Ответить

monyet

9 лет назад, # ^ |

it .. is .. simple. too bad i didn't get it.

Thanks for your explanation. I'll try to implement it in the future.

→ Ответить

smahdavi4

9 лет назад, # |

result are Here

→ Ответить

perec1970

9 лет назад, # ^ |

Никак не могу разобраться с решением. Может кто-нибудь кинет код задачи о лампочках (silver 1) на c++ или fpc. Заранее спасибо всем добрым людям.

→ Ответить

Infused

9 лет назад, # ^ |

← Rev. 2 →

Here you are :)

→ Ответить

Hepic_Antony_Skarlatos

9 лет назад, # |

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?

→ Ответить

smahdavi4

9 лет назад, # ^ |

but all of my prevois submissions have beeb saved of each problem...

→ Ответить

rnsiehemt

9 лет назад, # |

← Rev. 3 →

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.

→ Ответить

Laakeri

9 лет назад, # ^ |

Shorter code for the nonlazy segment tree.

→ Ответить

9 лет назад, # |

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?

→ Ответить

ssi7415

9 лет назад, # ^ |

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.

→ Ответить

9 лет назад, # ^ |

Same here! :D

→ Ответить

dcordb

9 лет назад, # ^ |

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

→ Ответить