Looking at the questions I expected a high cut-off for this one. However Q1 + small data set of Q3 apparently was sufficient.<\/p>\n
Q1 – I haven’t checked any answers but this seems trivial – count the number of unique symbols, that is your base (if only one symbol then its base 2). First symbol is 1, second symbol is 0, subsequent symbols are 2…n in left to right order. All that remains is to convert the result into text, using 64bit int to avoid overflow.
\nQ2 – This appears trivial, although there was 1 special case right off the bat I noticed. Looking at another answer there is a second. One I strongly suspect I would have noticed during implementation. Velocity of centre of mass is average velocity of all particles since they have same mass. At that point you have a simple line-point equation to determine the closest location. (Admittedly I don’t remember the line point equation off by heart, but its 30 seconds to find it on mathworld or somewhere…). Special cases are if closest location is prior to starting point (in which case you use the starting point) and if the average velocity is 0 (in which case you also take the starting point). Line point equation gets a divide by 0 if the average velocity is 0 anyway, so that special case shouldn’t be hard to see. In any case I was surprised that this wasn’t required to pass on to the next round. I guess that 1A and 1B had thinned the top levels enough that this round was easier to get through in.
\nQ3 – This is the real problem of the set but the constraints on the small data set mean it is a trivial brute force. The problem feels familiar but I don’t remember where I saw it before. It is however a classic brute force is too expensive and the seemingly obvious greedy solution is wrong problem. I looked at one of the solutions and they used dynamic programming as is to be expected in that scenario, but its late enough that I couldn’t translate the DP back into a sensible description of an approach. I’ll have to think about it some more and update this later.<\/p>\n
Edit: Okay so I definitely remember this problem now…
\nLast time I saw a problem like this this is what happened.
\n1) Identified n! brute force, as a failure.
\n2) Identified that after you select one prisoner to remove, either side is now an independent problem. This allows an algorithmic improvement on n!, but its still exponential, and I realise it is too slow.
\n3) Decide (incorrectly) that either the mean or median of a given section is always the right one and waste an hour trying variations on a theme to try and get it to work.<\/p>\n
If I was to solve this problem correctly I would have to have a different step 3 (obviously)
\n3) Recognise that there are repeated sub-problems in the independent problems.
\n4) Add caches
\n5) Win.(hopefully)
\nThe cool DP solution I couldn’t work out immediately is a variation on this starting at step 4.
\nTo go into step 4 in more detail, there are 3 different scenarios which have to be cached.
\n1) Minimum bribe for everything left of removed prisoner.
\n2) Minimum bribe for everything right of removed prisoner.
\n3) Minimum bribe for everything between 2 removed prisoners.
\nUsing sentinels we can store all 3 scenarios in a single cache rather than needing 3 caches, but still it is kind of messy.
\nThe cool DP solution realises that having added sentinels the problem can be restated as having one extra cell on each end also contain a prisoner, and those 2 prisoners are always the first 2 released. What is the minimum bribe now. Adjust that by the bribe paid when the first 2 are released and you have the answer to the original question. Or make it what is the minimum bribe left to be paid for this section after each end is released, then no adjustment is required. The advantage of this new question is that every sub-problem is now a variant of type 3, there are never any type 1 or type 2 scenarios. This makes the DP much simpler to write. Although slightly harder to understand…<\/p>\n
46 Australians through to round 2 a good 1.5% of contestants. 1C was a good round for Australia. Assuming (stupidly) results are random we should expect <0.4 Australians in the on-site finals :P\n\nIt is very annoying that round 2 and 3 are at 2am local time. But anyway.\n\n<\/p>\n","protected":false},"excerpt":{"rendered":"
Looking at the questions I expected a high cut-off for this one. However Q1 + small data set of Q3 apparently was sufficient. Q1 – I haven’t checked any answers but this seems trivial – count the number of unique symbols, that is your base (if only one symbol then its base 2). First symbol … Continue reading GCJ 09 Round 1C<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[],"class_list":["post-84","post","type-post","status-publish","format-standard","hentry","category-code-competitions","category-random-musings"],"_links":{"self":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/84","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=84"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/84\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=84"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=84"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=84"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}