Search found 40 matches
- Thu Oct 13, 2005 9:17 pm
- Forum: ACM ICPC Archive Board
- Topic: 3294,3295 - problems
- Replies: 8
- Views: 2821
:( i heard about Red black tree, i also heard about interval tree. but what is 2-D interval tree?? can any one tell me or give a link to any site where i can find it. i gave a search at google but no satisfactory result :cry: I think he meant 2D range trees, augmented with Max information: see this...
- Thu Oct 06, 2005 11:14 pm
- Forum: Algorithms
- Topic: Mincost Maxflow - help!
- Replies: 7
- Views: 3583
I believe it gives the impression that you should accumulate in the edge cost c(i,j) the values of - pot +pot[j], when what you really should do is something like c(i,j) = originalCost(i,j) - pot + pot[j]. I hope my explanation is clear enough. Yes, you're right. There's one thing I would like to u...
- Tue Oct 04, 2005 9:26 pm
- Forum: ACM ICPC Archive Board
- Topic: 3294,3295 - problems
- Replies: 8
- Views: 2821
Re: 3294,3295 - problems
The ultimate bamboo eater is something strange - anyone has an idea? All my ideas run out of time. the triangle counting is kind of easy, but what do you do with finding the lines with more than 2 points one them? I mean, how? I think 3295 has been solved there: http://forums.topcoder.com/?module=T...
- Tue Oct 04, 2005 8:18 pm
- Forum: Algorithms
- Topic: Mincost Maxflow - help!
- Replies: 7
- Views: 3583
Re: Still...
I've read about 200 times each of these .pdfs, but I can't quite understand the algorithm :oops: My code is something like this: 1. Run a Dijkstra and set the initial "potencial" value on the nodes to -d[i], where d[i] is the minimum distance from the source node to the node i. 2. Run a B...
- Sat Oct 01, 2005 10:05 pm
- Forum: Algorithms
- Topic: Mincost Maxflow - help!
- Replies: 7
- Views: 3583
Re: Mincost Maxflow - help!
Cost scaling(which is a cost scaling variant of successive shortest paths). has O(nm lg U) complexity. [Edit]: sorry what I said above is totally wrong In fact, one of the fastest algo is the double scaling algorithm which has a time complexity of O(nm logU log (nC) (Ahuja, Magnanti &Orlin, Netw...
- Sat Oct 01, 2005 9:02 pm
- Forum: ACM ICPC Archive Board
- Topic: Problem Alibaba from SouthEastern Europe 2004/2005
- Replies: 1
- Views: 1424
- Sun Feb 13, 2005 9:24 pm
- Forum: Algorithms
- Topic: Special case of Hamiltonian cycle
- Replies: 4
- Views: 2111
- Sun Feb 13, 2005 1:59 pm
- Forum: Algorithms
- Topic: Special case of Hamiltonian cycle
- Replies: 4
- Views: 2111
Re: Special case of Hamiltonian cycle
I need help with: http://acm.sgu.ru/problem.php?contest=0&problem=122 If you don't want to open it, the problem is: You have an undirected graph with N vertices. Each vertex has at least (N+1)/2 neighbours. Needed is to construct a hamiltonian cycle. I guess it is assumed that it always exists....
- Mon Feb 07, 2005 2:52 am
- Forum: Volume 8 (800-899)
- Topic: 880 - Cantor Fractions
- Replies: 24
- Views: 20880
- Sun Feb 06, 2005 10:39 pm
- Forum: Algorithms
- Topic: Number of n-element permutations with exactly k inversions
- Replies: 2
- Views: 1542
Re: Number of n-element permutations with exactly k inversio
http://academic.csuohio.edu/bmargolius/ ... invers.htmtytus wrote:How to find number of n-element permutations with exactly k inversions?? (n,k are given)
- Sun Jan 30, 2005 1:35 am
- Forum: Algorithms
- Topic: Please tell me the number of KMP's application problems,thx.
- Replies: 4
- Views: 2469
- Sat Jan 29, 2005 10:59 pm
- Forum: Volume 4 (400-499)
- Topic: 454 - Anagrams
- Replies: 97
- Views: 32540
Thx for your reply nnahas. I didn't realize that this is a multiple input problem. :wink: However, I have corrected this problem and I got RTE, again. input .junta[k]='\n'; } I think the above line has an error, because your string is not null terminated. You should write input .junta[k]=0; That is...
- Sat Jan 29, 2005 12:12 am
- Forum: Volume 4 (400-499)
- Topic: 454 - Anagrams
- Replies: 97
- Views: 32540
Re: 454 RTE Please, help me!!!!!!!
I got RTE several times, please help me. if(input[i].original[0]==' ') I didn't check very carefully but I think the above line of code has an error. Are you assuming a blank line starts with space character ? What if it is empty? Also your code looks like you are solving for a single test case . R...
- Wed Jan 26, 2005 7:30 pm
- Forum: Volume 108 (10800-10899)
- Topic: 10805 - Cockroach Escape Networks
- Replies: 38
- Views: 17253
c-Try to find a BFS Tree such that all these nodes are descendants of the same child of v. if such a BFS tree exists , then there is a tree of diameter 2*MaxDist , otherwise all we can say is that there is a tree of diameter 2*MaxDist +1 . That value will be an upper bound on the diameter. the leas...
- Tue Jan 25, 2005 12:48 am
- Forum: Volume 5 (500-599)
- Topic: 532 - Dungeon Master
- Replies: 39
- Views: 13881
Re: 532 WA ('ve tried some in/output...T^T)
I don't understand your algorithm. It looks something like floodfill , but you can't use floodfill here because you're looking for shortest time not just for connected components so you should use Breadth First Search . Could you explain your algorithm please ?