gridnevvvit's blog

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

Hello!

A few hours later, 25 апреля в 19:30 MSK, you are lucky to participate in Codeforces Round #181 for Div. 2 participants. Traditionally, Div. 1 participants can take part out of the competition.

Problems have been prepared by: Gridnev Vitaliy (gridnevvvit), Ignatyev Alexander (aiMR). We want to thank Gerald Agapov(Gerald) for help in preparation of this round, Michael Mirzayanov(MikeMirzayanov) for marvelous Codeforces and Polygon systems, Mary Belova(Delinur) for translating the problems.

About authors: me and Alexander are third year students of Mathematics Department, Saratov State University. It’s our first round and I hope not last.

We hope you will like these problems, and that it will be fun to solve them.

Also we strongly recommend you to read all the problems.

We wish everyone good luck and high rating!

UPD: Scoring will be dynamic. Problems are sorted by increasing order of difficulty.

UPD1: Editorial here

UPD2: Contest finished. Congratulations to winners:

  1. ballmaids02
  2. VIProgrammer
  3. emachaidze
  • Vote: I like it
  • +164
  • Vote: I do not like it

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

Can't wait, hopefully it won't be too much maths :D

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

a

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

I think it will be interesting.

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

Good Luck ^_^

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

I hope the system testing starts soon after the contest not like the last contests.

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

    System testing after contest starts when authors of task check all hacks.

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

      I think it's not true because all hacks are checked automatically by validator.

      I suppose that main reason of our waitin' is that validator checks all the hacks.

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

Welcome ! New authors always have interesting problems I think today it will be too :)

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

One of the best announcements I ever read !!

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

i hope today will be my day :))

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

gl & hf all! :)

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

This is my first contest in codeforces, hope i can solve some problems in the contest

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

Hello, I'm Commander Sheppard and this is my first contest on Codeforces!

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

Hope to solve at least 3 problems :)

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

what'er pity not joinning this contest= =..dynamic scoring could be really exciting and fun T____T...hope to reach 1700 T_T

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

WTF???
UPD: he has already -179 hacks...
→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Codeforces was down. But how could lrb know about it? He was sure that the solution was incorrect. He pressed and pressed the button Hack! but nothing was happening. "Ok, I'm going to count how many times I pressed that damned button!", he thought: "66, 67, 68! Codeforces is available again! Let's see where my +100 points are..."

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

    Now he has 215 unsuccessful hacks

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

    Психанул!)

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

    When I saw that lrb wanted to hack my code my heart started boom boom boom:)I thought that my solution is wrong:)but when i saw that he has more than 100 unsuccessful hacks i understood that he want to break record and i calmed down:)

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

    우리의 위대한 지도자 김 장군의 명예에, 나는 미국 제국주의를 정복 할 수있을만큼 우리 민족 강하게 만들기 위하여 열심히 컴퓨터 과학을 공부합니다!

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

what is the 5th test in B problem??? "@

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

Hey, really enjoyed this competition, but i got a little problem with problem C. So im asking you for little help.

Here is what i came up with: We generate all possible sums ( highest possible sum has 6 digits ) and make equation

N = x*a + y*b, where N is our sum ( we do this with every generated sum ).

And we find number of solutions to this equation that: x>0, y>0 and a+b<=N ( it's pretty

clear ).

For most of my time i was trying to come up with some nice dp solution, but it turned

out to be impossible for me... If it's one right solution desribed above, then please explain to me how to calculate

those all solutions nicely?? Because for me it got too messy and i finished with only 2

