Hi all,
Very soon the last elimination round of Google Code Jam will kick off.
The top 25 contestants, along with last year's champion tourist, will advance to the onsite final round.
Let's discuss the problems here after the round.
Good luck!
UPD: contest starts in less than one hour, you can load the dashboard now.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | adamant | 152 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
How many problems do you expect? 4 or 5?
Quite strange problemset.
During the contest I bet no C-large will pass (geometry with no example). Surprisingly 19 passes!
But only one of them ranked in top 25.
Probably because the better strategy turned out to be to focus on D rather than C.
That's because points assigned to C and D are a bit strange
You were getting bonus points for believing that D-large is not much harder than D-small. Much more bonus points than for solving C-large, for example.
I looked at what score was generally needed to advance to the finals in the previous years and thought that it would be enough to have everything but D-large. (But my C-large failed anyways)
How to solve D-large? For D-small, I used
"1"*(L - 1)and"0?"*LLet b = a1... an.
If s[i]! = b for all i, output
and
Code Jam has been playing a lot of tricks this year! This one being that the good set is completely irrelevant as long as it doesn't contain B.
There is almost nothing from geometry in the solution. You only need to find a time interval in which two particular asteroids are closer than a particular distance, and that is just an inequality.
Figuring out the coefficients from those asteroids and then solving quadratic inequality is something nobody likes and also not that straightforward for most people and it demands a slight part of geo3D library (however one that most people should be able to write during contest, but again not something people like). However when preparing to WF16 I coded problem A from WF12 about asteroids, so it was very tempting for me to solve that problem, because I simply copy-pasted all of the needed code for geometry part :P. I made a bet that D large will be sufficiently hard so that it won't be required to qualify and I have big advantage in problem C, so I will solve it significantly faster than others. Turned out both assumptions were very wrong...
I didn't manage to solve C. But about that interval of times, I think that you can find the optimal t(which generates smallest distance) for each pair of asteroids through ternary search. Than, I thought that you may want to bynary search the answer so for a maxD, you can binary search the t in each of the two segments [0, t] and [t, inf) where t is that optimal time for those two fixed asteroids. Unfortunately, after determining these intervals of time, I was unable to solve the remaining problem (which I guess was the hard part).
Yeah, you're right, I also noted it in the meantime. This way it is definitely easier.
I needed just a few extra minutes to finish solving C-large. The problem is not very hard if solved the right way. My solution maintains a graph, where there is an edge between two asteroids if it is possible to jump between them. A list of events (edge added, edge removed) is generated and processed while maintaining the set of reachable asteroids. For isolated asteroids, there is also a "time limit", but it is only checked when this asteroid is connected again (if this is done too late, it is marked as unreachable). I think that the complexity is
, because, while many asteroids may become reachable as the result of event, only at most two can stop becoming reachable. The only "geometric" part is to compute, for two asteroids, the time when they become within distance d from each other and when they stop being within such a distance.
I need 6 dropouts. Fat chance :(
Too bad. :( The scoring was really weird; IMO solving C-large is a lot more impressive than solving D-large!
If the points for C-large were >= than the points on D-large, then I would expect the contest to go the other way: almost everybody would try to get C-large, since that problem is difficult but it's clear in which direction to move and one can make progress, whereas with D-large one may get stuck for a long time and only then see the solution.
As a result, most if not all people in top 25 would end up solving C-large, and there would be many people disappointed for two reasons: failing C-large because there are a few tiny implementation details that are easy to get wrong, and not advancing despite solving the difficult D-large.
Also, I didn't expect so many people to solve D-large — it seemed harder to me.
I see your reasoning: C-large was the only problem this GCJ where the Small input didn't help you at all with debugging the Large. But it seems worse to not go to the finals after getting C-large because you didn't realize D-large was mandatory. :) (I'm not bitter; I didn't solve either of them!)
I agree D is a hard problem, but it's a math problem with no implementation, and there are a lot of reeeeeally clever people competing...
You could get a WF ticket last year, and I also need 6 dropouts in this year. Wish me luck! :)
It turned to rather has no meaning, but "8+17" was a really strange partition of point for C. I would rather set 1+24.
Can someone please explain how to solve problem B?
Randomly generate 100,000 valid sequences. Note that probability must be higher for strings that can occurs multiple times, this is done by assigning weights to all courses: weight(u) = #descendants(u).
So, you choose a random node from all current tree roots according to this weight (= size of the subtree)?
Yes
Your description sounds a bit like one has to guess the correct weight, whereas it's not that hard to actually find it by reasoning.
More specifically, if we were to count the number of valid sequences, after some thought we can see that their number is n! divided by the product of sizes of all subtrees. Now we can use that to count the number of valid sequences with course A on first place, course B on first place, etc, and it turns out that those numbers are proportional to the sizes of subtrees of those courses.
I just guess that solution when see more then 40 AC solutions and got AC. It's interesting how many participants proved their solution during the contest?
I implemented it in overcomplicated way (by calculating number of outcomes for each choice using DP and binomial coefficients instead of these simple formulas); I remember Petr giving quite similar problem with same idea behind it at Petrozavodsk training camp some time ago, so during a round I was sure about correctness of solution and pretty sure that I know who prepared this problem as well:) But still I completely missed the fact about "size of the subtree magic".
Could you tell which problem are you referring to? The most similar one I remember is "Random Domino Placements", but it seems to me that it didn't share any ideas with this one.
I had problem Number of Close Strings from the same contest in my mind; I rechecked exact statement now indeed these two tasks are very different... Yet remembering idea from that one helped me in this problem somehow :)
Thanks! I think the common part is essentially the Central Limit Theorem, which was indeed useful in both problems.
Going a little offtopic, but "Number of Close Strings" is one of my favourite problems!
Talking about Random Domino Placement — this one has been bouncing in my head for a long time. Would you mind giving some hints :)? Should we generate those placements "really uniformly" or is the trick within creating them as a result of some Markov chain?
It's Markov chain this time. You have to come up with some Markov chain where transitions are quick to do and stationary distribution is uniform.
I read somewhere that you can make a fair shuffle of an array using mergesort, but when you merge you have to weight the selection according to the number of elements in each part.
Then I just assumed it worked like that for trees too and YOLO submitted, it's Small anyway :P
I think that the hardest part is to come up with the size of subtree.
Btw, why GCJ doesn't ignore additional whitespaces? I was struggling for a long time with B, because I put an additional endline after "Case" templated thingy, because I remembered empirically observed rule that if output is not of constant size then there used to be end of line there :.
Yeah, I guess this is mostly for historical reasons (wow, it's our 9th Code Jam using this platform now!). We try to write the problem statement clearly (in this case it said "For each test case, output one line..."), but I agree that ideally we would not care about newlines in your output.
Sorry you had to struggle with this.
Maybe points weren't adjusted properly but problems were very nice! I feel bad for my bad score because topics were perfect for me :/
Fun fact: There doesn't exist a person so that taking all his points he earned in C or giving him all points in C he didn't earn changes whether he qualified. Null. Zero. Nada. Nil. Zilch. Zippo.
what about those with 58 points? (time penalty would matter in that case though)
Ahhh, I missed fact that two last finalists didn't get Csmall, you're right.
How to solve A?
It's obvious following greedy works: if last problem set requested is the same as current mood today, submit it for 10 points; otherwise request a new one. The problem sets that remain can be paired for 5 points each.
DOH!
I get 7-th position, I'm very happy ^_^.
But there are the exam in my university in 8/5 (;_;).
Contest editorial is available at last.