Sereja's blog

By Sereja, 8 years ago, translation, ,

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). apricotea
3). pablobce

You can view tutorial here.

• +284

 » 8 years ago, # |   -36 Good luck everybody!!! :)
 » 8 years ago, # |   -29 " Problems’ point values will be published before contest. " So the point values may not be as general?
•  » » 8 years ago, # ^ |   -27 "I strongly recommend you to read ALL the problems.". Probably.
•  » » 8 years ago, # ^ |   +4 Sereja always recommends to read all problems and it doesnt mean that point values may not be as general.
•  » » » 8 years ago, # ^ |   +1 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.
 » 8 years ago, # |   +13 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 :)
•  » » 8 years ago, # ^ |   +39 You're lucky if you're sleeping not preparing last night :)
 » 8 years ago, # |   +13 Good luck everyone ! Anyway, does anyone know any good book to prepare for Codeforces's contests ?
•  » » 8 years ago, # ^ |   +1 Uh, I think doing past problems on codeforces will help.
•  » » 8 years ago, # ^ |   +1
•  » » 8 years ago, # ^ |   +12
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 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.
 » 8 years ago, # |   +1 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)?
•  » » 8 years ago, # ^ |   0 No. You need to buy all the items.
•  » » 8 years ago, # ^ |   0 The statement wasn't clear to me either :-/You are asking two questions in fact: Q: Can any item be left out? A: No Q: Can you not to use a discount? A: Yes 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.
 » 8 years ago, # | ← Rev. 2 →   -12 In problem A (Div 1), can somebody explain me what the sentence "_each of them mustn't be more expensive than the cheapest item out of the qi items in the cart_" means?
•  » » 8 years ago, # ^ |   +5 do you mean problem A (Div 1)?
•  » » » 8 years ago, # ^ |   +3 I'm sorry, you are right
•  » » » » 8 years ago, # ^ |   +3 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
•  » » 8 years ago, # ^ |   0 It simply means, that if you want a discount, you can apply it only to the item, that's cheapest in your cart.
 » 8 years ago, # | ← Rev. 2 →   -16 Sorry, I'm just noob
•  » » 8 years ago, # ^ |   +18 In div1 :)
 » 8 years ago, # | ← Rev. 2 →   +5 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. :(
•  » » 8 years ago, # ^ |   0 double works fine because answer is floating point number
•  » » » 8 years ago, # ^ |   0 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).
•  » » » » 8 years ago, # ^ |   +4 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
•  » » 8 years ago, # ^ |   +3 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.
 » 8 years ago, # |   +9 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)
•  » » 8 years ago, # ^ |   +17 Yes, ofcourse :)
•  » » » 8 years ago, # ^ |   -11 wn will u publish tutorials??
•  » » » » 8 years ago, # ^ |   +4 As soon as it will be done :)
 » 8 years ago, # |   +1 Very nice problems ... I have learned some new tricks ;))
•  » » 8 years ago, # ^ |   +1 what exactly?
•  » » » 8 years ago, # ^ |   +27 Write down all the cases of a problem (I failed B div2 because of not taking all cases in consideration) 1LL is 1 in long long (C++) Use a dynamic approach instead of a greedy one, if you're not sure The first solution that comes through your head is not good :)) (this applies to me, lack of work) Think that every problem is solvable (determined me to try more than 2 problems and I had time to read the fourth one) I have managed to partially demonstrate why the solution to B div2 is correct (I have been trying for a long time to demonstrate the solution of a problem, in general, still cannot do it properly) 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:)
 » 8 years ago, # | ← Rev. 3 →   0 Any ideas for solving C ?? I was trying to find some pattern but of no use.
•  » » 8 years ago, # ^ |   +3 Number of one's in the last row if the matrix has a size of m http://oeis.org/A048896
•  » » 8 years ago, # ^ | ← Rev. 4 →   +23 Number of ones in i-th row equals to 2 bin(i) - 1, where bin(x) is number of ones in binary representation of x. 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).
 » 8 years ago, # |   +1 very fast system testing!
