Due to technical reasons Codeforces may be unavailable on April 21st from 01:00-07:00 (MSK). ×

Temirulan's blog

By Temirulan, history, 3 years ago, translation, ,

Let's discuss problems.

How to solve E and F.

•
• +13
•

 » 3 years ago, # |   0 Auto comment: topic has been translated by Temirulan (original revision, translated revision, compare)
 » 3 years ago, # |   +5 E — sort edges in descending order. Then add edges one by one keeping number of: Vertices with degree = 0 (v0). Vertices with degree = 2 (v2). Connected components which are one whole cycle. (cycle). Then numv = v - v0 - v2 + cycle and nume = eadded - v2 + cycle.
•  » » 3 years ago, # ^ |   0 What about 10^5 queries?
•  » » » 3 years ago, # ^ |   0 Sort them and answer query in time when graph is in conditions described by it.
 » 3 years ago, # |   0 How to solve div.2 B — "B. Book Borders", I've got TLE. And div.2. D — "D. Digit Division"?
•  » » 3 years ago, # ^ |   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
 » 3 years ago, # |   +22 Here are the slides from the solution presentation held onsite: https://goo.gl/6IFvGQThey don't describe solutions in great depths, but hopefully you can get some hints from the slides.
 » 3 years ago, # |   +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 )
•  » » 3 years ago, # ^ |   0 Or u could just copy it from input
•  » » » 3 years ago, # ^ |   0 You coudn't fast-copy chunks of 7 x 5 from input, you copy whole 7 lines.
•  » » » » 3 years ago, # ^ |   0 w/e
 » 3 years ago, # | ← 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.
•  » » 3 years ago, # ^ |   +19 It's not a bug, it's a feature =)
 » 3 years ago, # |   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 :(
•  » » 3 years ago, # ^ | ← 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).
•  » » » 3 years ago, # ^ |   0 It requires @google.com account :/
•  » » » » 3 years ago, # ^ |   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)
•  » » » 3 years ago, # ^ |   0 Thanks a lot. Now we have something to compare and can find out why our code is so slow.
 » 3 years ago, # |   +5 Could someone please outline the alternative solution to problem F, which doesn't involve Karatsuba or FFT.
•  » » 3 years ago, # ^ |   +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) + know 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)
•  » » » 3 years ago, # ^ |   +8 Thanks. Btw, when can we expect to see the problemset and test data? I'm looking forward to solving them.
•  » » 3 years ago, # ^ | ← 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
 » 3 years ago, # |   +1 Explain please Div2 L(Larry’s Lemma)
 » 3 years ago, # |   0 Where can I submit for practice?
 » 3 years ago, # |   0 How to solve J?