Блог пользователя dj3500

Автор dj3500, 8 лет назад, По-английски

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

Теги hc2
  • Проголосовать: нравится
  • +309
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится -23 Проголосовать: не нравится

ыщккн

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is Everyone eligible for the contest?

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +56 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

Is team allowed to use only one machine?

»
8 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Parse failed. :(

»
8 лет назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

lucky number 14

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Why answer for n = 4 is 0 in A2?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +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.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +52 Проголосовать: не нравится

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

UPD: Editorial is out. Thanks :)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +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?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 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?

»
8 лет назад, # |
  Проголосовать: нравится +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?

»
8 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +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.

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 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?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 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.

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 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??

»
8 лет назад, # |
  Проголосовать: нравится +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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    I didn't understand too

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Может ли кто-нибудь доходчиво объяснить мне, откуда взялась та формула в разборе к D2? почему число сочитаний из c + n по n?