Code Jam R3 starts today at 14:00 UTC. Don't miss!
Top-25 contestants will pass to onsite this August in Google's LA office.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
Code Jam R3 starts today at 14:00 UTC. Don't miss!
Top-25 contestants will pass to onsite this August in Google's LA office.
Name |
---|
LOL
To be more precise, only Top-24 and ivan.metelsky are going to LA.
Edit: I was wrong, Top-25 and ivan.metelsky will advance to the Onsite Finals.
Previous year champion has a wildcard?
Are you sure?
There are a total of 26 spots in the Finals, including mystic's spot. So if he places in the top 25, the top 26 contestants will all advance to the finals. Otherwise, the top 25 + mystic will advance.
Right, for some reason I thought top-25 including mystic will advance, however the official site says that top-25 along with mystic are going to LA.
How to solve Clarge?
Min-cost-max-flow (the idea isn't very hard, but it'd take a lot of time to explain it in details).
I used just max-flow. The idea is co create a chain of vertices for each person, with vertices within the chain corresponding to events. A flow equal to 1 indicates than a person is inside, and a flow equal to 0 indicates that he is outside. Unfortunately, it's (O(n2)) vertices and edges.
Maximal matching, then adding E? before and L? after, if needed.
Can you write your solution more detailed? I had something like that, but each variation of my matching solution didn't work on some test =\
You can download my solution.
mincost maxflow: Imagine that there are two vertices of infinite capacity, but edges cost 1. For every ID!=0 look if first entry is E , connect it to first vertex. If last entry is L, connect it to second.
I wrote Matching that does the same.
Check if your original graph (without that vertices) is correct.
I have greedy solution, through it is quite complex
How to solve D-small?
I had simple bruteforce:
Choose 2 starting points then recoursively choose an edge, move the player, remove edge, make recoursive call, then add edge back.
When I saw the constraint is N <= 80, I immediately thought that any brute force would time out. :(
Could you leave your handle so I can take a look at how you implemented this idea? Thanks :)
handle is RiaD
Dynamic programming: D[Hs][Hc][Ss][Sc], where Hs and Hc are starting and current position of Hanaa and similarly Ss and Sc for Sherine. Value is the maximal balance we can achieve if it's currently Hanaa's turn.
For each state we carefully make one turn for Hanaa and one turn for Sherine. Sherine tries to minimize the value of the state we come to, Hanaa tries to maximize. Also we do not forget to separately process states where one of the girls has no way to move (in this case we have similar solution, making the other girl collect as much as she can).
It can be possibly implemented even easier if we'll make turn only for one girl in each DP state, but it was much more clear for me to implement it in such way as I described.
Also the answer is maxHsminSsD[Hs][Hs][Ss][Ss] because Hanaa starts choosing starting position first, and then Sherine will choose the worst position from all possible.
Recursive case analysis worked 2 minutes for me (but I stored tree as a 2D matrix, so it could be more efficient). Iterate over all starting points for A and B, then iterate over all possible moves:
This is reasonable, because we make a recursive call only if we move to the same subtree, which can happen exactly once in each function call, so maximum recursive depth will be O(N).
Hello!
Im'ranked the 26th at this round, and considering that mystic is ranked 21st, it is certain that top 26 participants are qualified to the on-site finals?
Thanks!
Even if it isn't, you'll be qualified because someone in top-25 definitely will decline invitation.
Thank you very much!
And that's what you're hoping for :D
I'm having an internship at Google from 06/23 till 09/26. I don't really know if I'm eligible to participate in onsite in this situation.
I'm going to ask something from jury about that (of course if I'll be invited).
The e-mail for the invitation for the round was pretty clear that 25 people + mystic would advance, so the 26th is also qualified.
See you in LA! :)
Thanks for your answer!
I look forward to seeing you in LA aswell!