### ko_osaga's blog

By ko_osaga, history, 20 months ago, ,

Hello Codeforces!

In 2018/05/26 21:30 Korea Standard Time (UTC+9) we will hold an online mirror of 2018 KAIST RUN Spring Contest. This is an annual individual contest held by KAIST's algorithm club RUN.

Problems are available in English, and you should individually solve 11 problems in 5 hours. The problems will be prepared in Gym, so this contest is unrated. Grading rules are ICPC-style. There are no prizes in this contest, but if any top scorers come to KAIST, we will bring you to our favorite restaurants or pubs ( ͡° ͜ʖ ͡°)

This online mirror might not reflect the onsite contest fully, due to some technical limits. For example, the grading rules in main contests were IOI-style, every problems were 100 points with subtasks and we had no penalties, but we had some difficulties implementing it on CF environment :/

Problems were prepared by koosaga, HYEA, alex9801, etaehyun4, platinant. alex9801's rating is 2399, so he hopes to be called as "semi-red", not orange.

Special thanks to HYEA, who hoped to upload this contest to gym (and actually worked on it), and MikeMirzayanov, who is the maintainer of this great community and system!

In the online mirror for Korean participants (including some famous red/nutella coders), nobody was able to solve all problems — I challenge you to beat them! :D

The contest is now finished! Congratulation to winners!

Local open contest scoreboard

Tests, checkers, solutions (warning, over 400MB!)

Editorial

Problemsetters :

• HYEA : P (Puyo Puyo), Y (Yut Nori)
• ko_osaga : Q (QueryreuQ), T (Touch The Sky), U (United States of Eurasia), V (Voronoi Diagram), W (Winter Olympic Games), Z (Zigzag)
• alex9801 : X (Xtreme NP-Hard Problem?!)
• platinant : R (Recipe)
• etaehyun4 : S (Segmentation)

Thanks to everyone who participated!

• +152

 » 20 months ago, # | ← Rev. 2 →   +15 While setting the problem, I've encountered the problem :(When I set contest to public, anyone who enabled coach mode can see the content of the contests. What should I do? (Display to the gym, but coach cannot see the problems)I ask some help of who knows well about gym system.
•  » » 20 months ago, # ^ |   +21 Sometimes they do online mirrors under CONTESTS tab then move them later to the gym, I think you need to contact the coordinators for that.Another option is to click "Update Contest" two minutes before the contest, but make sure everything is working when it's private then replace the contest.xml file as anyone in coach mode can update the contest.
•  » » » 20 months ago, # ^ |   +51 Thanks, I just decided to open the day before the contest. Anyway the contests already held and actually anyone can find problem in the Korean judge system (with poor English translation)I bet on people's sportsmanship.
 » 20 months ago, # |   0 How long is contest?
•  » » 20 months ago, # ^ |   0 5 hours. I updated the text. Thanks!
 » 20 months ago, # |   +19 Semi-red guy here. Really hoping to participate in a Div.1 contest soon. Anyway have fun in the online mirror!
•  » » 20 months ago, # ^ |   -64 I am semi-purple.
 » 20 months ago, # |   +15 Is this contest intended for solo participation or team?
•  » » 20 months ago, # ^ |   +15 It is intended for solo.
•  » » 20 months ago, # ^ |   +10 "you should individually solve", so solo participation!
 » 20 months ago, # | ← Rev. 2 →   +5 If I win the contest take me to Kaimaru ( ͡° ͜ʖ ͡°)- semi-banana
•  » » 20 months ago, # ^ |   +11 Why Kaimaru, there are much better places
•  » » » 20 months ago, # ^ | ← Rev. 2 →   +18
 » 20 months ago, # |   +8 How do you define a "top scorer"? :P
 » 20 months ago, # |   +16 The contest starts in 24 hours — links to the contests were updated. http://codeforces.com/contests/101806
 » 20 months ago, # | ← Rev. 2 →   +10 From now on, you can register to the contest.
 » 20 months ago, # | ← Rev. 2 →   0 Will the problems be sorted by difficulty?
