JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
TCO13 algorithm rounds commentary | Reply
Hi everyone! I will be doing live, play-by-play commentary for all TCO13 Algorithm rounds. I will edit this post later to add links to the commentary. Read my post @ the TCO13 blog for more info on how this will work.

I will not have the time to follow this thread *during* the actual matches (just TC arena chat and twitter, as promised in the blog post), but if you have any questions or comments in the meantime, reply to this post and I'll get back to you as soon as I can.

See you tomorrow in the arena! :)

Semifinal 1:
Problems: easy:RabbitsAndCakes (by lyrically), medium:TheGameDAG (by gojira_tc), hard:GameWithTree (by K.A.D.R).
Commentary: http://goo.gl/ECGiLZ.
Editorials: easy (by Rustyoldman), medium (by vexorian with help from bmerry), hard (by Rustyoldman). Both mystic_tc and [[rng_58]] were also involved in writing these editorials.

Semifinal 2:
Problems: easy:GoodNumbers (by snuke), medium:JumpingOnTheGrid (by K.A.D.R), hard:OneBlack (by [[rng_58]]).
Commentary: http://goo.gl/Fx5N3K
Editorials: easy (by vexorian), medium (by misof), hard (by misof and bmerry).

Wildcard Round:
Problems: easy:TheFourSquares (by gojira_tc), medium:ModuloCounters (by [[rng_58]]), hard:SemiMultiple (by snuke).
Commentary: http://goo.gl/WK6LDi
Editorials: easy (by vexorian), medium (by mystic_tc), hard (by misof).

Finals:
Commentary: http://goo.gl/fHRChF
Re: TCO13 algorithm rounds commentary (response to post by misof) | Reply
Offtopic question: where do i see the algorithm schedule?
Event calendar does not contain TCO13 events (right?).
http://community.topcoder.com/tco13/algorithm/algorithm-schedule/ shows TBD.
Re: TCO13 algorithm rounds commentary (response to post by nigulh) | Reply
http://community.topcoder.com/tco13/overview/overview-onsite-events/ should be up to date. The times are US eastern time, and the coding phase will only start 30 minutes into the scheduled time, as the coders have some time to prepare their computers. Right now you should already see the times for the first semifinal in the arena.
Re: TCO13 algorithm rounds commentary (response to post by nigulh) | Reply
(double post, ignore)
Re: TCO13 algorithm rounds commentary (response to post by misof) | Reply
thoroughtly enjoyed the commentary. It would be really great if you could tell us some idea of tackling the problem, some small pointers towards the solution as petr usually does.
Re: TCO13 algorithm rounds commentary (response to post by misof) | Reply
Who were the writers?
Re: TCO13 algorithm rounds commentary (response to post by ltaravilse) | Reply
I added this info to the top post in this thread.
Re: TCO13 algorithm rounds commentary (response to post by misof) | Reply
I have an alternative solution for Wildcard Round Medium (Modulo Counters). You can see my code in edit.

The first thing I'll prove is that if you have the real values in the counters instead of the values modulo m then there is a position in the corridor where every fox steped. Assume there is not, then we take out one fox, and for each position he stepped there is at least one fox that didn't step in that position, so we make that fox step in that position. Now we know that if the counters have the real values instead of the values modulo m, the solution (if there is a valid way of stepping that leads to that numbers) is the greatest value of the counters.

Second part of the solution is knowing if there is a solution given the numbers (the original numbers, not the numbers modulo m) of the counters. We know that if there is a solution it is T = greatest value of the counters. So if there are T foxes, the only way of getting that values of the counters is if for every two consecutive positions, every fox steps in at least one of those two positions, then for each i we have to test:

T-counter[i]+T-counter[i-1] <= T

that is the same as

T <= counter[i]+counter[i-1]

Now if for every two consecutive positions all the foxes stepped in at least one of them that is a valid solution. It's easy to prove by induction that you can choose a fox, select the positions where he steps, and take out this fox and the following two equations will stil hold:

max(counter[i]) = T (the new value of T, that will be the original T-1)
T<= min(counter[i]+counter[i-1])

Now another thing we need to prove is that if there area T foxes, and there is a position with its counter equal to R<T then there is a solution with T foxes and with the same value on each counter except for that counter with value R changed for T. It's not hard to prove it as every fox that didn't step on that position can step there.

Now the only thing we need to do is try with the original counter as if it was not modulo m, and then change the minimum value of counter (let's say R) to R+M while the solution is not valid, changing all ocurrences of R to R+M. This need to be done at most 50 times as if all the counters are greater or equal than M but less than 2M then the solution is valid as we can make half of the foxes step on (0,2,4...), half of the foxes step on (1,3,5...) and then make them complete the steps as I proved that we can do.>
Re: TCO13 algorithm rounds commentary (response to post by ltaravilse) | Reply
I think this is the same as tomek's solution.
Thank you for providing the explanation.
Re: TCO13 algorithm rounds commentary (response to post by misof) | Reply
Thank you for the comments, misof. They made following the competition far more interesting :)

About the finals. It seems to me that 300s usually take longer to solve 400, 450 or even 500s. Does this point distribution still make sense?
Re: TCO13 algorithm rounds commentary (response to post by mogers) | Reply
I think the PackingSquares editorial is a little too complicated. You don't have to bother with "packing" at all, because a square of size x can contain ANY NUMBER of squares of size <x following it. Why? Well, it clearly has enough room for one square each of size 1, 2, ..., x-1. But then you can just nest subsequent squares of the same size within each other. There's no need for optimization.

By the same token, if the largest square size is x, and there are (at least) two squares of size x, you'll always want to wait and put the later one into the earlier one. Otherwise you'll have to add two squares of size x to the plane (instead of one), and the smaller squares in between all take up less area than one square of size x.

So the following simple greedy algorithm works:
- Find the largest square size x, and the last index i at which it appears.
- Add this square (size x) to the plane.
- Delete all squares of size x from your array, as well as all squares with index >i.
- Repeat.
Re: TCO13 algorithm rounds commentary (response to post by misof) | Reply
It seems that editorials for onsite problems have not been added into editorials page. Is this intentional?
RSS