Hi there!
Tomorrow Today at 19:00 MSK will be held Topcoder SRM 670.
Let's discuss problems after contest!
# | User | Rating |
---|---|---|
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 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
4 | atcoder_official | 161 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Hi there!
Tomorrow Today at 19:00 MSK will be held Topcoder SRM 670.
Let's discuss problems after contest!
Name |
---|
Is https://arena.topcoder.com/ loading??
How to solve Div. 1 1000?
Oops, I was wrong, we should fix the order of vertices, not edges. I'll try to explain more clear.
Suppose we have some graph. Let's build it spanning tree adding edges in order (0, 1), (0, 2), ..., (0, n-1), (1, 2), ..., (n-2, n-1) (of course edge is added only if it's presented in graph and if it does not make a cycle). This is what I called lex-min MST. Clearly, all connected graphs are split into equivalency components such that lex-min MST of all graphs from one component is the same.
Now, let's fix some spanning tree with edges e1, ..., en - 1. count number of graphs with such lex-min MST. What can we say about such graphs? We know that edges e1, ..., en - 1 must be in the graph. More, for some other edges we know that they must not be in the graph, because otherwise lex-min MST would be different.
So we have a problem: for each edge we either must include it, or must not, or this edge does not matter. In terms of problem it means that we should take a linear combination of input graphs such that on some positions there are 1-s and on some there are zeros. How to count them? Remove all columns corresponding to edges which we don't care for. Now check using Gauss method if we have at least one way to make this linear combination. If yes, total count is 2m - r, where m is the number of vectors (input graphs) and r is the rank of matrix with selected columns.
The answer for the problem is sum of answers for all permutations of n vertices. Thus overall complexity is O(nn - 2·mn2) (because there are nn - 2 trees on n vertices). It probably won't fit into time limit so we should build trees recursively and do Gauss steps one by one in recursion.
"Thus we fix a lex-min spanning tree". Can you explain this? You iterate over every possible spanning tree?
I tried to explain a bit more clear in the update.
Thanks a lot for explaining. I have one more doubt.How are you fixing the tree based on the ordering of vertices alone? It looks you are fixing that the tree must be a path to me.
I was wrong again, sorry, fixed now. This is the solution described mostly by my teammate, at first I didn't understand him properly.
I didn't get your solution, how can you know that some edges should be in the resulting graph? Two spanning trees can be valid and disjoint!
If you build a spanning tree like in Kruskal algorithm adding edges in order I described then you'll get a unique spanning tree for each graph.
My solution doing this runs in 1.9s on system tests.
With doing one iteration of gauss on each step of recursion or without this optimize?
Yes, I maintain the rows online in this bruteforce.
Intended solution was to count for each partition number of subsets where there is no edges between different part. Then you can calculate the answer using exclusion formula.
I was really surprised during contest that when I coded program to compute correct multiplicities it turned out that if I consider partition to k parts I have to multiply it by (k - 1)!( - 1)k - 1 :). I was rather expecting some random values. I really enjoyed solving this problem :).
How to solve Div 1 250?
LCS is always n - 1, so you need to move one character so that the new string is also correct and it differs from original string. You can store all these strings in a set and the answer will be the size of the set.
How to solve Div2 1000?
For each red player, find the maximum time till which it can play the game. To do that,Let
dB[i] = Min time in which any player B can reach node i
dA[i] = Time in which current red player under consideration can reach node i.
We basically try to find the minimum time till which all the red ones can survive in the game . To that for each red player we find the max time till which it can play the game and take min over all these.
My idea is:We want to focus on a single red token,it doesn't matter a set of them,just one,so all blue tokens can focus on it and catch it.
Ok.Now for this red token,we want a path so it resists maximal time.How does this path look?Like a normal path,because if we go on an edge,and come back from it,it's like staying.
Good,so we fix a node to go (i is red token,j is final node).Now we also want to see if the red token,on it's way ,is safe(no blue token catches it before reaching j).
This can be done with some array(dp[x]=minimal time for a blue token to reach x).And then for every node on path(excluding j,cuz already we want to catch i on j) we compare time[i][x] with dp[x].
Taking into account all GOOD possible paths for i,we want the one with maximal time(to resist more).Take care that for a path(i going to j),the time to catch i is dp[j].
Also from all red tokens,we choose one that we can catch fastest.
Complexity O(n^3).
my idea is the same during contest and passed. But i found a counterexample after that. if te tree is 1-2-3-4-5-6-7 and 1/7 is playerB and 4 is player A. The algorithm gives ans 3 but it should be 4. So i guess the system test cases may be very weak. Correct me if anything wrong
Isn't the answer 3 only?
aaaa yah im sorry i rethink the problem this morning and remember one player can move only ONE node once. I check the problem and found he can move SOME of the nodes
I am struggling with div1 250.
Correct solutions say that the answer for input string "((()))" is 3 and suggest strings "(()())", "(())()" and "()(())" as those that fulfil problem statement (here the length of lcs is 4).
Mine solution however apart from above mentioned strings gives me one more string, namely "()()()".
The question. Why string "()()()" does not fulfil problem statement?
Here is my code btw. The DP's state is (pos in string, balance between opened and closed brackets, length of lcs )
Lcs is 5 in correct answers
cool, thanks. My bad.
Is it possible to solve this problem with dp? I suppose it is, however I have problems with doing it... My new DP with state (pos in given str, pos in str with brackets, lcs) is failing...
Look at this code http://pastebin.com/Qj2Ebw4E. I found it there http://kmjp.hatenablog.jp/entry/2015/10/11/0900. But I don't understand what mean abbreviation FORR
This is not a DP solutions though.
FORR macro walks each element in a container.
#define FORR(x,arr) for(auto& x:arr)
As k0st1a said, my solution is not DP.
What does mean CL(dp, 0); in your code?