When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

ko_osaga's blog

By ko_osaga, history, 6 years ago, In English

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!

  1. sunset
  2. Reyna
  3. Bedge
  4. gamegame
  5. the_art_of_war

Local open contest scoreboard

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

Editorial

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!

  • Vote: I like it
  • +152
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

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.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +51 Vote: I do not like it

      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.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How long is contest?

»
6 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Is this contest intended for solo participation or team?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    It is intended for solo.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    "you should individually solve", so solo participation!

»
6 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

The contest starts in 24 hours — links to the contests were updated.

http://codeforces.com/contests/101806

»
6 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

From now on, you can register to the contest.

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Will the problems be sorted by difficulty?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The contest starts in 20 minutes!

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 beside O(N2) dp.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought uva 1153 is a well-known problem(?

»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh I see..

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

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Indented solution was O(NlogN) managing half-line (ray) using BBST

    Editorial will be uploaded soon (soon?)

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :/

»
6 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Any prize for solving Y? :)

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

»
6 years ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

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.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve X btw?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      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.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

My Submission.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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)

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +34 Vote: I do not like it
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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<Q; ++i)
    {
    	int r = (__builtin_popcount(i) % 2) * 16;
    	char c = 'a' + r;
    	s += c;
    }
    cout << Q << endl << s << endl;
    
»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

The editorial link no longer works. Any chance it can get updated?

Edit: In case anyone ever needs it: Editorial