dj3500's blog

By dj3500, 8 days 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: mjy0724, OO0OOO00O0OOO0O00OOO0OO

  2. (`・ω・´): King_George, OhWeOnFire, FizzyDavid

  3. ymd队长ioi捧杯超稳: yjq_naiive, fjzzq2002, yanQval

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

See you again next year!

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

»
8 days ago, # |
  Vote: I like it +27 Vote: I do not like it

hoping for short prob statements unlike previous year

»
8 days 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.

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

    That's why it's unrated

    • »
      »
      »
      7 days 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.

  • »
    »
    7 days 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).

    • »
      »
      »
      7 days 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.

»
7 days ago, # |
  Vote: I like it +67 Vote: I do not like it

OH GOD, THIS PHOTO IS SO HOT

»
7 days ago, # |
  Vote: I like it -62 Vote: I do not like it

is it rated?

»
7 days 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.

»
7 days ago, # |
  Vote: I like it +3 Vote: I do not like it

there is no team option in the register form .

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

»
7 days ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

who will take me on the team? /also I can speak Russian/ Кто возьмет в команду ?

»
7 days ago, # |
  Vote: I like it +12 Vote: I do not like it

Why am I not able to register as a team?

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

    It's now fixed!

  • »
    »
    7 days 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.

»
7 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
7 days ago, # |
  Vote: I like it -23 Vote: I do not like it

Is It Rated?

»
7 days ago, # |
  Vote: I like it -20 Vote: I do not like it

Is it semirated?

»
7 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

??????????????????happy

»
6 days 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 :)

»
6 days ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

Can we register from two different teams ?

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Servers are down :(

5 queue pages

»
6 days ago, # |
Rev. 2   Vote: I like it +117 Vote: I do not like it

»
6 days ago, # |
  Vote: I like it +21 Vote: I do not like it

Is scoreboard frozen??

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

contest extended by half an hour

»
6 days 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 ;)

»
6 days ago, # |
  Vote: I like it +16 Vote: I do not like it

The editorial is up: editorial

»
6 days 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

»
6 days 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?

  • »
    »
    6 days 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.

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

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

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

[del]

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 days 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...

»
6 days ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

Any1 plzz explain B2 (medium)..in simple way..??i read editorial but didn't get

and recommend me similar type of problem :)

»
6 days ago, # |
  Vote: I like it +20 Vote: I do not like it

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

Spoiler
  • »
    »
    5 days 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?

»
6 days ago, # |
  Vote: I like it +5 Vote: I do not like it

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

Spoiler
»
6 days 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.

  • »
    »
    6 days 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.

    • »
      »
      »
      6 days 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?

    • »
      »
      »
      6 days 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).

      • »
        »
        »
        »
        5 days 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.

        • »
          »
          »
          »
          »
          5 days 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).

  • »
    »
    5 days 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.com/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.

    • »
      »
      »
      5 days 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.

      • »
        »
        »
        »
        5 days 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)

        • »
          »
          »
          »
          »
          5 days 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.

        • »
          »
          »
          »
          »
          4 days 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.

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

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

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

    search up APIO 2007 Backup for O(nlogn)

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

    There is a solution with lambda optimization.

    • »
      »
      »
      5 days 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.

      • »
        »
        »
        »
        5 days 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.

      • »
        »
        »
        »
        5 days 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).

      • »
        »
        »
        »
        4 days 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.