Codeforces Round #457 (Div. 2) Editorial

Revision en3, by STommydx, 2018-01-19 23:14:17

I would like to take this opportunity to express my deepest apology to all of you who take your own precious time to participate in this unrated round. Also, apologies to vintage_Vlad_Makeev who really helped a lot in preparing the round and MikeMirzayanov who helped to host the round, I did not do a good job in managing the round. As the main author of this round, I'm undoubtedly responsible for the mistake that not writing a brute force solution to test the correctness of the intended solution. It is my responsibility to make sure everything is right before the round starts.

I hope all of you can learn something from the contest. Do not claim a greedy solution absolutely correct (like me :C) unless you have proved it. On the bright side, I'm really glad that some of you found problem D and E interesting as said in some comments in the announcement blog post.

Just a little unimportant fact: The original div2B problem was a harder data structure problem which involves a slightly complicate mathematical proof (which the current one doesn't have :C). We replaced it because it is too difficult for div2B as the coordinator suggested.

916A - Jamie and Alarm Snooze

idea: STommydx, preparation: southball

Let's use brute force the find the answer. We first set the alarm time as hh: mm and initialize the answer as 0. While the time is not lucky, set the alarm time to x minute before and add 1 to the answer.

Why does this solution run in time? As x <  = 60, hh decrease at most 1 for every iteration. Also, after at most 60 iterations, hh must decrease at least once. All time representation that hh = 07 (07:XX) is lucky so at most 24 times decrement of hh will lead to a lucky time. Therefore, the max. number of iteration possible is 26 * 60 = 1440 which is very small for 1 sec TL.

In fact, the largest possible answer is 390 where x = 2, hh = 06 and mm = 58.

916B - Jamie and Binary Sequence (changed after round)

idea: southball, preparation: STommydx

Work in progress!

916C - Jamie and Interesting Graph

idea: STommydx, preparation: STommydx

First, observe that only n - 1 edges is required to fulfill the requirement, so we will make the other m - n + 1 edges with a very large number so they would not contribute to the shortest path or the MST. Now, the problem is reduced to building a tree with prime weight sum and two nodes in the tree have prime distance.

Recall that a path graph is also a tree! If we join (i, i + 1) for all 1 ≤ i < n, the shortest path will lie on the whole tree. We are left with a problem finding n - 1 numbers that sums to a prime. Let's make 1 edge with weight p - n + 2 and others with weight 1. Choosing a prime slightly larger than n (e.g. 100003) will fulfill requirement for all cases.

916D - Jamie and To-do List

idea: STommydx, preparation: STommydx

916E - Jamie and Tree

idea: longhuenchan, preparation: longhuenchan

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English STommydx 2018-01-20 15:42:53 158 Updated E editorial
en9 English STommydx 2018-01-20 11:18:08 2604 Added E tutorial
en8 English STommydx 2018-01-20 10:17:13 317 Added my implementation
en7 English STommydx 2018-01-20 08:09:28 681 Added B editorial (published)
en6 English STommydx 2018-01-20 07:13:01 1117 Added D tutorial
en5 English STommydx 2018-01-20 04:09:14 2 fix typo
en4 English STommydx 2018-01-19 23:15:03 6 Tiny change: 'me? As $x <= 60$, $hh$' -> 'me? As $x \leq 60$, $hh$' (saved to drafts)
en3 English STommydx 2018-01-19 23:14:17 95 Tiny change: 'answer is 390 where $x ' -> 'answer is $390$ where $x ' (published)
en2 English STommydx 2018-01-19 23:04:28 1519 Added A and C tutorial
en1 English STommydx 2018-01-19 21:45:30 1539 Initial revision (saved to drafts)