625A - Гость из прошлого
Автор идеи: народное творчество, разработка: feldsherov.
Заметим, что если у нас больше либо равно b денег, то суммарная стоймость стеклянной бутылки составляет b - c копеек. Значит если a ≤ b - c, то нам не имеет смысла покупать стеклянные бутылки и ответ будет . Иначе выгоднее в начале покупать стеклянные бутылки, пока можно. В этом случае, если у нас есть хотя бы b денег, мы купим
стеклянных бутылок, а на остаток докупим пластиковых. Получаем решение формулами за O(1).
625B - Война корпораций
Автор идеи: gustokashin, разработка: thefacetakt.
Давайте для начала найдем первое вхождение второго слова в первое. Так как нам нужно запретить первое вхождение, то куда бы нам поставить решетку внутри этого слова? Понятно, что в самую правую позицию, чтобы запретить как можно больше вариантов вхождений данного слова. После этого давайте надем следующее вхождение после поставленной решетки и повторим операцию. Самая простая реализация работает за O(|S|·|T|), но с помощью продвинутых алгоритмов поиска подстроки в строке (например, алгоритм Кнута-Морриса-Пратта) можно добиться асимптотики O(|S| + |T|).
Hint/Bug/Feature: в языке Python уже реализована функция, которая делает ровно то, что описано в условии:
print(input().count(input()))
625C - K-специальные таблички
Автор идеи: Андреева Елена Владимировна, разработка: wilwell.
Давайте заполнять строки таблицы по очереди жадным образом. Мы хотим, чтобы на k-м месте стояло максимальное число. В этой строке после него должно быть n - k значений, строго больших него, то есть наше число будет не больше n2 - (n - k). Давайте все эти числа и поставим в первой строке после k-го столбца. А на первые k - 1 мест давайте ставить минимальные числа, то есть 1, 2, ... , k - 1. В следующей строке давайте поступим абсолютно таким же образом, тогда в начале будут идти числа от k до 2(k - 1), а начиная с k-го будут идти следующие максимально возможные числа, то есть от n2 - (n - k) - (n - k + 1) до n2 - (n - k + 1). Таким образом мы заполним всю таблицу. Заметим, что при эффективной реализации нам не нужно хранить саму таблицу, можно обойтись O(1) памяти. Сам алгоритм работает за размер ответа, то есть O(n2).
625D - Контрольная по арифметике
Автор идеи: Sender, разработка: Sender.
Если длина суммы равна n, то длина иходного числа равна n, если не было переноса, либо n - 1, если был перенос. Зафиксируем длину и обозначим ее за m. Обозначим i-ю цифру искомого числа за ai. Тогда заметим, что мы знаем . Попробуем понять чему равно
. Если остаток равен 9, то так как максимальная сумма двух цифр равна 18, значит
. В противном случае результат однозначно определяется тем, был ли перенос в самом левом разряде при сложении или нет. Получается, что мы выяснили чему равно a1 + am. Заметим, что абсолютно неважно, как мы распределим эту сумму между первым и последним разрядом — сумма чисел не поменяется. Зная эти разряды мы можем определить, был ли перенос в сложении после первого разряда и до последнего. Повторяя эту операцию m / 2 раз мы сможем восстановить всё требуемое число. Получаем итоговую асимптотику O(n).
Если не заметить однозначности перехода, то можно реализовать данное решение с помощью динамического программирования.
625E - Лягушачьи бои
Автор идеи: Андреева Елена Владимировна, разработка: iskhakovt.
Давайте аккуратно моделировать процесс. Заведем структуру данных, в которой будем хранить все ключевые события, которые могут произойти с лягушками (кто-то ест кого-то). Тогда мы можем доставать из нашей структуры событие, которое произойдет раньше всех, выполнять прыжок и пересчитывать изменившиеся события. В качестве структуры можно воспользоваться стандартной структурой set языка C++ или TreeSet языка Java или рукописным деревом отрезков. Для того, чтобы быстро понимать, кого следующего будет есть наша лягушка, будем хранить их в двусвязном списке в порядке обхода нашего поля. Тогда мы легко сможем понимать, кого мы пытаемся есть впереди и кто пытается съесть нас. Техническим нюансом является вычислить по двум лягушкам ближайший момент времени, когда первая съест вторую, но это легко делается из физических соображений линейного движения двух точек. Так как лягушек может умереть не более n - 1, то весь алгоритм в итоге будет работать за .
можно подробней про ДП решение в D?
Ну у нас dp[сколько прошли с обоих сторон от ответа][какой перенос слева][какой перенос справа], а в пересчете состояний просто перебираем сумму чисел, которые встанут на две текущие позиции.
Thanks for nice editorial!
Can anybody help explain or give intuition as to why is the formula for A that? The n-c bit.
Lets say that we reserve c coins for later, then we can spend b - c coins plus reserve on the bottle and get the reserve back, so the reserve stays untouched. And after we bought
glass bottles we can't buy another one, because n1 - c < b - c, which is the same as n1 < b.
Also, some people used
floor( (n-b)/(b-c) ) + 1. Is it the same as that formula? It does give AC on the system tests.
http://codeforces.com/contest/625/submission/15870223
Its the same formula and will give AC if you add the condition if(b<=n)
Yeah, I was a little slow. Thanks for appreciating slow learners with negative contribution Codeforces community!
Also, thanks for clarifying mate! :)
"Lets say that we reserve c coins for later, then we can spend b - c coins plus reserve on the bottle and get the reserve back, so the reserve stays untouched."
I am sorry, but I don't understand that sentence. I've reread it several times and still don't see how it comes that the numerator is n - c. Could you, please, give a little bit more detail?
what is the dynamic programming solution for D ?
dp[how many digits from both sides we are already passed][is there a carry to the left][is there a carry from the the right], and to move to the next position we will iterate over the sum of the left digit and the right digit, which we are passing now.
can u please illustrate how are we obtaining answer for 165(ans->87) and 867 ( ans -> 285 ), it would be grt help.. :)
can you please illustrate how are we getting ans for 867 -> ans(285) and 165 -> ans( 87 ) and 111 (ans->0) using above mentioned tutorial for problem D
answer to problem A reduces to a simple mathematical equation if (b-c)<=a ;
n — k*b + k*c < b n-b < k(b-c)
(n-b)/b-c < k
therefore k = (n-b)/(b-c) + 1 here is the code http://codeforces.com/contest/625/submission/15886431
Problem A soln — >
if (b-c) <= a
equation reduces to
here is the code 15886431
How did you add 1 to
RHS
fromk > (n - b) / (b - c)
to make them equal?you have made a mistake , it should be
and i have added one to make it strictly greater
thanks, got it!
np!
Lets have a data structure with times of key events that could've happened during simulation (some frog removed other frog from the board)
How do I calculate this list of events in less than O(N*N) ? I am really confused and I think that to calculate all different collisions I would need to calculate collision time of each frog to each other frog. How can I handle it?
You need to calculate the events only for the neighbors of each frog, It can be done with a bidirectional linked list.
Notice, that the order of the frogs doesn't change during the game, some of them are just knocked out.
dammit. I almost had A . Same logic. Only blunder I made was forgetting b can be greater than N :/
Same here. :(
I'd like to thank the hacker of my Problem A for rescuing 300+ points. It's never a good idea to get hacked by system tests.
+1. I wish I was hacked instead of FST.
My solution for Problem D with dp is this -
Let the answer be a 5 digit number then it is written like this.
a4 * 10^4 + a3 * 10^3 + a2 * 10^2 + a1 * 10^1 + a0 * 10^0
Then its reverse is —
a0 * 10^4 + a1 * 10^3 + a2 * 10^2 + a3 * 10^1 + a4 * 10^0
The sum of the 2 numbers is —
(a0 + a4) * (10^0 + 10^4) + (a1 + a3) * (10^1 + 10^3) + (a2 + a2) * (10^2 + 10^2)
This means that a0 and a4 contributes to the 0th place and 4th place of the number to be made, where if a0 + a4 >= 10 then it would give a carry over to the 1st and 5th place.
Similiarly, a1 and a3 contributes to the 1st and 3rd place of the number to made, where if a1 + a3 >= 10 then it would give a carry over to the 2nd and 4th place.
Also we know that at max the carry over will be of at max 1 only.
Intuition -> 99999...9999 + 99999...9999 (Here also only a carry over of at max 1 takes place)
Now we have also established relationship between (a0, a4) and (a1, a3), ie.
If((a0 + a4) % 10 == 4th place) then a1 + a3 < 10, this is because the carry over given by a1 + a3, wouldve disturbed the equality on the 4th place.
Otherwise, If((a0 + a4 + 1) % 10 == 4th place) then a1 + a3 >= 10, this is because the carry over given by a1 + a3 is necessary for the equality on the 4th place.
Also,
If(a0 + a4 >= 10) then (a1, a3) gets a carry over on the 1st place, but NOT on the 3rd place.
Else if(a0 + a4 < 10) then (a1, a3) doesn't get a carry over on the 1st place.
Now our dp[i][greater_than_equal_to_ten][carry_over_till_here] = true, If for any (a, b), 0 <= a, b <= 9, we can make a number from i to len-i-1, where the carry over on the left place given by previous state is (carry_over_till_here) and the number (a, b) is restricted to either be >= 10 or < 10 so as to support the previous state's right place.
Net complexity — (N * 2 * 2) (number of dp states) * (10 * 10) time taken to solve a dp ==> O(N*400)
For clear understanding or to handle the corner case where i == n/2, refer my code ==> 15894317
If u could add some comments to your soln , it would be grt
Here. 15898045
In prob D how to determine if there was carry or not? I didnt understand the line "Let us figure out what does \sout.....equals to"
can anybody explain editorial for probelm E. what is mean of "times of key events that could've happened during simulation"
In this case the key event will be elimination of a frog. see the line reads "(some frog removed other frog from the board)". So here we store time of elimination of frog with other details.
maxA->number of plastic bottles maxB->number of glass bottles
otherwise: suppose we have n=14 rubles , b=8 rubles for each glass bottle at each c from 1 to 7
we can see that at c=1, valid n are 14 at c=2, valid n are 14 at c=3, valid n are 14,9 at c=4, valid n are 14,10 at c=5, valid n are 14,11,8 at c=6, valid n are 14,12,10,8 at c=7, valid n are 14,13,12,11,10,9,8
if we want to know number of valid values of n so we conclusion this equation : (n=14, b=8) length of numbers = n-b+1 then divide it over b-c we need ciel value so we add denominator-1 so equation will be (n-b+1 + b-c-1) / (b-c) save this value at maxB->number of glass bottles
reminder rubles we can buy plastic bottles with it total cost of glass bottles = number of glass bottles* cost of glass bottles = maxB * (b-c)
maxA->number of plastic bottles = ( total rubles — total cost of glass bottles ) / cost of plastic bottle = ( n-maxB*(b-c) ) / a
Does anyone have the correct codes for this contest?
Problem A:
Why can't we say if b — c < a then ans = n / (b — c)? Why c is subtracted from n so the formula became (n — c) / (b — c)?
In case (b — c) < a and N >= b:
While the condition (N — b + c >= b) holds we have to do N -= b, N += c.
Say that we do those operations k times:
it's clear that (Nk — (b — c)) < b and Nk >= b, otherwise we would do more than k operations.
So, in the end we just do Nk -= b without Nk += c.
It means that we did k operations N = N — b + c and 1 operation N = N — b:
So, in order to calculate the result without case handling ( N -= (b — c) or N -= b )
we assume that we do k + 1 operations of this type: N = N — b + c.
But now we know that N has 1 extra c. so, that's why we subtract c from N.
Hope it makes sense.