dj3500's blog

By dj3500, history, 5 years ago, In English

UPDATE: the editorial is here

Link to the online mirror

Hello CodeForces! This year again, I'd like to invite you to the online mirror of an open championship of Switzerland called HC2 (the Helvetic Coding Contest). A mirror was also held one, two and three years ago.

The Helvetic Coding Contest is a yearly contest held at the EPFL in Lausanne by the PolyProg association. The contest itself took place on April the 13th, but the online mirror is scheduled on Sunday, 7th of July, 10:05 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.

The contest this year is Doctor Who-themed. It features 5 series of 2-3 related tasks with increasing difficulty (easy/medium/hard). (For the online mirror, we will skip one series that had appeared in the onsite contest.) Sometimes it may be the case that a solution for the hard version solves all of them, but usually not. We think that the problemset is diverse and interesting, and while the contest is ACM-style, you will find that some problems are not so standard. Most easy&medium problems are even solvable in Python, so you can also recommend this contest to your newbie friends :) We promise to post a nice editorial as soon as the contest ends.

Acknowledgments: the problems were set by bgamlath, DamianS, esrever, milenkoviclazar, Wajeb (who coordinated), and myself. Thanks also go out to people who helped with the statements and testing: anayMehrotra, Michalina Pacholska (who also draws the cows), cdkrot for the Russian statements, KAN for 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 nexthink. 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:

>>> Editorial <<<

Also:

Thanks to everyone who participated! We hope you have enjoyed the problems. The top three teams are:

  1. 大象大象你的鼻子为什么那么长 (solved all 14 problems!): FizzyDavid, 300iq, TLE

  2. zxtxdy (13 problems): cuizhuyefei, MarkF, zx2003

  3. helveticow (12 problems): scott_wu, ksun48, ecnerwala

See you again next year!

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

| Write comment?
»
5 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Thank you for your efforts guys :D

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it -27 Vote: I do not like it

    Nevermind :D

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

      No one says that's because of your profile picture, and I can't see evidence for any racism.

      I think the downvotes are because of the meaningless comment. Being grateful to problem setters is good, however, you can upvote the post, make meaningful comments (not the ones which can be used for every round), or simply participate in this round to show your thanks.

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 4   Vote: I like it +17 Vote: I do not like it

        I talked about racism because there was a racism comment but it seems he deleted it ,I tried to reply at him or at anyone who has the same mindset.
        Also,I respect your point of view,but when the problem setter or anyone who did any kind of hard works will appreciate any feedback or grateful comment. And I agree With you at "make meaningful comments (not the ones which can be used for every round)" :D

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I can see there are many comments downvoted without any critical thing. Also I know many people from various communities who use Codeforces alts to make significant amount of downvotes(or upvotes). I don't know why they are doing this but sometimes it makes me to feel toxic.

»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

there is no option showing for choosing the members of the team

»
5 years ago, # |
  Vote: I like it -34 Vote: I do not like it

Handsome!

»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

ong time no see the contest that we can team.It's also a good time for Chinese CFer.

Great!

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    Don't be so selfish. It's always good time for some users while bad for others.

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      Though I agree on the timing part, is celebrating a good rank on some contest also considered selfish even when someone else is bound to get worse rank?

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

      While I think it's good for all users to practice their team capabilities :)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to form team?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm curious as to how the team ratings are calculated. Can somebody explain?

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

    This contest is not rated. In general, there is some system actually, though I'm not sure whether it has been used recently.

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

      I know it's unrated. I was just curious about how the calculation is done. Surely, doesn't look like an average of ratings of all members. That's why I was wondering.

»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Can teams use multiple systems?

»
5 years ago, # |
Rev. 2   Vote: I like it -11 Vote: I do not like it

deleted

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is the contest running but it says, "Standings are frozen."? Did something happen? I just solved D1 but it didn't show on the leader board, then I noticed the "Standings are frozen." phrase beneath "Contest is running."

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

    That's something that's traditionally done in ACM ICPC type contests — the standings are frozen for the last hour of the contest.

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

      Oh OK, thanks. I didn't know that.

»
5 years ago, # |
  Vote: I like it +70 Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's over. Thanks everyone! The editorial is up.

»
5 years ago, # |
  Vote: I like it +42 Vote: I do not like it

We solved D2 using the idea from sunset's problem. After the contest he showed me the problem from which he get inspiration for his problem.

Well, so it seems like a notorious coincidence

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

    Could you also link to sunset's problem?

  • »
    »
    5 years ago, # ^ |
    Rev. 4   Vote: I like it +8 Vote: I do not like it

    Could someone clarify the last paragraph of the editorial for D2?

    "We can represent x4,2 as a function of x5,2, x5,3 and x2,2 which is already a function of x4,2 and x4,3."

    So $$$x_{4,2}$$$ is a linear combination of $$$x_{5,2}, x_{5,3}$$$ and $$$x_{2,2}?$$$ Or a linear combination of $$$x_{5,2}, x_{5,3}, x_{2,2}, x_{4,2}, x_{4,3}?$$$ Either way, how does this help?

    "Continuing in this fashion"

    What fashion? I don't see how the previous two sentences display a pattern. Are we writing equations for all $$$x_{i,j}$$$ in increasing order of $$$i$$$ until we get until $$$i=m?$$$ If so, don't we need to run Gaussian Elimination every time we increase $$$i?$$$

    I tried reading some of the solutions, but I don't understand exactly what they're doing ...

    EDIT: Nvm, I solved it (see 56770140). It's essentially the same as 56662502.

»
5 years ago, # |
  Vote: I like it +63 Vote: I do not like it

