HolkinPV's blog

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

Welcome, dear friends)

We are glad to introduce you regular Codeforces round #151 for Div.2 participants. Traditionally the others can take part out of the competition.

Today's problems were prepared by authors: Pavel Kholkin (HolkinPV) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for perfect Codeforces and Polygon systems and Mary Belova (Delinur) for translating the problems.

Score distribution will be standard.

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

UPD: the contest is over, hope you enjoy it)

Congratulations to winners:

  1. a58 (he solved all 5 problems)
  2. thangpc
  3. Minecraft
  4. xiaoshua3
  5. Noskov

UPD2: you can find the editorial here

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

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

Can you please fix the registration for Div.1 participants? We can't register out of the competition.

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

lets fun everybody :)))

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

    we want to register , watching others writing contest isn't very attractive :))

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

Div1 people are unable to register for the contest (unrated). Please fix this issue.

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

We are very lucky div2 participants. Sorry for you(div1) :D.

They will fix it,I am sure. Because many people wants it.

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

Fix please :D can't not wait until succesful register message appear :))))

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

all contestmakers are offline :(

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

I guess if Div 1 registration won't be fixed soon, there will be more new users than usual in this contest.

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

Good Luck everybody!

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

Don't worry, some of the contest authors will connect before the contest start because they have to check everything is ok, and they will fix it.

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

REGISTERED!!!

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

151 minutes before the start Codeforces Round #**151**,Good Luck everybody!

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

Thank god! I has just register succesfull :))

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

Lucky codings and hackings to everybody ;) Just Have Fun!

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

    sorry to say,but I don't like when someone says "wish you successful hacks",Simply say that I wish you success,sorry again if I said something bad,This is only my opinion.

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

      "wish you successful hack" it is not bad wish. It means you help someone who coded wrong to know that his/her solution wrong! If he/she didn't locked that problem he/she will resubmit it. Otherwise if he/she already locked that problem wil not wait for that problem while judging.

      If someone didn't hack your problem while you submitted wrong solution. You will think your solution is acceptable

      Hacker gain 50 more point for their goodness ;)

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

        Yup! I think so

        Just imagine that you submit, accept pretest but WA in the main test

        You may wish that somebody hack your solution and you will recheck your submission :)

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

gl & hf

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

good luck everybody, happy solving! :D

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

Hope server will stable today.

→ Reply
»
12 years ago, # |
  Vote: I like it -13 Vote: I do not like it
The comment removed because of Codeforces rules violation
→ Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I liked the problems, but they seem much easier than usual div2... Hope I am wrong and my solutions will fail full system test =D

Edit: nevermind, just figured out that my E solution is a complete failure. :D Edit2: YEAH! E failed with Time Limit on 60 =D

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

    You should not talk about your solutions during the contest: you give a advantage at the coders who are on the same room than you and who came here by saying that your E, if it isn't some bluff, has chance to be hacked.

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

      that's why I'm not even going to unlock it.. =D Anyway, I didn't say anything clear about it...

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

Could anyone explain it to me please:

Q(k) = {cu :  cu ≠ k and there is vertex v belonging to set V(k) such that nodes v and u are connected by an edge of the graph}.

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

Nice contest.

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

Can we give input with leadings zeros when it must be integers? I have seen a scanf("%i") on my room, but didn't know if I can hack him by giving integers like 033 who will be considered like a hexadecimal.

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

in how much time are the systests completed? EDIT: So, much negative votes just for asking a question!

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

Wow Amazing system testing speed.

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

In question D , the definition of Q(k) was quite mathematical , I could not figure it out correctly so got a lot of wrong answers.

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

perhaps it was better if problems C and D were swapped, for a more standard score distribution!

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

this contest was very good, one time it is difficult an one time it is fun :D :)))

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

will be the rating soon?? i cant wait, am nervious :D :D

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

What is the main idea of problem C? Though I could managed to make it accepted by randomized algorithm(2616018), but I think it's not beautiful...

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

2) n-1 times 2 (pairs with most beautiful)

3) n-2 times 3 (two most beautiful with others)
...
k) n-k+1 times k (k-1 most beautiful with others)
...
n) all of them
    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Sorry, I posted my solution in Russian, but forgot to translate it... First step. Let's print every soldier. Second step. We take the "beautiest" soldier and print him with every differrent soldiers. Third step. We take two "beautiest" soldiers and print them with every differrent soldiers. And so on. Obviously, all these sums are different (because of monotony). And thier number: n+(n-1)+(n-2)+...+2+1=n*(n+1)/2. Example of output:

    1