•  » » 20 months ago, # ^ |   0 Nope
 » 20 months ago, # |   0 The contest starts in 20 minutes!
 » 20 months ago, # | ← Rev. 2 →   0 Me after half of the contest attempting TPS: How to solve it. I figured out that we need to sort the balloon in increasing order of L + D, but can't come up with anything else beside O(N2) dp.
•  » » 20 months ago, # ^ |   +10 After sorting it by L[i] + D[i], maintain a max heap. If currentAltitude ≤ L[i] then we add it in the heap and increase the answer counter. Another case is that currentAltitude - maxElementInHeap ≤ L[i] and D[i] ≤ MaxElementInHeap, so it is cool to change the max element in heap with the current element. So O(NlogN).
•  » » 20 months ago, # ^ |   0 I thought uva 1153 is a well-known problem(?
 » 20 months ago, # |   +11 I am problemsetter of the problem Puyo Puyo.Actually I hoped at least one people could solve this.But there were no submissions and I feel a little bit strange now.
•  » » 20 months ago, # ^ |   0 Do people personally hate the game or something?? In fact, it was estimated to be the contest's 5th~6th easiest problem..
•  » » » 20 months ago, # ^ |   0 It remind me of the infamous problem L from ACM ICPC Vietnam National Round 2017. It is estimated to be the 3rd easiest problem, and not even a single submission was made during the official contest.
•  » » » » 20 months ago, # ^ | ← Rev. 2 →   0 Actually, it was 4th easiest problem for main contest, and 6th easiest problem for online mirror contest for Korean
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 IMO, for fun contest, I never read long/complicated-statement problem.
•  » » » 20 months ago, # ^ |   0 Oh I see..But, trust me and give it a shot! It's a fun little problem.
 » 20 months ago, # | ← Rev. 2 →   0 What was intended solution for R? I got TL on 16-th test. My complexity is n log (n+ maxf) log(max F). But with big constant :((Why all problems had big time limit, but for this was only 1 second? P.S. I got that almost all problems had TL 1 second.
•  » » 20 months ago, # ^ |   0 Indented solution was O(NlogN) managing half-line (ray) using BBSTEditorial will be uploaded soon (soon?)
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 I implemented a n log (n + maxf) log maxc solution and got AC.
•  » » 20 months ago, # ^ |   0 Author's solution was O(nlgn). I solved it in O(nlg2n) with Divide and conquer, and it's running time was not very different (1.5x from intended)We gave 4x time limit from official solution, but it is like 2.5x in CF :/
 » 20 months ago, # |   +26 Any prize for solving Y? :)
•  » » 20 months ago, # ^ |   0 In the on-site contest, we actually gave special prize to first-solver of Y. Maybe if you have chance to visit our campus someday ;)
•  » » 20 months ago, # ^ |   +3 If you want, I can send you a yut set. It is well made game with some luck and strategy.Actually, there is one more additional game rule not written in statement, such as player throws Yut alternatively but there is condition for throwing Yuts twice or more in a row.
 » 20 months ago, # | ← Rev. 2 →   +18 Thank you so much for participating! First solving U, First solving Y, or anything cool — let me know if you visit KAIST :)This is the Korean Open contest scoreboard. Actually the progress of Gym contest was totally out of our expectation :))) Our difficulty expectation : Z S Q <<<< V P T W X <<<< Y R UEditorial will be completed until tomorrow. You can watch me writing the editorial live.
•  » » 20 months ago, # ^ |   0 It show 404 to me.
•  » » » 20 months ago, # ^ |   0 My bad, it's fixed now!
•  » » 20 months ago, # ^ |   +5 Hope, you will add english translation.
 » 20 months ago, # |   0 How to solve X btw?
