Hi, everyone!

Regular Codeforces round #273 for participants from the second division will take place on 16 October, 19:30 MSK. Participants from the first division are able to participate out of the contest.

Problem setter: KhaustovPavel (Khaustov Pavel, Russia, Tomsk, Tomsk Polytechnic University)

Special thanks to Codeforces team and, in particular, Maxim Akhmedov (zlobober) for help in round preparations and Maria Belova (Delinur) for translations.

Participants will be given five problems and two hours to solve this problems.

**Points distribution: 500-1000-1500-2000-2500**

**UPD: +10 minutes to start**

Good luck!

zlobober has contribution +125. But why he isn't in top contributors?

For the same reason as MikeMirzayanov. He is a member of Codeforces team.

emm..ok..so why Gerald is in contributors list? He is member of Codeforces team too.

My prediction: It looks like Gerald has left codeforces and zlobober has joined in place of him.

P.S. Another interesting argument to support the speculation: See submissions of Gerald on topcoder last SRM and last to last SRM. In the last SRM, he did not include the footer having a note about contacting him for problem creation which he usually does.

What about Fefer_Ivan?

Bad luck to everyone , because I want to be first at ranking. I gotta have the only good luck in participants.

rip in pepperonis kursatba324's contribution.

He is the author of the most-downvote comment on Codeforces

Exactly -600 :D

How is possible?I downvoted one minute ago.And also is -600.

Maybe -600 is the lower bound of downvoting.

It seems like it would be a lot of programming with no math

You meant a lot of math with no programming right? Because that's two different things.

So I guess no math this time :(

insert sad music hereI believe you mean:

insert*happy music hereWow, apparently other people share my ideas as well :o

As it turns out,

allproblems are math (with some programming)...REVENGE!!!

Also, I noticed that usually when competitive programmers say "mathematics", they mean "number theory" :P

Combinatorics (counting) is also common. I think D is combinatorics?

Other fields of mathematics are hard to use in computer programming. I once made an algebra/geometry problem of sorts (given three points on plane, find a line that minimizes the sum of distances from the points to the line), but those kinds of problems are hard to find.

Sure, dp/greedy are all combinatorics and so, are essentially mathematics. The point I was trying to make is that many people don't accept this and according to them, mathematics problems means problems involving numbers and equations. So, if some such guy says that some contest was full of math problems, it means that it was full of number theoretic or elementary algebra problems.

you know you are in a math oriented contest when memory of your first 3 solutions is 0 Kb.

Most of programming doesn't involve math at all: look what typical job postings say.

Looked to become Blue Coder

:D

Это баян :D

GOOD LUCK & HAVE FUN!!!With the timing of this round, does it mean we won't have a gym training this week or it will be moved to another day?

Your last contest had nice problems.

Thank you for creating another contest.

Darn, I wonder how you would know..

Hello. This is my second contest on Codeforces and strangely, I don't get an option to register for this round. Any idea why it's so?

Registration will be opened later (see on Contests tab).

My bad. Timezone confusion. Thanks!

I'm registering the first :P

Thank you for earlier registration opening! ;)

How do I get contribution scores? Thanks.

by not getting downvotes

no, by getting upvotes

No, by getting ~1.5 times more upvotes, than downvotes.

from here

so I guess only MikeMirzayanov knows the exact answer to this question.

Thank you very much!

THX~

THX~

THX~

Strangely nobody has answered your question in details. To get contribution scores you can try to:

write editorials for the round which do not have any.

prepare a CF round or at least a gym contest. Announcement might bring a lot of contribution points, though it depends on the announcement.

post some funny jokes on CF. This seems to be the most effective way but you need to stay on-topic while posting the jokes.

maybe write some good programming related articles here? Didn't try this one though.

Thank you very much!

Meta-jokes are the most effective

Please give the score distribution just 20 mins left.

standard

got it thanks

Delayed

Delay :/

nehrena ne rabotaet :\

Those who cannot remember the past are condemned to repeat it. By Dynamic Programming How many up votes for Dynamic Programming??

I registered for the contest but still couldn't submit as if I wasn't registered. This has happened with my friend once too. Some bug. admin please fix! -_-

Problem C = a bunch of hacks.

How to solve D?

You find the maximum possible height (approximately ) and do dynamic programming:

DP[h][r] = the number of possibilities to build the tower with heighthand usingrred blocks (andh* (h+ 1) / 2 -rgreen blocks).I saw some faster solution. This one looks easy to TLE(Although I used this one and locked)

so O(r * sqrt(r)) will pass? :O

It passed for me ^^

h <= 900 r <= 2 * 10^5, long long dp[900][2 * 10^5]. Won't it be a memory or time limit?

The recurrence only uses the previous line, so we don't have to keep the whole matrix.

dynamic line-by-line needs only O(max(g,r))memory

Can it be solved using the no. of partition possible for a number.summing from the maximum possible red to minimum possible red using constraints of green balls ?

R and G are 2e5 so number of levels are at most 600 ! It can be solved like Knapsack problem !

could you explain what kind of knapsack?

DP[i][j] :: How many ways exist that we choose some level between 1 to i and sum of levels widths be j ...

DP[i][j] = DP[i-1][j] + DP[i-1][j — i];

when i tried to store dp[i][j] i got memory limit error. it is possible to use only dp[j] vector. And h times recalculate values.

R+G <= 4e5

number of levels < 900

You are right, but it is not important ! 1e3 * 2e5 = 2e8 and is fast enough.

First, you compute maximun height and do dynamic programming:dp[h][r] = dp[h — 1][r — h] + dp[h — 1][r], r is the number of using reds.

I have never seen so many hacks.

Because you have participated in so many contest, right?

Haha, I have participated in some contest, but I forgot that handle! So I had to register a new one.

I made 12 successful hacks for problem c, but my own solution is wrong. Ridiculous.

What was the hack test case ?

12 2 2

Answer is 4 ?

Yes

My code is right then .. Thanks :D

Oh, really, I have taken similar case in mind while thought about way to solve, but forgot to implement...

Would someone please tell how to solve D !

try to formulate a top-down DP solution that takes O((r+g)*h), this will give you MLE, then try to formulate the same DP bottom-up, this will require only O(r) in space and runtime of O((r+g)*h), if you see my code you will see both approaches

how to solve problem D?

C hack case?

For example "0 0 3" to crack some of the solutions. TLE was also achievable on others by entering numbers close to the set variable limits.

In my case 12 2 2 It worked successfully for 12 solutions.

1000000000 2000000000 2000000000

7 2 1 answer-3

I'm seeing people in top 10 (including unofficial participants) which had a wrong answer of test 3 of problem A!

case 0 0 0 0 0

it is easy to forget about 0 case, ant first time I had fogotten too/

Yeah, I'm one of them. It's so easy to miss the non-zero requirement. Wish they hadn't put this case in pretests for another gazillion of hacks ;d

so

How to solve E? (Quite interesting problem)

Thank you KhaustovPavel for the round. I especially enjoying hacking the solutions of C! Apparently the pretests were rather weak.

Unfortunately, this seems to cause some agression among the contest participants who happen to get hacked... after hacking this guys solution, I got this "friendly" message, of which I can't even understand the half:

LOL ! He's translating the same message into different languages !! what a guy :/

Why admin has block the page that we can see contest's history of each member?

Duplicate comment. Please ignore.

Hints for problem D:

Let h denote the maximal height made.

so overall complexity would be O(r.sqrt(r)) ? I didnt't realise that would pass, so i didn't code it up :\

It's the same for me :/ I thought about this algorithm, and I said "Meh, this doesn't work" because I saw the limit of r as 10^9.

that was exactly what i did, but received RTE ): no idea why.. EDIT: not exactly, i used a map to store answer, instead of optimizing space.

This should be O(10^8) which i think it should give TLE :D

However I am surprised because (10^8) gives MLE but don't give TLE :D

TL is 2sec. 10^8 shouldn't give TLE

My submission gave tle cuz i used long long int rather than int. :/

Strange. Long long 2s+, and int 0.8s (on keeping h and sum ints). I really wonder why there's such a drastic difference on changing sum and h. Note: I was using int type 2d matrix even previously. Changing sum and int were the only 2 changes. TLE : http://codeforces.com/contest/478/submission/12699584 AC : http://codeforces.com/contest/478/submission/12699606

Using long long gave TLE, got AC when I change it to int.

the first observation is false (and the reason I got RTE during contest). For

r=g= 2 * 10^{5},H= 793. My upper limit for H was 700, using 800 should result in TLE instead of RTE :Dit should be , as if we could use all of them and obtain a height

hwe'd haveWhoa ! what a speed of system testing !

Terrible!! What such a hack attempts :D

This is the shortest solution for C problem that I ever wrote !!!

sol = min(sum / 3, t[0] + t[1])

Can you please explain the solution? I can't get it till now. Thanks

Max number is sum / 3. I thought in the idea to form groups taking 2 items from the bigger one and taking only one item from the lower groups each time. Using this way if sum / 3 is bigger than the sum of the 2 lower values then it means that I can get only a + b (sum of the two lowest values) taking 2 from biggest value and 1 from any lower value. I am thinking in a mathematical proof but this was my approach.

you are right

you forgot to sort t =)

I sorted in my solution.

I solved it using the same solution .. do you have a proof of correctness?

No, I don't have a proof. I saw that the max number is sum / 3 and then I thought in the idea to form groups taking 2 items from the bigger and taking only one item from the lower groups each time.

Hi can you please explain it? Thanks :)

assume t[0] <= t[1] <= t[2]. and sum = t[0] + t[1] + t[2].

best case would be sum / 3. because no matter what we do we will always be left with sum % 3 balloons. now when can we get sum / 3 tables and when we can not:

case 1: if 2 * (t[0] + t[1]) <= t[2] than it is obvious that we can not get more then t[0] + t[1] tables because at each table at least 1 balloon is subtracted from t[0] + t[1], and by taking 2 from t[2] and 1 from t[0] + t[1] at each turn we can get exactly t[0] + t[1] tables.

case 2: if 2 * (t[0] + t[1]) > t[2]. let's prove that we can get sum / 3 tables in such case. by tactic taking 2 from t[2] and one from max(t[0], t[1]), t[0] + t[1] will not become zero before t[2] becomes zero, which means that at some point t[2] will become at most max(t[0], t[1]). and at that point difference between t[2] and max(t[0], t[1]) will not be more than 2. no we know that max(t[0], t[1], t[2]) — second_max(t[0], t[1], t[2]) is not more then 2. we can use this as an invariant. tactic taking 2 from max and one from second_max does not change invariant. now suppose we have some choosing tactic, we are stuck when we have situation like this a 0 0 where a >= 0 or 1 1 0. if a <= 2 it means choosing was optimal because no matter what we do we will be left with sum % 3 ballons. and second finish(1, 1, 0) is also optimal by same reason. answer in both cases will be sum / 3. according to our invariant we will not be left with a 0 0 with a > 2 because if a > 2 then our invariant does not hold. so we now that our choosing was optimal and answer is sum / 3.

now what min(sum / 3, t[0] + t[1]) does is exactly checking if 2 * (t[0] + t[1]) <= t[2]. because if t[2] >= 2 * (t[0] + t[1]) (case 1) then sum / 3 = (t[0] + t[1] + t[2]) / 3 >= (t[0] + t[1] + 2 * (t[0] + t[1])) / 3 = t[0] + t[1]. so min(sum / 3, t[0] + t[1]) will be t[0] + t[1] (exactly answer to case 1).

if t[2] < 2 * (t[0] + t[1]) (case 2) then sum / 3 = (t[0] + t[1] + t[2]) / 3 <= (t[0] + t[1] + 2 * (t[0] + t[1])) / 3 = t[0] + t[1] so min(sum / 3, t[0] + t[1]) will be sum / 3 (exactly answer to case 2).

hope it was helpful :D

Do you think we can extend it to any for any number of colors? In the contest I came up with this formula for 2 numbers i.e. min((r+g)/3,r). You have proved it for 3 numbers. Can it be extended for 4,5,6,7...?

Any takers?

Yes, I think it can be extended. Everything is the same, we only check if max is more then 2 * (sum — max).

sorry for late replay.

Proof should be possible by induction for all n

Thanks sb-man , Was having a hard time finding explanations for old problems......:P

can you prove how "min(sum / 3, t[0] + t[1])" is always answer ?

This comment deserves a thousand up-votes.

TLE on test 11 in D cuz I used long long int. Changed it to int AC. -_-

Gotta appreciate the fast system tests & rating updates at the same time. Usually one of them only occurs that fast :D

in cf 273 div 2 , I have submitted problem A,B,C. but I got no verdict for problem B . in my submissions it is written "skipped" !! whats the problem ?? can anyone plz help me !! http://codeforces.com/submissions/kifayat

It's really weird case ! :/

http://codeforces.com/contest/478/submission/8255696

I've seen solutions skipped because of plagiarism before. Don't know about you.

Plagiarism. I refer to this 8255446.

How did you find the Plagiarism soln ?

Heh, solved 3 problems and became blue!!! It have surprised me!

I solved 3 problems and became purple and I am not surprised :D

Question about E) How comes the number "11" to not be a wavy number? I cannot find the definition like two adjacent digits should be different..

Read the problem statement. It says: "A wavy number is such positive integer that for any digit of its decimal representation except for the first one and the last one following condition holds: the digit is either strictly larger than both its adjacent digits or strictly less than both its adjacent digits." For the first and last digits the adjacent digit if exits should also be strictly larger or strictly less than the digit. "strictly larger" or "strictly less" does imply that two adjacent digits should be different. Hence the number "11" cannot be a wavy number.

"for any digit of its decimal representation

except for the first one and the last one..."So 11, ignoring the first and last digits, becomes an empty string; all of its digits are (vacuously) strictly more or less than the adjacent digits. Of course, this is definitely an oversight on their part.

Completely agree, the statement is wrong, 11, 22, 33,..., 99 are wavy numbers.

After loosing a lot of time, I had to assume that 11, 22, ...,99 are not wavy in order to get the problem accepted. What disappointing.

questions was very easy and interesting.

Can anybody tell me concepts in problem A and B

my solution : http://codeforces.com/contest/478/my

Constantly getting wrong answer.

in A don't forget 0 case (0 0 0 0 0)!

In B your max looks OK, but... I think, it is good to use function like my, to make code easier (c++):

What is 'a' here in your code?

And what is concept in calculating the minimum pairs?

function returns number of pairs in 1 comand, a-number of people in that comand. min pairs will be if participants were split equally, as possible.

Link to your solution is the 7digit number written on the left.

Open it and send the URL

http://codeforces.com/contest/478/submission/8261061

Formula Error for kmax. Editorial dekhliyo.

How to solve C? Pleas with proof

if you wont i will send my solution. my solution is to short. i think you will uderstand

First of all take the maximum if it is >2*(sum of other two) then answer will be (sum of other two) because for every element taken of rest two take 2 elements of maximum. now suppose max<= 2*(sum of other two) then answer will be (sum of three)/3. you can observe this by take the balls greedily.

This is your algorithm, but what is your proof?

Easy to noticed there are only 2 case of arrangements, RRG and RGB. Use the second one when number of colors "balanced" enough, and the first one to the rest. Then consider if all arrangement is first scenario. So, you have (a[1] + a[2]) triples, and use 2 * (a[1] + a[2]) from the a[0]

explain for 1 50 70

thanks a lot to

KhaustovPavelfor contest.i want to know how the rating is changed,when it is positive and when it is negative??

Your last contest and this contest has nice problems.

Thanks a lot KhaustovPavel . you are a good designer(problem).

your rate is a good proof -_-

Can D be solved without dynamic programming? (like a combinatorial formula)

it looks like can, but difficult to understand and to find a formula.

It looks like it's related to the problem of integer partitions — the number of ways to make a tower using R red blocks is the number of ways to write R as a sum of unique positive integers. I got stuck writing a solution like this, but it seems doable.

that's wrong, because you don't need to use all the blocks

You're right — so the full solution would be to find how many different numbers of red blocks you can use to make a tower and sum these partitions for each number.

Hey mates, on the E-problem I get a runtime error here on the 3rd test, but on my computer the test passes just fine and I'm using the same GHC version. Any ideas on that?

huy guys. could you tell me what I dont understand in task A (yeah I know its simple)?? I feel depressed because of it :(

JS: (fails on test 3)

var N = readline().trim().split(" ").map(function(x){return parseInt(x);}); var sum = 0; for(var i=0; i < N.length; i++){ sum+=N[i]; } if (sum%5 != 0) {print(-1);} else {print(sum / 5);}

if sum==0 the answer is -1 to. Because all values need to be positive.

problem says non zero coins were placed as bet so if all input was zero then you should print - 1

yes you right. thanks guys! I thought sum cant be zero by default :(

When does the Editorial be showed?

Problem E seems very interesting, could anyone give a hint?

Can I get the explanation for problem C? I don't understand the logic behind it.

lol my B (http://codeforces.com/contest/478/submission/8257290) failed because js arithmetics check in js console: 499967831017438365 * 2 / 2

output: 499967831017438340

:)

When will the Editorial be up?

http://codeforces.ru/blog/entry/14307#comment-192751

we are waiting for editorials!

http://codeforces.ru/blog/entry/14307#comment-192751

thanks!

Oh! The solution is in Russian while my Russian is very poor. I'm looking forward the solution in English. And I hope that the author can offer us the solution in English.

It was a great contest!!

Where can i find editorial of this contest?

http://codeforces.ru/blog/entry/14307#comment-192751

Thank you :)

How can ternary search be applied to solve Div 2 C (Table decorations). It is tagged as Ternary search in the problem practice section. Will appreciate any help. Thanks

Please add Editorial for this Round.

KhaustovPavel Where is the editorial?

I don't know why haven't the editorial been added until now .

My English editorial for this round.

Anyone having trouble understanding Div 2 C should try this Editorial.

Testcase 11 for prob C

Input 500000000 1000000000 500000000 Jury's answer 666666666

Please explain(theoretically) ,how to arrive at this solution for the given input?

for Problem C , can someone explain this test: 100500 100500 3 Answer : 67001