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 ko_osaga, Konijntje, alex9801, etaehyun4, platinant. alex9801's rating is 2399, so he hopes to be called as "semi-red", not orange.

Special thanks to Konijntje, 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!

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

Problemsetters :

- Konijntje : 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!

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.

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.

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.

How long is contest?

5 hours.

I updated the text. Thanks!

Semi-red guy here. Really hoping to participate in a Div.1 contest soon. Anyway have fun in the online mirror!

I am semi-purple.

Is this contest intended for solo participation or team?

It is intended for solo.

"you should individually solve", so solo participation!

If I win the contest take me to Kaimaru ( ͡° ͜ʖ ͡°)

- semi-banana

Why Kaimaru, there are much better places

How do you define a "top scorer"? :P

The contest starts in 24 hours— links to the contests were updated.http://codeforces.com/contests/101806

From now on, you can register to the contest.

Will the problems be sorted by difficulty?

Nope

The contest starts in 20 minutes!Me after half of the contest attempting T

PS: 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 besideO(N^{2}) dp.After sorting it by

L[i] +D[i], maintain a max heap. IfcurrentAltitude≤L[i] then we add it in the heap and increase the answer counter. Another case is thatcurrentAltitude-maxElementInHeap≤L[i] andD[i] ≤MaxElementInHeap, so it is cool to change the max element in heap with the current element. SoO(NlogN).I thought uva 1153 is a well-known problem(?

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.

Do people personally hate the game or something?? In fact, it was estimated to be the contest's 5th~6th easiest problem..

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.

Actually, it was 4th easiest problem for main contest, and 6th easiest problem for online mirror contest for Korean

IMO, for fun contest, I never read long/complicated-statement problem.

Oh I see..

But, trust me and give it a shot! It's a fun little problem.

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.

Indented solution was

O(NlogN) managing half-line (ray) using BBSTEditorial will be uploaded soon (soon?)

I implemented a n log (n + maxf) log maxc solution and got AC.

Author's solution was

O(nlgn). I solved it inO(nlg^{2n}) 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 :/

Any prize for solving Y? :)

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 ;)

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.

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 U`

Editorial will be completed until tomorrow. You can watch me writing the editorial live.

It show 404 to me.

My bad, it's fixed now!

Hope, you will add english translation.

How to solve X btw?

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.

Thanks!

For

n≤ 5, exhaust every possible path. Fork>mork≥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 andnat the intermediate node.For

k= 3, exhaust every edge as the intermediate edge.For

k= 4, for every nodevexcluding 1 andn. We find the two smallest length for 1 ->x->v. And two smallest length forn->y->v. Then exhaust every nodev, ifx≠ythen we could update our answer.For

k= 5, it is similar fork= 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 ifx≠uandy≠vandx≠y.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.)

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.

How to solve Q (QueryreuQ)? I used hasing but wrong answer in test 48.

My Submission.

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.

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 changeMto 10^{9}+ 9 instead of 10^{9}+ 7.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 10

^{9}+ 9 passed.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)

Yes, this sounds like a more efficient way to implement my DP solution.

Tests and Editorials are finally live!

Tests, Model Solutions, Checkers (warning, over 400MB!)

Editorial

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

overflow hash is not a good idea usually as you can see here

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)The editorial link no longer works. Any chance it can get updated?

Edit: In case anyone ever needs it: Editorial

Sorry, now everything is here https://kaist.run/ko/contests/

In Porblem Y, the sample input in English pdf and in Korean pdf is different. It seems to me that the correct one is the Korean version