•  » » 8 years ago, # ^ |   +5 Even during the contest, pretest results were very fast. Nice Work
 » 8 years ago, # |   -61
 » 8 years ago, # |   +5 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 :) !
 » 8 years ago, # |   +4 can div 2E be solved using http://oeis.org/A048896 and binary search ???
 » 8 years ago, # | ← Rev. 2 →   +17 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.
 » 8 years ago, # |   +11 Wow! Fast System test and no bugs and etc. Thanks.
 » 8 years ago, # |   +11 Thank you Sereja and everyone else for these great problems. Have fun everyone with great coding time :)
 » 8 years ago, # |   +21 my preciousssss
•  » » 8 years ago, # ^ |   +2 In order to get in div1, it took me a year to learn and practise, while you only needs one contest :)
•  » » » 8 years ago, # ^ |   0 where have u learned these stuffs??
•  » » » » 8 years ago, # ^ |   0 practice.
•  » » » 8 years ago, # ^ |   0 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 :)
•  » » » 8 years ago, # ^ |   +11 we can solve any riddles, my preciousssss
•  » » » » 8 years ago, # ^ |   +3 What have I got in my pocket?
•  » » » » » 8 years ago, # ^ |   0 it isn't fair, my precious, is it, to ask us what it's got in it's nassty little pocketsess?
 » 8 years ago, # |   +1 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.
 » 8 years ago, # |   0 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.
•  » » 8 years ago, # ^ |   0 No. A special basket must have exactly qi 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"?
 » 8 years ago, # | ← Rev. 5 →   0 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 1according 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 ?
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 1 1 1 1 1 1 1b b b b f f b( b == buy; f== free)answer — > 5
•  » » » 8 years ago, # ^ |   0 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
 » 8 years ago, # |   0 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.
•  » » 8 years ago, # ^ |   +3 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."
•  » » 8 years ago, # ^ |   +1 I think you understood it wrong. The free items you get are not the ones you have in your discount but additional ones.
•  » » 8 years ago, # ^ |   0 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.
•  » » 8 years ago, # ^ |   0 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...
•  » » 8 years ago, # ^ |   0 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.
 » 8 years ago, # | ← Rev. 2 →   0 if( j < 0 ) { break ; }just absence of this line in my code has cost me 2nd place in div 2 today :(
 » 8 years ago, # |   0 nice problems ..
 » 8 years ago, # |   0 Codeforces Round #111 (Div. 2)i just want to ask about problem C. in this test case : 1 2 3 50 50 100why 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
•  » » 8 years ago, # ^ |   0 You must put in cart exactly qi 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 = 150You buy 50 + 50, you get no discount, because 100>50. This way you buy everything so the total cost is 200.
•  » » » 8 years ago, # ^ |   +1 aha okay got it .. thanks man !
 » 8 years ago, # |   0 Who can explain this http://www.codeforces.com/contest/261/submission/2917414 solution for Div1-B?
 » 8 years ago, # |   0 Everything was great, except too bad English translation for problem C.
 » 8 years ago, # |   0 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.
•  » » 8 years ago, # ^ |   0 Yes, I was also confused about problem A, & had to ask 2 questions to understand the problem clearly .
 » 8 years ago, # |   0 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 .
•  » » 8 years ago, # ^ |   0 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.
•  » » » 8 years ago, # ^ |   0 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 .
•  » » 8 years ago, # ^ | ← Rev. 2 →   +5 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.
•  » » » 8 years ago, # ^ |   0 But should that happen when the same problem appeared in both the divisions . 261A is same problem as problem C of division 2 .
•  » » » » 8 years ago, # ^ |   0 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.
•  » » » » » 8 years ago, # ^ |   0 Okay , thanks for your replies .
 » 8 years ago, # |   0 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" )
 » 7 years ago, # | ← Rev. 2 →   0 edit : oh, missed something "where he puts exactly qi items he buys"