Всем привет!
Завтра в 14:00 MSK состоится Topcoder SRM 687.
Приглашаю всех поучаствовать и предлагаю обсудить задачи после контеста.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 25.04.2024 05:11:00 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
Starts in less than an hour.
I forgot about it :-(
Spend half an hour trying to compile my code using Arena.
Now I can't even try to challenge anyone. 'Your request timed out'.
How to solve the Div-1 500?
Maybe cgy4ever has one of his crazy simple solutions, but notice that if a graph exists, then a tree exists. min-cut from u to v in a tree is simply smallest edge in the path from u to v, so you can greedily add the edges in the matrix from largest to smallest weight as long as the graph remains a tree (no cycles are formed).
This tree is called Gomory-Hu tree :)
And the algorithm he described is called Kruskal.
I did exactly like that (kruskal for max spanning tree), but failed systest. Just noticed that the problem need connected graph, (we can add edge with weight = 0), at first I think the problem only reject empty vector (if the flow matches the given input). Next time I should to read problem more carefully :X
Yup. Figured that out with 2 minutes to spare, sadly couldn't code it up in a way that accounts for the possibility of no solution (if a solution were guaranteed, you just return a copy of the row containing the largest element, with a single zero removed).
Basically I'm pretty sure the answer is look for the largest element (or rather any one of them), construct a bidirectional edge from the row index to the column index (it is evident that the largest edge must be on the very end). Then from now on look only in that row. Look for the largest element (remember, only in the chosen row) whose index hasn't been added yet (you can do this very naively). Now add an edge from the last added index to that index, with the given weight. Continue until every vertex is accounted for. Do a modified Floyd-Warshall (with max instead of min, and min instead of add) on the resulting graph. Change all i,i values to zero because the problem says so. If the result is the exact same as your input matrix, return a copy of the row, minus the i,i element. If it's not, then return -1 since this means there is no solution.
Does that sound right?
Just found a counterexample... so I guess instead you could do the following. Find the largest value... that edge is still in the tree. After that, find the largest value in the whole matrix that contains at least one vertex that hasn't been added yet. Add that edge. Continue until you've added n-1 edges. Now do the modified Floyd-Warshall check I mentioned above, but instead of a row, return the added weights.
What is the proof that if a graph exists, then a tree exists?
the proof is Gomory-Hu tree. As mentioned before.
500 div1: https://www.e-olymp.com/ru/problems/5468
Original contest — http://codeforces.com/gym/100153.
Oh, we even got a "first to solve" on this task during that contest :D. I came up with solution (since it's trivial if somebody knows about Gomory-Hu tree) and Smu coded it :).
Why every sample in medium that results in a graph results in a star graph with center at zero? Was that intended?
Wasn't answer to pretest 2 a triangle? (Although it could be also a chain of length 2, which is indeed a star graph)
How to solve div2-1000 ?
Окей, заслать какую-то полнейшую ересь по 1000 и внезапно получить АС — achievement unlocked:)
Кто-нибудь может рассказать, почему верно или не верно такое решение? (Мне кажется, что оно должно быть вообще не верно, потому что венгерский алгоритм находит максимум в среднем, а мы хотим, чтобы максимумы в каждой строке образовывали паросочетание):
1). Заменить все веса ребер на ∞ - wij
2). Запустить венгерский алгоритм. Для каждого ребра j если происходит изменение wij + = A (то есть j правой доли была посещена в последней итерации прохождения по чередующимся путям, а i левой нет) добавлять A к ansj
3). Вернуть ∞ - ans
Двойственная задача к взвешенному паросочетанию — такая:
найти веса ws, wt для вершин (обоих долей), такие что:
Для любого ребра s - t, ws + wt ≤ ws, t,
Несложно заметить, что если есть решение двойственной задачи, то оптимальное взвешенное паросочетание достигается на рёбрах ws + wt = ws, t. Т.е. если бы мы могли менять высоты вершин обоих долей, то потенциалы из Венгерки дали бы решение, где рёбра ответа 0, а остальные ≤ 0. Теперь забьём на потенциалы чуваков, оставим только destinations. Тогда рёбра ответа уже не 0, но порядок рёбер у чуваков сохранится.
How to prove that greedy strategy works for Div 1 250?
Let's assume greedy works for every number between 2 and N - 1.
Let's define Ai as the biggest number in the sequence s.t. Ai = N or Ai < N - 1. The number N - Ai is smaller than N and is not 1, so for it a greedy strategy works.
The only thing left to show is that the greedy solution for N - Ai does not contain Ai and therefore no number is duplicated. (Obviously, it will not contain numbers bigger than Ai). Let's assume the opposite. Then N - Ai ≥ Ai, then N ≥ 2 * Ai ≥ Ai + Ai - 1 - 1 = Ai + 1, which contradicts our definition of Ai.
Thanks!
Hey , I think you missed out Ai = N - 1.
We can still show in this case too, there always exists an answer:
Ai - 1 + Ai - 2 - 1 = N - 1. that implies:
Ai - 1 + Ai - 2 = N ( For all i > 2)
It is a question of definition of Ai. Look again at mine — I don't define it as a largest element of sequence not exceeding N, I say that Ai is never N - 1, which implies that when largest element of sequence Fx not exceeding N is N - 1, I instead use Ai = Fx - 1, and so N = Fx - 1 + Fx - 2.
Let's say N = 10
According to your definition of Ai, Ai = 6. Here N is in fact >= Ai+1 which is 9, so how does it contradict your definition of Ai?
I don't think I got that proof properly
Yes, according to my definition, Ai = 6. Which is exactly why according to the strategy I described we will choose the solution (6, 4), instead of trying (9, ???) which won't work.
Using induction method
Now the hard question comes: How to solve div1Hard? The only thing I noticed was that the negative difference was not a problem, because if we have an answer a0, a1, .., a(N-1) we can substract the minimum, obtaining at least one 0, guaranteeing the existence ofpozitive maximum difference for each allien, but I'm not even sure if this observation is usefull.
There was a thread in Russian UI about it already. The solution is as follows. Let's solve weighted-matching problem (in graph with weights - wij) together with its dual (most algorithms provide dual solution — potentials in Hungarian algorithm, potentials for Dijkstra inside min-cost-max-flow). Then just take - πi where i is a destination, and possibly adjust all of them so that they're non-negative.
Proof. Dual problem for weighted matching is as follows:
find weights ws, wt for all vertices, so that:
For each edge s - t, ws + wt ≤ ws, t,
One can notice that for an optimal solution of dual problem, every optimal solution of weighted-matching problem uses edges with ws + wt = ws, t. I.e. if we can adjust both skiers and destinations, we can adjust them with πi, and get a graph where there is a full matching on edges with adjusted weight 0, and all other edges have adjusted weight ≤ 0. This would be enough for us, but we cannot touch skiers. Fortunately, if we just ignore them, relative order of their edges preserves, and potentials of destinations still give us a solution.
Hello everyone. I was the author for this round, and this is my 11th SRM. To be honest, this is probably not one of my better rounds because div1 med/hard were standard problems, but I had thought before they were not too standard, so I hope you still enjoyed seeing them.
Here are some solutions:
div2: http://pastebin.com/Qg6gSjyc
div1: http://pastebin.com/JJvhwVbA
Quorum — sort the array and take the sum of the first k numbers
Quacking — Greedily spell quack until string is empty. Also, you can see the solution that I linked.
Queueing — Instead of the probability distribution, we can say a cashier with experience p has probability 1/p of successfully processing a customer at any particular second. So, we can write a dp[i][j] -> prob that first cashier finishes if there are i people in the first line and j people in the second line. See the code for how to compute this dp table.
AlmostFibonacciKnapsack — Greedy works (i.e. choose largest a[i] <= x), except when a[i]+1 = x, but in that case a[i-1]+a[i-2] works. You also need to show that indices will be unique, but I'll leave the proof up to the reader.
AllGraphCuts — It's tempting to google and find Gomory Hu tree. But that is too complex for this problem. Instead, this problem is almost exactly like: http://codeforces.com/contest/632/problem/F. We can show that a solution exists if and only if the diagonal is zero, the matrix is symmetric and x[i][j] >= min(x[i][k], x[k][j]). If this condition is satisfied, then you can find a maximum spanning tree to get the actual graph.
Comments: I felt this was a fairly standard problem, and I originally set the difficulty as div2 hard. However, I thought it was also ok as a div1 med. It has shown up on a previous contest before (based on comments above), so I apologize for that.
AlienSkiSlopes — Suppose there isn't a perfect matching. Then, by Hall's theorem, there exist a subset of aliens S, such that their neighborhood to destinations T is smaller than S. Then, we increase all the heights of destinations until someone in S wants to choose something outside of T. Note that this may destroy some edges from aliens not in S to destinations in T. However, we can show that a modification of this process will terminate. (this is modified from cgy4ever's logic) Namely let's choose S,T such that D=|S|-|T| is maximized, and if there are still ties then find one with |S| minimized. You can show that D will increase, or D will remain the same and |S| will increase. To see this, even if we remove all edges from non-S to T, for each subset A of non-T: |adj(A)| >= |A| (otherwise let (S + A) be the new S, we will get a larger |S| — |T|).
You can also use this to show an answer always exists. Suppose that aliens can choose destinations with negative height differences. Then, if X is a solution, then adding any constant to all elements of X is also a solution. So, we can shift them until one of the entries in X is zero. Now, the maximum height difference for all aliens is nonnegative, so this is also a valid answer for the original problem.
Comments: I knew about the Hungarian algorithm, but I didn't actually understand how it works. It seems most competitors found a solution using the potentials computing during the Hungarian algorithm, so this reduced to a standard problem. I need to study my algorithms more.
Sorry, I read your code but just can't know exactly how div2 1000 works. Assume q1 as the probability cashier1 finishes this second, q2 as the probability cashier2 finishes this second. dp[i][j] = dp[i-1][j]*q1*(1-q2) / (1- (1-q1)*(1-q2)) + ... so this means that one of the possiblity that c1 processes i people quicker than c2 processes j people contains: c1 processes (i — 1) people quicker than c2 processes j people, and now, c1 processes 1 more person but c2 doesn't, and this probability is divided by the prob that someone has processed a person. So how does this solution take care of the situation that c1 processes more quickly and even if c1 stops for a while, it could still be quicker than c2? Thanks. I just don't quite understand the solution. And would someone kindly provide a more detailed description of this solution?
It might be easier to restate the problem. Let's say we have two people. Person 1 has a coin that comes up heads with probability 1/p1=q1, Person 2 has a coin that comes up heads with probability 1/p2=q2. Let X be the random variable representing the number of tosses person 1 takes to get len1 heads, and Y be the random variable representing the number of tosses person 2 takes to get len2 heads. We want to compute the probability X<Y. This is equivalent to the original problem.
Now, the dp works as follows. At a particular second, person 1 still needs to toss i heads, and person 2 needs to toss j heads. Now, four things can happen. Person 1/2 can toss heads/tails. So we can compute dp[i][j] = dp[i][j]*P(TT) + dp[i-1][j]*P(HT) + dp[i][j-1]*P(TH) + dp[i-1][j-1]*P(HH). The base cases are dp[0][j>0] = 1 and dp[0][0] = 0.
It seems dp[i][j]*P(TT) didn't include in your codes. Could you tell me why? Thanks
Note that the recurrence is circular, so evaluating as is isn't correct.
Instead, write it as dp[i][j] — dp[i][j]*P(TT) = X => dp[i][j](1-P(TT)) = X => dp[i][j] = X/(1-P(TT)), where X = dp[i-1][j]*P(HT) + dp[i][j-1]*P(TH) + dp[i-1][j-1]*P(HH).
Hello, why the base case i.e. :
Probability to make 0 heads by person 1 and j > 0 heads by person 2 is exactly 1?
For eg: dp[0][1] represents that the second guy has exactly 1 Head and first guy has no Heads yet. How can the probability of this happening be 1?
Thanks! I think I understand how that works. Still another question, why would the original probability that
be equivalent to at any particular second one process a customer successfully with a probability of 1/p ?
Is that: At any particular second, assume the probability is P, then, a cashier would end up this second if he started 1, 2, 3... seconds ago:
(which is wrong but i can't figure out how.)
Could you please add a detailed editorial also to the TopCoder problem set analysis? http://apps.topcoder.com/wiki/display/tc/Algorithm+Problem+Set+Analysis
Could anyone explain solution of Div.2 C, please?
Could someone explain to me the implementation of Div-2 500 ? Understand the idea but not the implementation. Thanks.
At each step keep deleting multiple subsequence "quack" that donot coincide in string a. If in the end you found a non empty string in then answer is -1 else it will be a positive integer.
Problem lies here -> While searching for subsequence you need will delete terms in string but what if in the end you didn't find "quack" in it?
Example -> quackq
We delete first quack then we delete q thinking we will find subsequence in it.
This is not what we want.
So we will save from where we start assuming that we will find a subsequence. And if we don't find it then add the remaining part of the string.
Code
div 2 medium. solution idea
DIV — 2 1000, anyone ??