### dj3500's blog

By dj3500, 3 years ago,

UPDATE: the editorial is here

Hello CodeForces! This year again, I'd like to invite you to the online mirror of an open championship of Switzerland called HC2 (the Helvetic Coding Contest). A mirror was also held last year and two years ago.

The Helvetic Coding Contest is a yearly contest held at the EPFL in Lausanne by the PolyProg association. The contest itself took place on March the 17th, but the online mirror is scheduled on Saturday, 14th of April, 10:05 Moscow time. The duration is 4:30.

Rules:

• you can participate in teams or individually (1-3 people),

• standard ACM-ICPC rules (no hacking),

• the contest is not rated,

• if you have participated in the onsite contest, please do not participate in the mirror.

The contest this year is Star Wars-themed. It features 6 series of 2-3 related tasks with increasing difficulty (easy/medium/hard). Sometimes it may be the case that a solution for the hard version solves all of them, but usually not. We think that the problemset is diverse and interesting, and while the contest is ACM-style, you will find that some problems are not so standard. Most easy&medium problems are even solvable in Python, so you can also recommend this contest to your newbie friends :) We promise to post a nice editorial as soon as the contest ends.

Acknowledgments: the problems were set by maksay, boba5551, mukel, DamianS, esrever, and myself. Thanks also go out to people who helped with the statements and testing: bgamlath, Michalina Pacholska (who also draws the cows), and KAN for CodeForces coordination, as well as everyone involved in the actual onsite contest, who are too many to name here. We also thank the sponsors Open Systems and AdNovum. Lastly, thanks to MikeMirzayanov for CodeForces and Polygon (which was used to prepare the problems).

Finally, in a bit of autopromotion, note that you can use Hightail to automatically test your solutions :) Good luck!

After-contest UPDATE:

## >>> Editorial <<<

Feel free to ask questions in this topic.

Thanks to everyone who participated! We hope you have enjoyed the problems despite the interruption in judging. The top 4 teams, who have solved all problems, are:

1. SpicyFriedTomatoes: AbstractKangaroo, Retired_MiFaFaOvO

2. (｀・ω・´): King_George, ohweonfire, FizzyDavid

3. ymd队长ioi捧杯超稳: sunset, TLE, yanQval

4. ★SweeT DiscoverY★: dotorya, molamola., zigui

See you again next year!

• +240

 » 3 years ago, # |   +27 hoping for short prob statements unlike previous year
 » 3 years ago, # |   0 what happens when onsite participator sees the problem with the help of other user ID.
•  » » 3 years ago, # ^ |   0 That's why it's unrated
•  » » » 3 years ago, # ^ |   0 I think it's unrated because ACM style is always unrated instead. We do have contests that's rated that are later than their onsite contest.
•  » » 3 years ago, # ^ |   0 I think u misread the dates .It's 17th of March (Not April).
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +1 Yes you are right. Sorry for this issue. It's my mistake. Thanks.
 » 3 years ago, # |   +67 OH GOD, THIS PHOTO IS SO HOT
•  » » 3 years ago, # ^ | ← Rev. 2 →   +118
 » 3 years ago, # |   -62 is it rated?
•  » » 3 years ago, # ^ |   +7 Why not :D
 » 3 years ago, # | ← Rev. 2 →   +61 How to register as a team member...I can't see it...UPD: Fixed now, and wish everyone will enjoy the contest, GL & HF.
•  » » 3 years ago, # ^ |   +9 Thanks for noticing. It will be fixed as soon as possible.
•  » » » 3 years ago, # ^ |   +11 And 3 hours later it hasn't be fixed still.Please be quick about it qwq
•  » » » 3 years ago, # ^ |   0 It's fixed now.
•  » » » » 3 years ago, # ^ |   0 Thx a lot :)
 » 3 years ago, # |   +3 there is no team option in the register form .
 » 3 years ago, # |   +14 Why...the "register as team member" button doesn't show up.. Is that a BUG?
 » 3 years ago, # | ← Rev. 3 →   -10 great
 » 3 years ago, # |   +12 Why am I not able to register as a team?
•  » » 3 years ago, # ^ | ← Rev. 2 →   -8 It's now fixed!
•  » » 3 years ago, # ^ |   +4 If you want to participate in Helvetic Coding Contest 2018 in a team, but have already registered personally, just delete your personal registration on the page with a list of all registrations and register again.
 » 3 years ago, # |   +1 I have a question. Why I can register as a team member?
»
3 years ago, # |
-23

