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

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

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!

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

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

Thank you for your efforts guys :D

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

    Nevermind :D

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

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

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

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

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

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

Handsome!

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

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

Great!

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

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

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

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

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

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

How to form team?

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

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

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

Can teams use multiple systems?

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

deleted

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

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

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

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

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

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

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

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

    Could you also link to sunset's problem?

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

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

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

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

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

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

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

    Test:

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

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

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

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

Proof and intuition for B3
»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

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

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

Why is the alternative solution working for problem E1 ?

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

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

Problem E2 was very similar to this

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

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

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

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

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

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

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

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

          Thanks mate and sorry for me being noobiee.

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

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

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

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

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

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

        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.