dj3500's blog

Helvetic Coding Contest 2018 online mirror
By dj3500, 7 years ago, In English

UPDATE: the editorial is here

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 last year and two 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 March the 17th, but the online mirror is scheduled on Saturday, 14th of April, 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 Star Wars-themed. It features 6 series of 2-3 related tasks with increasing difficulty (easy/medium/hard). 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 maksay, boba5551, mukel, DamianS, esrever, and myself. Thanks also go out to people who helped with the statements and testing: bgamlath, Michalina Pacholska (who also draws the cows), and 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 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:

>>> Editorial <<<

Feel free to ask questions in this topic.

Thanks to everyone who participated! We hope you have enjoyed the problems despite the interruption in judging. The top 4 teams, who have solved all problems, are:

  1. SpicyFriedTomatoes: AbstractKangaroo, jqdai0815

  2. (｀・ω・´): King_George, ohweonfire, FizzyDavid

  3. ymd队长ioi捧杯超稳: sunset, TLE, yanQval

  4. ★SweeT DiscoverY★: dotorya, molamola., zigui

See you again next year!

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

Comments Comments (79)
| Write comment?
»
7 years ago, # |
  Vote: I like it +27 Vote: I do not like it

hoping for short prob statements unlike previous year

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

what happens when onsite participator sees the problem with the help of other user ID.

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

    That's why it's unrated

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

      I think it's unrated because ACM style is always unrated instead. We do have contests that's rated that are later than their onsite contest.

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

    I think u misread the dates .It's 17th of March (Not April).

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

      Yes you are right. Sorry for this issue. It's my mistake. Thanks.

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

OH GOD, THIS PHOTO IS SO HOT

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

is it rated?

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

How to register as a team member...

I can't see it...

UPD: Fixed now, and wish everyone will enjoy the contest, GL & HF.

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

there is no team option in the register form .

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

Why...the "register as team member" button doesn't show up.. Is that a BUG?

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

Why am I not able to register as a team?

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

    It's now fixed!

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

    If you want to participate in Helvetic Coding Contest 2018 in a team, but have already registered personally, just delete your personal registration on the page with a list of all registrations and register again.

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

I have a question. Why I can register as a team member?

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

Is It Rated?

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

    Look this "Helvetic Coding Contest 2018 online mirror (teams allowed, unrated)".

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

Is it semirated?

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

I'm looking for a team to participate in the contest. Please PM me in case you want to solve it together :)

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

Can we register from two different teams ?

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

Someone want to take me on their team, or form a team?

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

Servers are down :(

5 queue pages

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

    Will the contest be extended in that case?

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

      I don't think so because it's unrated.

      UPD : They extended for 30 min

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

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

Is scoreboard frozen??

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

contest extended by half an hour

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

We apologize for the technical problems with CodeForces. The queue is now moving again. The contest is extended by 30 minutes. It will remain unrated ;)

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

The editorial is up: editorial

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

We delayed the start of ARC/ABC by 10 minutes due to the extension of a contest in Codeforces. https://beta.atcoder.jp/post/220

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

I don't how to prove the correctness of the solution in the problem B2. Can you guys help me?

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

    I didn't prove it during the contest, but here's a stab at it. Let g1, g2, g3, ..., gK be the vertices the prescribed solution adds, in order. Suppose you have a solution S which is better than the prescribed solution. Let p be the smallest integer for which gp is not included in S. Let the "cover" of S be all planets controlled by the rebels in solution S. Since gp is a leaf, it is not part of the cover of S. Let A be the nearest node in the cover of S to gp. If we rebuild S on vertex at a time, starting with g1, ..., gp - 1, then there is some first vertex B which when added to S causes A to become covered. Because of how gp was chosen, it must be at least as deep in the tree as B. Thus, we can remove B from S replace it with gp, without decreasing the score: we will gain all the planets on the path from A to gp, and at worst lose all the planets on the path from A to B.

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

      Wow! Thank you very much. I really do learn something today!

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

      Wow, this is proof is so wrong that I don't even know where to start.

      If we rebuild S on vertex at a time, starting with g1, ..., gp - 1, then there is some first vertex B which when added to S causes A to become covered

      So you propose to remove $$$B$$$? If $$$B$$$ is among $$$g_1, g_2, g_3... g_{p-1}$$$, then does that not make your hypothesis invalid? And there is no reason why $$$B$$$ should be the $$$p^{th}$$$ element of $$$S$$$.

      And even if we overlook this glaring error, you just show that if $$$g_p$$$ is the first such element, the score does not decrease. But it changes the graph completely. So it may happen that, in the long term, the set $$$S$$$ overcomes our proposed optimal algorithm.

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

        By the way, I have a correct proof: it's main argument is cases on LCA of chosen points and infinite descent. So cool!

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

[del]

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

is there any O(Nk) solution of problem c2?

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

Great problemset today (especially B2, C3 and E2). Feel a bit sad for not figuring out B2 though...

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