# Is It Rated?

•  » » 3 years ago, # ^ | ← Rev. 3 →   0 Look this "Helvetic Coding Contest 2018 online mirror (teams allowed, unrated)".
•  » » 3 years ago, # ^ |   -14 yes
 » 3 years ago, # |   -20 Is it semirated?
•  » » 3 years ago, # ^ |   0 Is it ln(2)-rated?
•  » » » 3 years ago, # ^ |   -13 is it -1-rated?
•  » » » » 3 years ago, # ^ |   -6 Is it overrated?
•  » » » » » 3 years ago, # ^ |   +3 FFS
 » 3 years ago, # | ← Rev. 3 →   0 ??????????????????happy
 » 3 years ago, # |   +3 I'm looking for a team to participate in the contest. Please PM me in case you want to solve it together :)
 » 3 years ago, # | ← Rev. 2 →   +4 Can we register from two different teams ?
 » 3 years ago, # |   0 Someone want to take me on their team, or form a team?
 » 3 years ago, # |   +3 Servers are down :(5 queue pages
•  » » 3 years ago, # ^ |   +3 Will the contest be extended in that case?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 I don't think so because it's unrated.UPD : They extended for 30 min
 » 3 years ago, # | ← Rev. 2 →   +117
 » 3 years ago, # |   +21 Is scoreboard frozen??
•  » » 3 years ago, # ^ |   -20 Yes!!
 » 3 years ago, # |   0 contest extended by half an hour
 » 3 years ago, # |   +39 We apologize for the technical problems with CodeForces. The queue is now moving again. The contest is extended by 30 minutes. It will remain unrated ;)
 » 3 years ago, # | ← Rev. 2 →   +16 The editorial is up: editorial
 » 3 years ago, # |   +34 We delayed the start of ARC/ABC by 10 minutes due to the extension of a contest in Codeforces. https://beta.atcoder.jp/post/220
 » 3 years ago, # |   +3 I don't how to prove the correctness of the solution in the problem B2. Can you guys help me?
•  » » 3 years ago, # ^ |   +5 I didn't prove it during the contest, but here's a stab at it. Let g1, g2, g3, ..., gK be the vertices the prescribed solution adds, in order. Suppose you have a solution S which is better than the prescribed solution. Let p be the smallest integer for which gp is not included in S. Let the "cover" of S be all planets controlled by the rebels in solution S. Since gp is a leaf, it is not part of the cover of S. Let A be the nearest node in the cover of S to gp. If we rebuild S on vertex at a time, starting with g1, ..., gp - 1, then there is some first vertex B which when added to S causes A to become covered. Because of how gp was chosen, it must be at least as deep in the tree as B. Thus, we can remove B from S replace it with gp, without decreasing the score: we will gain all the planets on the path from A to gp, and at worst lose all the planets on the path from A to B.
•  » » » 3 years ago, # ^ |   0 Wow! Thank you very much. I really do learn something today!
•  » » » 8 months ago, # ^ |   0 Wow, this is proof is so wrong that I don't even know where to start.If we rebuild S on vertex at a time, starting with g1, ..., gp - 1, then there is some first vertex B which when added to S causes A to become coveredSo you propose to remove $B$? If $B$ is among $g_1, g_2, g_3... g_{p-1}$, then does that not make your hypothesis invalid? And there is no reason why $B$ should be the $p^{th}$ element of $S$.And even if we overlook this glaring error, you just show that if $g_p$ is the first such element, the score does not decrease. But it changes the graph completely. So it may happen that, in the long term, the set $S$ overcomes our proposed optimal algorithm.
•  » » » » 8 months ago, # ^ |   0 By the way, I have a correct proof: it's main argument is cases on LCA of chosen points and infinite descent. So cool!
 » 3 years ago, # | ← Rev. 2 →   0 [del]
•  » » 3 years ago, # ^ |   +18 It does not say "1 <= ki <= n".
•  » » » 3 years ago, # ^ |   0 rly...
•  » » 3 years ago, # ^ |   +9 I made exactly the same mistake and wasted 40 minutes on it...
 » 3 years ago, # |   0 is there any O(Nk) solution of problem c2?
 » 3 years ago, # |   +21 Great problemset today (especially B2, C3 and E2). Feel a bit sad for not figuring out B2 though...
 » 3 years ago, # | ← Rev. 2 →   -8 Any1 plzz explain B2 (medium)..in simple way..??i read editorial but didn't getand recommend me similar type of problem :)
 » 3 years ago, # |   +20 I solved E3 with O(N2), not O(N2logN). Spoiler First, We sort all points. We look the leftmost point and rightmost point If two points have same type, we scan points from left to right, and we divide problem(this technichq is same with editorial) If two points have diff type, we make upper_convex(because we sorted at first, this complexity isn't O(NlogN), but O(N)), and scan convex and get adjacent (spaceship-base) pair or (base-spaceship) pair, we can use this pair.
