Hello CodeForces! I'd like to invite you to the online mirror of an open championship of Switzerland called the Helvetic Coding Contest. 
The Helvetic Coding Contest is a yearly contest held at the EPFL in Lausanne by the PolyProg association. The contest itself took place in March, but the online mirror is scheduled on Sunday, 10th of July, 11:00 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.
You will help the cow Heidi protect humanity against a zombie apocalypse. The contest will feature 6 series of 2-3 related tasks with increasing difficulty (say easy/medium/hard). Sometimes it may be the case that a solution for the hard version solves all of them, but usually not. In the onsite contest, teams could only access the medium version of a problem once they have solved the easy, and so on; in the mirror, there is no such constraint and you will be able to see all versions since the beginning. (Otherwise, the formats of the onsite and the mirror are the same.) We think that the problemset is diverse and interesting, and while the contest is ACM-style, you will find that some problems are far from standard :)
We promise to publish a very nice editorial as soon as the contest ends.
Acknowledgments: I had the pleasure of coordinating the team of problemsetters for this contest: gawry, Christian Kauth, maksay, boba5551, DamianS and myself. Thanks also go out to people who helped with the statements and testing: Jeremy Rabasco, Valerian Rousset, Sjlver, Wajeb; GlebsHP for Russian translations and 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:
- congratulations to the winners:
squark_tutan_RR: ngfam_kongu, I_love_Hoang_Yen, s-quark
mehlxneh: AntiForest, JoeyWheeler, xxTastyHypeBeast666xx
FTP++: pwypeanut, jacobtpl, zhangguangxuan99
Команда, в которой непростые в...ку с максимальным рейтингом: Um_nik, kb., Tinsane
Khodaro Shokr: SeyedParsa, PrinceOfPersia
the editorial is available (PDF); feel free to ask questions here,
hope you enjoyed the contest!
What is the Contest platform ? Is it CF or any other Site.
CodeForces.
Is that cow your pic? You look like a hostile bear.
It's not my autoportrait, if that's what you mean. And you have to be stern with zombies.
Wait, didn't Farmer John lose a cow the other day? How the mooo did it end up in Switzerland?
It looks much happier killing zombies than finding ways to get grass at Farmer John's.
Windboy Можно попробовать вместе контест написать.
https://www.youtube.com/watch?v=FDO6rSTUcvE&index=69
ыщккн
Looks like a really big set of problems. http://hc2.ch/res/hc2_2016_short_score.png
Is Everyone eligible for the contest?
Yes (except for participants of the onsite round). Teams of 1-3.
Is team allowed to use only one machine?
No. Since this is unenforceable anyway, we do not require it.
Parse failed. :(
In Hightail, you mean? Indeed :( Not sure if I can fix it during the contest, but I will take a look at what's wrong.
Finally fixed in the new release :)
lucky number 14
Why answer for n = 4 is 0 in A2?
If the 3rd zombie declines the proposal of 0 brains for everyone, then it's gonna be his turn. But then, he is going to propose the same, and 1st and 2nd are going to refuse, and he is dead. And he doesn't want to be dead... again. So, 3rd zombie is ok with the proposal, and we have 2 ok's.
Thanks, I've got it.
Thanks for the contest. :) How soon will the editorial be published?
UPD: Editorial is out. Thanks :)
It's up now, I hope you like it :)
In F2 the editorial states "At this stage, it’s clear that we will need a clever way of checking whether two trees are the same. While this problem is quite hard for general graphs, for trees there is a simple (though not at all obvious) linear-time solution".
Do you have a resource detailing how to check unrooted tree isomorphism in linear time?
You can find centres of both trees and then compare rooted trees. However there can be situtation when there are two centres, so it requires a bit more work.
UPD. Got stupid TL in contest time, now got accepted in upsolving.
It is rather standard, should probably be described in algorithms textbooks. I found the following online: http://crypto.cs.mcgill.ca/~crepeau/CS250/2004/HW5+.pdf
In D3, shouldn't the base cases be dp[0] = dp[-1] = 1, so that it can cover the case when a segment is made with all available columns?
I personally found problem A2 a bit confusing(maybe it was just me) and also I think that tasks C2/3 were too easy(they are relatively well-known algorithms). What are your impressions from the competition?
Great problems! All the problems required more thinking than coding which is nice
some hints:
A2 — you need to figure out why answer for 8 is 0 (it is 1 for 6 which is simpler) and then you can guess the pattern
A3 — well known problem, very simple solution
B2,B3 — all 4 neighbors need to have value >0
C3 — it is simple if you solved C2 using 2 farthest points
D3 — standard matrix multiplication
E2 — calculating differences directly is not accurate enough, needs some aggregation
C3
How do I prove that fact about new diameter? Or how does it even help us?
When we have multiple maximum diameters I can't understand, why does this work.
One of the tests for B3 is as follows:
and I don't think it corresponds to any polygon, can anyone check/confirm it?
This test seems to be incorrect, my accepted solution outputs
and all these points have to be among the vertices (can be checked manually with a picture). But then cells (3, 3) and (4, 4) have to be completely inside, so they shouldn't be in the input.
Can you show where you found this test?
I found it while trying to find a bug with asserts, for "proof" see 19010431 .
Thanks! It does look like the test might have no answer. We will investigate this.
Thanks for the question! Indeed, it turns out that some testcases had no solution. This is corrected now. We have rejudged all the failed solutions from during the contest and fortunately, only two contestants were affected. The practice-mode submissions were not rejudged — feel free to resubmit your code.
Actually cells (4,2) and (5,3) have one corner inside the polygon and need to be in the list.
Why answer in A2 for n=3 is 1.
Actually I think the suggestion is 1 brain to zombie2 and 0 brain to zombie1, but if they reject that suggestion, then zombie2 will make same offer and it will be accepted, which means initial offer is not strictly better than this one, so offer made by the cow will be rejected.
Where did I mess it up??
Give 1 brain to zombie 1 instead.
OK, now I understand.
In B3 (and also B2), an easy solution is to construct a convex hull of all input points (with values 1, 2 and 3). This hull must have horizontal sides on the top and on the bottom, and vertical sides on the left and on the right. Shrink these four sides by 1 to get the answer.
Who made this cow? tehqin is available for future use.
I can vouch for the beauty of this tehqin's cows. That man can draw a cow like no other.
why is D2 solution is C(n c+n)?
I didn't understand too
We can put n balls in k bucket (n+k-1,k-1) ways, where every bucket has a non-negative number of balls and the total number of balls in all buckets, is n.
In this problem, suppose we have C+1 columns. We take one extra column for those bricks which are not used in other C columns. So, the total number of ways is (n+C+1-1,C+1-1)=(n+C,C) . But using all n bricks in the extra column is invalid. So, the final result is (n+C,C)-1.
Может ли кто-нибудь доходчиво объяснить мне, откуда взялась та формула в разборе к D2? почему число сочитаний из c + n по n?