OJ Board

:( 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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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

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 ...

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 ...

tytus wrote:How to find number of n-element permutations with exactly k inversions?? (n,k are given)

http://academic.csuohio.edu/bmargolius/ ... invers.htm

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 ...

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 ...

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 ...

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 ...

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 ?