What should be the approach to find all paths with maximum flow? The graph is directed acyclic graph and the maximum number of nodes(vertices) in the graph can be 40 and edges around 80. Also, most of the edges have unit capacity.
# | User | Rating |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
# | User | Contrib. |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | adamant | 155 |
4 | cry | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
What should be the approach to find all paths with maximum flow? The graph is directed acyclic graph and the maximum number of nodes(vertices) in the graph can be 40 and edges around 80. Also, most of the edges have unit capacity.
Help needed in the following problem :
There are N (1<=N<=200000) line segments (end-point coordinates are positive integers less than 1e9). The task is to merge the line segments that are overlapping and finally print the coordinates of all the merged line-segments.
Sample Test Case
N = 4
Line segments:
[(1,1) (5,1)]
[(4,1) (7,1)]
[(3,3) (9,3)]
[(5,3) (8,3)]
The answer for this test case would be :
[(1,1) (7,1)]
[(3,3) (9,3)]
My Approach : Consider each line segment as a vertex and make edges between segments U and V if U and V overlaps. Then, find the connected components. For each connected components, answer can be calculated by taking the min of left coordinates and maximum of right coordinates. But this approach is O(N^2) and will not work for N=200000.
Can someone explain me how to solve this problem http://poj.org/problem?id=1927 If the length of rope is smaller than the perimeter of circle with radius equal to radius of inscribed circle, we can directly find the answer. But, how to deal with cases when length of the rope is greater than perimeter of such circle and less than perimeter of triangle.
this contest is organised in techniche,annual technical fest of IIT GUWAHATI. the link to the contest is: http://www.codechef.com/BTCD2012/ Its duration is from 12 Aug to 26 Aug. Its got good mathematical problems which require your skills of beating the time. Enjoy and Code!!!!
It was my first contest.As a beginner,it was quite challenging for me.The questions were great and thought provoking.Hope everyone enjoyed that. Thanking codeforces for organising such a fantastic contest. CODERS rock!!!!
I have just started using codeforeces and I am spell bound and totally i awe after seeing its interface.Its an awesome website for beginners, with the facility of seeing test cases enable the new programmers to find the bugs in their code. Codeforces rocks!!!
Name |
---|