### Sereja's blog

By Sereja, 7 years ago, ,

This problem just need to simulate everithing that was given in statment.

We will "reverse" numbers from the begining to the end while numebrers are negative and we did't spend all k operations.
In the end there can leave some operetions, and we will "reverse" only one numeber, with minimal value k(that remains) times.

Ofcourse the most optimal way is to use discount with minimal q_i. We will sort our numbers and will go from the end to begin of the array. We will by use our discount as soon as it will be possible. It's not hard to see that we will buy all the items with numbers I (zero-numeration from the end of the sorted array) such, that I%(q+2)<q.

261B - Maxim and Restaurant
If all people can come, we will return answer as n.
If it is impossible, there will be finded some person that will be the last to come. We will brtueforce this value. Then we will detrminate dp[i,j,s] in how many ways j persons from the first i with total length s can be in the resturant. It is easy to calculate.
Then we will add to the answer values dp[n][i][s]*i!*(n-1-i)! for all i,s such that s+p[h]>P. Where P — total length of the table, p[h] — length of the fixed person.

261C - Maxim and Matrix
For fixed m, the sum in the last row will be 2^(bit_count(m+1)-1). So now if T is not power of 2, answer is 0. Else we can find number of bits that we need. And know we have stndart problem. How many numbers form 2 to n+1 have exactly P bits in binary presentation of the number. It is well known problem can be done using binomial cooficients. We will count number of numebers smaller then out number with fixed prefix.

This problem can be done using dp[i,j] where we can end our increasing sequence with length i and last number j. Its not hard to understand that number of states will be n*b. To make a tranfer we need to know array first[j] — first position of the number j in the sequence b, next[i][j] — first position of the number j in the sequence b after position i.

Now its easy to calculate all values.

I will add tutorial later. But I will give you a hint: number of numbers with maximal prime divisor<=100 is near 3000000 numbers.

• +23

 » 7 years ago, # | ← Rev. 7 →   -13 typo in 262B/261C: "...number of numebers..." — should be numberstypo in 262A: "...everithing..." — should be everything "...statment..." — should be statement typos in 261C: "...stndart..." — should be standard "...binomial cooficients..." — should be binomial coefficients "...smaller then out..." — should be smaller than our
•  » » 7 years ago, # ^ |   0 +"will be finded"
 » 7 years ago, # |   0 Only thing that stops me from solving E is the case when number is 2^p*q, how to distribute 2^p becomes really interesting.
 » 7 years ago, # |   +3 May be im getting a bit lame ... any way in 261B — Maxim and Restaurant why adding up dp[n][i][s]i!(n-1-i)! values will work ? May be I need a detailed explanation. I was also going through the following submissions but failed to get those also.http://codeforces.com/contest/261/submission/2917070http://codeforces.com/contest/261/submission/2915955All i know about average is to find the (good ways / total ways) ... So i understood the solutions which find the sum by dp and finally divides by n!.
 » 7 years ago, # | ← Rev. 2 →   +3 In the solution given above for 261B:How can you be sure that the H(fixed person) isn't used in some of the ways counted in dp[n][i][s] because if he will be counted in those we may use him twice:for example, suppose:a1 a2 a3.... aj — 1 HS = sum of length of these persons.S < P and S + p[h](length of the fixed man) > Pbut this state is not acceptable.
•  » » 7 years ago, # ^ |   0 First you have to fix the person H , for each fixed person you have to do the dp thing by not taking H in consideration.
 » 7 years ago, # |   0 The google translation of the question 261B Max and restaurant is not proper enough to understand. I understand the recursive solution but am not able to apply dp in it. so, someone please help me understand.
 » 7 years ago, # | ← Rev. 3 →   0 i think that's orignal in english :) brtueforce the "blocked" customer, say 5th customer wont be admitted, and dp[i][j][s] means first i people, j gets in with total length s, after you get dp[n][j][s], you can get how many will fill the table and 5th people will blocked, say 6 people can fill the table but adding the 5th is impossible, the number these 6people can form is 6!, so 6!*43!will be the result for this case.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 hope it helps:)
•  » » » 7 years ago, # ^ |   0 please explain in detail..i am not able to get it.
•  » » » » 7 years ago, # ^ |   0 dp[i][j][s] = k, means there are k ways to accomplish event (i, j, s), where event (i, j, s) is : let j of the first i people come in, with total length s. dp[i, j, s] = dp[i-1, j-1, s — len[i]] * j + dp[i-1, j, s]
•  » » » » » 7 years ago, # ^ |   0 sir can you please give me some nice link to tutorial on dp or some dp questions?
 » 7 years ago, # |   +3 Could someone give a more detailed explanation to D (Div 1)? What is the dp computing? how does the transition used the mentioned arrays? Thanks
 » 7 years ago, # |   0 somebody please explain meaning of ans[i][j][k] = ans[i — 1][j][k] * (1 — tmp); and also why is (1-tmp) used, why not tmp like in case (a[i]<=k)if possible plz explain full solution as i am not good in dp.
•  » » 7 years ago, # ^ |   +4 here tmp = probability of the i'th element to be in the first 'j' elements of the permutation(1-tmp) = probability of the i'th element NOT to be in the first 'j' elements of the permutationans[i][j][k] = ans[i — 1][j][k] * (1 — tmp); // we don't want i'th element in first j if (a[i] <= k) ans[i][j][k] += ans[i — 1][j — 1][k — a[i]] * tmp; //here we want the i'th element in the first j
 » 7 years ago, # |   0 What is the proof the formula 2^(bit_count(m+1)-1) of problem E(Div2).
 » 7 years ago, # |   0 Can you explain to me why greedy alroritm is good for Cdiv2 about sales)) Thank you very much
 » 7 years ago, # |   0 Any update on tutorial on Maxim and Calculator?
 » 7 years ago, # |   +5 I tried to discuss 261B - Maxim and Restaurant here in my blog — Part 1 and Part 2.
 » 5 years ago, # | ← Rev. 3 →   0 Hi, can anyone please explain why the "most optimal way is to use discount with minimal q_i" in Div2 Problem C : (Maxim and Discounts) 262C - Maxim and Discounts ?
•  » » 5 years ago, # ^ |   0 Well, is it more viable to buy 1 and get 2 free or 2 and also get 2 free?