## Search found 40 matches

- Thu Oct 13, 2005 9:17 pm
- Forum: ACM ICPC Archive Board
- Topic: 3294,3295 - problems
- Replies:
**8** - Views:
**2048**

:( 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:
**2661**

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:
**2048**

### 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:
**2661**

### 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:
**2661**

### 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, Network ...

- Sat Oct 01, 2005 9:02 pm
- Forum: ACM ICPC Archive Board
- Topic: Problem Alibaba from SouthEastern Europe 2004/2005
- Replies:
**1** - Views:
**1029**

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:
**1427**

- Sun Feb 13, 2005 1:59 pm
- Forum: Algorithms
- Topic: Special case of Hamiltonian cycle
- Replies:
**4** - Views:
**1427**

### 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:
**17149**

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:
**1097**

### 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:
**1785**

- Sat Jan 29, 2005 10:59 pm
- Forum: Volume 4 (400-499)
- Topic: 454 - Anagrams
- Replies:
**97** - Views:
**20873**

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:
**20873**

### 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:
**12997**

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:
**9920**

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