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

262B - Roma and Changing Signs

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.

261D - Maxim and Increasing Subsequence

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.

typo in 262B/261C: "...number of numebers..." — should be numbers

typo in 262A:

typos in 261C:

+"will be finded"

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.

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/2917070

http://codeforces.com/contest/261/submission/2915955

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

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 H

S = sum of length of these persons.

S < P and S + p[h](length of the fixed man) > P

but this state is not acceptable.

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.

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.

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.

hope it helps:)

please explain in detail..i am not able to get it.

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]

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

in solution http://codeforces.com/contest/261/submission/2917070

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.

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 permutation

ans[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

What is the proof the formula 2^(bit_count(m+1)-1) of problem E(Div2).

Can you explain to me why greedy alroritm is good for Cdiv2 about sales)) Thank you very much

Any update on tutorial on Maxim and Calculator?

I tried to discuss 261B - Максим и ресторан here in my blog — Part 1 and Part 2.

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 - Максим и скидки ?

Well, is it more viable to buy 1 and get 2 free or 2 and also get 2 free?

Is there any prove for the Problem C in Div1?

It's not easy to find the conclusion from Combinatorics.

The occurance of 1 in m+1-th row equals to the number of i such that $$$\binom{m}{i}-\binom{m}{i+1} \equiv 0(\bmod 2),0\leq i \leq \frac{m}{2}$$$ But how to get the conclusion?

Instead of XOR, if we were simply using base 10 addition, then the construction of the array can be thought of as building the left half of pascal's triangle, hence the numbers in a row are the coefficients of the binomial expansion (1+x)^N. What we then want is the coefficients mod 2, which can be calculated using lucas' theorem.