HolkinPV's blog

Codeforces Round #166 (Div. 2)
By HolkinPV, 12 years ago, translation, In English

Good day, friends)

Soon is coming regular Codeforces round #166 for Div.2 participants. Traditionally the others can take part out of the competition.

And again the problems were prepared by the group of authors: Pavel Kholkin (HolkinPV), Nikolay Kuznetsov (NALP), Rakhov Artem (RAD) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces and Polygon systems and Mary Belova (Delinur) for translating the problems.

UPD: Score distribution will be not standard a little bit — 500, 1000, 1500, 2000, 3000.

We wish everyone good luck, successful hacks and high rating)

UPD2: the contest is over, we hope you enjoy it)

Congratulations to winners:

1) xrvpud221
2) xyz111
3) nanoha
4) wyx528
5) GuyUpLion

UPD3: the editorial is published, you can find it here

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

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

This group always offers good problems...!!!

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

MikeMirzayanov's contribution is +210 O_O

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

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

    Такие все шутники) но иногда приятно) ставлю плюс)

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

its time

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

Hi authors, Problem C div2 says that any alternative solution is accepted. So this answer for test: 11 3 11122233123 shouldn't be accepted?

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

    It should, but you should have printed the blank spaces between each number...

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

    if we divided in three group it will be:

    • 1 2 3 9
    • 4 5 6 10
    • 7 8 11

    all 3 of the sequence is not an arithmetic progression

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

for all who had WA #8 in problem D,I think the test case is

abaab 01 2

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

    and what do you say abt TLE + memory limit exceeded for D.

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

The problems were excellent! The problem-setters deserve a round of applause.

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

Nice problem set, the writers managed to come up with balanced problems, got 4 out 5.

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

waiting for rating update .....

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

In problem D, I use 2 hash value with int always get wrong answer on test 41, and my answer always is 241238 (the right is 398680), and I use long long with same hash numbers get accepted. Why there is so big difference between them ? Many helps !

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

    I just exchanjed power of prime number from 31 to 29 and 37, then got accept.

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

      You guys use hash without handling conflict, and still got ACCEPTED! How unfair... I found a nice c++ solution(3100030) in my room that use set<string>, and the worst time complexity is O(n^3 log(n)), still very nice, though.

      My first attempt was a Python solution using a Trie, which is O(n^2). It got TLE, saddly. Then I was forced to translate the Python script into C++.

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

        I used suffix array with time complexity O(nlog^2n) in building the array and O(nlogn) for the rest.3108063 This is totally unfair that even solution with time complexity O(n^3logn) can be accepted. The test case should be bigger, say string of length 1000,000.

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

          When the data scale is too large, we will lost some interesting solutions. It's also unfair for some dynamic languages since a loop with 1000000 times may cost about 1 sec. So I think 10^3 or 10^5 is fine.

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

After participating in some contests here, now, I confess that I'm not clever enough as I thought I am :( I'm not sure if continue to participate will make it better; I even can not get to 1700 :(

Any friend has an idea about why I'm not successful here as much as my successful in business software development (I am Microsoft Visual C# MVP 2011)?!

I just like to know if I should continue or break to study more and then come back.

Thanks in advance!

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    1. Being successful in X does not automatically mean being successful in Y.
    2. Why take a break? Theory is nothing without practice. Study more and compete in contests.

    Remember… practice makes perfect.

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

    It is a wonderful place to get knowledge and I don't have a great result but I am trying to be better day by day here.

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

Anyone willing to share an idea for problem E?

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 5   Vote: I like it +6 Vote: I do not like it

    My idea was based on this observation:

    Suppose that y=x+k

    What we really care for is the difference between a pair of numbers (the k).

    (because we can get (a+1,b+1) and (a-1,b-1) from (a,b) )

    The first horse does not change the difference

    The second horse divides the difference (k) by two

    The third horse gets two pairs with differences = k1,k2 and gives a pair with difference=k1+k2

    (The rest is simple NT -divisibility, gcd,etc.- )

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

      I thought with the same idea in the contest but actually first horse give (a+1,b+1) form (a,b) but don't give (a-1,b-1)

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

        (a, b) -> (b, 2 * b — a) -> (a, 2 * b — a) -> (2 * a — 2, 2 * b — 2) -> (a — 1, b — 1)

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

Thanks to the creators , for making the catching stuff in the questions BOLD, it really helped!!

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

Unfortunately I missed the contest.. Was celebrating my birthday

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

its showing me blue color but with old rating :( :( yyyyyyyyyy so ?

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

It's showing me blue but with older rating 1448 :( why ???

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

Could someone explain Div2.E problem body? As I understand:

  1. We start with singleton, S = {(x,y)}.
  2. Given some set S of cards, we pick one card (x,y) from S, perform 1 of 3 operations(in third operation we would take two cards), and get new card (x', y')
  3. S now contains both (x,y) and (x',y') We want S to include some subset P.

But it surely isn't correct understanding.

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

Anyone willing to share an idea for problem D without hash? Thanks a lot.

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

    prefixs + substrings + set = 3103424

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

      thankyou

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

      please explain how could this pass?

      you have 2 "for" and inside them you have "substr" which has complexity O(j-i) so your total complexity is O(N^3)

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

        You are right, but it has a low constant, so 2 "for" and "substr" inside them take only 350 ms on a string with length=1500.

        Also working with set we have total complexity O(N^3*ln(n)), because comparing the string takes O(N). But it is also with low constant and is unattainable, because not all substrings are comparable in full length.

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

Four of the winners took part in Codeforces contest for the first time,the rest one only took part twice....

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

    I'm sure they are multiple accounts

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

    Absolutely agree,in most contests there are about 2-3 unrated winners,maybe I'm mistaken but I think they are multiple accounts

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

One question: the limit for the Div2 B were n,m <= 500, but what is the point to have such limits, when the max size of test file for hacking is just 256 KB? I mean there were a lot of solutions that could be hacked using a matrix of size 500 x 500, but it wasn't possible because the system won't accept files that big. Many solutions were done in O(n*m*nextPrime(x)) and I think this wasn't the complexity intended to solve this problem. An acceptable one would be done in O(n*m*log(closestprime(x)).

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

    you have to write code to generate test-cases you want ,not the test-case itself

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

    nextPrime(x) factor is extremely small ~ O(log x), so it's just looking for 20 consecutive bytes of memory. Bad binary search could be slower.

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I was using n^2(log(n)) approach for this question but don't know why 283113903 this submission was giving tle in test case 21 can somone help

→ Reply