### dj3500's blog

By dj3500, history, 9 months 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 one, two and three 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 April the 13th, but the online mirror is scheduled on Sunday, 7th of July, 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 Doctor Who-themed. It features 5 series of 2-3 related tasks with increasing difficulty (easy/medium/hard). (For the online mirror, we will skip one series that had appeared in the onsite contest.) 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 bgamlath, DamianS, esrever, milenkoviclazar, Wajeb (who coordinated), and myself. Thanks also go out to people who helped with the statements and testing: anayMehrotra, Michalina Pacholska (who also draws the cows), _kun_ for the Russian statements, 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 nexthink. 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 <<<

Also:

Thanks to everyone who participated! We hope you have enjoyed the problems. The top three teams are:

1. 大象大象你的鼻子为什么那么长 (solved all 14 problems!): FizzyDavid, 300iq, TLE

2. zxtxdy (13 problems): cuizhuyefei, MarkF, zx2003

3. helveticow (12 problems): scott_wu, ksun48, ecnerwala

See you again next year!

• +399

 » 9 months ago, # |   +26 Thank you for your efforts guys :D
•  » » 9 months ago, # ^ | ← Rev. 2 →   -27 Nevermind :D
•  » » » 9 months ago, # ^ |   +27 No one says that's because of your profile picture, and I can't see evidence for any racism.I think the downvotes are because of the meaningless comment. Being grateful to problem setters is good, however, you can upvote the post, make meaningful comments (not the ones which can be used for every round), or simply participate in this round to show your thanks.
•  » » » » 9 months ago, # ^ | ← Rev. 4 →   +17 I talked about racism because there was a racism comment but it seems he deleted it ,I tried to reply at him or at anyone who has the same mindset.Also,I respect your point of view,but when the problem setter or anyone who did any kind of hard works will appreciate any feedback or grateful comment. And I agree With you at "make meaningful comments (not the ones which can be used for every round)" :D
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   0 I can see there are many comments downvoted without any critical thing. Also I know many people from various communities who use Codeforces alts to make significant amount of downvotes(or upvotes). I don't know why they are doing this but sometimes it makes me to feel toxic.
 » 9 months ago, # |   -10 there is no option showing for choosing the members of the team
 » 9 months ago, # |   -34 Handsome!
 » 9 months ago, # |   -10 ong time no see the contest that we can team.It's also a good time for Chinese CFer.Great!
•  » » 9 months ago, # ^ |   -15 Don't be so selfish. It's always good time for some users while bad for others.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   +3 Though I agree on the timing part, is celebrating a good rank on some contest also considered selfish even when someone else is bound to get worse rank?
•  » » » 9 months ago, # ^ |   -8 While I think it's good for all users to practice their team capabilities :)
 » 9 months ago, # |   0 How to form team?
•  » » 9 months ago, # ^ |   +8 Profile -> teams -> create a new team
 » 9 months ago, # |   0 I'm curious as to how the team ratings are calculated. Can somebody explain?
•  » » 9 months ago, # ^ |   +10 This contest is not rated. In general, there is some system actually, though I'm not sure whether it has been used recently.
•  » » » 9 months ago, # ^ |   +12 I know it's unrated. I was just curious about how the calculation is done. Surely, doesn't look like an average of ratings of all members. That's why I was wondering.
•  » » » » 9 months ago, # ^ |   +6
•  » » » » » 9 months ago, # ^ |   0 Ah, that explains it. Thanks!
 » 9 months ago, # |   +18 Can teams use multiple systems?
•  » » 9 months ago, # ^ |   +3 Yes.
 » 9 months ago, # | ← Rev. 2 →   -11 deleted
 » 9 months ago, # |   0 Why is the contest running but it says, "Standings are frozen."? Did something happen? I just solved D1 but it didn't show on the leader board, then I noticed the "Standings are frozen." phrase beneath "Contest is running."
•  » » 9 months ago, # ^ |   +16 That's something that's traditionally done in ACM ICPC type contests — the standings are frozen for the last hour of the contest.
•  » » » 9 months ago, # ^ |   0 Oh OK, thanks. I didn't know that.
 » 9 months ago, # |   +70
 » 9 months ago, # |   0 It's over. Thanks everyone! The editorial is up.
