CODE FESTIVAL 2017 Qualification Round B will be held on Sunday (time). The writers are maroonrk, snuke, and myself.
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.
C & D solutions, pleaseC: 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..1or1..101; if there are x 1-s in such a substring, it gives you x - 1 operations... linear DP over 0-sE 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)
Thank you. What was your way of thoughts, i.e. how did you develop C's solution from the beginning?
I wanted to find out when the graph can be a clique, noticed the bipartiteness preserving property and worked from there.
I think the editorial is pretty clear link
Got AC in D one minute before the end
D for me was much easier than C, i just made a stupid big.
E for me was much easier than D. Almost an hour spent on D, 20 minutes on E. FML
Everything was easier than D. Seriously.. I can't believe the scoreboard.
What's test #3 in problem D?
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.
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'].
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.)
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
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.
We ran the rating updater twice, it will be fixed soon.
And there I was happy with my +200. Oh well.
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
Is it n3 / (huge constant)? It's hard to imagine that 20003 modulo operations in long long works that fast.
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
Note that operations modulo constant are much faster (because they compile to some shifts and multiplications)
Congrats E869120, you lost my ranking from 1st to 159th (more than 150 times).
Is this a plug-in ?
This is beta atcoder. You can see your ranking here.
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.
Seems like it's impossible to judge. I want to cry TT
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.
Note that points are written according to that :D Whatever thanks for pointing out
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.
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.
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.
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.
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.
But there will be round 3, that's the problem.
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)