Блог пользователя ko_osaga

Автор ko_osaga, история, 6 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +152
  • Проголосовать: не нравится

»
6 лет назад, # |
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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How long is contest?

»
6 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Is this contest intended for solo participation or team?

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

http://codeforces.com/contests/101806

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

From now on, you can register to the contest.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Will the problems be sorted by difficulty?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The contest starts in 20 minutes!

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +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).

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 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.

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    Editorial will be uploaded soon (soon?)

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 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 :/

»
6 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

Any prize for solving Y? :)

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 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 ;)

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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.

»
6 лет назад, # |
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 U

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve X btw?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 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.)

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

My Submission.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 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.

      • »
        »
        »
        »
        6 лет назад, # ^ |
        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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +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)

»
6 лет назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится
»
6 лет назад, # |
  Проголосовать: нравится 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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 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<Q; ++i)
    {
    	int r = (__builtin_popcount(i) % 2) * 16;
    	char c = 'a' + r;
    	s += c;
    }
    cout << Q << endl << s << endl;
    
»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

Edit: In case anyone ever needs it: Editorial