•  » » 9 months ago, # ^ |   +26 till when will standings be frozen ?
•  » » » 9 months ago, # ^ |   +12 Unfrozen now.
 » 9 months ago, # |   +42 We solved D2 using the idea from sunset's problem. After the contest he showed me the problem from which he get inspiration for his problem. Well, so it seems like a notorious coincidence
•  » » 9 months ago, # ^ |   0 Could you also link to sunset's problem?
•  » » » 9 months ago, # ^ |   +8
•  » » 9 months ago, # ^ | ← Rev. 4 →   +8 Could someone clarify the last paragraph of the editorial for D2?"We can represent x4,2 as a function of x5,2, x5,3 and x2,2 which is already a function of x4,2 and x4,3."So $x_{4,2}$ is a linear combination of $x_{5,2}, x_{5,3}$ and $x_{2,2}?$ Or a linear combination of $x_{5,2}, x_{5,3}, x_{2,2}, x_{4,2}, x_{4,3}?$ Either way, how does this help?"Continuing in this fashion"What fashion? I don't see how the previous two sentences display a pattern. Are we writing equations for all $x_{i,j}$ in increasing order of $i$ until we get until $i=m?$ If so, don't we need to run Gaussian Elimination every time we increase $i?$I tried reading some of the solutions, but I don't understand exactly what they're doing ...EDIT: Nvm, I solved it (see 56770140). It's essentially the same as 56662502.
 » 9 months ago, # |   +63 I believe that 300iq is a member of the Chinese national IOI team. (joking :)
 » 9 months ago, # | ← Rev. 2 →   0 Of course it will not be possible to hack, but perhaps you can give time =)(or you need to increase the time to 7 days)
 » 9 months ago, # |   0 Solved B2 — using flow algorithm.Read B3 — very straightforward SCC problem, coded, got AC. Opened editorial and it is flow problem ( I was very surprised here).I am only one who just coded SCC? P.S. I thought ( s * n * log b shouldn't pass in the first part of the solution) and wrote it in O(s * n + (s + b) * log(s + b) )
