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), cdkrot 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:
two extra problems from the onsite contest that were left out for the online mirror are available in the Gym
the new uphacking feature is available for all problems except A3 and C3
Thanks to everyone who participated! We hope you have enjoyed the problems. The top three teams are:
大象大象你的鼻子为什么那么长 (solved all 14 problems!): FizzyDavid, 300iq, TLE
zxtxdy (13 problems): cuizhuyefei, MarkF, zx2003
See you again next year!
Thank you for your efforts guys :D
Nevermind :D
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.
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
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.
there is no option showing for choosing the members of the team
Handsome!
ong time no see the contest that we can team.It's also a good time for Chinese CFer.
Great!
Don't be so selfish. It's always good time for some users while bad for others.
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?
While I think it's good for all users to practice their team capabilities :)
How to form team?
Profile -> teams -> create a new team
I'm curious as to how the team ratings are calculated. Can somebody explain?
This contest is not rated. In general, there is some system actually, though I'm not sure whether it has been used recently.
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.
See here
Ah, that explains it. Thanks!
Can teams use multiple systems?
Yes.
deleted
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."
That's something that's traditionally done in ACM ICPC type contests — the standings are frozen for the last hour of the contest.
Oh OK, thanks. I didn't know that.
It's over. Thanks everyone! The editorial is up.
till when will standings be frozen ?
Unfrozen now.
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
Could you also link to sunset's problem?
LOJ 3080
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.
I believe that 300iq is a member of the Chinese national IOI team. (joking :)
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)
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?
Sumbission
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) )
Woops, seems like it's not SCC problem. Sorry, Ildar :(
Test:
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?
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.
Ohh, sure, now I see the problem. Thanks.
I found the max-flow solution to B3 with LP and duals:
The following linear program clearly gives the correct answer to the problem:
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:
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:
This seems pretty trivial, but I can't find a better proof than the following:
To 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.
B3 is obvious if you know Closure problem. They explicitly expose a clue by condition at the last of the statement.
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
Thanks. These should have been swapped.
Can Anyone share and explain there solution to A2 problem. Also if possible, share any resource to get acquainted with such types of problems.
Why is the alternative solution working for problem E1 ?
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.
So great explanation. Great way of teaching things.
Problem E2 was very similar to this
One of the open cup rounds this year had problem E3 exactly
Next contest is 12 days from now ($$$\pi$$$-$$$\pi$$$) <- (sad face)
I'm really hungry for more contests T.T , I hope they will add more interesting contests :D
and why zero is sad face?
Its not 0. Here $$$\pi$$$ is supposed to represent a crying eye and parentheses represent the face ($$$\pi$$$-$$$\pi$$$) Look carefully ...
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
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.
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. :)
"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 :)
aawwww, how can i miss that, even after reading it many times :( .
Thanks mate and sorry for me being noobiee.
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?
It's easier to think about an axis-aligned square.
How do we get $$$(x, y) \rightarrow (x + y, x - y)$$$ and $$$2\cdot r$$$ as the side of square?
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:
where $$$x'$$$ and $$$y'$$$ are new points after rotation. Here, $$$\phi = \frac{\pi}{4}$$$. Then, we get
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.