rng_58's blog

CODE FESTIVAL 2017 Qualification Round B
By rng_58, history, 7 years ago, In English

CODE FESTIVAL 2017 Qualification Round B will be held on Sunday (time). The writers are maroonrk, snuke, and myself.

Contest Link

Contest Announcement

This is one of the three qualification rounds of CODE FESTIVAL. In total, 20 foreign students will qualify in three rounds (Check the official site for detailed rules). If you are eligible for the onsite contest, please don't forget to fill the form at https://krs.bz/rhd-itm/m/codefes2017_en. Please check the detail of the tournament at http://codeforces.me/blog/entry/53502.

The contest duration is 2 hours, and there will be 6 problems. The first 4 problems are mainly used for choosing domestic students and much easier than other tournament competitions. However, we added two more problems and we hope these are interesting and challenging enough for choosing 20 qualifiers. Note that there is no time penalty for incorrect submissions. The time penalty is MAX, not SUM.

The point values are 100 — 200 (100) — 500 — 700 — 1600 — 1600. If you are unfamiliar with AtCoder System, 2X-point problem in AtCoder is as hard as TopCoder's d1 X-point problem.

Let's discuss problems after the contest.

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

»
7 years ago, # |
  Vote: I like it -7 Vote: I do not like it

C & D solutions, please

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    C: if a connected component is bipartite, you can only add edges between its two parts and make it a biclique; otherwise, you can make it a clique

    D: you're looking for disjoint substrings of the form 101..1 or 1..101; if there are x 1-s in such a substring, it gives you x - 1 operations... linear DP over 0-s

    E for completeness: when you take the first R, you can choose s optimally so you can take whatever you want in the next B - 1 operations; after those operations, if there's B - y > 0 R-s left and you take one, you can choose t optimally so you can take whatever in the next B - y - 1 operations; try all possible y-s, then you need all possible to distribute k A-s before these subsequences of lengths B and B - y, and that gives you all possibilities for how many (z) R-s you can have in the subsequence of length B - y; the answer for given y, k, z is C(B - 1, y - 1)(k + 1)C(B - y - 1, z - 1)

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

      Thank you. What was your way of thoughts, i.e. how did you develop C's solution from the beginning?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        I wanted to find out when the graph can be a clique, noticed the bipartiteness preserving property and worked from there.

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

    I think the editorial is pretty clear link

    → Reply
»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Got AC in D one minute before the end

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

D for me was much easier than C, i just made a stupid big.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    E for me was much easier than D. Almost an hour spent on D, 20 minutes on E. FML

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

    Everything was easier than D. Seriously.. I can't believe the scoreboard.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's test #3 in problem D?

→ Reply
»
7 years ago, # |
  Vote: I like it +40 Vote: I do not like it

Actually problem F could be solved by simple greedy.

Add X strings "a", Y strings "b" and Z strings "c" to multiset. While there are more than one element in set, took smallest one and biggest one, and put their concatenation back to set.

