262A - Рома и счастливые цифры
Просто выполним все то, что просят в условии.
Заменим самые маленькие отрицательные на положительные, сколько можем. Если у нас останутся операции, то будем оставшееся количество раз менять знак у числа — минимального по модулю.
Выведем сумму полученных чисел.
Заметим, что выгодно пользоваться только скидкой, для которой требуется минимальное количество купленных предметов. Отсортируем предметы по не возрастанию. Будем покупать предметы жадно, и как только сможем применять скиду — будем делать это, так как нам нужно применять скидку к самым дорогим предметам.
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 нужно предподсчитать заранее.
Сгенирируем все числа меньше равно R, которые содержат в себе простые множители не превышающие 100. Таких чисел порядка 3000000. Теперь будем поддерживать такое ДП. Сколько нужно операций умножения над первыми i числами, что бы получить число j. А так же отдельный массив, где для каждого числа будем хранить общее число умножений и увеличений на 1. Теперь нужно быстро обновлять динамику в первом случае. Будем двумя указателями (число которым обновляем и число которое обновляем) и будем выполнять переход. Указатели будем перемещать слева на право, что бы можно было умножить на одно число два раза, но не добавлять еще один цикл. Дальше будем проходить по нашему текущему дп, и обновлять наш массив, считая что мы сделали количество увеличений равное последнему числу, на которое умножали. .В конце пройдемся по всем числам и найдем те, в которых значение в массиве не больше P, а величина числа не меньше L.
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://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!.
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 : letjof the firstipeople come in, with total lengths.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://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.
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
Интересно получается, в div1 задачи интересные и разные, но в итоге все, кроме А, решаются через ДП :-)
У меня такой вопрос почему в задаче "B" Рома и замена знаков в разборе написано что нужно брать по модулю самые минимальные числа? Ведь на вроде нужно максимизировать последовательность? Вроде нужно искать максимальные отрицательные элементы (пройти с указателем с правого края). А потом если К>0 тогда умножать первое число на -1 пока к>0
А в задаче 261C - Максим и матрица за основу взят случайно не треугольник Серпинского?
Да не случайно, а специально)
Кто-нибудь, объясните, пожалуйста, на доступном для новичка языке вот эту проблемку: 261B - Максим и ресторан На примере вот этого теста: Ввод 5 1 2 3 1 2 3 Вывод 1.500000 Ответ 1.5000000000
Буду очень признателен!
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 - Maxim and Restaurant 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 - Maxim and Discounts ?
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.