Задача на технику программирования. Надо найти на каких позициях находятся кузнечик и насекомое. Если разность позиций не делится на k, то ответ — NO. В обратном случаи надо проверять позиции pos+k, pos+2k, ... , где pos — это минимальная из позиций кузнечика и насекомого. Если где-то есть препятствие, то ответ — NO, в обратном случаи — YES.
Во первых, надо заметить, что n1+n2 "избранные" должны быть люди с top (n1+n2) коэффициентами. Во вторых, если человек с интеллектом C будет в первом городе, то он будет добавить к суммарному коэффициенту IQ C/n1 баллов. Так что, если n1<n2, то top-n1 рейтингов надо "запихнуть" в маленький город, а из остальных top-n2 — в большой.
Давайте решать обратную задачу: сколько участников как минимум должен участвовать, если чемпион будет провести ровно n матчей. Тогда очевидно есть такая рекуррентая связь: f(n+1)=f(n)+f(n-1) (Сделаем сетку так, чтобы тот, кто победил в последнем матче до этого играл n матчей, а тот кто проиграл — сыграл (n-1) матчей). Значит, задача сводится к тому, чтобы найти индекс наибольшего числа Фибуначчи, не превосходящую число, данное в вводе.
Первый очевидный факт — для простых чисел ответ — 1 (Этот случай надо проифать в первую очередь). Если число не простое — то ответ по крайней мере — 2. А когда это возможно? Это возможно в двух случаях — когда число сумма двух простых или самый большой делитель числа — 2. Но если 2 делитель, то и n/2 тоже делитель отличные от n (n/2<=2 => n<=4 => n=4 — n не простое). По Гипотезе Гольбаха, которое проверено для чисел не превосходящих 10^9, каждое четное число является суммой двух простых чисел. А нечетное число может быть суммой двух простых чисел, если оно имеет вид 2+p, где p — простое. В обратное случаи, ответ равен — 3 (n=3+(n-3), (n-3) является суммой двух простых, так как оно четное).
Во-первых хочу сказать спасибо albert96 и GlebsHP за то, что помогли с разбором. Во-вторых, хочу извиниться за опоздан ие.
Задача решается методом динамического программирования. Пусть dp[v][i][j] будет количество покрасить поддерево вершины v так, чтобы ближайшая черная вершина была на глубине i, а ближайшая белая — на глубине j (еще и смотрим dp[v][-1][j] и dp[v][i][-1] — случаи где нету черных и белых вершин в диапазоне k в поддереве v соответственно). Чтобы объединить две поддеревья, надо перебирать все пары (i,j) в обеих поддеревьев. Пусть имеем пары (a,c) в первом поддереве и (b,d) — во втором. Если min(a,c)+max(b,d)<=k, то обновляем значение в нынешней вершине.
Сложность алгоритма O(n*k^4), что вполне достаточно для данной задачи (n — количество вершин, k^4 перебор всех пар (a,b); (c,d))
Эта задача состоит из трех идей. Идея 1: четность этого количества равна четности определителю матрицы, которая имеет 1 в позициях (ai,bi) и 0 — в других позициях (это — согласно определению). Идея 2: Если заменить одну единицу на нолик, но определитель будет меняться на величину, равную к алгебраического дополнения. То есть, если мы будем считать обратную матрицу то она будет отражать четности дополнений (B(m,n)=A'(n,m)/detA, мы знаем, что detA — нечетное). Идея 3: обратную матрицу можно найти за O(n^3), что медленно. Для этого мы будем перейти в алгебру по модулю 2, где мы умеем складывать числа с помощью XOR. Для этого мы в одном переменном храним не одно число а 32 — каждый бит один переменный. Тогда наша асимптотика будет O(n^3/32), что вполне нормально.
Допустим у нас есть множество (a1,a2,...,am) (уже дополненный список в неубывающем порядке). Тогда — оно является валидным, если множество {2m-2, 2m-4, 2m-6, ..., 0} мажорирует
множество {a1,a2,...,am}. Необходимость: top-n (n<=m) участников между собой играют n(n-1)/2 партий, в котором суммарно собирают 2 балла. В матчах с остальными они суммарно могут набирать 2*n(m-n) баллов (всего игр верхней части против нижней части 2n(m-n)). То есть баллов у них вместе взято будет не больше чем 2*(n(n-1)/2+n(m-n))=2*((m-1)+(m-2)+...+(m-n)) (легко проверить). Достаточность, конструкция примера: Давайте решим как играл чемпион, а потом опустим рекурсию (математически применяем метод математической индукции). Если количество баллов у чемпиона четно (например 2*(m-n) то мы допускаем, что он проиграл у участников занявшие места 2,3,4,...,n и выиграл у остальных). Если у чемпиона количество баллов нечетно (2*(m-n)-1, для некоторого n), то тогда мы предполагаем то же самое, только предполагая, что он играл вничью с (n+1)-ым. Легко проверять, что мажорация сохранится, то есть мы и в конце будем (в случаи n=1) будем иметь множество которая мажорируется множеством {0}, то есть {0} и задача будет решена. То есть алгоритм такой: Сначала доводим наше множество из n элементов к множеству из m элементов. Если это невозможно, то ответ — NO. В обратном случаи — ответ YES и надо конструктировать пример как описано. Асимптотика: O(m^2logm) (m раз мы вызываем рекурсию, каждый раз сортируем (это нам нужна потому что мы можем менять очередь из-за того, что результат игрока первого места может влиять на последовательность),и проходим на него линейно).
http://codeforces.net/contest/584/problem/D
https://www.quora.com/What-is-the-best-way-to-solve-SPOJ-problem-code-TENNIS1
HELLO FROM 2k15 BOYZ
thanks a lot it helped me a lot
Dear Codeforces administration and contest preparation team,
Should we all copy our comments from the neighbouring thread to this one (just like you did with the C/A problem statement) or would you please explain why this round is rated and why is this allowed to reuse the same problem?
The final decision is obviously yours, I'm just politely asking for the commentary on this.
Sorry, but this contest sucks big league. Some problems I assume are good, but those C and D are terrific!
Pls make codeforces great again.
together
I'll create a contest and make other authors give me problems for it.
You wrote terrific, but I'm not sure whether you mean terrific or terrible. Terrific also means great :|
It's not your business! You didn't even participate in that contest.
Where is editorial in english?
In Google.
I think you made a mistake. For problem A and B div 1 it should say: "Just google it"
Вы че на пацана напали? Ну забыл что на другой сайт год назад залил задачу. Кто ваще решает на этом SPOj (ахахахаххаха название смешное)
Влепил контесту класс за старания
эх, хотя бы извинился :(
Во-первых это моя задача. Во-вторых какой-то человек нашел эту задачу С который был тут 2 года назад за неделю и другие его повторили. Во-третьих, я заявку на этот раунд отправил еще в декабре прошлого года (могу доказать) и то что в течении этого года кто-то что-то подобное поставил это я должен жаловаться
Кто-то что-то подобное поставил, да. За почти три года до этого раунда всё предвидел и специально под ником albertg поставил. Не стыдно?
У Вас серьезные проблемы. Кто-то что подобное поставил задаче D в этом году. А то что это моя задача которую я давно спрятал и какой-то читер нашел — это не моя проблема.
Вопрос снят.
Ты какой-то странный. Извинился бы хоть. Совсем совести нет. Вот факты. Есть что сказать в свое оправдание? Может быть, тебя подставили?
Задача на SPOJ была добавлена пользователем albertg (какое совпадение!) в январе 2014, а затем один в один перекочевала в сегодняшний раунд под именем C.
Задача D встречалась до этого на одном из старейших сайтов acm.timus.ru, а там между прочим, указано: "Источник задачи: чемпионат школьников, март 2005". То есть это боян уже 11 лет, и подавляющее большинство участников слышали о той задаче.
Задача D также встречалась в раунде 324, который состоялся 6 октября 2015 и в котором участвовал пользователь albertg: вот ссылка на его выступление.
В декабре прошлого (2015) года, то есть по прошествии двух месяцев с раунда 324, albertg отправил заявку на этот раунд. И его не смутило, что два месяца назад он лично решил на раунде практически такую же задачу.
Что же вы только ко стыду да совести призываете, сразу уж к уголовной ответственности. Предлагаю всем пострадавшим "честным" и "совестливым" участникам (читай отгугалившим во время контеста) составить петицию в Гаагский международный трибунал. :)
Вопрос снят.
Вы не совсем правы и насчёт "свинства" и "русского языка".
Я считаю, что если человек пишет на русском так, что это ни то, что неприятно читать, а вообще почти невозможно понять смысл написанного, то он не должен этого делать. Ничто не останавливает от ответа на английском языке кроме формального системного ограничения.
Невозможность признать свою ошибку считаю свинством и плевком в сторону участников. Извинения сделаны. Беру свои слова назад.
Возможно, я бы смог аргументировать своё мнение лучше, если была бы понятна ваша точка зрения.
Норм же контест, че вы минусуете?
Let me tell you, this contest was so bigly good, you have no idea. I had so much fun googling problems, it was so fun, let me tell you.
Let me tell you, this round was so bigly good, it was so good folks. I had so much fun googling problems, let me tell you, you have no idea how much fun I had.
Who forced you to google?
I actually didn't google problem C.
For problem D, I knew it was some type of well known theorem, so I just googled it with no shame, since such problem shouldn't have been on a contest anyway.
Автокомментарий: текст был обновлен пользователем albertg (предыдущая версия, новая версия, сравнить).
Jokes aside, are there any other solutions for the Tennis contest problem (736A) not using the Fibonacci Sequence?
this is actually a problem on calculating the worst-case height of the AVL-Tree.
http://pages.cs.wisc.edu/~ealexand/cs367/NOTES/AVL-Trees/index.html
So the fibonacci pattern wasn't very intuitive to me. Hence I solved this question with a basic recurrence as described. Let us define a f(N) as minimum number of people required for a person to win N matches. If we have this, our answer is simply the greatest value of N where f(N)>=n, where n is the input, i.e. the number of people.
So, for N match wins, we need N losers, hence we add N to the answer(ret). Now we run recurrence over these losers, if we notice the number of wins required for these losers will be [0,N-2], inclusive, as only if the highest player had N-2 matches won, could he have played the winner who was at N-1, leading him to N victories. Hence we iterate over [0,N-2] and find the number of people needed for those players.
Hence we had all the losers counted, We add 1 to f(n) to get the total player count.
Here is the recursive method. Add memoization for AC.
This recurrence, naturally turned out give same output as fibonacci, but it is a non-experimantal way of solving this problem. Thanks :)
I found this way better than the non-intuitive fibbonacci pattern . Thanx for writing . :)
I know that this is an old comment, but I just wanted to say thank you for sharing your approach. Helped me a lot!
B. На апрель 2012 года бинарная гипотеза Гольдбаха была проверена для всех чётных чисел, не превышающих 4×10^18.
In problem D, If there are no solution without using bitset, you should set contraint for n is 500 instead. Making problem harder by bitset is not good idea!
Is the complexity using bitset O(n3 / 32)?
Why do you think bitset problem is not a good idea? Many people regard a single 32-bit integer arithmetic as a single unit time operation. Then why not a bitset?
complexity is (n/32)^3 ~ 80^3
The complexity is O(N^3 / 32). Using bitsets only reduces a factor of 32 in one dimension (the row XOR operations). The outer loops for Gaussian elimination are still O(N^2).
How to solve Div2E ?
Why has the determinant of a 0-1 matrix anything to do with the number of valid permutations? Can somebody explain the intuition behind this?
Actually, the Permanent of a matrix counts the number of valid permutations. However, calculating the permanent is a hard problem. But we only need the parity of the number of permutations, i.e. the parity of the permanent. For that, we can calculate the determinant of the matrix over a field of size 2 (the permanent and determinant are equal in
).
The permanent of an adjacency matrix counts the number of perfect matchings in bipartite graph of rows-columns. Since the determinant is something like a - b and permanent is a + b, they have the same parity. The number of perfect matchings in bipartite graph rows-columns is the number of vertex-disjoint covers of cycles in the original graph (every vertex will have one incoming edge and one outgoing edge). This is basically the number of valid permutations when you look at them as cycles.
Tennis Championship : "Then there's obvious recurrent formula: f(n+1)=f(n)+f(n-1)", is it really obvious ? Can someone explain the obviousness of the formula without a rigorous mathematical demonstration ?
Assuming we want a guy to have played n + 1 matches:
First of all, he must have played exactly n matches.
Secondly, he must have beaten someone else who had played at least n - 1 matches.
It is obvious that we want to minimize the number of matches used to maximize the answer. Therefore, we just assume that the guy that was beaten had played n - 1 matches before.
Thus the recurrence formula comes to the surface, which is F(n + 1) = F(n) + F(n - 1), where F(n) represents the number of people we need to have one guy who has played n matches.
The base case are F(0) = 1, F(1) = 2.
In Problem D, I didn't know the determinant will differ by algebraic compliment. Here is my approach I tried(ultimately same as calculating inverse). We know that the original matrix has inverse, which means the rows are linearly independent. So for every row vector e_i^T, there exists a unique combination of rows that make e_i^T. We can determine the combination with row-echelon form.
Next, if the matrix is singular, there exists a set of rows that XOR sum of it is zero. That is, if we change one 1 to 0 and the matrix becomes singular, we should be able to make zero with some rows, including the changed row. It is obvious that the combination originally produces e_i^T. Now we can determine the answer. (i,j) is NO if row i is included in the combination of e_j^T, YES otherwise.
The Problem D ( Div2 ) can be found Here
Which is a Contest Problem. Here
that Arranged in : Sat, Aug 13, 2016
Common for Some Guy. I got this problem by a Friend's resource. And Surprised .
I send round proposal at 20th December 2015, which is earlier than August 13, 2016.
Хорошая контест, особенно было нравиться задача С. Еще очень получать удовольствие от разбор. Меня интересовать задач "Остап и дерево". Он пока нет в разборе. Меня надеяться, эта будет публиковать в скоро.
In problem D, shouldn't it be O(n^3/32) instead of O((n/32)^3) ?
I think so, too
Actually if you are going to use big O notation, then both are wrong, correct order is O(n3). But yes you are right it should be n3 / 32, at least for most accepted solutions, have not seen author's code, but i'm pretty sure he could not reduce the outer N loop, so it would never be (n / 32)3
Why is this article downvoted so much? By the way, about the solution for D, I think it takes n*(n-1)/2 * (2*n/32) iterations for computing an inverse matrix in the worst case because it's based on the Gaussian elimination algorithm.
If someone knows a way with (n/32)^3 iterations, let me know ><.
Anyway, you shouldn't use Big-O notation for explaining time complexity with constants. So, O((n/32)^3) is not good notation in the first place.
How to solve div 2 E ? Editorial is also missing..
Such bad formatting.
Please make use of break tag in appropriate places, at least. Coming with so much enthusiasm to read the editorial of problems I couldn't solve and it is just disappointing to see what we get.
Just curious: why are the limits to Div1C n=100 and k=20 when a O(n*k*k) dynamic programming solution exists?
Maybe author's solution is O(n*2^k)?
Do you mind explaining your solution? It is particularly short and fast, but I can't understand it. Thanks!
O(n*k*k) solution: (EDIT: I think I made a mistake in the explanation for i > k) (Note: I am not good at explaining solutions, so this might not make much sense). Let us say a node q reaches a black node if for some p distance(q, p) <= k and p is black. The problem wants us to find the number of ways to color nodes such that all nodes can reach a black node.
First root the tree at any node.
dp[x][i] keeps track of info for node x, and 0 <= i <= 2*k.
If i <= k, then node x is a distance of i from the nearest black child, and all of its children can reach a black child.
If i > k, then some node in the subtree of node x is i-k-1 (<----EDIT) edges away and cannot reach a black node (there may be multiple nodes that cannot reach a black node, but it is OK to just select the farthest one, because if the farthest one is able to reach a black node in the future, then any closer ones will be able to too).
Examples: If i = 0, then node x is colored black and all of its children can reach a black node.
If i = k+1, then x cannot reach a black node, but all of its children can. (<----EDIT)
If i = 2*k, then node x is not colored black, and there is a node in the subtree of node x that is k edges away and cannot reach a black node.
At the beginning of the dfs, set dp[x][0] = 1 (this is the case when we color the node black) and dp[x][k+1] = 1 (this is the case when we don't color the case black).
During the dfs call on each child (call it j), update dp[x]. This can be done by iterating over dp[x][f] and dp[j][g] for 0 <= f, g <= 2*k.
There are 4 cases when updating. First let Y denote the union of x and the subtrees of the children that have already been visited (not including j). (For example, if there are edges 1-2, 1-3, 1-4, 1-5, then when j=4, Y = {1, subtree(2), subtree(3)}).
f<=k, g<=k: All nodes in Y and j can reach black nodes. Update nxtDP[min(f, g+1)] because that's the distance to the nearest black node.
f>k, g>k: Y and j both have a node that can't reach black nodes. Update nxtDP[max(f, g+1)] because some node max(f, g+1) edges away from x can't reach a black node.
f<=k, g>k: All nodes in Y can reach a black node, but some node in g can't. If the nodes in g that currently can't reach a black node can reach black nodes in Y, update nxtDP[f]. Otherwise update nxtDP[g+1].
Wow, the representation of state is ... fantastic.
I don't really understand the Sentence "If i <= k, then node x is a distance of i from the nearest black child, and all of its children can reach a black child." if the distance between node x and the nearest black child is exactly k,and,so the children of the x node might have a (k+1) distance from the nearest black child (of node x). Can you explain a little?
.
I don't completely understand your question, but here's an example when i <= k:
Let the tree be rooted at 1 and k=5
Edges are 1-2, 2-3, 3-4, 1-5
If 4 is colored black but none of the other nodes are, then this would correspond to dp[4][0], dp[3][1], dp[2][2], dp[1][3]
The initialization of dp[5] would NOT be affected.
Note that dp[x] only contains information about subtrees of children that have already been visited. If a child has not been visited, then it will NOT affect dp[x] until it is visited.
Can you elaborate a bit more on setting dp[x][0] = 1 and dp[x][k+1] = 1?
Quote: ----------
At the beginning of the dfs, set dp[x][0] = 1 (this is the case when we color the node black) and dp[x][k+1] = 1 (this is the case when we don't color the case black).
When we initialize the DP, the only node in the subtree of x that we have currently visited is x, so this is why dp[x][k+1] is used when the node is not colored black (a node of distance k+1-k-1=0 away cannot reach a black node). dp[x][0] covers the case when it is colored black, because a node of distance 0 away (in this case x itself) is black.
Thank you!
Exactly, what does the entry dp[i][j] represent? It seems as if it represents "number of ways to color subtree rooted at i, such that the closest black node to i is j units away". Is my understanding correct?
"Then let we have pair (a,c) in the first subtree and pair (b,d) in the second one. If min(a,c)+max(b,d)<=k, then we update value of current vertex."
Can anybody clarify this? Should it mean "pair (a,b) in the first subtree and pair (c,d) in the second one"? What does it mean if min(a, c) + max(b, d) > k, and why is the converse a sufficient condition for satisfiability?
I solved the problem using a completely different DP recurrence, so I would appreciate if somebody could provide some more intuition about this particular recurrence.
Can you also share your approach?
Sure, I'll try. Let f(x, l, d) = the number of ways to color the subtree rooted at x, where l is the distance of nearest black node to x that is NOT in the subtree rooted at x, and d is the distance to the nearest black node in the subtree of x (both can not exist, signalled by -1). The transition is very unwieldy:
If min(l, d) > k, the solution is 0.
If d = 0, we have to place a black node at x and we can use f(y, 1, d) for all of the children y of x and all d <= 2*k.
If d > 0, one of the children must have a black node that is at distance d — 1 of its root, and all of the other children must have d' >= d — 1. I solved this case via a second DP over the children of x.
Seems overly complicated... My code is here in case you want to check it out: http://codeforces.net/contest/736/submission/22556505
Thanks a lot. Great approach. It is really unwieldy.
Someone please explain the solution of "Ostap and the tree". What is the recurrence state? The editorial is not very clear. Thanks
A non-tex editorial?
Задача div2E/div1C
"Чтобы объединить две поддеревья, надо перебирать все пары (i,j) в обеих поддеревьев."
WTF?? Какие пары? Что за i и j? Пары вершин? Пары параметров динамики dp[v][i][j]? Для каких тогда вершин?
"Пусть имеем пары (a,c) в первом поддереве и (b,d) — во втором. Если min(a,c)+max(b,d)<=k, то обновляем значение в нынешней вершине."
a, c, b, d — произвольные числа? Почему для первого поддерева берется минимум, а для второго — максимум? Обновляем значение в нынешней вершине чем? К какому состоянию вообще обращаться?
Это, по-твоему, разбор задачи?
"According to Goldbach's conjecture, which is checked for all numbers no more than 10^9, every number is a sum of two prime numbers."
Actually, it states that every even number (integer, obviously), not every number is a sum of two prime numbers. A small lapse, I believe, for the rest of the solution is correct and based on the correct statement.
Can somebody explain the editorial for Div1D? I honestly have no idea what those three ideas are.
The determinant of a matrix is the sum of every combination of ((-1)^inv)*(the product of all the a[i][j] chosen) where every i and j doesn't repeat itself on another chosen pair and inv is the number of inversions on the number of columns/rows chosen. This means that it has information about the sum of every possible product without repeating the same row/column inside this matrix.
A key observation: -1=1 on MOD 2.
The inverse matrix is the transpost of the matrix of the cofactors. You get the cofactor of some position i,j by excluding the row i and column j and getting the determinant of the rest of the matrix and multiplying it by (-1)^(i+j). This means that the inverse matrix has information about every cofactor. Also, because of 2, you don't need to worry about the (-1)^(i+j)
If you change some a[i][j] from 1 to 0, the determinant will differ by the value of the cofactor associated to it because the 1 was originally multiplying cofactor and being summed to the original determinant. Think about Laplace's formula to calculate the determinant and you will understand. Since the inverse matrix has information about every cofactor, you can use it to get every single cofactor efficiently.
This is my take on this problem, it might have some mistake but I think that's it.
Please ignore. I miss a critical condition in the problem statement.
Just so anyone seeing this will understand: the problem would be when you can't get the inverse but since the number of permutations is always odd at the start, the determinant will be 1 on MOD 2. That means it is not equal to 0 and that's enough to say that you can get the inverse.
Thanks for the detailed explanation, it made me realise that my high school math has left me a huge hole in the concepts of matrix. If it wasn't you I wouldn't have thought of representing the combination of permutations in matrix. (They only bothered to teach me about finding the determinant of matrix using recursion in high school.)
PS: In case if anyone also got TLE using 2D array, use bitset should solve the problem.
can anybody explain the solution of [Ostap and Tree] not able to understand the part of editorial "Then let we have pair (a,c) in the first subtree and pair (b,d) in the second one. If min(a,c)+max(b,d)<=k, then we update value of current vertex."
what is the meaning of min(a,c) and max(b,d) here , what is the significance of this condition. and how to calculate the final answer ? I tried for two days but unable to grasp the solution. sorry for bad english.
For Problem E, Chess Championship, you're proof is that if there exists a solution, then set {2m-2, 2m-4..} majorizes {a1, a2..}, not the other way around, which is what you want. How do you prove that if set {2m-2, 2m-4..} majorizes {a1, a2..} then there exists a solution?
Also, another condition for the existence of a solution is that the sum of all a[i] is equal to m*(m-1).
Not able to understand the solution of 736C - Ostap and Tree. Can someone please explain this -> 22656733. What does dp[x][i] represent and also the transitions.
How does someone solve problem like D (Taxes), if he doesn't know the property of Goldbach's Conjecture. Is he supposed to derive this property on his own during a 2 hour contest?
Deleted
for the problem: 736A — Tennis Championship, I don't understand why the answer is not simply log((n+1)/2)... {where log is in base 2}.
what I am able to understand is that a player can only play with another player that has played same number of games or +/- 1 game.
Winner of the tournament needs to win all the rounds.
let's suppose 5 players: A, B, C, D, E; E is the winner of the tournament.
Following steps happen: (lets represent X[i] as number of matches played by X)
E plays with D: E[0] plays with D[0]
now we have n-1 players and at each level the number of players get halved
that is in our example: E[1] plays with C[0] = E[1] wins, A[0] plays with B[0] = B[0] wins, E[2] plays with B[1].
I don't get where the recursion is coming to place. Can anyone please help?