Hello Codeforces!
Back from the dead, we'd like to invite you to the online mirror of the Helvetic Coding Contest, Switzerland open championship! You can find past mirror from 2019, 2018, 2017, and 2016.
The Helvetic Coding Contest used to be held yearly at EPFL. This year, the Polympiads association is bringing it back alive! The contest itself took place on April the 13th, but the online mirror is scheduled on Saturday, 4th of May, 09:05 Swiss time. The duration is 4:30.
Rules:
you can participate in teams or individually with a single computer (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.
Contrary to what the mirror's date might lead you to believe, this year's theme is Harry Potter. It features 7 series of 3 related tasks with increasing difficulty (easy/medium/hard). Note that we do not guarantee that all problems are solvable using python.
Thanks a lot to:
Petr, Charbel, ScarletS, 3EVEHAR_KOAVA, AdrienVannson, bjornargh, and zehnsechs for setting and/or coordinating the problemsetting,
matrix for preparing the technical setup of the contest
paula, Macdu, McLovinn as well as problemsetters for testing the contest,
All of Polympiads committee and on the day staff for making the contest possible,
MikeMirzayanov for creating the amazing Codeforces and Polygon platforms!
UPDATE: Editorial is out, also available as a PDF. Thanks all for participating!
UPDATE 2: Congratulations to the winners who solved all 21 subtasks:
- thinking: Ormlis, Mangooste
- Captain take me!: crazy_sea, A_zjzj, 275307894a
- japan406364961: Nyaan, kotatsugame, risujiroh
- Qingyu Fan Club: xinyoudui, GapGapGap, InfiniteStarlight
- Idea Generators Club: tedi_2.0, Denisov, Valera_Grinenko
- 244mhq
- jiangly
UPDATE 3: Also huge congratulations to the winners of the onsite round (no prewritten code or Internet access was allowed, so the conditions were a bit different):
- Felt smart (might un-participate later) — 20 subtasks
- Nameless Silly Moon — 18 subtasks
- ***IsEvil? — 17 subtasks
- Breakfast Master Toaster — 16 subtasks
- Hairy Stofler — 16 subtasks
- thethingswedoforpizza — 15 subtasks
- huchibuchi — 15 subtasks
We hope you enjoyed the problems, please share your thoughts in comments!
Cauchico orz
Cauchico orz
Cauchico orz
Cauchico orz
Cauchico orz
Cauchico orz
Cauchico orz
Cauchico orz
Cauchico orz
Cauchico orz
Cauchico orz
Cauchico orz
orz
Cauchico orz
Cauchico orz
Cauchico orz
Cauchico orz
orz
move closer, don’t spoil your eyes
Harry Potter is a controversial series, a poor choice by the organizers :|
Harry potter is one of the most famous series of all time. I have read every book atleast twice and seen each movie >= 5 times. Thats how good it is. Stop bring politics into everything. NOBODY CARES.
... and RCB is the most supported IPL team of all time. Popularity of some entity in the modern day only indicates the number of midwits the creators of said entity managed to brainwash through advertising.
Petr orz
Relax Boyzz
I have to literally orz to spot them in the points table
_
RCB orz
When we're talking about things with such immense cultural value and influence as Harry Potter, we're not really bringing politics into it. Because it already is there, whether we care about it or not.
The series certainly carries a particular messaging on what's right and what's wrong, and since it is targeted at younger audience, it is also very likely to at least to some extent shape their values and worldview.
It is of course up to us whether to agree or to disagree with the ideas that J. K. Rowling put into the book, and I personally would be pretty much against canceling such a monumental work just due to a disagreement with its messaging. But turning a blind eye to its political nature and pretending that it's just not there is also a very questionable, and a somewhat dangerous act. Being conscious about what we promote and what political ramifications it carries is the least we can and must do.
Please separate the art from the artist.
EDIT: Oh I thought this was about JK Rowling's questionable comments. Well, still these aren't nearly serious enough things to justify boycotting such a famous series.
Any monumental series would be controversial in particular social circles. Sending a general link to the page doesn't help at all, unless you at least outline which particular messaging of the series you disagree with so much that you think it deserves to be boycotted. On a side note, if we keep being too nitpicky about what series we theme stuff around, we will end up in a very grey and boring world, because it is the only way to remain totally uncontroversial.
To be specific, I find it odd that a competition with the following eligibility policy on their website
chosen a theme for itself that was well-known for the mistreatment of minorities. In retrospect, I agree that my message was likely unclear to people out of the loop.
As an onsite participant, the problems are good!
What is difficulty level of problems?
Each problem has 3 versions (subtasks) with increasing difficulty (easy/medium/hard), therefore I hope there is something interesting to solve for everybody!
The easiest task is probably around Div2A, while the hardest task is probably around Div1E.
The contest as a whole is easier than Universal Cup rounds or strong ICPC regionals or World Finals. I would expect a World Finals medalist team to solve everything in about 3 hours, but my perception might not be spot on.
Which one do you suggest? Participating as a team or individually?
I think participating as a team is better,because it is fun and you can solve problem quickly.
Are you related to the font of Helvetica?
Basically "helvetic" is a fancy synonym for "swiss".
😲 😲 😲
Cauchico ORZ
Is there age limit when you participate onsite???
Wonderful set of problems, although i could only solve B3.
how to solve c2,c3?
You ca share C1 approach.
first make array after go to current node , and check whether the exist odd length on either side then ron wins . (2 3 1 we are standing on three , both side we have odd moves so ron will win)
Thank You
Code I am using dfs like loop to get array(starting from leaf and going further)
Think about a matching on the graph. If you start from an unmatched node what happens?
Isn't matching too much for such a problem?
No, because most problems about moving on a graph use it.
Here is a classical one:
Q: A and B take turns moving on a graph and cannot visit the same node twice. The one who cannot move loses. Who wins? A: if the graph has a perfect matching, B wins; otherwise, A wins.
DP on Trees Let's first solve it when $$$t=1$$$. Let's root the tree at the starting node. We can see that we can only go to one of its children, and when we go to one of its children we also can go only to the children since the parent is now active. Now let's solve for the rooted tree. Let's say that $$$dp_x=1$$$ when we can Win from node $$$x$$$, and $$$dp_x=0$$$ when we can't win from node $$$x$$$. How to calculate $$$dp_x$$$? We can only win from a node if one of its children is losing. It's just basic game theory. Now you just calculate $$$dp$$$ using dfs or bfs or something. Now, how do we solve for all roots? We use rerooting. Let's define or $$$dp$$$ in another way: $$$dp_x$$$ is the number of children of node $$$x$$$ that are losing states. Now, let's say we want to move the root from node $$$p$$$ to $$$x$$$ such that $$$p$$$ is currently the root and $$$x$$$ is one of its children. How will the $$$dp$$$ array change? It's $$$dp_x=0$$$ then it means its a losing state, so we have to to $$$dp_p:=dp_p-1$$$ (decrement $$$dp_p$$$). Now, if $$$dp_p$$$ became 0, that means it's now a losing node, so $$$x$$$ becomes a winning node, so if $$$dp_p=0$$$ after the change, we do $$$dp_x:=dp_x+1$$$. Now we store the answers for all the roots and answer each query in $$$O(1)$$$. See my submission for more details 259649513.
I understood most of the part, but can you please explain:
If dpx=0 --> losing state --> dpp = dpp−1
Why decrementing the dpp??
Because after changing the root, x will not be a child or p anymore, so it can't use x anymore as a way to win, so the number of children that p can use to win decreases
When I passed D1, I couldn't believe that I got the first blood!
Do these problems have an editorial? Or can we watch other participants' codes? Thanks!
I've just published the editorial.
W contest!
Auto comment: topic has been updated by Petr (previous revision, new revision, compare).
Auto comment: topic has been updated by Petr (previous revision, new revision, compare).
egg
Auto comment: topic has been updated by Petr (previous revision, new revision, compare).
High Quality tasks!!!
Codeforces Helvetic Contest 2024
Detailed Video Tutorial B1 + B2 + B3
https://youtu.be/1s9NN3D3TWY
(Language => Hindi)
Weak test cases on F1 where Quaffle doesn't move at all! However it does on F2 which confused me a lot :(
As an onsite participant, the problems are good!
for people wondering the onsite winner team was adamant and mango_lassi from eth zurich :)
Can rainboy tourist nor start solving problem J together? For the entire month provide advice and support, it's really important
Watch travel videos to learn more, I'm doing north region now
Will the rating of problems in this contest be updated?
I rarely do these kinds of mirror contest as the major problem for me is that the statements always make me hard to understand. I wish there are some explanations at the end of each problems, but they mostly don't have that.