I solved E3 with O(N2), not O(N2logN).

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

    Our solution during on-site participation when we had little time left was to pick a random point of each type and check whether they line through them has an equal number of points of each type to the left of it. Repeat this until we finde a suitable line, then solve the subproblems recusively.

    Is there an easy way of analysing the runtime?

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

    Just did the virtual contest today, so I'm 4 weeks late to the party. Nonetheless I just wanted to get this out since I thought it was an interesting approach to an interesting question.

    I claim that it's possible to find a dividing line that separates roughly into halves such that each half has equal spaceships and bases.

    I'm not exactly sure how to prove it formally, so I will talk through it for even N and hope that the proof is largely correct.

    Consider defining a half-plane by an angle theta from 0 to 2pi -- the dividing line is determined by the angle and theta and theta + pi are complementary half-planes. Moreover, we may shift the position of the dividing line so that N/2 points are on each side of the half plane.

    Let f(theta) denote the number of bases contained in the half plane minus N/2. For general theta (theta such that no 2 points are parallel to the line), f is well defined and f(theta) + f(theta + pi) = 0, since the half-planes are complementary.

    Note that f(theta) is "continuous" with respect to theta -- perturbing it slightly will include 1 more point and exclude 1 more point. Thus f will change no more than 1 at a time.

    Thus, by "Intermediate Value Theorem", we have a point in which f(theta) = 0, which is the dividing line we sought.

    To find this theta, we may binary search on theta by "Intermediate Value Theorem", starting from [0, pi] for example.

    If we believe that our binary search will terminate in X steps, then this gives each dividing step a time complexity of O(NX), for a total time complexity of O(NX lg N).

    (For this question X is not too large because the smallest gradient difference we can get is about 1/250^2. And by symmetry, a smallest possible angle between 2 lines lies between 0 and pi/4, so we can bound the smallest possible angle between 2 lines accordingly.)

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

      Actually, there always is a line that separates both the spaceships and the bases into half (Proof: Consider the dual space, then the median-level of the bases and the median-level of the spaceships intersect an odd number of times. The primal of the intersection point gives us the line we're looking for.) Such a line is called a Ham-Sandwich Cut. It can be found in linear time, but the algorithms for it have quite large constants AFAIK. This would lead to an solution, but nobody would want to code something like that.

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

        Very interesting. Thanks for the reference.

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

I had a different solution to C2 and C3, running in .

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

(Edit: fixed the formula)

How did people deal with overflow in F3? When multiplying two polynomials, the coefficients can be up to about 10082 * 105, which means you need to use a prime bigger than 232 in the number theoretic transform, which in turn means you have intermediate values bigger than 264 — and annoyingly Codeforces still uses 32-bit C++ compilers so no __int128.

I tried to get around it by using the convolution with two different primes and then using the CRT to reconstruct the value, but it was too slow. That could just be my FFT implementation, which I've often had time out on other problems.

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

    Your formula doesn't display, so not sure what it says, but the modulo was only 1009, so at least standard FFT works well enough, with a maximum of like 200000 * 1009 * 1009.

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

      I've fixed the formula. How do you determine the accuracy of standard FFT?

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

      I managed to get a solution accepted using double-precision FFT, but only after I changed the range from [0, 1009) to [-504, 504] to reduce the size of the numbers. Without that I had WA (and long double got TLE).

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

        Hmm, I myself don't understand the numerical stability of FFT too well. Experimentaly, all implementations that we had could handle 1009. With the neat trick you're describing, they could even handle 100009 AFAIR.

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

          Actually I think that's a different trick. What we do to handle 100009 is to randomly set each number to either x or x-100009. Then it's in [-100009,100009], and half of the multiplied coefficients become negative, so that it cancels out to a way smaller number (around sqrt(n) times smaller, I guess).

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

    I just multiplied using double FFT and added the result by 0.5 before rounding down. (Also, I used the trick to multiply using 2 calls to FFT instead of 3 making P[j] = A[j] + i * B[j] but that shouldn't matter). AFAIK, double works for things of value sqrt(10^9 + 7) because there's the trick of dividing a number v into v / B and v % B where B is around sqrt and using 4 multiplications to get the answer any modulo.

    This also might help with precision http://codeforces.me/blog/entry/48465?#comment-325890 and the last problem here http://petr-mitrichev.blogspot.com/2015/04/this-week-in-competitive-programming.html is where I learned about this trick.

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

      Yes, my precision problems are most likely from calculating powers of the primitive root incrementally.

      Unfortunately Petr's blog only links to a comment in Russian, so I don't follow how the v/B and v%B trick works.

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

        Divide the coefficients A[i] into 2 polynomials. A0[i] = A[i] % sq, A1[i] = A[i] / sq, so A[i] = A0[i] + A1[i] * sq. Do the same thing for the polynomial B. The answer is

        C = A * B = A0 * B0 + sq * (A1 * B0 + A0 * B1) + sq * sq * (A1 * B1)

        It works kinda like writing the numbers in base sqrt(mod)

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

          Thanks, I follow. It does mean 4x as many FFTs though, which for my implementation would definitely push it over the time limit. Even my attempt at using two different primes plus the CRT only required 2x as many FFTs and that was too slow.

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

          Actually, there's only need for 3x FFTs. One only needs to calculate A0*B0 , A1*B1 and (A0+A1)*(B0+B1) to get the answer. Also, more research about precision problems in FFT can be found in a research paper by matthew99 in Chinese.

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

Is there a faster algorithm than O(K2) for E2?

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

    search up APIO 2007 Backup for O(nlogn)

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

    There is a solution with lambda optimization.

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

      Do you know any tutorial about this technique? This is the first time I have heard about it.

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

        I think he means to refer to the IOI 2016 Aliens trick, you can read about it here: blog My submission 37355142 uses it for O(N·log(max)) complexity.

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

        Another name is Lagrangean relaxation (if I understand correctly what you're referring to).

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

        Let sort the given array and calculate differences between adjacent elements. Now we need to select k elements in array of differences, such that any two of them are not adjacent, and minimize their sum.

        Let ignore the condition about k elements and maximize value of (sum — lambda * cnt), where cnt — number of chosen element ans lamda — some number. It can be done with O(n) complexity. It will be the best answer for cnt elements. The more lambda, the more cnt. We can make a binsearch and find such lambda when cnt = k. Answer to this lambda is answer to the task.

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

          What about the proof that the function is concave?

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

Shame on the editorialist for problem B2. The proof is soooooooooooo hard. And all he writes is "exercise for the reader" and just describes the implementation. Yuck.

→ Reply