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

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

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!

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

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

hoping for short prob statements unlike previous year

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

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

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

OH GOD, THIS PHOTO IS SO HOT

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

is it rated?

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

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

there is no team option in the register form .

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

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

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

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

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

Why am I not able to register as a team?

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

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

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

Is It Rated?

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

Is it semirated?

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

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

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

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

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

Can we register from two different teams ?

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

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

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

Servers are down :(

5 queue pages

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

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

Is scoreboard frozen??

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

contest extended by half an hour

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

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 ;)

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

The editorial is up: editorial

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

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

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

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

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

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

[del]

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

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

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

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

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

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

and recommend me similar type of problem :)

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

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

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

    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?

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

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

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

(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.

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

    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.

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

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

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

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

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

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

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

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

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

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

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

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

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

    search up APIO 2007 Backup for O(nlogn)

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

    There is a solution with lambda optimization.

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

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

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

        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.

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

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

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

        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.