## Search found 19 matches

Mon Sep 24, 2007 8:23 pm
Forum: Algorithms
Topic: Need expert's view for geometry algos.
Replies: 23
Views: 9518
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...
Thu Jun 16, 2005 6:36 pm
Forum: Other words
Topic: How to solve the problem
Replies: 6
Views: 1590

### Re: How to solve the problem

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.
Wed Oct 06, 2004 5:45 pm
Forum: Volume 107 (10700-10799)
Topic: 10733 - The Colored Cubes
Replies: 14
Views: 4135
My (accepted) program's output is:

Code: Select all

57
240
800
2226
5390
11712
23355
43450
651886250
41679670000
651049541750000
7415811246281250
41417415833541750

Sun Aug 08, 2004 9:36 pm
Forum: Volume 106 (10600-10699)
Topic: 10685 - Nature
Replies: 41
Views: 18169
[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 strcmp calls (so with...
Tue Aug 03, 2004 3:43 pm
Forum: Algorithms
Topic: Help on BOI Questions
Replies: 3
Views: 1379
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 this child is...
Mon Aug 02, 2004 4:01 pm
Forum: Algorithms
Topic: Help on BOI Questions
Replies: 3
Views: 1379
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...
Mon Jul 12, 2004 11:38 pm
Forum: Volume 106 (10600-10699)
Topic: 10625 - GNU = GNU'sNotUnix
Replies: 16
Views: 8794
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;...
Sat Jul 03, 2004 6:05 pm
Forum: Algorithms
Topic: Aho/Corasick
Replies: 2
Views: 1577
M. Crochemore, W.Rytter, Text Algorithms
http://web.njit.edu/~rytter/TEACHING/TEXTS/book.html
Wed Jun 16, 2004 6:13 pm
Forum: Other words
Topic: "Mondriaan's Dream" made me crazy
Replies: 3
Views: 2175
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.
Wed Feb 18, 2004 9:53 pm
Forum: Volume 106 (10600-10699)
Topic: 10608 - Friends
Replies: 75
Views: 27087
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)).
Sat Jan 31, 2004 6:07 pm
Forum: Volume 106 (10600-10699)
Topic: 10615 - Rooks
Replies: 12
Views: 4584
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...
Tue Dec 23, 2003 12:48 pm
Forum: Volume 105 (10500-10599)
Topic: 10574 - Counting Rectangles
Replies: 23
Views: 9298
Just make big table bool t[5000][5000] and set t[x][y] iff there is point with (normalized) coordinates (x,y).
Tue Dec 23, 2003 12:46 pm
Forum: Volume 105 (10500-10599)
Topic: 10581 - Partitioning for fun and profit
Replies: 15
Views: 8495
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
Tue Sep 09, 2003 12:07 pm
Forum: Volume 103 (10300-10399)
Topic: 10377 - Maze Traversal
Replies: 26
Views: 9899

### Re: 10377 why wrong answer?

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(x+1<=r && table...
Thu Jul 24, 2003 1:30 pm
Forum: Volume 105 (10500-10599)
Topic: 10515 - Powers Et Al.
Replies: 124
Views: 30075

### Re: 10515

Zhao Le wrote:Can someone give me test case!