## Search found 19 matches

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

- 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

I think you could solve it using Hu-Tucker algorithm, but it seems to be very complicated.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

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

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

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

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

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

- 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

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

- Wed Jun 16, 2004 6:13 pm
- Forum: Other words
- Topic: "Mondriaan's Dream" made me crazy
- Replies:
**3** - Views:
**2144**

- Wed Feb 18, 2004 9:53 pm
- Forum: Volume 106 (10600-10699)
- Topic: 10608 - Friends
- Replies:
**75** - Views:
**26793**

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

- Tue Dec 23, 2003 12:48 pm
- Forum: Volume 105 (10500-10599)
- Topic: 10574 - Counting Rectangles
- Replies:
**23** - Views:
**9244**

- Tue Dec 23, 2003 12:46 pm
- Forum: Volume 105 (10500-10599)
- Topic: 10581 - Partitioning for fun and profit
- Replies:
**15** - Views:
**8432**

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

- Thu Jul 24, 2003 1:30 pm
- Forum: Volume 105 (10500-10599)
- Topic: 10515 - Powers Et Al.
- Replies:
**124** - Views:
**29713**

### Re: 10515

Here's another one:Zhao Le wrote:Can someone give me test case!

Thanks in advance.

12 100

0 0