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:

**UPD2**: you can find the editorial here

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

I have the same problem.

It works now, thank you.

lets fun everybody :)))

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

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

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

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

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

all contestmakers are offline :(

:D :D hahaha

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

Good Luck everybody!

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.

REGISTERED!!!

151minutes before the start Codeforces Round #**151**,Good Luck everybody!Thank god! I has just register succesfull :))

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

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.

"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 acceptableHacker gain 50 more point for their goodness ;)

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 :)

you are right,sorry for my comment. so WISH YOU SUCCESSFUL HACKS!!!

gl & hf

thanks

Waiting for a competitive contest. Also expecting a good problemset.

good luck everybody, happy solving! :D

Hope server will stable today.

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

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.

that's why I'm not even going to unlock it.. =D Anyway, I didn't say anything clear about 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}.

Nice contest.

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.

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

Wow Amazing system testing speed.

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.

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

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

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

still no rating change...

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...

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:

Code

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

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

Same here(

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.

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

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

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

1 Vertex color is 1.

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.

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.

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

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.

We can make an unlimited number of moves.

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

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

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=)

Thanks all of you.

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

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

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 !

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

Ratings are updated now.

plz quiqly :(

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.....

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

What is the approach for problem E?

First, solve the original version. http://codeforces.com/search?query=130&_tta=375

For E they said that

Print mBut printed integers on new lines.whitespace-separated integers— the answers to Polycarpus's records.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.

Thanks. I didn't know that.

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

http://codeforces.ru/blog/entry/5935

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

At first calculate it in linear time.

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://codeforces.ru/blog/entry/5935 :-)

For arbitrary queries [

L,R] your may for eachiprecalculatenext[i] (minimumj>i:a[i] =a[j]), and then answer to query will be number ofiin [L,R] such thatnext[i] >R. In offline it can be calculated in using segment tree with sweeping line.Does it consists of sorting queries or you can get the answer for arbitrary query in o(logN) time ?

"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`

`cnt[next[i]]++`

`for all q : R=i`

increase`answer[q]`

by Sum of`cnt`

on`[R+1..n+1]`

`for all q : L=i+1`

decrease`answer[q]`

by Sum of`cnt`

on`[R+1..n+1]`

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].

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