I believe that 300iq is a member of the Chinese national IOI team. (joking :)

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Of course it will not be possible to hack, but perhaps you can give time =)

(or you need to increase the time to 7 days)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Solved B2 — using flow algorithm.

Read B3 — very straightforward SCC problem, coded, got AC.

Opened editorial and it is flow problem ( I was very surprised here).

I am only one who just coded SCC?

Sumbission

P.S. I thought ( s * n * log b shouldn't pass in the first part of the solution) and wrote it in O(s * n + (s + b) * log(s + b) )

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

    Woops, seems like it's not SCC problem. Sorry, Ildar :(

    Test:

    Spoiler
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry, I'm confused. Are you saying that the solution with SCC is wrong for this test case? Or could you explain what you mean by this test?

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

        The solution of the_art_of_war is wrong for this test. He tried to solve this problem greedily without any flows and cuts but this solution is wrong and I just provided this case which breaks it.

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

          Ohh, sure, now I see the problem. Thanks.

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

I found the max-flow solution to B3 with LP and duals:

Proof and intuition for B3
»
5 years ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

Hi there,

Such a great tutorial but the explanation for the first problem says that: Alternatively, one can observe that if r is odd then there is no solution and if r is even then (x, y) = (1,(r−3)/2) always works (as long as y is positive)!

But,

If r is even then there is no solution and if r is odd then always the above-stated formula works.

Thanks, Teja

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

    Thanks. These should have been swapped.

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can Anyone share and explain there solution to A2 problem. Also if possible, share any resource to get acquainted with such types of problems.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is the alternative solution working for problem E1 ?

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

    Let X be the weight that this method yields. Think about what Kruskal's algorithm would do if the weight of this edge were set to less than X, and what it would to if it were set to more than X.

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem E2 was very similar to this

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

    One of the open cup rounds this year had problem E3 exactly

»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Next contest is 12 days from now ($$$\pi$$$-$$$\pi$$$) <- (sad face)

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

    I'm really hungry for more contests T.T , I hope they will add more interesting contests :D

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

    and why zero is sad face?

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +14 Vote: I do not like it

      Its not 0. Here $$$\pi$$$ is supposed to represent a crying eye and parentheses represent the face ($$$\pi$$$-$$$\pi$$$) Look carefully ...

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem B2, I understood that one of the answer can be: (maximum_matching * k) ,
but i am not getting why other answer is "**no of spaceships * h**",
my thoughts about second answer:
1. it should be (**maximum_matching * h**), but i know its wrong .
2. it should be (maximum bases that are under threat of being attacked by any ship * h).
I don't know if i explained it right, but if someone got what i am trying to say please tell what i am missing.
Thank You

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

    The two alternatives are:

    1. You do nothing, as in you build zero dummy bases. In this case, it's clear why the answer is maximum matching * k

    2. You build enough dummy bases to guarantee that all ships that were attacking real bases will now attack dummy ones. In this case, it can be shown that you need to build s dummy bases. This is because unpaired ships will be paired initially with dummy bases, then the ones in the matching.

    Doing anything in between is guaranteed to be less optimal.

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

      lets say if one of ship is having 0 fuel(i.e., not able to attack any base), than instead of taking s*h , we should take (s-1)*h as a second alternative.

      Thank you for replying. :)

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

        "With the Doctor's help, these bases would exist beyond space and time, so all spaceship can reach them and attack them."

        Fuel and attack don't matter for dummy bases :)

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

          aawwww, how can i miss that, even after reading it many times :( .

          Thanks mate and sorry for me being noobiee.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I want to ask about problem C2 (Medium). Can anybody give reason why do we need rotating the plane by 45 degrees? Cannot we do the same algorithm using the original coordinates?

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

    It's easier to think about an axis-aligned square.

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

      How do we get $$$(x, y) \rightarrow (x + y, x - y)$$$ and $$$2\cdot r$$$ as the side of square?

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

        I think I figured it out. Please let me know if I did anything wrong in my analysis.

        How do we get $$$(x - y, x + y)$$$ after rotation?

        We would like to rotate (integer-based) point $$$(x, y)$$$ by $$$45^{\circ}$$$. In general to rotate any point by degree $$$\phi$$$, we use the following transformation:

        $$$ \begin{pmatrix} \cos\phi & -\sin\phi \\ \sin\phi & \cos\phi \end{pmatrix} \cdot \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} x' \\ y' \end{pmatrix} $$$

        where $$$x'$$$ and $$$y'$$$ are new points after rotation. Here, $$$\phi = \frac{\pi}{4}$$$. Then, we get

        $$$ \begin{pmatrix} \frac{\sqrt{2}}{2} & -\frac{\sqrt{2}}{2} \\ \frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} \end{pmatrix} \cdot \begin{pmatrix} x \\ y \end{pmatrix} = \frac{\sqrt{2}}{2} \begin{pmatrix} x - y \\ x + y \end{pmatrix} $$$

        Since we need to work with integer-based coordinates, we scale the points by a factor of $$$\sqrt{2}$$$, then we get $$$(x - y, x + y)$$$.

        What is the side of square after rotation?

        Before the rotation, the diameter of square is $$$2 \cdot r$$$ because a point $$$(x, y)$$$ is assumed to be the lower corner the square. We consider such assumption as it helps cover all cases in our sweep line + segment tree solution. Therefore, the side of square should be $$$\frac{2}{\sqrt{2}} \cdot r$$$. Note that after rotation, we scale all points with a factor of $$$\sqrt{2}$$$. Therefore, the side of square will be $$$\sqrt{2} \cdot \frac{2}{\sqrt{2}} \cdot r = 2 \cdot r$$$ after $$$45^{\circ}$$$ rotation.