Igor_Kudryashov's blog

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

Hi to all!)

Codeforces #143 for participants from second division is going to be today. I think, it is not necessary to remind, that coders with rating greater than 1699 will be able to take part out of the competition.

Problems' autors for this event are Kholkin Pavel (HolkinPV) and Kuznetsov Nikolay (NALP). Kudryashov Igor Igor_Kudryashov and Agapov Gerald (Gerald) helped in contest's preparation too. Special thanks to creator great resource Codeforces Mike Mirzayanov (MikeMirzayanov) and our translator Maria Belova (Delinur).

Score distribution will be determine later, monitor for changes).

We wish you enjoy participating this competition and want you to get something new and useful.

UPD: Score distribution will be standart 500-1000-1500-2000-2500.

UPD2: Round is over. Thanks to all for participating. Six first coders solved all 5 problems, congratulations.

1) teoy

2) gomineral02

3) mrNobody

4) Ryannnnnnn

5) marschenly

6) KuchumovIlya

Editorial will be published soon.

UPD3: Editorial is published, you can find it here

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

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

270 new user and keep growing.

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

First Codeforces round on Sunday since a long time!!! This should happen more frequently!! Thanks to authors!!! Good luck to new users!!

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

    Thank, U for this words "Good luck to new users!!!".

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

Was Problem D really that easy or have I done some mistake ??My code

If I am correct then I think the problems should have been aranged as A , RightShift( B,C,D ) ,E

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

    I agree with you. But I appreciate it as a test to come up with such an easy idea for a problem of 2000 points after writing harder solutions for 1000/1500 :-) [I am aware that those who open D first have got extra points ;-)]

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

    I´m totally agree with you problem D was really easy and problem B was a little bit tricky

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

Really nice competition, though it was kinda surprising that the 4-th task was solved by 6 IF-s, i mean at standart score distribution it's expected to be sorted by difficulty. :)

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

What an amazing Round. 5 Problems are very nice. Thank Authors very much :)

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

any simple solutions of B?just some words about solution pls

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

    Well you can notice that the number that's resulted at the end is a1-a2+a3-a4+a5... where 'a' are the numbers from the initial array. And i suppose you can find em easily knowing that, didn't have enough time to realize that solution.

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

      yes had exactly the same idea,but somehow could not realize,my bad...

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

    S1=x1+x3+x5+... S2=x2+x4+x6+... n1=n div 2+(n mod 2) n2=n-n1 d=S1-S2 n1<=S1<=l*n1 n2<=S2<=l*n2

    Look over possible S1 and S2 values. If it is possible to take such S2 and S1 that d=S1-S2 then answer exists else it doesn`t. In case of its existance some efforts to output the sequence are required.

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

the order should be A,D,B,C,E

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

Nice problem set and competition, though, I believe System test was fast because of El Clasico :D

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

Hi! How can this submission get AC on problem C: http://www.codeforces.com/contest/231/submission/2319083 But it gets the wrong answer on this test:

10 0
1 2 3 4 5 6 7 8 9 10

Correct output must be: 1 1, but its result is 2 2. Is the test case weak ?

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

The problemset was good. Not very easy and not very hard. Liked it really much.

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

Has anybody here solved B using Dynamic Programming?

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

    yes.

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

      Great. I thought it was too slow to get Accepted. The time complexity is nearly O(10^8). However, I got AC.

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

        If time complexity is O(10^8) be sure you'll get AC. :D UPD: Of course on Codeforces

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

          I don't know, i've got a lot of TLE's with time complexity O(10^8). Before SPOJ gets a faster processor, it was a bit hard to get AC with this time complexity. Anyway, CodeForces has a fast judge.

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

Great competition!

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

very nice problem set, thank you very much ^^

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

I think there were lots of WA's on problem C. Maybe reason is there were no alert about not using %lld specifier on C++. So lots of people didn't use 64-bit integer. and maybe 64-bit integer was not neccessary on authors solution.

UPD: The only thing different with this comment and mine is downvotes and upvotes :D

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

    Numbers that you need to find are fit in 32-bit type, so I think the warning about %lld was not necessary.

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

    I made 2 successful hacks on submissions which did not deal with overflow in multiplication. It seems to be the most common mistake I think.

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

……

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

I really got surprised when I saw problem B is dp, ...!

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

    Greedy is accepted too.

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

      How can we Dp problem B. Can you show me ???

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

        dp f[i][s]=true means that where are a[0]...a[i] left after some operations(a[i] is not the origional one), and a[i]=s(probably negative)... we can enumerate a[i] from 1 to l to check if condition f[i+1][s2] is true, here (s = a[i] — s2).finally check if f[n-1][i] is true for some i from 1 to l

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

The hyperlink of editorial is linked to russian editorial again:( hope you can fix it:)

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

I think that problem C was extremely harder than problem D!

→ Reply