When we have only one element in set, it is the answer.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +20 Vote: I do not like it

    Another similar solution:

    Let f(x,y,z) be the answer to the question with x As, y Bs, z Cs.

    Then if x >= z > 0, f(x,y,z) is made by taking f(x,y,z-x) with ['a','b','c'] replaced by ['ac','b','c'].

    If z > x > 0, f(x,y,z) is made by taking f(x-z,z,y) with ['a','b','c'] replaced by ['a','ac','b'].

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Do you know the proof of this solution?

    (By stress-testing it seems correct, but I don't have a proof. My intended solution is O(N5) described in the editorial.)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 4   Vote: I like it +18 Vote: I do not like it

      I believe i've got a provable O(N^2) from which you can prove the multiset solution.

      Solution here

      I have tried to add as many comments as I can.

      UPD. One thing, that I didn't proved in comments.

      While we understand, that the longest substring of consecutive A's in optimal answer will be is , it is not obvious, that there are only parts only of num and num - 1 length (Since there are b + c symbols of "b" and "c" we can consider parts of consecutive A's between them, sometimes part can be empty, like in aabc we will have "aa" and "" part).

      For example division (num) + (num - 1) + (num - 1) may potentially be worse, than (num) + (num) + (num - 2).

      Suppose in optimal answer there is a group of A's of length  ≤ num - 2, surounded by other symbols.

      It will be simpler to explain on example:

      let num = 4 and suppose answer looks like "aaaabaaaabaaabaabaaab" (it is not important what separates groups of A's "b" or "c", so i've written only "b").

      We want to tell that "aa" is bad.

      We know, that there is at least one group with length of num (and actually there are at least 2, because otherways num will be less), let's select the closest to the left from the bad group. Take one "a" symbol from there and move to the bad group.

      aaaabaaa[a]baaabaa[]baaab -> aaaabaaa[]baaabaa[a]baaab

      The minimal cyclical shift in original answer must start with num A's, but after our transfer all such cyclical shifts have become larger and since bad group was  ≤ num - 2 it doesn't make possible to start minimal cyclical shift there even after a move, hence contradiction, answer wasn't optimal

      → Reply
»
7 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

It seems everyone's rating volatility is approximately doubled. (For evidence, (my rating — my perf) is about 130, but rating is decreased by 26, and also, KAN's rating decreased by 257)
Is it a bug, or a special rule in Code Festival Qualification B?
UPD: Fixed.

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

    We ran the rating updater twice, it will be fixed soon.

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

      And there I was happy with my +200. Oh well.

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My AC solution (during the contest) in E works in O(n^3) and after the contest I had a solution which is still O(n^3) but works a bit less then 1s, so it was probably worth making constraints bigger

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

    Is it n3 / (huge constant)? It's hard to imagine that 20003 modulo operations in long long works that fast.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      the first solution seems to be (it enters the most internal cycle 1333333000 times on test a=b=2000).

      It also uses optimisation: it uses modulo operation not after every iteration of form a += b * c but once in 16 iterations.

      The second one (which works in 1s) is

      UPD: updated constants in denominators

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

      Note that operations modulo constant are much faster (because they compile to some shifts and multiplications)

      → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -30 Vote: I do not like it

Congrats E869120, you lost my ranking from 1st to 159th (more than 150 times).

→ Reply
»
7 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Poor ko_osaga, who had to judge between Taiwan ICPC Regional (24-25) and Code Festival 2017 (25-26), made this scoreboard to check whether I'm eligible or not.

(Please correct me for any mistakes or informations.)

Seems like it's impossible to judge. I want to cry TT

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

    Some of the ranks are wrong, as you're supposed to ignore all Japanese participants when computing rank in a round. For example I got 8th and you got 9th today.

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

      Note that points are written according to that :D Whatever thanks for pointing out

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

    Do you have a special motivation for Taiwan regional?

    As far as I remember, there are several regional contests in our subregion, and you can choose only two.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +10 Vote: I do not like it
      • We have final exam in Dec 11 ~ Dec 15, so we can't afford many of them (Ho Chi Minh, Yangon, Manila).
      • Jakarta clashes with Daejeon.
      • We wanted to take a day off after final exam, so no Tsukuba. And registration is over now.

      So we have very limited choice (only two), and I wanted to avoid Seoul NU gold medalist team making schedules in end of the year. That's why I thought Hua Lien will be best.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +34 Vote: I do not like it

        If you want to attend Taiwan regional, please prepare codebook for "Weighted Perfect Matching in General Graphs" and "Maximal Clique". Taiwan regional is really really suck.

        → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Maybe you should try to ask if people above you are going to go to Japan. For now it seems highly unlikely for you to advance if all of them are going to participate.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      In case I read the rules right and we assume there's no round 3 (to avoid guessing), he already advanced. 20 international people advance: 10 based on best from regions, then 10 best remaining.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        But there will be round 3, that's the problem.

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

      Thanks for the advice. My guess is :

      Regarding this, I become 5th place. So it seems kinda safe? (I don't know, hope they get the notification and confirm this)

      → Reply