OJ Board

6.Minimum circle enclosing n points->O(nlog n)+O(h^3),where h is the number of points on convex-hull. O(n) is optimal for this problem, but for all purposes, O(n log n) using furthest point voronoi diagram is sufficient. The center will be either a vertex or on an edge of the diagram. There is also...

windows2k wrote: http://acm.pku.edu.cn/JudgeOnline/show ... m_id=1738
It looks an classic DP problem, but it seems have terrible time limit.
Could someone give some hints? Thx

I think you could solve it using Hu-Tucker algorithm, but it seems to be very complicated.

My (accepted) program's output is:

[cpp] for(y=0;y<m;y++) { scanf("%s",str); for(u=0;u<n;u++) if(strcmp(name ,str)==0) break; scanf("%s",str); for(v=0;v<n;v++) if(strcmp(name[v],str)==0) break; fu=find(u); fv=find(v); if(fu==fv) continue; link(fu,fv); } [/cpp] It's simply too slow - it's possible that you do n*m s...

No...when you try make some vertex of gem with price i you must make all its children of different kinds of gems. So for each child you must choose "best" gem - if you just remember all solution, you must look at each of them. But if you remember only two best ones, then in one of them thi...

First prove that there are at most m=1+log_2 n different kinds of gems in the optimal solution. Then use dynamic programming: for each vertex try to made it of gem with price 1,2,...,m. It should give you O(nm^2) algorithm which you can speed up to O(nm) by observing that it's enough to remember two...

I think it was rather runtime error than a real wrong answer. program p10625; const MIN = 33;MAX = 126; type row = array[MIN..MAX] of int64; matrix = array[MIN..MAX] of row; var TempM,m,m1:matrix; inp,i,j,k,tests,rules:integer; number,Left,Right:integer; ch,letter:char; s:array[MIN..MAX] of integer;...

You can read about this algorithm (and many others in
M. Crochemore, W.Rytter, Text Algorithms
It's possible to download it from author's webpage:
http://web.njit.edu/~rytter/TEACHING/TEXTS/book.html

Maybe dynamic programming? For each 1<=i<=w and S - subset of fields in the ith column calculate number of different ways fields in the i-1 first columns AND S can be filled.

I don't know how you want to get O(n) complexity with union-find. As far as I know it will be rather O(m\alpha(m,n)).

It's possible to solve this problem by finding maximum matchings, you have to add to this graphs edges so that it becomes d-regular (where d is maximum vertex degree). From Hall's theorem such graph has exactly d edge-disjoint perfect matchings, so we can just color each of them with one color and t...

Just make big table bool t[5000][5000] and set t[x][y] iff there is point with (normalized) coordinates (x,y).

I don't think there are any tricks in this problem. Try this input:
3
220 10 1234567
100 2 49
220 5 132345
output should be:
1
1
1
1
2
11
42
42
59
60
49
51
2
26
58
60
74

ori=oreo((ori-1)%4); You must change it into: ori=oreo((3+ori)%4); because in C x%y is not always positive (you get negative result when x<0 and y>0) if(ori==N) if(x-1>=1 && table[x-1][y]!='*') x--; else; else if(ori==E) if(y+1<=c && table[x][y+1]!='*') y++; else; else if(ori==S) if...

Zhao Le wrote:Can someone give me test case!

Thanks in advance.

Here's another one:

12 100
0 0