Sereja's blog

Codeforces Round #160
By Sereja, 12 years ago, translation, In English

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.

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

Comments Comments (81)
| Write comment?
»
12 years ago, # |
  Vote: I like it -36 Vote: I do not like it

Good luck everybody!!! :)

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

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

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

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

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

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

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

      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.

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

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

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

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

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

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

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

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

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

    No. You need to buy all the items.

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

    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.

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

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?

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

    do you mean problem A (Div 1)?

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

      I'm sorry, you are right

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

        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

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

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

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

Sorry, I'm just noob

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

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

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

    double works fine because answer is floating point number

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

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

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

        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

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

    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.

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

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)

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

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

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

    what exactly?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +27 Vote: I do not like it
      • 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

      :)

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

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

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

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

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

    Number of ones in i-th row equals to 2bin(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).

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

very fast system testing!

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

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

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

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

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

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

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

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

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

My solution: http://codeforces.me/contest/261/submission/2919058 and ACube's solution: http://codeforces.me/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.

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

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

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

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

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

my preciousssss

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

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

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

      where have u learned these stuffs??

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

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

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

      we can solve any riddles, my preciousssss

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

        What have I got in my pocket?

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

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

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

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.

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

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.

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

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

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

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 ?

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

    1 1 1 1 1 1 1

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

    answer — > 5

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

      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

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

DIV 2: Problem C

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.

Input: 1 2 4 50 50 100 100

Output: 200

Note: 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=150

According to the statement it's allow.

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

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

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

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

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

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

    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.

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

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

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

    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.

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

if( j < 0 ) { break ; }

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

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

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

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

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

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

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

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

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

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.

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

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

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

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 .

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

    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.

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

      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 .

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

    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.

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

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

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

        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.

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

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

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

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

→ Reply