В этой задаче нужно было совсем немного техники программирования. Можно было брать свободные гирьки по одной и добавлять на ту чашу весов, где сейчас меньше гирек. После этого требовалось просто вывести ответ в правильном формате.
В этой задаче нужно было понять, что из себя представляет хитрая операция Артура. На самом деле, если перед выполнением всех действий сделать присвоение b = w - b - 1 (то есть как бы перевернуть ситуацию), то операция аналогична присвоению b = (b + x) % w. Причем если происходит переполнение через w, то дополнительно происходит присвоение a = a - 1.
Таким образом, если выполнить k таких операций, то переменные изменятся так: b = (b + k·x) % w, a = a - (b + k·x) / w, c = c - k. Зная это, легко решить задачу бинарным поиском по ответу.
382C - Арифметическая прогрессия
В этой задаче нужно было разобрать несколько несложных случаев:
1) если n = 1, то ответ: -1, потому что любые два числа будут являться арифметической прогрессией;
2) если массив состоит целиком из одного числа, то ответ: эта единственная константа;
3) если вам уже дана арифметическая прогрессия, то ответ это 2 числа: minVal - d, maxVal + d, где minVal — минимум, maxVal — максимум, d — разность прогрессии.
Однако, если n = 2, то в этом случае ответ бывает 3 числа (как, например, в последнем тестовом примере, когда разность (a[1] - a[0]) четна);
4) иначе, возможно, в прогрессии пропущено ровно одно число и его можно аккуратно найти двигаясь по исходному массиву (предварительно его удобнее отcортировать). Разность прогрессии можно вычислить, как d = min(a[i + 1] - a[i]) (если n > 2);
5) во всех иных случаях ответ 0;
В этой задаче из всех клеток кроме # один переход. Поэтому граф на клетках является почти фунцкиональным графом. Если в этом графе есть цикл, то очевидно ответ -1, потому что этот цикл имеет длину не менее 2 и мы можем разместить на нем две наши пешки.
Иначе в графе нет циклов. Найдем в нем самый длинный путь, пусть его длина len. Тогда если мы расположим две наши пешки в первую и вторую клетку пути, то ответ на задачу уже будет 2·len - 1.
Однако, иногда можно получить ответ 2·len, если в этом графе есть два непересекающихся по вершинам пути (вершины, не являющиеся #). Непересекающиеся они будут потому, что если вдруг они пересеклись в какой-то клетке, то дальше они будут совпадать (а по условию задачи такие ходы совершать нельзя).
Остается проверить есть ли в этом графе два непересекающихся по вершинам (не #) пути длины len. Это можно сделать как угодно. Например, посчитать для каждого истока v величину d[v] длины пути из него. После серией поисков в глубину из всех истоков с максимальным d[v] = len проверить найдутся для два непересекающихся пути. (если очередной поиск в глубину не находит поюзанной вершины, значит этот путь новый).
Чтобы решить задачу, нужно было посчитать количество деревьев с заданными свойствами. Сделать это можно с помощью динамического программирования. Основная идея динамического программирования в том, что размер максимального паросочетания в дереве ищется простой линейной динамикой dp[v][used] (v —- вершина, used —- уже использована она в паросочетании или нет), поэтому для подсчета количества деревьев достаточно включить в состояние динамики два значения dp[v][0] и dp[v][1].
Другими словами, нужно написать динамику z[n][dp0][dp1], значение которой — это количество подвешенных деревьев, состоящих из n вершин, в корне которых динамика dp[root][0] = dp0, а dp[root][1] = dp1. Если просто написать такую динамику она будет получить TL по времени. Из этого положения можно выйти двумя способами. Либо посчитать все значения динамики прекалком, немного оптимизировав код, либо ассимптотически оптимизировать динамику.
Авторское решение использует второй подход. Для того, чтобы оптимизировать динамику достаточно заметить, что значение dp0 отличается от значения dp1 не больше чем на 1. То есть либо dp0 = dp1, либо dp0 = dp1 + 1. Тогда динамика превращается в динамику r[n][dp0][add], которая работает сильно быстрее. Другая важная оптимизация состоит в том, что возможных троек (n, dp0, add), для которых значение r[n][dp0][add] ненулевое очень мало (около 250). Это значит, что достижимых состояний динамики не много, поэтому если написать ее "лениво" с отсечениями, программа будет работать в несколько раз быстрее.
Комментарии, которые описывают решения (некоторые отличаются):
http://codeforces.net/blog/entry/10423#comment-158177
http://codeforces.net/blog/entry/10423#comment-158182
when input 2 3 3 the answer is 1 3 why it's true? the answer 3 3 3 3 also correct i think
The statement implies that all numbers should be distinct.
No, you're asked to find the number you can put on one card, regardless their position, so 1 3 is correct since you can place it anywhere within the sequence.
Very fast tutorial, thanks!
Very fast (incomplete) tutorial, thanks!
This was my first contest and I'm unrated. How long does it take for the ratings to show up ?
Just wait.
for problem C, i feel that the the case where
(a[0] + a[1]) / 2
also had to be included in the answer could have been omitted from the pretests (or atleast from the examples), as a good number of participants may not have seen that.5716844
I solved Problem B in a quite different way.
(I'm not sure if it's absolutely correct,and sorry for my poor English)
if b ≥ x, perform the assignment b = b - x
if b < x, then perform two consecutive assignments a = a - 1; b = w - (x - b)
Let's define the b ≥ x one as operation A,and the other operation B
You may notice that a and c seems works as counters,and (c-a)gets smaller after operation A,(c-a) won't change after operation B
Define the times doing operation B as k
So the time Alexander gets ahead of Arthur is c-a+k
Also,you can easily find that the time Alexander gets ahead of Arthur can be also described as ceil((b+kw)/x)
So,now we have a formula
(b+kw)/x=(c-a)+k
we can get:
k=((c-a)*x-b)/(w-x)
and now we can get the answer by calculating ceil(c-a+k)
However,the (c-a)*x can be very large,bigger than INT_MAX.So,we should use long long.(That's why I made two Wrong Answer submissions)
I can't get neither this nor author's solution for B :(
"the time Alexander gets ahead of Arthur can be also described as ceil((b+kw)/x)"
Why is it so?
Well another approach is using dfs and finding cycles.
Sorry for the trouble I caused.I forgot to explain that,and I may have made a mistake.
operation B says,if b < x, then perform two consecutive assignments a = a - 1; b = w - (x - b)
It's a little tricky
b=w-(x-b)=b+w-x
Which means,In operation B,we also did minus x.And we only add w for k times
So no matter which operation we did, b always -x.
If we don't -x during each operation B,b will be (b+kw) after k operation B.
And (total times minus x)*x is supposed to be smaller or equal to (b+kw).
(After a second thought, I think we don't need a ceil() here)
So (total times minus x)<=(b+kw)/x
So (c-a)+k<=(b+kw)/x
So k>=((c-a)*x-b)/(w-x)
Since We want to find the minimum time ,k=((c-a)*x-b)/(w-x)
What should we do if k is't a integer?We can't do a half of operation B
k=ceil(((c-a)*x-b)/(w-x))
Wow,That was an awesome solution. I really liked your idea.
Finally understood :D. Thanks so much!
hi, look here http://codeforces.net/blog/entry/10423 for the explanation of clp012345 is a good one.
i first use binary search , but WA twice . then in the last five minutes i try nearly the same algorithm with you then AC. lucky! k=((c-a)*x-b)/(w-x)
for(int i=k-10000;;k++) { when i find a i,break. }
i find that my bsearch is wrong just because the right need to be larger than 2000000000000LL a simple mistake takes me nearly all the time……
我猜这个你能看懂
What do you hope to achieve by posting something that the vast majority of people here can't read?
Chullu bhar pani mein doob mar yeh samajh mein aa jae to batana
Из разбора задачи D: " После серией поисков в глубину из всех истоков с максимальным d[v] = len проверить найдутся для два непересекающихся пути. (если очередной поиск в глубину не находит поюзанной вершины, значит этот путь новый)." Как доказать, что это работать будет быстро?
Я понял. Тут имелось ввиду, что мы просматриваем пути с макс. длиной не попарно, а просто по одному и красим путь с false в true. Если 2 пути пересекаются, "то дальше они будут совпадать". =)
my solution for B is completely different from author`s
notice that 0 <= b < w <= 1000, this means that we had a cycle on b, so find it and compute its length and delta -- count of decreasing c (without a). now we can say how many times we should pass this cycle and then pass one more time for end. It works O(w)
5725480
thx a lot~
Let me state another solution for problem B. The key observation is that both b=b-x and b=b-x+w are equivalent modulo w, and number b is always going to lie in [0, w-1]. So each operation means taking (b-x) instead of b (modulo w). So if we look at the reminders mod w, the sequence becomes b, b-x, b-2x, ..., b-kx, ... Now it's clear, that there is going to be a period P (we can find it via simulation in O(w) initially or notice that it's just the minimal p : b-px=b(mod w), or px=0(mod w), or p = w / gcd(w, p).). Also we should calculate the decrease of a variable "a" in this period — call it S.
Now, we can calculate the decrease of a variable a in X steps the following way: If X <= P, then it's just a simulation in O(P). Otherwise, it's just S*(X/P) + simulation of (X % P). Clearly, it works in O(P) which is also O(w).
All that left is a binary search: obviously, c always increases, while a increases just sometimes. So once c<=a is satisfied, it's gonna stay like that all the time afterwards.
Hopefully it's clear :)
px = 0 (mod w), then p = w/gcd(w,x), not p = w/gcd(w,p). Anyway, thank for your clear explanation!
That's right, sorry for the typo :)
may someone explain solution for D?, thx
The problem can be formulated in terms of directed graphs: each cell is a vertex, it has outdegree 0 if it's '#' (let's call those vertices endpoints) and outdegree 1 otherwise, with the only outgoing edge pointing to the cell that a pawn moves to from it.
If there's a cycle in this graph, the answer is -1.
Otherwise, the path from every cell must end in an endpoint; notice that the graph is, in fact, a forest of trees rooted at endpoints. For every such tree, you can count (BFS, DFS, whatever you wish) its depth in its tree, which is equal to the number of moves, and the last vertex on the path from it before the root.
Now, you can only put pawns in vertices which either have different depths or "last" vertices, or they'd meet on a non-end vertex; think why it works. For different depths, it's simple: just find the largest (a) and second largest (b) depth overall. If you want to choose 2 vertices with the same depths, both must be equal to a or it won't be better than a + b; that means you can choose a vertex v with depth a, iterate over all vertices with depth a and iff you find one with "last" different from last(v), then there's a better solution 2a. Just check all those possibilities.
The time for this is O(NM).
thanks :D
Thanks for fast editorial.. But what about 382D and 382E?
Although I pass the problem b,I can't understand your explaination. I use the pigeonhole principle and have a way to solve it in o(2*x). Could you explain that how to get these formulas in details? Thank you very much.
Could you please explain how have you used pigeonhole principle in problem B?? Thank you
First,you should find the if the datas is enough big,the value of b will repeat.So it's easy to see that the value of b will repeat at most of x times. For example,if you use a array[x] to record the value of b when it appear,it must have one of the array[x] to equal 2 and that means b repeats. So we just need to use the value to devide the remain of a,and then caculate at most x times to get the answer.
Can someone please help me understand why this submission of mine for problem A gives WA at test 5.
Problem D i Got MLE in test 35
please help,though my array is arr[2000][2000] it shows MLE solution
For problem C: I have a test case for which my solution which got accepted will fail and I have no idea how many other solutions will fail
my code : 88891597
expected 0 , output 1 => 5
HolkinPV I think this test case should be added. maybe only my solution fails.
Alternative approach for Problem C: Let, l=last term of A.P a= First term of A.P d=Common difference Then,
n( Required number of terms) = (l-a)/d+1
and Sum of all terms = [n*(l+a)]/2
Using difference of sum of actual array and desired sum(computed using parameters l,a and d) gives us the left element(which must be included to make all elements of array follow the Arithmetic Sequence for given a,l and d. Ambiguous cases need not be worried out, all such cases can be judged as they don't follow the mathematical equations mentioned. https://codeforces.net/contest/382/submission/104538828