Блог пользователя Sereja

Автор Sereja, 12 лет назад, перевод, По-русски

262A - Рома и счастливые цифры

Просто выполним все то, что просят в условии.

262B - Рома и замена знаков

Заменим самые маленькие отрицательные на положительные, сколько можем. Если у нас останутся операции, то будем оставшееся количество раз менять знак у числа — минимального по модулю.
Выведем сумму полученных чисел.

261A - Максим и скидки

Заметим, что выгодно пользоваться только скидкой, для которой требуется минимальное количество купленных предметов. Отсортируем предметы по не возрастанию. Будем покупать предметы жадно, и как только сможем применять скиду — будем делать это, так как нам нужно применять скидку к самым дорогим предметам.

261B - Максим и ресторан
Если все люди поместятся в ресторан, то выведем ответ — .n. Иначе зафиксируем человека, который не сможет поместиться в ресторан. Напишем ДП: d[i,j,s] сколько существует способов набрать из i первых людей j, что их ширина равна s.
Далее переберем числа i и s и посчитаем, сколько существует способов, что i человек с общей шириной s придут до зафиксированого человека, при том что зафиксированый не влезет. Количество способов такого равна d[n,i,s]*i! далее считаем количество окончаний, их (n-i-1)! перемножаем и добавляем к количеству умноженым на i — количество людей которые поместятся. В конце сумму поделим на n! — общее количество способов.

261C - Максим и матрица
Если выписать последовательность сумм(f[n]), которые выходят на nтом шагу, то можно заметить f[n] = f[n/2], n%2=0, f[n] = f[n-1]*2, n%2=1. Иными словами f[n] = 2^(bit_count(n)-1). Теперь нужно посчитать, сколько чисел больше 1 и меньше-равно (заданного +1) содержат в себе log2(T)+1 двоичных бит. Это стандартная задача, решается с помощью дп. Будем идти по двоичному представлению числа и считать количество чисел, у которых совпадает некоторый префикс, а следующий бит — меньше. Количество окончаний это биномиальный коефициент, с помощью которого считаем, сколько последовательностей из 0 и 1 длины Н содержат К единичных бит.

261D - Максим и возрастающая подпоследовательность

Заведем дп, q[i][j] в какой позиции массива мы можем закончить нашу последовательность, если последнее число в ней i, а длина j. Переход:
будем переносить q[i][j] -> q[i+1][j]. Так как не ухудшим результат.
будем переносить q[i][j] -> q[i+1][next[q[i][j]][i+1]], где next[x][y] — первое вхождения числа y после позиции x. Массив next нужно предподсчитать заранее.

261E - Максим и калькулятор

Сгенирируем все числа меньше равно R, которые содержат в себе простые множители не превышающие 100. Таких чисел порядка 3000000. Теперь будем поддерживать такое ДП. Сколько нужно операций умножения над первыми i числами, что бы получить число j. А так же отдельный массив, где для каждого числа будем хранить общее число умножений и увеличений на 1. Теперь нужно быстро обновлять динамику в первом случае. Будем двумя указателями (число которым обновляем и число которое обновляем) и будем выполнять переход. Указатели будем перемещать слева на право, что бы можно было умножить на одно число два раза, но не добавлять еще один цикл. Дальше будем проходить по нашему текущему дп, и обновлять наш массив, считая что мы сделали количество увеличений равное последнему числу, на которое умножали. .В конце пройдемся по всем числам и найдем те, в которых значение в массиве не больше P, а величина числа не меньше L.

Разбор задач Codeforces Round 160 (Div. 1)
Разбор задач Codeforces Round 160 (Div. 2)
  • Проголосовать: нравится
  • +23
  • Проголосовать: не нравится

»
12 лет назад, # |
Rev. 7   Проголосовать: нравится -13 Проголосовать: не нравится

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
»
12 лет назад, # |
  Проголосовать: нравится 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.

»
12 лет назад, # |
  Проголосовать: нравится +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.me/contest/261/submission/2917070

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

»
12 лет назад, # |
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 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.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 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.

»
12 лет назад, # |
  Проголосовать: нравится 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.

»
12 лет назад, # |
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.

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    hope it helps:)

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 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]

»
12 лет назад, # |
  Проголосовать: нравится +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

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +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 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

»
12 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Интересно получается, в div1 задачи интересные и разные, но в итоге все, кроме А, решаются через ДП :-)

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

У меня такой вопрос почему в задаче "B" Рома и замена знаков в разборе написано что нужно брать по модулю самые минимальные числа? Ведь на вроде нужно максимизировать последовательность? Вроде нужно искать максимальные отрицательные элементы (пройти с указателем с правого края). А потом если К>0 тогда умножать первое число на -1 пока к>0

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1. Сначала нужно идти с конца(левого края, т.к последовательность неубывающая) и пока есть К( количество замен), и встретилось отрицательное число то нужно его превращать в положительное, а также вычитать 1 из К.
    2. Если к осталось больше нуля, то нужно именно минимальное по модулю брать, потому что есть 0 , который по модулю минимален)))
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А в задаче 261C - Максим и матрица за основу взят случайно не треугольник Серпинского?

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Кто-нибудь, объясните, пожалуйста, на доступном для новичка языке вот эту проблемку: 261B - Максим и ресторан На примере вот этого теста: Ввод 5 1 2 3 1 2 3 Вывод 1.500000 Ответ 1.5000000000

Буду очень признателен!

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any update on tutorial on Maxim and Calculator?

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
10 лет назад, # |
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 ?

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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?

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.