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

Автор Temirulan, история, 8 лет назад, По-русски

Let's discuss problems.

How to solve E and F.

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

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

Auto comment: topic has been translated by Temirulan (original revision, translated revision, compare)

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

E — sort edges in descending order. Then add edges one by one keeping number of:

  1. Vertices with degree = 0 (v0).
  2. Vertices with degree = 2 (v2).
  3. Connected components which are one whole cycle. (cycle).

Then numv = v - v0 - v2 + cycle

and nume = eadded - v2 + cycle.

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

How to solve div.2 B — "B. Book Borders", I've got TLE. And div.2. D — "D. Digit Division"?

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

    My solution is Log(b — a) * (b — a) * Log(w). I iterate from a to b foreach i finding how many words would be on each next string of length i. This is O((b — a) / i * f(i)), where f(i) is the complexity of "finding how many words would be on each next string of length i".

    f(i) can be doen with binsearch: lets assume we've already proceded L words, so now we have to find maximum of such R that lengths of words from [L + 1, R] + R — L(count space characters) is <= i. Well, calculate prefix sums for words' length, then find R simply with binsearch. Dont forget to add length of L + 1 word to your answer(thats what we have to do :) )

    Why is this (b — a) * Log(b — a) * log(w)? Log(w) goes for binsearch obviously; for some reason Sum(i / n, {i from 1 to n}) is Log(n) / n, so when we iterate for each i in [a, b] we do O(b — a) * Log(b — a) operations. Idk why it passes time limit, it looks like ~1.8 * 10^8, but it does. That's it

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

Here are the slides from the solution presentation held onsite: https://goo.gl/6IFvGQ

They don't describe solutions in great depths, but hopefully you can get some hints from the slides.

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

Расскажите как решать G из Div2.

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

Problem div.2 'A. ASCII Addition' in russian differed from english that it had a screenshot of ASCII art instead of text in pdf (which is copied very comfortable as chunks of 7 x 5 lines) and it could save some minutes of coding. (Besides scripting languages here were helpful http://ideone.com/7Hz8qP )

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

It seems that there are some problems with standings. My team solved 4 tasks during contest, but in official standings we have 7.
UPD. Fixed.

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

Could someone please share code for problem I that passed without additional optimizations?

Our solution is O(max_coordinates) per one query and doesn't use sqrt (only arithmetic operations with doubles), but gets TL 11 and I have no idea what to do with it :(

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

    Here's our code (author is meshanya). It passed with 2x gap, even though it is Java. Actual solution is in method solve() (as it is always the case with CHelper's code).

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

      It requires @google.com account :/

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

        Oh shi~, wrong pastebin :( Updated the link. (I would also be grateful to CF admins if they remove the previous revision of the comment)

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

      Thanks a lot. Now we have something to compare and can find out why our code is so slow.

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

Could someone please outline the alternative solution to problem F, which doesn't involve Karatsuba or FFT.

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

    There is one solution that passes the tests but is wrong:

    find k = c / (a+b-1)

    let G(i, j) = F(i, j) + k

    now G(i, j) = aG(i, j-1) + bG(i-1,j)

    find G(n, n) and use F(n, n) = G(n, n) — k to obtain final solution.

    solution fails on case where a+b-1 = 0 (mod 10^6+3)

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

      Thanks. Btw, when can we expect to see the problemset and test data? I'm looking forward to solving them.

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

    There are also solutions that work ;). To recollect, main problem is to compute sum . Let S(k) be sum of all summands such that i + j = k. We can note that it is almost true that S(k) = (a + b)S(k - 1). It is true for k ≤ n - 2, however for k > n - 2 you need to subtract two terms, which can be done in constant time (possibly after some precomputations of factorials etc.). Key argument here is of course

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

Explain please Div2 L(Larry’s Lemma)

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

Как реализовывать FFT в задаче F? Там же элементы до 10^6, а когда полиномы перемножаются, они становятся до 10^12, из-за чего сильно страдает точность. Даже на втором примере g(2) = 500002, f(2) = 500014, g * k (4) = 250008000028, а FFT находит 250008000031. Считать FFT в кольце по модулю 1000006, не получается, так как у него нет первообразного корня степени двойки.

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

    Если серьёзные проблемы с точностью, а времени хватает, то можно представить , , найти fb·gb, fb·gs, fs·gb, fs·gs с помощью вещественного FFT, а потом посчитать . Там коэффициенты уже порядка p получаются во всех четырёх слагаемых.

    Ещё можно считать по двум другим хорошим модулям с произведением больше 10^12, чтобы однозначно восстановить ответ по модулю p.

    Но у меня и так в long double зашло.

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

How to solve J?