Temirulan's blog

Opencup Grand Prix of Europe (CERC 2015)
By Temirulan, history, 9 years ago, translation, In English

Let's discuss problems.

How to solve E and F.

  • Vote: I like it
  • +13
  • Vote: I do not like it

Comments Comments (24)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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.

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

    What about 10^5 queries?

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

      Sort them and answer query in time when graph is in conditions described by it.

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

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

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

    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

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

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.

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

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 )

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

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.

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

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

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

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

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

      It requires @google.com account :/

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

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

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

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

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

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

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

    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)

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

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

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

    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

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

Explain please Div2 L(Larry’s Lemma)

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

How to solve J?

→ Reply