•  » » 3 years ago, # ^ |   0 Our solution during on-site participation when we had little time left was to pick a random point of each type and check whether they line through them has an equal number of points of each type to the left of it. Repeat this until we finde a suitable line, then solve the subproblems recusively.Is there an easy way of analysing the runtime?
•  » » 3 years ago, # ^ |   +2 Just did the virtual contest today, so I'm 4 weeks late to the party. Nonetheless I just wanted to get this out since I thought it was an interesting approach to an interesting question.I claim that it's possible to find a dividing line that separates roughly into halves such that each half has equal spaceships and bases.I'm not exactly sure how to prove it formally, so I will talk through it for even N and hope that the proof is largely correct.Consider defining a half-plane by an angle theta from 0 to 2pi -- the dividing line is determined by the angle and theta and theta + pi are complementary half-planes. Moreover, we may shift the position of the dividing line so that N/2 points are on each side of the half plane.Let f(theta) denote the number of bases contained in the half plane minus N/2. For general theta (theta such that no 2 points are parallel to the line), f is well defined and f(theta) + f(theta + pi) = 0, since the half-planes are complementary.Note that f(theta) is "continuous" with respect to theta -- perturbing it slightly will include 1 more point and exclude 1 more point. Thus f will change no more than 1 at a time.Thus, by "Intermediate Value Theorem", we have a point in which f(theta) = 0, which is the dividing line we sought.To find this theta, we may binary search on theta by "Intermediate Value Theorem", starting from [0, pi] for example.If we believe that our binary search will terminate in X steps, then this gives each dividing step a time complexity of O(NX), for a total time complexity of O(NX lg N).(For this question X is not too large because the smallest gradient difference we can get is about 1/250^2. And by symmetry, a smallest possible angle between 2 lines lies between 0 and pi/4, so we can bound the smallest possible angle between 2 lines accordingly.)
•  » » » 3 years ago, # ^ |   +5 Actually, there always is a line that separates both the spaceships and the bases into half (Proof: Consider the dual space, then the median-level of the bases and the median-level of the spaceships intersect an odd number of times. The primal of the intersection point gives us the line we're looking for.) Such a line is called a Ham-Sandwich Cut. It can be found in linear time, but the algorithms for it have quite large constants AFAIK. This would lead to an solution, but nobody would want to code something like that.
•  » » » » 3 years ago, # ^ |   0 Very interesting. Thanks for the reference.
 » 3 years ago, # |   +5 I had a different solution to C2 and C3, running in . SpoilerLet f(i, j) be the length of the smallest prefix which can be divided into i pieces with a total score of exactly j (or ∞ if there is no such prefix). The maximum possible score is k(p-1), so there are only O(k^2p) values to compute.To compute f(i, j), consider all p possible scores for the last segment. Let this score be s. Then we can divide a solution into two parts: [0, a), where a ≥ f(i - 1, j - s) and ; and [a, b), where b > a and . Note that the final condition does not depend on a, so we may as well choose b = f(i — 1, j — s). Then we just need to find the smallest b greater than a with a given prefix sum (modulo p). For each remainder mod p we can precompute a list of all the prefix sums that have that remainder, and then binary search it in the inner loop.Thus, each of the O(k2p) DP states can be found in O(p) binary searches, for a runtime of .
 » 3 years ago, # | ← Rev. 2 →   0 (Edit: fixed the formula)How did people deal with overflow in F3? When multiplying two polynomials, the coefficients can be up to about 10082 * 105, which means you need to use a prime bigger than 232 in the number theoretic transform, which in turn means you have intermediate values bigger than 264 — and annoyingly Codeforces still uses 32-bit C++ compilers so no __int128.I tried to get around it by using the convolution with two different primes and then using the CRT to reconstruct the value, but it was too slow. That could just be my FFT implementation, which I've often had time out on other problems.