•  » » 9 months ago, # ^ |   +86 Woops, seems like it's not SCC problem. Sorry, Ildar :(Test: Spoiler2 0 3 2 2 1 1 1 10 2 1 1 0 2 1 1 0 1 1 0 2 1 7 2 1 3 1 
•  » » » 9 months ago, # ^ |   0 Sorry, I'm confused. Are you saying that the solution with SCC is wrong for this test case? Or could you explain what you mean by this test?
•  » » » » 9 months ago, # ^ |   +30 The solution of the_art_of_war is wrong for this test. He tried to solve this problem greedily without any flows and cuts but this solution is wrong and I just provided this case which breaks it.
•  » » » » » 9 months ago, # ^ |   0 Ohh, sure, now I see the problem. Thanks.
 » 9 months ago, # |   +8 I found the max-flow solution to B3 with LP and duals: Proof and intuition for B3The following linear program clearly gives the correct answer to the problem: Maximize $v_{1} x_{1} + \dots + v_{n} x_{n}$ $x_{i} - x_{j} \leq 0$ when $(i, j) \in E$ $0 \leq x_{i} \leq 1$ Where $x_{i}$ represents how much of every node we take. It is easy to prove that the objective function for an optimal solution doesn't decrease when we round down all $x_{i}$, so we don't need to specify all $x_{i}$ to be integers. Its dual is: Minimize $y_{1} + \dots + y_{n}$ $y_{i} + \sum_{e \in outs(i)} f_{e} \geq v_{i} + \sum_{e \in ins(i)} f_{e}$ for $i = 1, \dots, n$ $0 \leq f_{e}, a_{i}$ Where $ins(i)$ is the set of edges into $i$, and $outs(i)$ is the set of edges out of $i$.In order to not get annoyed by the sign of $v_{i}$, we'll consider equations of the form$y_{i} + a_{i} + \sum_{e \in outs(i)} f_{e} \geq b_{i} + \sum_{e \in ins(i)} f_{e}$instead, where $a_{i} = -v_{i}$ if $v_{i} < 0$ and $0$ otherwise, and $b_{i} = v_{i}$ if $v_{i} \geq 0$. From the dual we get the intuition for the max-flow: out-terms are on the left side and in-terms on the right side. Indeed, this LP can be solved with max-flow the same way as the problem was solved in the editorial: Add edge from source to node $i$ with capacity $b_{i}$, and edge from node $i$ to sink with capacity $a_{i}$. Add edge from node $i$ to node $j$ if we have edge $i, j$ in the original graph. Do max flow on the graph. Minimal value the dual objective function can take will be $\sum b_{i} - flow$. This seems pretty trivial, but I can't find a better proof than the following: proofTo prove this, we'll prove that any better solution to the LP produces a better solution to the max flow and the other way around.First we'll show that given a flow with size $flow$, we can achieve objective cost $\sum b_{i} - flow$ as claimed.To do this, select variables $f_{e}$ to be the same as in the flow, and let $0 \leq a^{'}_{i} \leq a_{i}$ be the flow from source to node $i$, and $0 \leq b^{'}_{i} \leq b_{i}$ be the flow from node $i$ to the sink. We have for all $i$:$a^{'}_{i} + \sum_{e \in outs(i)} f_{e} = b^{'}_{i} + \sum_{e \in ins_{i}} f_{e}$Therefore when we satisfy $y_{i} \geq max(0, (b_{i}-b^{'}_{i}) - (a_{i} - a^{'}_{i})) = b_{i}-b^{'}_{i}$ (since always either $a^{'}_{i} = a_{i}$ or $b^{'}_{i} = b_{i}$ or we could push more flow through), we satisfy$y_{i} + (a_{i} - a^{'}_{i}) + a^{'}_{i} + \sum_{e \in outs(i)} f_{e} \geq (b_{i} - b^{'}_{i}) + b^{'}_{i} + \sum_{e \in ins_{i}} f_{e}$Which is exactly the LP condition. This gives $\sum y_{i} \geq \sum b_{i}-b^{'}_{i} = \sum b_{i} - flow$ since $flow = \sum b^{'}_{i}$.Secondly we'll show that given a solution with cost $\sum b_{i} - flow$ to the LP, we can achieve a flow with size $flow$. To do this, build an alternative max flow graph that is otherwise the same, but we have an edge with capacity and flow $y_{i}$ from node $i$ to the source. Set the flow among actual edges to be the $f$-values, $b^{'}_{i} = b_{i}$ and $a^{'}_{i} = s_{i}$, where $s_{i}$ is the slack in the $i$'th equation ($s_{i} = (y_{i} + a_{i} + \sum_{e \in outs(i)} f_{e}) - (b_{i} + \sum_{e \in ins(i)} f_{e})$).This is a valid flow with size $flow$, since cutting over edges from the source we get $\sum b^{'}_{i} - y_{i} = \sum b_{i} - (\sum b_{i} - flow) = flow$.Lastly note that edges to the source never do anything in a maximum flow graph, so there exists a solution with the same amount of flow in the original max-flow graph.
•  » » 9 months ago, # ^ | ← Rev. 2 →   +7 B3 is obvious if you know Closure problem. They explicitly expose a clue by condition at the last of the statement.
 » 9 months ago, # | ← Rev. 2 →   +7 Hi there,Such a great tutorial but the explanation for the first problem says that: Alternatively, one can observe that if r is odd then there is no solution and if r is even then (x, y) = (1,(r−3)/2) always works (as long as y is positive)!But,If r is even then there is no solution and if r is odd then always the above-stated formula works.Thanks, Teja
•  » » 9 months ago, # ^ |   0 Thanks. These should have been swapped.
 » 9 months ago, # |   +1 Can Anyone share and explain there solution to A2 problem. Also if possible, share any resource to get acquainted with such types of problems.
 » 9 months ago, # |   0 Why is the alternative solution working for problem E1 ?
•  » » 9 months ago, # ^ |   0 Let X be the weight that this method yields. Think about what Kruskal's algorithm would do if the weight of this edge were set to less than X, and what it would to if it were set to more than X.
•  » » » 9 months ago, # ^ |   +1 So great explanation. Great way of teaching things.
 » 9 months ago, # | ← Rev. 2 →   0 Problem E2 was very similar to this