first tasks :(

:) Thanks in advance

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

    I think that answer is sum(C(n, x)) if N = x*a +y*b is good, but there is small problem for me, how fast and correct calc C) Sorry for my bad english.

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

    n!/(x!*y!) — number of different numbers of length n and containing x of "a" digits and y of "b" digits.

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

      You can use this : C( n , k ) = n! * pow( (n-k)! * k! , mod-2 )

      from the "Number Theory" : (1 / b) % mod == ( b^(mod-2) ) % mod , because mod is a prime number !

      Sorry for my bad english

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

        i knew there is must be using some number theory, but, sadly after knowing a and b value, i cant compute C(n,a)

        could you explain more with n = 14215 and k = 13517 ?

        thx (taken from test 3 )

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

          only pre-calculate every factorials module 1000000007 and store this numbers in an array .( for example fact array ) this step takes O(N) time and space .

          then C( n , k ) = fact[n] * power( fact[k] , mod-2 ) * power( fact[n-k] , mod-2 ) . this step takes O( Log N ) .

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

            or calculating c(n,k) using c(n,k-1) c(n,k) = c(n,k-1)*(n-k+1)/(k)

            but as Reza said, we have to pre-caculate them.

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

              actually this wont work !

              because there is no necessity that c(n,k-1)%MOD or (n-k+1) is divisible by k.

              this will lead you to WA.

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

                of course!

                i didn't mention that for dividing u need to use modular division, i just said that this is another way tu calculate c(n,k)...

                for dividing u can use pow(k, mod-2)(as Reza said) or use Extended Euclid algorithm :

                // ax + by = gcd(a,b) = d
void eea(int a, int b, int& x, int& y, int& d) {
    if (!b) {x = 1; y = 0; d = a; return; }
    eea(b, a % b, x, y, d);
    int x1 = y, y1 = x - (a / b) * y;
    x = x1, y = y1;
}
int divide(int a, int b) {
    int d, x, y;
    eea(b, MOD, x, y, d);
    // if(a%d==0)
    return ((x+MOD)*(a/d)) % (MOD/d);
    // else   "no quotient"
}

                both run in O(logn) time. however, pow(k,mod-2) is a lot easier... ;)

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

                  so that was my fault, I misunderstood you. :)

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

        "from the "Number Theory" : (1 / b) % mod == ( b^(mod-2) ) % mod , because mod is a prime number !"

        Could you provide references to this proof?

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

          from "fermet's little theorem" : a^(p-1) % p = 1

          thus a * a^(p-2) % p = 1 and a % p == a^(p-2) % p from other view a * ( 1/a ) % p = 1 and a % p == (1/a) % p

          finally : (1/a) % p == a^(p-2) % p

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

    the same idea, but a little bit differences. x is the number of digits a still have sum=a*x+b*(n-x) (a,b from input), for each single value of x, i check whether sum is a good number. if yes, calculate number of numbers you can create with that.

    the only problem that i had is the final step.

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

I can't believe that my B is going to fail because I forgot to check if the "connected-team" size is less than or equal to 3, submitted and locked it. Just after I locked it I remembered that. :(

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

I think the problem more difficult than before.. a lot of counter testcase..

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

I loved the contest, especially C, got it accepted at the last minute (stupid overflow mistake :(). This is when you have to love the dynamic scoring :)

Thanks!

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

When is the rating come out??

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

Nice contest, keep up the good work.

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

The problem A — Array in the description it guarantees a correct solution: 1st list -product should be negative 2nd list — product should be positive 3rd list — product should be zero

where as your pretext 3 test case is : Input 5 -1 -2 1 2 0 Output 1 -2 3 -1 1 2 1 0

This is incorrect. List 2 doesn't have a positive product. -1 * 1 * 2 = -2 is NEGATIVE. WRONG TEST CASE.

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

    It's your output, not jury's.

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

    ohh.. sorry.. got it now. i read it in the incorrect order... thanks.

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

what's the idea of problem D

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

UPD :

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

Hey a newbie question but I can't seem to find it in the FAQ or anywhere

How long does it take for ratings to change after a competition?

I go back to sleep right after matches (I'm in Austrlia) so I don't find out.

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

my first contest still rating is not updated ? why always me ?

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

    Your rating will be updated soon..it takes little time to update ratings. Happy coding :)

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

Problems were quite interesting.Hope to see you again soon.

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

this round was better than I expect !

→ Reply