Sereja's blog

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

262A - Roma and Lucky Numbers

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.

261A - Maxim and Discounts

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.

261E - Maxim and Calculator

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

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

Comments Comments (22)
| Write comment?
»
12 years ago, # |
← Rev. 7   Vote: I like it -13 Vote: I do not like it

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

typo 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
→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

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://mirror.codeforces.com/contest/261/submission/2917070

http://mirror.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!.

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

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.

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

    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.

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

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.

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

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.

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

    hope it helps:)

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

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

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

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

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

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

in solution http://mirror.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.

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

    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

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

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

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

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

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

Any update on tutorial on Maxim and Calculator?

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

I tried to discuss 261B - Maxim and Restaurant here in my blog — Part 1 and Part 2.

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

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 ?

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

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

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

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?

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

    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.

    → Reply