Codeforces Round #342 (Div. 2) : разбор

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

625A - Гость из прошлого

Автор идеи: народное творчество, разработка: feldsherov.

Заметим, что если у нас больше либо равно b денег, то суммарная стоймость стеклянной бутылки составляет b - c копеек. Значит если a ≤ b - c, то нам не имеет смысла покупать стеклянные бутылки и ответ будет $\text{[math]}$ . Иначе выгоднее в начале покупать стеклянные бутылки, пока можно. В этом случае, если у нас есть хотя бы b денег, мы купим $\text{[math]}$ стеклянных бутылок, а на остаток докупим пластиковых. Получаем решение формулами за 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 значений, строго больших него, то есть наше число будет не больше n² - (n - k). Давайте все эти числа и поставим в первой строке после k-го столбца. А на первые k - 1 мест давайте ставить минимальные числа, то есть 1, 2, ... , k - 1. В следующей строке давайте поступим абсолютно таким же образом, тогда в начале будут идти числа от k до 2(k - 1), а начиная с k-го будут идти следующие максимально возможные числа, то есть от n² - (n - k) - (n - k + 1) до n² - (n - k + 1). Таким образом мы заполним всю таблицу. Заметим, что при эффективной реализации нам не нужно хранить саму таблицу, можно обойтись O(1) памяти. Сам алгоритм работает за размер ответа, то есть O(n²).

625D - Контрольная по арифметике

Автор идеи: Sender, разработка: Sender.

Если длина суммы равна n, то длина иходного числа равна n, если не было переноса, либо n - 1, если был перенос. Зафиксируем длину и обозначим ее за m. Обозначим i-ю цифру искомого числа за a_i. Тогда заметим, что мы знаем $\text{[math]}$ . Попробуем понять чему равно $\text{[math]}$ . Если остаток равен 9, то так как максимальная сумма двух цифр равна 18, значит $\text{[math]}$ . В противном случае результат однозначно определяется тем, был ли перенос в самом левом разряде при сложении или нет. Получается, что мы выяснили чему равно a₁ + a_m. Заметим, что абсолютно неважно, как мы распределим эту сумму между первым и последним разрядом — сумма чисел не поменяется. Зная эти разряды мы можем определить, был ли перенос в сложении после первого разряда и до последнего. Повторяя эту операцию m / 2 раз мы сможем восстановить всё требуемое число. Получаем итоговую асимптотику O(n).

Если не заметить однозначности перехода, то можно реализовать данное решение с помощью динамического программирования.

625E - Лягушачьи бои

Автор идеи: Андреева Елена Владимировна, разработка: iskhakovt.

Давайте аккуратно моделировать процесс. Заведем структуру данных, в которой будем хранить все ключевые события, которые могут произойти с лягушками (кто-то ест кого-то). Тогда мы можем доставать из нашей структуры событие, которое произойдет раньше всех, выполнять прыжок и пересчитывать изменившиеся события. В качестве структуры можно воспользоваться стандартной структурой set языка C++ или TreeSet языка Java или рукописным деревом отрезков. Для того, чтобы быстро понимать, кого следующего будет есть наша лягушка, будем хранить их в двусвязном списке в порядке обхода нашего поля. Тогда мы легко сможем понимать, кого мы пытаемся есть впереди и кто пытается съесть нас. Техническим нюансом является вычислить по двум лягушкам ближайший момент времени, когда первая съест вторую, но это легко делается из физических соображений линейного движения двух точек. Так как лягушек может умереть не более n - 1, то весь алгоритм в итоге будет работать за $\text{[math]}$ .

Комментарии (36)

Показать архивные | Написать комментарий?

mondayguy

9 лет назад, # |

← Rev. 2 →

можно подробней про ДП решение в D?

→ Ответить

romanandreev

9 лет назад, # ^ |

+10

Ну у нас dp[сколько прошли с обоих сторон от ответа][какой перенос слева][какой перенос справа], а в пересчете состояний просто перебираем сумму чисел, которые встанут на две текущие позиции.

Kerim.K

Thanks for nice editorial!

FoolForCS

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 $\text{[math]}$ glass bottles we can't buy another one, because n₁ - c < b - c, which is the same as n₁ < b.

-10

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.net/contest/625/submission/15870223

saisumit

+19

adding and subtracting 1
floor ( (n-c)/(b-c) -1 + 1)
 == floor ( (n-c + c -b)/(b-c) ) + 1
 == floor ( (n-b)/(b-c) ) + 1

inactive06

-7

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! :)

egor.okhterov

"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?

kingofnumbers

If you've missed the fact that every step is uniquely defined, then you could've wrote basically the same solution, but with dynamic programming.

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.. :)

-13

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.net/contest/625/submission/15886431

← Rev. 4 →

-9

Problem A soln — >

if (b-c) <= a

equation reduces to

n-k*b + k*c < b
n-b < k*(b-c)

k = (n-b)/(b-c) + 1 

therefore ans = k + ( n- k*b + k*c)/a

here is the code 15886431

rahulkhairwar

How did you add 1 to RHS from k > (n - b) / (b - c) to make them equal?

you have made a mistake , it should be

k > (n-b)/(b-c)

and i have added one to make it strictly greater

thanks, got it!

np!

ariel.nowik

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?

iskhakovt

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

kevin5396

Same here. :(

ultmaster

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.

Ir1d

+1. I wish I was hacked instead of FST.

sidhant

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

sanket407

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"

shark_s

can anybody explain editorial for probelm E. what is mean of "times of key events that could've happened during simulation"

shubham_1559

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.

Mohamed_Ayman

maxA->number of plastic bottles maxB->number of glass bottles

at the beginning if a<=b-c so best choice is spend all money to buy plastic bottles

otherwise: suppose we have n=14 rubles , b=8 rubles for each glass bottle at each c from 1 to 7

when c=1 : we have n=14 then n=7 not enough money we get 1 glass bottle when c=1
when c=2 : we have n=14 then n=8 not enough money we get 1 glass bottle when c=2
when c=3 : we have n=14, n=9 then n=4 not enough money we get 2 glass bottles when c=3
when c=4 : we have n=14, n=10 then n=6 not enough money we get 2 glass bottles when c=4
when c=5 : we have n=14, n=11, n=8 then n=5 not enough money we get 3 glass bottles when c=5
when c=6 : we have n=14, n=12, n=10, n=8 then n=6 not enough money we get 4 glass bottles when c=6
when c=7 : we have n=14, n=13, n=12, n=11, n=10, n=9, n=8 then n=7 not enough money we get 7 glass bottles when c=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

finally we print number of glass bottles + number of plastic bottles print : maxA+maxB

wfe2017

8 лет назад, # |

Does anyone have the correct codes for this contest?

mahmoud_arafa

4 года назад, # |

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)?

maxovic

4 года назад, # ^ |

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:

N0 = N
N1 = N0 — b + c = N0 — (b — c)
N2 = N1 — b + c = N1 — (b — c)
...
Nk = Nk-1 — b + c = Nk-1-(b — c)

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:

N0 = N
N1 = N0 — b + c = N0 — (b — c)
N2 = N1 — b + c = N1 — (b — c)
...
Nk = Nk-1 — b + c = Nk-1-(b — c)
Nk = Nk — 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.

N0 = N
N1 = N0 — b + c = N0 — (b — c)
N2 = N1 — b + c = N1 — (b — c)
...
Nk = Nk-1 — b + c = Nk-1-(b — c)
Nk = Nk — 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.