Search found 19 matches

by gawry
Mon Sep 24, 2007 8:23 pm
Forum: Algorithms
Topic: Need expert's view for geometry algos.
Replies: 23
Views: 9379

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...
by gawry
Thu Jun 16, 2005 6:36 pm
Forum: Other words
Topic: How to solve the problem
Replies: 6
Views: 1557

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.
by gawry
Wed Oct 06, 2004 5:45 pm
Forum: Volume 107 (10700-10799)
Topic: 10733 - The Colored Cubes
Replies: 14
Views: 4113

My (accepted) program's output is:

Code: Select all

57
240
800
2226
5390
11712
23355
43450
651886250
41679670000
651049541750000
7415811246281250
41417415833541750
by gawry
Sun Aug 08, 2004 9:36 pm
Forum: Volume 106 (10600-10699)
Topic: 10685 - Nature
Replies: 41
Views: 17970

[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...
by gawry
Tue Aug 03, 2004 3:43 pm
Forum: Algorithms
Topic: Help on BOI Questions
Replies: 3
Views: 1360

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...
by gawry
Mon Aug 02, 2004 4:01 pm
Forum: Algorithms
Topic: Help on BOI Questions
Replies: 3
Views: 1360

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...
by gawry
Mon Jul 12, 2004 11:38 pm
Forum: Volume 106 (10600-10699)
Topic: 10625 - GNU = GNU'sNotUnix
Replies: 16
Views: 8751

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;...
by gawry
Sat Jul 03, 2004 6:05 pm
Forum: Algorithms
Topic: Aho/Corasick
Replies: 2
Views: 1558

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
by gawry
Wed Jun 16, 2004 6:13 pm
Forum: Other words
Topic: "Mondriaan's Dream" made me crazy
Replies: 3
Views: 2144

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.
by gawry
Wed Feb 18, 2004 9:53 pm
Forum: Volume 106 (10600-10699)
Topic: 10608 - Friends
Replies: 75
Views: 26793

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)).
by gawry
Sat Jan 31, 2004 6:07 pm
Forum: Volume 106 (10600-10699)
Topic: 10615 - Rooks
Replies: 12
Views: 4551

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...
by gawry
Tue Dec 23, 2003 12:48 pm
Forum: Volume 105 (10500-10599)
Topic: 10574 - Counting Rectangles
Replies: 23
Views: 9244

Just make big table bool t[5000][5000] and set t[x][y] iff there is point with (normalized) coordinates (x,y).
by gawry
Tue Dec 23, 2003 12:46 pm
Forum: Volume 105 (10500-10599)
Topic: 10581 - Partitioning for fun and profit
Replies: 15
Views: 8432

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
by gawry
Tue Sep 09, 2003 12:07 pm
Forum: Volume 103 (10300-10399)
Topic: 10377 - Maze Traversal
Replies: 26
Views: 9725

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...
by gawry
Thu Jul 24, 2003 1:30 pm
Forum: Volume 105 (10500-10599)
Topic: 10515 - Powers Et Al.
Replies: 124
Views: 29713

Re: 10515

Zhao Le wrote:Can someone give me test case!

Thanks in advance.
Here's another one:

12 100
0 0

Go to advanced search