10989 - Bomb, Divide and Conquer

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Wed Feb 15, 2006 12:07 pm

Cho wrote:
misof wrote:I'm down to 2.870 :)
I've tried the same approach after reading your post, but TLE.
Could you tell me whether you use the same maxflow routine as your 10983 (Buy one, get the rest free) to solve this problem?
I had to play with optimizations to get this one. I have a pre-written maxflow, but it is in C++ and uses some STL (basically just a bunch of vectors). Of course, here at UVa the judge has an old g++, and compiles without the for-STL-necessary -O2, so this was quite a setback. This solution didn't pass even the 10 seconds time limit.

The first step was basically to rewrite it to plain C -- a global int G[][] instead of a vector< vector<int> > &G passed as a parameter, and such.

Other optimizations include:
- once the current flow exceeds your so-far-best cut, terminate it
- using a heuristic to get the first bound on the mincut (cutting off any one vertex)
- I fix a vertex v and search all pairs [v,w], I use an heuristic to choose v so that the above pruning is expected to be a bit more effective.\

One other optimization I didn't implement: run BFS first, and process the vertices w in decreasing distance order.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Mon Jun 05, 2006 11:28 am

after readin the posts i come to know the names of some algos... can any one plz give me web addr to know about these algos? [i searched in yahoo but did not find much helpful links.]

Karger's algorithm
Dinic's maxflow algorithm
Stoer and Wagner's algorithm

Thanks in advance.

Mahbub
Self judging is the best judging!

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Mon Jun 05, 2006 2:35 pm

You'd better google them. Queries like "Karger min cut" will easily get you this link.

Good luck!
JongMan @ Yonsei

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Mon Jun 05, 2006 2:38 pm

Thanks
Self judging is the best judging!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Mon Jun 05, 2006 7:29 pm

I can't understand Dinic's algortihm. can any one please make me understand it through example?
Self judging is the best judging!

nima101
New poster
Posts: 2
Joined: Sat Jun 02, 2007 11:48 pm
Contact:

WA on 10989

Post by nima101 » Wed Jun 06, 2007 7:29 pm

hi everybody.
I've applied the Stoer-Wagner algo to find the min-edge-cut
but I'm getting WA!
I've tried any kind of test cases... (disconnected graph, containing bridge, complete graph, ....)
is there any tricky test data???
can any one give me some test data plz...
tnx in advance.

nima101
New poster
Posts: 2
Joined: Sat Jun 02, 2007 11:48 pm
Contact:

Post by nima101 » Wed Jun 06, 2007 7:47 pm

shanto86 wrote:after readin the posts i come to know the names of some algos... can any one plz give me web addr to know about these algos? [i searched in yahoo but did not find much helpful links.]

Karger's algorithm
Dinic's maxflow algorithm
Stoer and Wagner's algorithm

Thanks in advance.

Mahbub
read Stoer-Wagner algo + Karger-Stein algo here:
http://maagar.openu.ac.il/opus/Static/b ... s%5D_0.pdf
and here's a good step-by-step sample for stoer-wagner algo:
http://www.cs.dartmouth.edu/~rahul/Teac ... mincut.pdf

good luck.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Fri Jun 08, 2007 2:59 pm

I got AC using stoer wagner's algorithm! Thanks a lot nima!
Self judging is the best judging!

LucasSchm
New poster
Posts: 17
Joined: Mon May 18, 2009 10:00 pm

Re:

Post by LucasSchm » Sun May 09, 2010 12:03 am

nima101 wrote:
shanto86 wrote:after readin the posts i come to know the names of some algos... can any one plz give me web addr to know about these algos? [i searched in yahoo but did not find much helpful links.]

Karger's algorithm
Dinic's maxflow algorithm
Stoer and Wagner's algorithm

Thanks in advance.

Mahbub
read Stoer-Wagner algo + Karger-Stein algo here:
http://maagar.openu.ac.il/opus/Static/b ... s%5D_0.pdf
and here's a good step-by-step sample for stoer-wagner algo:
http://www.cs.dartmouth.edu/~rahul/Teac ... mincut.pdf

good luck.
Did anyone saved those pdfs? The links are down :(

fidels
New poster
Posts: 6
Joined: Thu Jan 25, 2007 4:07 pm
Location: La Plata, Argentina

Re: 10989 - Bomb, Divide and Conquer

Post by fidels » Mon Jun 21, 2010 3:04 am

at least one of the pdf's is still online: http://www.cs.dartmouth.edu/~ac/Teach/C ... mincut.pdf

do go to http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/, as it seems to have a few very interesting resources ;-)

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: WA on 10989

Post by DD » Sun Mar 13, 2011 4:24 am

nima101 wrote:hi everybody.
I've applied the Stoer-Wagner algo to find the min-edge-cut
but I'm getting WA!
I've tried any kind of test cases... (disconnected graph, containing bridge, complete graph, ....)
is there any tricky test data???
can any one give me some test data plz...
tnx in advance.
I also implement Stoer-Wagner algorithm and get AC. My program checks the input graph is a connected component or not. If it is not a connected component, output 0; otherwise, find min-cut by using Stoer-Wagner algorithm. :)
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

Post Reply

Return to “Volume 109 (10900-10999)”