dj3500's blog

By dj3500, 2 years ago, ,

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:
1. Zg: gustav, ikatanic

2. Endagorion

3. squark_tutan_RR: tutanjokersharp, I_love_Hoang_Yen, s-quark

4. mehlxneh: AntiForest, izrak, abyssmall

5. Команда, в которой непростые в...ку с максимальным рейтингом: Um_nik, kb., Tinsane

6. Khodaro Shokr: SeyedParsa, amd

7. Coder

•
• +309
•

 » 2 years ago, # |   -13 What is the Contest platform ? Is it CF or any other Site.
•  » » 2 years ago, # ^ |   0 CodeForces.
•  » » » 2 years ago, # ^ |   0 Thanks
 » 2 years ago, # |   -16 Is that cow your pic? You look like a hostile bear.
•  » » 2 years ago, # ^ |   +6 It's not my autoportrait, if that's what you mean. And you have to be stern with zombies.
 » 2 years ago, # |   +19 Wait, didn't Farmer John lose a cow the other day? How the mooo did it end up in Switzerland?
•  » » 2 years ago, # ^ |   +3 It looks much happier killing zombies than finding ways to get grass at Farmer John's.
 » 2 years ago, # |   -24 windboy Можно попробовать вместе контест написать.
•  » » 2 years ago, # ^ |   -12
•  » » » 2 years ago, # ^ |   -13 LoL
 » 2 years ago, # | ← Rev. 2 →   -23 ыщккн
 » 2 years ago, # |   0 Looks like a really big set of problems. http://hc2.ch/res/hc2_2016_short_score.png
 » 2 years ago, # |   0 Is Everyone eligible for the contest?
•  » » 2 years ago, # ^ |   0 Yes (except for participants of the onsite round). Teams of 1-3.
 » 2 years ago, # | ← Rev. 3 →   +56 The Next Episode On The Walking Dead, A Cow Is Going To Protect Humanity!
 » 2 years ago, # |   +27 Is team allowed to use only one machine?
•  » » 2 years ago, # ^ |   +8 No. Since this is unenforceable anyway, we do not require it.
 » 2 years ago, # |   +18 Parse failed. :(
•  » » 2 years ago, # ^ |   0 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.
•  » » 2 years ago, # ^ |   +5 Finally fixed in the new release :)
 » 2 years ago, # |   +32 lucky number 14
 » 2 years ago, # |   +5 Why answer for n = 4 is 0 in A2?
•  » » 2 years ago, # ^ |   +3 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.
•  » » » 2 years ago, # ^ |   +5 Thanks, I've got it.
 » 2 years ago, # | ← Rev. 2 →   +52 Thanks for the contest. :) How soon will the editorial be published?UPD: Editorial is out. Thanks :)
•  » » 2 years ago, # ^ |   +5 It's up now, I hope you like it :)
•  » » » 2 years ago, # ^ |   +5 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?
•  » » » » 2 years ago, # ^ | ← Rev. 3 →   0 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.
•  » » » » 2 years ago, # ^ |   0 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
•  » » » 2 years ago, # ^ |   0 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?
 » 2 years ago, # |   +11 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?
 » 2 years ago, # |   +33 Great problems! All the problems required more thinking than coding which is nicesome 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 patternA3 — well known problem, very simple solutionB2,B3 — all 4 neighbors need to have value >0C3 — it is simple if you solved C2 using 2 farthest pointsD3 — standard matrix multiplicationE2 — calculating differences directly is not accurate enough, needs some aggregation
•  » » 2 years ago, # ^ |   +21
 » 2 years ago, # |   +13 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.
 » 2 years ago, # |   +10 One of the tests for B3 is as follows: Spoiler10 21 2 1 2 2 2 3 2 4 2 5 3 1 3 2 3 3 3 5 4 3 4 4 4 5 4 6 5 4 5 6 6 4 6 5 6 6 6 7 7 6 7 7 and I don't think it corresponds to any polygon, can anyone check/confirm it?
•  » » 2 years ago, # ^ |   0 This test seems to be incorrect, my accepted solution outputs 4 2 1 2 4 6 6 5 4 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?
•  » » » 2 years ago, # ^ |   0 I found it while trying to find a bug with asserts, for "proof" see 19010431 .
•  » » » » 2 years ago, # ^ |   0 Thanks! It does look like the test might have no answer. We will investigate this.
•  » » » » » 2 years ago, # ^ |   0 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.
•  » » » 2 years ago, # ^ | ← Rev. 3 →   0 Actually cells (4,2) and (5,3) have one corner inside the polygon and need to be in the list.
 » 2 years ago, # | ← Rev. 2 →   0 I couldn't parse with hightail , parsing failed. Where i can find instruction for this ?
 » 2 years ago, # |   0 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??
•  » » 2 years ago, # ^ |   0 Give 1 brain to zombie 1 instead.
•  » » » 2 years ago, # ^ |   0 OK, now I understand.
 » 2 years ago, # |   +11 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.
 » 2 years ago, # |   0 Who made this cow? tehqin is available for future use.
•  » » 2 years ago, # ^ |   0 I can vouch for the beauty of this tehqin's cows. That man can draw a cow like no other.
 » 2 years ago, # |   0 why is D2 solution is C(n c+n)?
•  » » 23 months ago, # ^ |   -8 I didn't understand too