## Search found 19 matches

- Mon Sep 24, 2007 8:23 pm
- Forum: Algorithms
- Topic: Need expert's view for geometry algos.
- Replies:
**23** - Views:
**10035**

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:
**1771**

### 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:
**4407**

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:
**19128**

- Tue Aug 03, 2004 3:43 pm
- Forum: Algorithms
- Topic: Help on BOI Questions
- Replies:
**3** - Views:
**1523**

- Mon Aug 02, 2004 4:01 pm
- Forum: Algorithms
- Topic: Help on BOI Questions
- Replies:
**3** - Views:
**1523**

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:
**9148**

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:
**1678**

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:
**2360**

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

- Sat Jan 31, 2004 6:07 pm
- Forum: Volume 106 (10600-10699)
- Topic: 10615 - Rooks
- Replies:
**12** - Views:
**4864**

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:
**9781**

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

- Tue Sep 09, 2003 12:07 pm
- Forum: Volume 103 (10300-10399)
- Topic: 10377 - Maze Traversal
- Replies:
**26** - Views:
**10587**

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

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

### Re: 10515

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

Thanks in advance.

12 100

0 0