Temirulan's blog

By Temirulan, history, 22 months 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  

»
22 months 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)

»
22 months 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.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What about 10^5 queries?

    • »
      »
      »
      22 months 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.

»
22 months 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"?

  • »
    »
    22 months 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

»
22 months 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.

»
22 months 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 )

»
22 months 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.

»
22 months 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 :(

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

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It requires @google.com account :/

      • »
        »
        »
        »
        22 months 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)

    • »
      »
      »
      22 months 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.

»
22 months 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.

  • »
    »
    22 months 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)

    • »
      »
      »
      22 months 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.

  • »
    »
    22 months 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

»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Explain please Div2 L(Larry’s Lemma)

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can I submit for practice?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve J?