## Search found 40 matches

Thu Oct 13, 2005 9:17 pm
Forum: ACM ICPC Archive Board
Topic: 3294,3295 - problems
Replies: 8
Views: 2109
:( 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: 2714
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: 2109

### 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: 2714

### 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 BFS and aug...
Sat Oct 01, 2005 10:05 pm
Forum: Algorithms
Topic: Mincost Maxflow - help!
Replies: 7
Views: 2714

### Re: Mincost Maxflow - help!

Cost scaling(which is a cost scaling variant of successive shortest paths). has O(nm lg U) complexity. : 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, Network ...
Sat Oct 01, 2005 9:02 pm
Forum: ACM ICPC Archive Board
Topic: Problem Alibaba from SouthEastern Europe 2004/2005
Replies: 1
Views: 1069
See the discussion here.: http://forums.topcoder.com/?module=Thread&threadID=398406&start=0&mc=12#398479 In the last message in the thread I discuss an algorithm, which is still O(N^2) but with some tricks to speed up the code. I haven't implemented the algo. If you decide to try it, please tell me ...
Sun Feb 13, 2005 9:24 pm
Forum: Algorithms
Topic: Special case of Hamiltonian cycle
Replies: 4
Views: 1473
alex[LSD] wrote:Got AC, sad that I can't come up with trics like this.
I don't know if that can make you feel better, but I didn't come up with it either. I just had studied the theorem (and its proof) when I was at university
Sun Feb 13, 2005 1:59 pm
Forum: Algorithms
Topic: Special case of Hamiltonian cycle
Replies: 4
Views: 1473

### 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. I h...
Mon Feb 07, 2005 2:52 am
Forum: Volume 8 (800-899)
Topic: 880 - Cantor Fractions
Replies: 24
Views: 17414
Hi, I got TLE, can anyone say what's wrong ? #include<stdio.h> void main() { unsigned long long n,x,p; while(scanf("%llu",&n)==1) { x=1; while((p=x*(x+1)/2)<n) { if(p>=n) break; else x++; } printf("%llu/%llu\n",1+(p-n),x-(p-n)); } } Well, I haven't attempted the problem, but if the input value can ...
Sun Feb 06, 2005 10:39 pm
Forum: Algorithms
Topic: Number of n-element permutations with exactly k inversions
Replies: 2
Views: 1130

### Re: Number of n-element permutations with exactly k inversio

tytus 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: 1829
hi ,i used KMP for this problem(10679). it gets lime limit exceeded. I didn't check your code carefully , but you seem to rebuild your failure table for each query, and that is too time consuming. You should build it only once for the big string, then use the obtained table to process the queries.
Sat Jan 29, 2005 10:59 pm
Forum: Volume 4 (400-499)
Topic: 454 - Anagrams
Replies: 97
Views: 21505
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: 21505

### 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: 13267
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: 10048

### 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 ?