Igor_Kudryashov's blog

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

Hi to all!)

Regular round Codeforces #205 for participants from 2 division will take place today. Traditional, participants from 1 division can take part out of the competition.

The problems were prepared by Igor Kudryashov (Igor_Kudryashov) and Gerald Agapov (Gerald). Also thanks to Michael Mirzayanov (MikeMirzayanov) for very cool system Codeforces and Mary Belova (Delinur) for translating the problems into english.

We wish everyone good luck, high rating and excellent mood)

UPD: It is decided to use dynamic scoring system.

UPD 2: The contest is over, thanks to all participants.

Congratulations to the winners:

  1. hos_epic
  2. gzh1996n
  3. I_LOVE_ELE

UPD 3: you can find the tutorial here

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

Comments Comments (47)
| Write comment?
»
11 years ago, # |
  Vote: I like it -37 Vote: I do not like it

I will participate.

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

    THANK YOU! We are delighted to hear that.

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

will the scoring system be static or dynamic?

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

Next Round is on Sunday. Awesome!!!

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

The worst round I've ever performed. Sad... T_T

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

Does anyone know what B — test case 6 is about?

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

    People say, that your programm could fall down because of different count of bones on both bags.

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

    Try this: 4 99 89 88 98 89 88 89 88 This should give 9 as answer

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

    There's one apparent reason that contributed to B being as hard as it was: the answer is (number of different numbers in first half)*(in second half); if there's a number occuring at least 2 times in the input, we should choose one copy of it to each half, and for the remaining numbers (occuring once), we could put them into both halves in any way (then, we complete the halves by putting the remaining copies of the numbers occuring at least thrice, and it doesn't matter how we do that).

    But since we want the answer to be as large as possible, we need to put half of those once occuring numbers to one half ad the other half to the other — the answer is (x + a)(x + b), when there are x numbers occuring at least twice in the input and a + b occuring once, and that expression increases as |a - b| decreases. Proof by taking the zero of the derivative (when we allow ).

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

      I struggle if you mean (x + a)(x + b) & that expression increases as |a - b| decreases.

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

        Yeah, that's what I meant. I wrote it in a hurry, so typos are inevitable :D

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

          Excuse me, does that mean that if we just sort the numbers and then in a sorted array will put all the odd indexed elements in one heap and all even indexed in another and just count the number of different pairs, since n is not big, we have a correct solution?

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

            No. It fails on the array "1 2 2 2 3 4 4 4" — you put 1 and 3 in the same heap (answer=8), but you should put 1 in one heap and 3 in the other (answer=9).

            But if you try this approach separately on once occuring elements and separately on multiple times occuring ones, it works.

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

              Yeah, now I see. Thank you very much! :-)

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

            consider:

            1 2 2 2 3 4 4 4

            you'll get
            8
            1 2 1 2 1 2 1 2

            while correct answer is

            9
            1 1 2 2 2 2 1 1

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

    That is the 6th system test, which falls down my prog till now:

    50

    49 13 81 20 73 62 19 49 65 95 32 84 24 96 51 57 53 83 40 44 26 65 78 80 92 87 87 95 56 46 22 44 69 80 41 61 97 92 58 53 42 78 53 19 47 36 25 77 65 81 14 61 38 99 27 58 67 37 67 80 77 51 32 43 31 48 19 79 31 91 46 97 91 71 27 63 22 84 73 73 89 44 34 84 70 23 45 31 56 73 83 38 68 45 99 33 83 86 87 80

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

thanks for this great contest .......!!

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

What is the intended solution for E?

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

It was fastest system testing i've ever faced on Codeforces.

Whole system testing phase just took 8 minutes. Codeforces Rocks!

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

    May the rating changes take just as long next time :D

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

very good and fast system testing today! :)

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

First time I solved 4 problems during a contest on codeforces :-D

I'm happy although it's unrated for me :-) Thank you for preparing this contest!

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

I joined late , problem C is very interested .. isn't it guys ?

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

    Yeah, well the whole round was interesting. I like D most, though.

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

How solve the problem B??

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

    You can solve B with greedy assignment of the blocks.

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

    My solution: 4730199

    Idea:

    To solve problem B, you should put the number in balance (n numbers to heap 1 and n numbers to heap 2), to make the number of distinct 4 digit number maximum, if there are same number, say there are i number x (i>1, if i=1 it considered unique number that will be processed later), you should put (i div 2) number x into heap 1 and (i div 2) to heap 2, and if there are remainder (i is odd), save to heap 3 temporaryly (will be processed later).

    After that process the rest unique number (i=1) into heap 1 and heap 2 equaly, if there are j unique number, put (j div 2) to heap 1 and j-(j div 2) to the heap 2. And then the rest (heap 3) will fill heap 1 and heap 2 until full (have n numbers each, the order isn't important)

    Finally count the distinct number in heap 1, save to variable a and heap 2 to variable b, and the total distinct 4 digit number is a*b. and then just print the output.

    If there are more simple solution I would like to know :-)

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

Lot's of DP problems. Love that contest though i miss A for some silly mistake. :( (Y)

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

    Actually any of this the problems may be solved without DP (except, maybe D, where solution could be called DP, but I wouldn't call it so)

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

Any ideas of around when the tutorial will be published?

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

Awesome round. It is always a surprise when scoring goes dynamic. #Enjoyed. Looking forward for more matches of this kind.

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

it was a awful contest!!!

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

It is 70 minutes after the contest now and ratings are not published yet...

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

how the system testing is so fast and the rating is so slow? Isn't harder to judge than to update the rating? Maybe I'm wrong, but it would be nice to know.

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

    maybe checks all solutions to find cheaters .

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

dynamic scoring system and dynamic problems ! thank you

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

Update: The original comment is my mistake.

(353B - Two Heaps, test 6)
I think Problem B judgement is wrong (the checker issues false negatives for some valid solutions).

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

    In the problem statement there is a phrase:

    "He arbitrarily chooses n cubes and puts them in the first heap. "

    So it IS necessary that the heaps have the same size.

    → Reply