The problems and results of last week's VK Cup 2015 have been published after the online mirror took place on Thursday (
problems,
results, top 5 on the left,
online mirror results with shuffled problems). Congratulations to Team Never Sorry who have squeezed out the first place by being the only team to solve problem C, taking advantage of the dynamic scoring system.
The problem in question wasn't extremely difficult - it required one nice idea that gives most of the solution and then a lot of careful logical reasoning to figure out all corner cases: consider a tree, and for each vertex find the set of vertices at distance at most 2 from it. You're given those n sets in random order (so you don't know which vertex each set corresponds to), and you need to reconstruct the orignial tree. The size of the tree is at most 1000.
TopCoder SRM 664 wrapped up this week on Saturday with three mathy problems (
problems,
results, top 5 on the left,
my screencast).
The easiest one went like this: we have two numbers, x and y, and repeatedly double the smaller number, subtracting it from the larger number at the same time, so that the sum stays the same. For example, if we start from (1, 6), then we get (2, 5), then (4, 3), then (1, 6) again and so on. Which two number are we going to get after two billion steps? x and y are up to 1 billion.
Many people have noticed that several examples all lead to a periodic sequence quickly, and implemented general period-finding algorithms. However, it turns out that the period can be rather large, and we got an eventful challenge phase.
In fact, it's an interesting (and not very difficult) question by itself: what is the largest period length under the given constraints?
Thanks for reading, and check back next week!
0 komentar:
Post a Comment