•  » » 20 months ago, # ^ |   +8 You should solve only when k = 5, all others are much simpler with the same idea.For k = 5, brute force the middle edge, then you just need to know the shortest distance from start to every vertex with 2 edges, and the same with destination. You need carefully check, that there is no repetetition. I stored three minimun for each distance and then calculate answer.O(n+m)P.S. if k > 5, there is no solution.
•  » » » 20 months ago, # ^ |   0 Thanks!
•  » » 20 months ago, # ^ |   +8 For n ≤ 5, exhaust every possible path. For k > m or k ≥ n, answer is -1.So now only k ≤ 5 left.For k = 1, just find if edge (1, n) exist.For k = 2, exhaust every node excluding 1 and n at the intermediate node.For k = 3, exhaust every edge as the intermediate edge.For k = 4, for every node v excluding 1 and n. We find the two smallest length for 1 -> x -> v. And two smallest length for n -> y -> v. Then exhaust every node v, if x ≠ y then we could update our answer. For k = 5, it is similar for k = 4 but this time we store three smallest length. It look like this, 1 -> x -> v -> u -> y -> n. So exhaust every edge (v, u). For those 3x3 possible path. update answer if x ≠ u and y ≠ v and x ≠ y.
•  » » » 20 months ago, # ^ |   0 Also thanks for the long explanation! :d (I actually needed only the part with saving 3 minimums as I didn't think of that but the comment might be helpful for someone else.)
•  » » » 20 months ago, # ^ |   +16 Exactly the model solution, but you don’t have to separate cases for k<5. You can just add 5-k edges of cost 0 from n to virtual destination. Then you only have to implement case k = 5.
 » 20 months ago, # |   0 How to solve Q (QueryreuQ)? I used hasing but wrong answer in test 48.
•  » » 20 months ago, # ^ |   +5 Any hashing that uses modulo 2^64 will fail in test 48. Hashing is hard to implement correctly, and if you implement correctly then it has very poor constant factor. I recommend you to use another approach.Easier solution is DP. Let DP[i][j] = (is substring [i, j] a palindrome?). The answer is the number of nonzero element in DP matrix. You can maintain DP table in O(Q) time for each query. We will soon describe this approach in editorial.Alternatively, you can use Manacher's algorithm for each string you've encountered.
•  » » » 20 months ago, # ^ |   0 I'm curious about test 32 of W. Winter Olympic Games, is it random? I'm asking because this solution 38614874 gets AC if we change M to 109 + 9 instead of 109 + 7.
•  » » » » 20 months ago, # ^ | ← Rev. 2 →   0 It is random. We didn't made tests that hack specific modulos (beside ones that are obviously wrong) I think it was really lucky that 109 + 9 passed.
•  » » » 20 months ago, # ^ |   +10 Manacher is not needed. I calculated in the way find the longest pallindrome with center in i. And after each step, increase asnwer for every position or decrease it in the stupid way. Complexity O(Q^2)
•  » » » » 20 months ago, # ^ |   0 Yes, this sounds like a more efficient way to implement my DP solution.
•  » » 20 months ago, # ^ |   0 People can't view your submission as this is a gym contest.
 » 20 months ago, # |   +34 Tests and Editorials are finally live!Tests, Model Solutions, Checkers (warning, over 400MB!)Editorial
 » 19 months ago, # |   0 Hi ko_osaga , For problem Q, I wrote a straight forward solution with hashing. complexity was O(N^2). I just brute force it. But unfortunately I got WA. Can you me help me out the reason. my submission: 39053588
•  » » 19 months ago, # ^ |   0 overflow hash is not a good idea usually as you can see here
•  » » 19 months ago, # ^ |   0 Data was generated using following code with Q=10,000 You can check hash collision about this string (check whether s[0:4096] and s[4096:8192] is same both hash and naive string comparison) string s = ""; for(int i=0; i
 » 8 months ago, # | ← Rev. 2 →   0 The editorial link no longer works. Any chance it can get updated?Edit: In case anyone ever needs it: Editorial
•  » » 8 months ago, # ^ |   +5 Sorry, now everything is here https://kaist.run/ko/contests/