Search found 519 matches

by sclo
Sat Jan 28, 2006 8:16 am
Forum: Volume 109 (10900-10999)
Topic: 10988 - From G to H and back
Replies: 11
Views: 3784

Still no success at getting accepted. My program will fail all the graphs on Mathworld. I've tried adding more vertices and edges (keeping the property that they contain the induced subgraph) and they still fail. Now I keep getting wrong answers. One thing, if my algorithm says yes, it is definitely...
by sclo
Sat Jan 28, 2006 8:08 am
Forum: Volume 109 (10900-10999)
Topic: 10984 - Double NP-hard
Replies: 32
Views: 10412

Hint: Think about how you can find a lower bound for the minimum number of nodes in the vertex cover (it turns out, if you find the right lower bound, that it is in fact the solution). Another Hint: In a bipartite graph, the size of the minimum vertex cover can be found in polynomial time. We can t...
by sclo
Sat Jan 28, 2006 1:18 am
Forum: Volume 109 (10900-10999)
Topic: 10985 - Rings'n'Ropes
Replies: 11
Views: 4343

Finally got the O(n^3) algorithm instead of TLE. Thx for all the ideas on this board.
by sclo
Fri Jan 27, 2006 10:51 pm
Forum: Volume 109 (10900-10999)
Topic: 10984 - Double NP-hard
Replies: 32
Views: 10412

I had the same problem with presentation error, I don't know what's wrong, but definitely there's some problem with the judge's output format. I'm sure mine is correct.
by sclo
Wed Jan 25, 2006 10:05 pm
Forum: Volume 109 (10900-10999)
Topic: 10988 - From G to H and back
Replies: 11
Views: 3784

I have some sort of greedy algorithm that can fail all 9 of those graphs, now I just need to make sure that a graph can pass if it doesn't contain those induced subgraphs. I bet that this is linear.
by sclo
Wed Jan 25, 2006 9:53 pm
Forum: Volume 109 (10900-10999)
Topic: 10989 - Bomb, Divide and Conquer
Replies: 25
Views: 13205

There is a faster randomized algorithm for this problem, finding mincut from a graph.
by sclo
Mon Jan 23, 2006 11:54 pm
Forum: Volume 1 (100-199)
Topic: 170 - Clock Patience
Replies: 28
Views: 2515

by sclo
Mon Jan 23, 2006 11:49 pm
Forum: Volume 1 (100-199)
Topic: 100 - The 3n + 1 problem
Replies: 1394
Views: 185232

this problem is not the easiest problems, if you're new, try some other problems first
by sclo
Mon Jan 23, 2006 10:51 pm
Forum: Volume 109 (10900-10999)
Topic: 10988 - From G to H and back
Replies: 11
Views: 3784

10988 - From G to H and back

Is there any hint for this question?

Go to advanced search