•  » » 9 months ago, # ^ |   +7 One of the open cup rounds this year had problem E3 exactly
 » 9 months ago, # |   +7 Next contest is 12 days from now ($\pi$-$\pi$) <- (sad face)
•  » » 9 months ago, # ^ |   +6 I'm really hungry for more contests T.T , I hope they will add more interesting contests :D
•  » » 9 months ago, # ^ |   +1 and why zero is sad face?
•  » » » 9 months ago, # ^ | ← Rev. 2 →   +14 Its not 0. Here $\pi$ is supposed to represent a crying eye and parentheses represent the face ($\pi$-$\pi$) Look carefully ...
 » 9 months ago, # | ← Rev. 2 →   0 In problem B2, I understood that one of the answer can be: (maximum_matching * k) ,but i am not getting why other answer is "**no of spaceships * h**",my thoughts about second answer:1. it should be (**maximum_matching * h**), but i know its wrong .2. it should be (maximum bases that are under threat of being attacked by any ship * h).I don't know if i explained it right, but if someone got what i am trying to say please tell what i am missing.Thank You
•  » » 9 months ago, # ^ |   0 The two alternatives are: You do nothing, as in you build zero dummy bases. In this case, it's clear why the answer is maximum matching * k You build enough dummy bases to guarantee that all ships that were attacking real bases will now attack dummy ones. In this case, it can be shown that you need to build s dummy bases. This is because unpaired ships will be paired initially with dummy bases, then the ones in the matching. Doing anything in between is guaranteed to be less optimal.
•  » » » 9 months ago, # ^ |   0 lets say if one of ship is having 0 fuel(i.e., not able to attack any base), than instead of taking s*h , we should take (s-1)*h as a second alternative.Thank you for replying. :)
•  » » » » 9 months ago, # ^ |   0 "With the Doctor's help, these bases would exist beyond space and time, so all spaceship can reach them and attack them."Fuel and attack don't matter for dummy bases :)
•  » » » » » 9 months ago, # ^ |   0 aawwww, how can i miss that, even after reading it many times :( .Thanks mate and sorry for me being noobiee.
 » 9 months ago, # |   -15 upvote for petr meme
 » 9 months ago, # |   0 I want to ask about problem C2 (Medium). Can anybody give reason why do we need rotating the plane by 45 degrees? Cannot we do the same algorithm using the original coordinates?
•  » » 9 months ago, # ^ |   0 It's easier to think about an axis-aligned square.
•  » » » 7 months ago, # ^ |   0 How do we get $(x, y) \rightarrow (x + y, x - y)$ and $2\cdot r$ as the side of square?
•  » » » » 7 months ago, # ^ |   0 I think I figured it out. Please let me know if I did anything wrong in my analysis.How do we get $(x - y, x + y)$ after rotation?We would like to rotate (integer-based) point $(x, y)$ by $45^{\circ}$. In general to rotate any point by degree $\phi$, we use the following transformation: $\begin{pmatrix} \cos\phi & -\sin\phi \\ \sin\phi & \cos\phi \end{pmatrix} \cdot \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} x' \\ y' \end{pmatrix}$where $x'$ and $y'$ are new points after rotation. Here, $\phi = \frac{\pi}{4}$. Then, we get $\begin{pmatrix} \frac{\sqrt{2}}{2} & -\frac{\sqrt{2}}{2} \\ \frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} \end{pmatrix} \cdot \begin{pmatrix} x \\ y \end{pmatrix} = \frac{\sqrt{2}}{2} \begin{pmatrix} x - y \\ x + y \end{pmatrix}$Since we need to work with integer-based coordinates, we scale the points by a factor of $\sqrt{2}$, then we get $(x - y, x + y)$.What is the side of square after rotation?Before the rotation, the diameter of square is $2 \cdot r$ because a point $(x, y)$ is assumed to be the lower corner the square. We consider such assumption as it helps cover all cases in our sweep line + segment tree solution. Therefore, the side of square should be $\frac{2}{\sqrt{2}} \cdot r$. Note that after rotation, we scale all points with a factor of $\sqrt{2}$. Therefore, the side of square will be $\sqrt{2} \cdot \frac{2}{\sqrt{2}} \cdot r = 2 \cdot r$ after $45^{\circ}$ rotation.