2
3
4
4 1
4 2
4 3
4 3 1
4 3 2
4 3 2 1

    Code

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

      I was wondering how to make sure that the total beauty is different from other combinations. Now it's clear. Thank you very much!

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

      banging my head on the wall after hearing the solun :(

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

    Randomized algorithm, cool =)

    Notice that k is at most n.(n+1)/2 Solution is to use the following values:

    (a[0]),(a[1]),...,(a[n-1]), (contains n detachments)

    (a[0],a[n-1]),(a[1],a[n-1]),...,(a[n-2],a[n-1]), (contains n-1 detachments)

    (a[0],a[n-1],a[n-2]),(a[1],a[n-1],a[n-2]),...,(a[n-3],a[n-2],a[n-1]), (contains n-2 detachments)

    ...

    All of these sums are different. Number of available detachments using this method = n + n-1 + n-2 + ... + 1 = n*(n+1)/2 so you will always be able to get k detachments.

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

    The randomized solution is much more beatiful for me :| I didn't implement it well myself though.

    2619137 — a fixed 50 percent probability was way too slow

    2621963 — a randomized probability makes the solution quite fast

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

    There exists a rather simple deterministic solution which has O ( N * K * ln ( K ) ) complexity. Traverse though the array and try to add current number to any of the possible sums and if you can make a non existing sum add it to the list of existing sums. Use a set to check if a sum exists or not in logarithmic time.

    Solution : 2616373

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

Problem D:

Please note, that you want to find such color, that the graph has at least one vertex with such color.

for the sample below

3 1

1 2 2

2 3

my output is 1, it passed system test though there is no vertex with color 1. i m still confused. o.O

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

    1 Vertex color is 1.

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

    you are confusing between vertex color and color of those vertices which are connected by edges. vertex 1 is colored by color 1 and hence it counts.

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

      vertex 2 and 3 has same color, so they are not "colored" => they have 0 colored neighbours, so as vertex 1 that has color 1. So the answer is 1.

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

Sorry if this seems to be a stupid question, but why is B's solution, n if sum mod n = 0, otherwise n-1?

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

    It's obvious that we always can make n-1 equal by adding or subtracting 1 from any other sacrifice-lamb element (e.g. n'th). If sum mod n == 0 then we can also do this for that last element, making all of them equal to sum div n.

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

    We can make an unlimited number of moves.

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

    1. n-1 is always possible: we can make a[2]..a[n] equal to 10000, decreasing a[1] at every step.

    2. If sum % n == 0, we can make all a[i] equal to sum / n. And it's obvious that we cannot make it otherwise.

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

    when sum%n==0, we can get n numbers, which will be equal to average. when sum%n>0, we can get n-1 numbers, which will be equal to average, and 1, which will be average+sum%n=)

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

    Thanks all of you.

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

it is frustrating to continuously check whether the ratings have changed or not after the end of a great contest...

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

    can the admins tell when the ratings will get updated??

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

      6 4 11 22 22 44 55 66 1 2 1 3 4 5 4 6 How about this data of problem B,, the right is 44 or not ?? Thank you !

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

        The right answer is 44 or not ?? Thank you ,,

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

      Ratings are updated now.

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

plz quiqly :(

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

Banging my head after solving problem C now :| I was using bit-masking and unordered_set in the contest and got hacked (TLE)! It couldn't pass the test cases though,, by the way,, very nice contest. Loved the problems. Tricky yet pretty simple solutions :)

One simple request,, found it bit hard to understand the problem descriptions,, a simple note and easy explanation could help us and save much time of us. Thanks :)

Sorry for my bad English.....

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

    I think there's room for improvement in the English Descriptions. Anyhow, they're always comprehensible.

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

What is the approach for problem E?

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

For E they said that Print m whitespace-separated integers — the answers to Polycarpus's records. But printed integers on new lines.

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

    Actually it doesn't matter, depending on the judge used. When we must print numbers, usually the CF system checks your output token-by-token, ingoring whitespaces and new lines.

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

which data structure should we use to find the number of different strings on a segment in problem E?

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

    http://mirror.codeforces.com/blog/entry/5935

    It's link to AC solution, which do it in such a way:

    1. At first calculate it in linear time.

    2. Cache the answer into some map and in future answer to the same query in O(logN) time.

    P.S. If you would like to read some prove of correctness, look at http://mirror.codeforces.com/blog/entry/5935 :-)

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

    For arbitrary queries [L, R] your may for each i precalculate next[i] (minimum j > i : a[i] = a[j]), and then answer to query will be number of i in [L, R] such that next[i] > R. In offline it can be calculated in using segment tree with sweeping line.

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

      Does it consists of sorting queries or you can get the answer for arbitrary query in o(logN) time ?

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

        "In offline" means, if I have m queries, I can get all m answers in time.

        Let our quries are segments [L..R], and array "next" is already calculated.

        for i = 1..N

        1. cnt[next[i]]++
        2. for all q : R=i increase answer[q] by Sum of cnt on [R+1..n+1]
        3. for all q : L=i+1 decrease answer[q] by Sum of cnt on [R+1..n+1]
        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          This can be done in o(N+M) time. You are always looking for sum on [r+1..n+1] so you can easyly change it in o(1) when you step to next i.Sum will decrease by cnt[i].and you will go to i+1.Looks like you will get LogN for binary search to transform V[i], K[i] into L[i],R[i].

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

            I'm sorry. Right version: R[q]. I thougt it's obviously =(

            → Reply