•  » » 3 years ago, # ^ |   0 Your formula doesn't display, so not sure what it says, but the modulo was only 1009, so at least standard FFT works well enough, with a maximum of like 200000 * 1009 * 1009.
•  » » » 3 years ago, # ^ |   0 I've fixed the formula. How do you determine the accuracy of standard FFT?
•  » » » 3 years ago, # ^ |   0 I managed to get a solution accepted using double-precision FFT, but only after I changed the range from [0, 1009) to [-504, 504] to reduce the size of the numbers. Without that I had WA (and long double got TLE).
•  » » » » 3 years ago, # ^ |   0 Hmm, I myself don't understand the numerical stability of FFT too well. Experimentaly, all implementations that we had could handle 1009. With the neat trick you're describing, they could even handle 100009 AFAIR.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +10 Actually I think that's a different trick. What we do to handle 100009 is to randomly set each number to either x or x-100009. Then it's in [-100009,100009], and half of the multiplied coefficients become negative, so that it cancels out to a way smaller number (around sqrt(n) times smaller, I guess).
•  » » 3 years ago, # ^ |   0 I just multiplied using double FFT and added the result by 0.5 before rounding down. (Also, I used the trick to multiply using 2 calls to FFT instead of 3 making P[j] = A[j] + i * B[j] but that shouldn't matter). AFAIK, double works for things of value sqrt(10^9 + 7) because there's the trick of dividing a number v into v / B and v % B where B is around sqrt and using 4 multiplications to get the answer any modulo.This also might help with precision http://codeforces.com/blog/entry/48465?#comment-325890 and the last problem here http://petr-mitrichev.blogspot.com/2015/04/this-week-in-competitive-programming.html is where I learned about this trick.
•  » » » 3 years ago, # ^ |   0 Yes, my precision problems are most likely from calculating powers of the primitive root incrementally.Unfortunately Petr's blog only links to a comment in Russian, so I don't follow how the v/B and v%B trick works.
•  » » » » 3 years ago, # ^ |   0 Divide the coefficients A[i] into 2 polynomials. A0[i] = A[i] % sq, A1[i] = A[i] / sq, so A[i] = A0[i] + A1[i] * sq. Do the same thing for the polynomial B. The answer isC = A * B = A0 * B0 + sq * (A1 * B0 + A0 * B1) + sq * sq * (A1 * B1)It works kinda like writing the numbers in base sqrt(mod)
•  » » » » » 3 years ago, # ^ |   0 Thanks, I follow. It does mean 4x as many FFTs though, which for my implementation would definitely push it over the time limit. Even my attempt at using two different primes plus the CRT only required 2x as many FFTs and that was too slow.
•  » » » » » » 3 years ago, # ^ |   0 The FFT code here (method DOIT) is amazingly accurate (written by ko_osaga) http://codeforces.com/contest/958/submission/37318120
•  » » » » » 3 years ago, # ^ |   0 Actually, there's only need for 3x FFTs. One only needs to calculate A0*B0 , A1*B1 and (A0+A1)*(B0+B1) to get the answer. Also, more research about precision problems in FFT can be found in a research paper by matthew99 in Chinese.
 » 3 years ago, # |   0 Is there a faster algorithm than O(K2) for E2?
•  » » 3 years ago, # ^ |   +5 search up APIO 2007 Backup for O(nlogn)
•  » » 3 years ago, # ^ |   0 There is a solution with lambda optimization.
•  » » » 3 years ago, # ^ |   0 Do you know any tutorial about this technique? This is the first time I have heard about it.
•  » » » » 3 years ago, # ^ |   0 I think he means to refer to the IOI 2016 Aliens trick, you can read about it here: blog My submission 37355142 uses it for O(N·log(max)) complexity.
•  » » » » 3 years ago, # ^ |   +8 Another name is Lagrangean relaxation (if I understand correctly what you're referring to).
•  » » » » 3 years ago, # ^ |   +3 Let sort the given array and calculate differences between adjacent elements. Now we need to select k elements in array of differences, such that any two of them are not adjacent, and minimize their sum.Let ignore the condition about k elements and maximize value of (sum — lambda * cnt), where cnt — number of chosen element ans lamda — some number. It can be done with O(n) complexity. It will be the best answer for cnt elements. The more lambda, the more cnt. We can make a binsearch and find such lambda when cnt = k. Answer to this lambda is answer to the task.
•  » » » » » 3 years ago, # ^ |   0 What about the proof that the function is concave?
 » 8 months ago, # |   0 Shame on the editorialist for problem B2. The proof is soooooooooooo hard. And all he writes is "exercise for the reader" and just describes the implementation. Yuck.