agul's blog

Opencup GP of Europe
By agul, 10 years ago, In Russian

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

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Div.2 easier string problems N4 [C--] and O4 [Allo] using Perl as higher-level language (C--, Allo).

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

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.

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

How to solve E4 Exress As The Sum: faster than O(t * N ^ 3/4) ?, N = 10^9, t — unknown amount of tests. TL.

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

    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.

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

      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

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

        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?

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

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

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

.

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

hello,where is the place to see and submitt the problem

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

hello,could some friend share the statements of the open cup gp of europe div2,thanks very much,my email is zgjx0802@sina.com

→ Reply