dj3500's blog

Helvetic Coding Contest 2016 online mirror
By dj3500, 9 years ago, In English

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: ngfam_kongu, I_love_Hoang_Yen, s-quark

  4. mehlxneh: AntiForest, JoeyWheeler, xxTastyHypeBeast666xx

  5. FTP++: pwypeanut, jacobtpl, zhangguangxuan99

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

  7. Khodaro Shokr: SeyedParsa, PrinceOfPersia

  8. Coder

Tags hc2
  • Vote: I like it
  • +309
  • Vote: I do not like it

Comments Comments (47)
| Write comment?
»
9 years ago, # |
  Vote: I like it -13 Vote: I do not like it

What is the Contest platform ? Is it CF or any other Site.

→ Reply
»
9 years ago, # |
  Vote: I like it -16 Vote: I do not like it

Is that cow your pic? You look like a hostile bear.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    It's not my autoportrait, if that's what you mean. And you have to be stern with zombies.

    → Reply
»
9 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Wait, didn't Farmer John lose a cow the other day? How the mooo did it end up in Switzerland?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It looks much happier killing zombies than finding ways to get grass at Farmer John's.

    → Reply
»
8 years ago, # |
  Vote: I like it -24 Vote: I do not like it

Windboy Можно попробовать вместе контест написать.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it -23 Vote: I do not like it

ыщккн

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Looks like a really big set of problems. http://hc2.ch/res/hc2_2016_short_score.png

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is Everyone eligible for the contest?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes (except for participants of the onsite round). Teams of 1-3.

    → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +56 Vote: I do not like it

The Next Episode On The Walking Dead, A Cow Is Going To Protect Humanity!

→ Reply
»
8 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Is team allowed to use only one machine?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    No. Since this is unenforceable anyway, we do not require it.

    → Reply
»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Parse failed. :(

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Finally fixed in the new release :)

    → Reply
»
8 years ago, # |
  Vote: I like it +32 Vote: I do not like it

lucky number 14

→ Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Why answer for n = 4 is 0 in A2?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +52 Vote: I do not like it

Thanks for the contest. :) How soon will the editorial be published?

UPD: Editorial is out. Thanks :)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It's up now, I hope you like it :)

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not 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?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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?

→ Reply
»
8 years ago, # |
  Vote: I like it +33 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

One of the tests for B3 is as follows:

Spoiler

and I don't think it corresponds to any polygon, can anyone check/confirm it?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I found it while trying to find a bug with asserts, for "proof" see 19010431 .

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks! It does look like the test might have no answer. We will investigate this.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Actually cells (4,2) and (5,3) have one corner inside the polygon and need to be in the list.

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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??

→ Reply
»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Who made this cow? tehqin is available for future use.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I can vouch for the beauty of this tehqin's cows. That man can draw a cow like no other.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why is D2 solution is C(n c+n)?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I didn't understand too

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply