Hello everyone!

Codeforces Round #160 will take place on Sunday, January 13th at 19:30 MSK. This is my third Codeforces round and I hope not the last.

I'd like to thank Seyaua, sdya and Gerald for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

Problems’ point values will be standard in both divisions.

I strongly recommend you to read ALL the problems.

Gl & hf ! :)

Contest is over, I hope it was interesting for you :)

Congratulations to div1 winners:

1). PavelKunyavskiy

2). Dmitry_Egorov

3). Nerevar

4). Egor

4). gawry

and div2 winners:

1). Pad

2). nirvanafreak

3). pablobce

You can view tutorial here.

Good luck everybody!!! :)

" Problems’ point values will be published before contest. " So the point values may not be as general?

"I strongly recommend you to read ALL the problems.". Probably.

Sereja always recommends to read all problems and it doesnt mean that point values may not be as general.

I suggest this phrase means that E will be easier than usual. At least, E from the last Sereja's round was simple segment tree.

So sad,I have a important final exam in tomorrow moring.I have to sleep early so I can't participate this round. And wish all the participants get high rating :)

You're lucky if you're sleeping not preparing last night :)

Good luck everyone ! Anyway, does anyone know any good book to prepare for Codeforces's contests ?

Uh, I think doing past problems on codeforces will help.

CLRS

Codeforces Gym.

The Codeforces Tutorial page is a good resource if you get stuck on a problem.

Edit: However, it's currently missing the most recent rounds. It would be nice to have them all collected somewhere.

Sorry but a little question for pro C div.2 (it's not clearly stated)

can any item be left out (not using the discount)?

No. You need to buy all the items.

The statement wasn't clear to me either :-/

You are asking two questions in fact:

In my case I was lost in how the discount works. It works so, you have something in basket, and you add new (0, 1, 2) items to the basket that are for free than, but the condition from statement have to hold.

In problem A (Div 1), can somebody explain me what the sentence "_each of them mustn't be more expensive than the cheapest item

outof the qi items in the cart_" means?do you mean

problem A (Div 1)?I'm sorry, you are right

It means that, after using the i-th discount, and buying its qi items you are able to select (0,1,2) items cheaper-than or equal-to the cheapest among qi

It simply means, that if you want a discount, you can apply it only to the item, that's cheapest in your cart.

Sorry, I'm just noob

In div1 :)

for problem B in Div 1 , I could not find any way to fit values in any data type except big int. So I had to go for python (though I could not complete the code) . I would like to know how guys managed to do in c/c++.

EDIT: I had underrated power of double. :(

double works fine because answer is floating point number

I've computed factorial using long double and it passed. value of 50 factorial using long double have significant difference with actual value, i thought i wont pass. I am curious to know what is the reason that long double didn't cause bigger error? (my code got tle system test just because i forgot to set dp array :(, it passed later in practice).

actual value of 50! is, A=30414093201713378043612608166064768844377641568960512000000000000 & using long double it is, B=30414093201713378039796484017234741538658648106343392576177963008 so the relative error is 100*(A-B)/A = 0.00000000000000001255 % which is very little, & thus can be ignored

If you solved the problem using DP to count how many subsets of a given size can appear before the i-th element for each i, you can also use long long int since the answer will not exceed 2^50. One can also use long double to compute the factorials and the "final" answer if one doesn't trust enough on double.

In Div1 E, does author's solution consider the following case? When you want to write 64, 7 moves is optimal: (1,0) -> (1,1) -> (1,2) -> (1,3) -> (1,4) -> (4,4) -> (16,4) -> (64,4)

Yes, ofcourse :)

wn will u publish tutorials??

As soon as it will be done :)

Very nice problems ... I have learned some new tricks ;))

what exactly?

This tricks or tips or whatever you would like to call them apply to me, I don't know about you, but maybe you can learn something from here

:)

Any ideas for solving C ?? I was trying to find some pattern but of no use.

Number of one's in the last row if the matrix has a size of m http://oeis.org/A048896

Number of ones in i-th row equals to 2

^{bin(i) - 1}, wherebin(x) is number of ones in binary representation ofx. It's quite simple fact: if you draw a picture 100x100 you'll see lots of Serpinsky Triangles, also known as Pascal Triangles modulo 2. And number of ones in a row of Pascal Triangle modulo 2 has well-known formula (One way to prove it is using Luka's Theorem).very fast system testing!

Even during the contest, pretest results were very fast. Nice Work

WOW ! That was a very cool contest . I liked the problems very much :) , the system testing was very fast :) and there weren't any bugs with the system :). With one word — great :) !

can div 2E be solved using http://oeis.org/A048896 and binary search ???

There might be an issue with the testcases for problem div1-C.

My solution: http://codeforces.com/contest/261/submission/2919058 and ACube's solution: http://codeforces.com/contest/261/submission/2919909 give different results for the test case 1505335291 524288 . On my computer my output is 42353463, while ACube's is 42353462.

Wow! Fast System test and no bugs and etc. Thanks.

Thank you Sereja and everyone else for these great problems. Have fun everyone with great coding time :)

my preciousssss

In order to get in div1, it took me a year to learn and practise, while you only needs one contest :)

where have u learned these stuffs??

practice.

In my case, it took about 2 years. I started solving problems from 16th January, 2011. That day I was introduced to my mentor by my friends :)

we can solve any riddles, my preciousssss

What have I got in my pocket?

it isn't fair, my precious, is it, to ask us what it's got in it's nassty little pocketsess?

Servers are fast these days! For Div1 B, I submitted a O(p * n^4) solution, and to my surprise it got accepted! It took 1/2 second on the toughest test.

Problem C div-2 wasn't clear. The statement says " To use the discount number i, the customer takes a special basket, where he puts exactly qi items he buys." and that wasn't clear enough to state that a basket may have less than qi items in it.

No. A special basket must have

exactlyqi items in it. But there was also said that he can buy items normally without discounts. I overlooked it at the start, too, but that's the first thing one needs to ask: could there be "no solution"?can anyone tell me for div2 C why the correct output for this test case is 5 ?

`2`

`4 7`

`7`

`1 1 1 1 1 1 1 1`

according to this statement "where he puts exactly qi items he buys", isn't the correct output is 7 ? because if we use first discount, it can't be fit with the number of items in any ways ?

1 1 1 1 1 1 1

b b b b f f b( b == buy; f== free)

answer — > 5

I also struggled on this part for a minute. If you read carefully the problem statement says you can use the same discount multiple times

DIV 2: Problem CStatement:The only condition imposed on the selected "free items" is as follows: each of them mustn't be more expensive than the cheapest item out of the qi items in the cart.Input:1 2 4 50 50 100 100Output:200Note:In the first sample Maxim needs to buy two items that cost 100 and get a discount for two free items that cost 50. In that case, Maxim is going to pay 200.Am I correct?If i take 50 50 in the cart and take a discount of 1 item. Then 100 100 in the cart and take a discount for 1 item Total Cost=150According to the statement it's allow.

If i am wrong, please explain. Thanks in advance.

50 50 100 100 if you take 50 50 you can't use discount because according to statement:"The only condition imposed on the selected "free items" is as follows: each of them mustn't be more expensive than the cheapest item out of the qi items in the cart."

I think you understood it wrong. The free items you get are not the ones you have in your discount but additional ones.

Wrong, in your case, you will pay for (50, 50) and get extra 0 items for discount, and you will pay for (100, 100) and get extra 0 item for discount.

You are paying 300 in total, discount doesn't mean you can deduct value for what you've paid for.

Hope this helps.

For me the statement wasn't clear too.

Most important is this sentence: "..in addition to the items in the cart the customer can receive at most two items from the supermarket for free...". That means, that you choose items to buy, add those to cart and as a bonus you can choose 0-2 items as free ones.

In this case you choose 100 and 100 in cart and then you get 50 and 50 as a bonus items, so you pay 200.

I asked 3 questions during the contest how the discount works and none of the answers helped me to realize that, later I somehow realized...

So, at the end of the test case any of the free items price has to be less than or equal to the item that has been bought. :)

Now, i have understand. Thanks.

if( j < 0 ) { break ; }

just absence of this line in my code has cost me 2nd place in div 2 today :(

nice problems ..

Codeforces Round #111 (Div. 2)

i just want to ask about problem C. in this test case :

1 2 3 50 50 100

why the answer is 150 ? why not 100 ? if he got the first and second he'll get '50' free .. so 2 items of 50 and 1 item 50 free .

please if someone can explain

You must put in cart

exactlyqi items ...There is only one qi, which is 2. So you must buy 2 items to get a discount.

You buy 100 + 50, and get free 50 => total cost = 150

You buy 50 + 50, you get no discount, because 100>50. This way you buy everything so the total cost is 200.

aha okay got it .. thanks man !

Who can explain this http://www.codeforces.com/contest/261/submission/2917414 solution for Div1-B?

Everything was great, except too bad English translation for problem C.

In Div1 Problem A, I was confused because the problem statement considers the terms "basket" and "cart" to be the exact same thing.... Maybe that also caused many people confused about the discount system.

Yes, I was also confused about problem A, & had to ask 2 questions to understand the problem clearly .

I solved three problems in yesterday's contest 160 in Division 2 . The contest page shows 3 out of 5 solved . However the problems page shows the "solved" color in only two of the three problems I solved . The third problem "Maxim and discounts" is not colored as solved . My rating has gone down from 1620 to 1579 . Last time my rating increased when I solved only two problems correctly . This time my rating has gone down after 3 successful submissions . I suspect there is some error in record keeping .

Number of solved problems on its own doesn't matter. Only place in contest standings matters. Your place in this contest is worse than in previous, so it's natural that your rating decreased.

Yes , but what about color code of problems solved successfully in the problems page . It is colored only for 2 of 3 problems I solved .

Rating is recalculated after each contest based on your contest rank, not number of problems solved. About 'color not showing solved' in the problem set page, it is because the last 3 problems of div 2 is added from div 1. I solved 4 in div 2 and problem set page shows 2. See the problem ids in the problem set page — (262B,262A),261E,261D,261C,261B,261A. Only 262A and 262B will show solved. Rest are from div 1.

But should that happen when the same problem appeared in both the divisions . 261A is same problem as problem C of division 2 .

They only upload the div 1 version, otherwise if they added both problems, same problem will be added twice, I guess that's why they do it.

Okay , thanks for your replies .

In problem-C Div2, the problem statement first uses "special basket" then "cart". And I think, maybe, it will be helpful to use only one of them so that contestants which have bad English ( for example : me ) would not get confused. ( I didn't know "cart" == "basket" )

edit : oh, missed something "where he puts exactly qi items he buys"