### agul's blog

By agul, 10 years ago,

Привет, расскажите, пожалуйста, задачи A, B, H.

• +31

 » 10 years ago, # |   0 Div.2 easier string problems N4 [C--] and O4 [Allo] using Perl as higher-level language (C--, Allo).
 » 10 years ago, # |   +13 It seems that problemset from CERC 2014 was used today, but with renamed and shuffled problems.Here you may find standings from original contest; i guess that mapping between problems is following: CERC Opencup A C B L C E D F E G F D G B H K I J J I K H L A Announcement at CERC site says that the contest data (problems, tests, and model solutions) will be posted at Sunday, November 23. — i guess Opencup was a reason for such a delay:) And we'll see solutions published soon.
 » 10 years ago, # |   0 How to solve E4 Exress As The Sum: faster than O(t * N ^ 3/4) ?, N = 10^9, t — unknown amount of tests. TL.
•  » » 10 years ago, # ^ |   +1 We can represent our segment as [x + 1, ..., x + k]. The sum equals to , so now it's clear that . Now we can iterate over all possible k.
•  » » » 10 years ago, # ^ | ← Rev. 3 →   +1 We can also show that the smallest k satisfying the equation is either a prime or a power of two. So it is sufficient to iterate over all primes and all powers of 2 less than or equal to The primes can be precomputed using Eratosthenes sieve. This gives total complexity of π(N) (the number of primes less than N) can be approximated as N / log(N).The approximation gives total complexity which is a little better than . Actually my solution in received time limit exceeded and the optimization above helped to get it accepted. Maybe this is because I am using slow Ejudge server and it makes even the simplest problem more interesting:)Accepted code (a little ugly, I call 2^n a prime:): http://pastie.org/9739170
•  » » » » 10 years ago, # ^ |   0 I haven't realized that we need no only primes, but primes**2 also. So I used all numbers from 2 to sqrt(N), but now I've written with primes, but still getting TL on tc 2. Can't understand why. (code). Ideone says, that such primes are generated in 0.1 sec (and there are 4.7k of them). And I can't understand what can be the biggest interval of numbers?
•  » » » » » 10 years ago, # ^ | ← Rev. 8 →   +1 1) We do not need primes2, we need powers of two; i.e., 21, 22, 23, ..., . Your code gives incorrect result for 999990008. The answer should be 999990008 = 62499368 + 62499369 + 62499370 + 62499371 + 62499372 + 62499373 + 62499374 + 62499375 + 62499376 + 62499377 + 62499378 + 62499379 + 62499380 + 62499381 + 62499382 + 62499383 (24 = 16 elements)2) I don't know Perl, but I couldn't get my Java solution working. 1 second time limit seems rather strict. Probably you should try C/C++.
 » 10 years ago, # | ← Rev. 2 →   +1 .
 » 10 years ago, # |   -22 hello,where is the place to see and submitt the problem
 » 10 years ago, # |   0 hello,could some friend share the statements of the open cup gp of europe div2,thanks very much,my email is [email protected]