## Search found 76 matches

- Tue Oct 04, 2005 10:15 am
- Forum: Volume 109 (10900-10999)
- Topic: 10917 - Walk Through the Forest
- Replies:
**19** - Views:
**10412**

method for representation of graph with adjancey list is well-known and easy fomular: you can find them in many books, or internet pages. My another question is : "Can I use long array[1000][1000] in uva judge?" Sure, memory is enough. and I didn't knew that there exist a compiler which doesn't supp...

- Sun Oct 02, 2005 3:47 pm
- Forum: Algorithms
- Topic: To calculate the area of a polygon
- Replies:
**3** - Views:
**915**

prerequisites: no edges are intersecting each other. Let consecutive coordinates of the n-vertex polygon : (x1, y1) (x2, y2) ... (xn, yn) then, x1 x2 x3 ... xn-1 xn x1 y1 y2 y3 ... yn-1 yn y1 let the area of polygon S: 2 * S = (x1 * y2 + x2 * y3 + x3 * y4 + ... + xn-1 * yn + xn * y1 ) - (y2 * y1 + ...

- Sun Oct 02, 2005 2:46 pm
- Forum: Volume 109 (10900-10999)
- Topic: 10920 - Spiral Tap
- Replies:
**12** - Views:
**7357**

hi, if you got WA with this problem, there might be some bugs in your code or algorithm; my program uses only 32bit integers. and got AC. it seems that P < 2^31 (well, P <= SZ^2) plus output also fits in 32bit integer; some random test cases below: 3 2 1 1 7 2 5 7 5 8 5 9 7 16 7 49 21 137 511 3215 1...

- Sun Oct 02, 2005 2:35 pm
- Forum: Algorithms
- Topic: Mincost Maxflow - help!
- Replies:
**7** - Views:
**2748**

### well

well, there are many algorithms for mincost-maxflow problem, the fast and efficient, and the slow, I only use one, which uses successive shortest path method, and its time complexity is about o(|f|n^2) I use this because it is just easy to write! I think it is quite slow; but in 10594 problem, it gi...

- Sun Oct 02, 2005 5:11 am
- Forum: Volume 109 (10900-10999)
- Topic: 10922 - 2 the 9s
- Replies:
**38** - Views:
**14480**

### scanf is enough

Code: Select all

`scanf("%s", temp);`

btw, using gets, just ignoring non-digit characters, it works also

- Sun Oct 02, 2005 5:08 am
- Forum: Volume 109 (10900-10999)
- Topic: 10925 - Krakovia
- Replies:
**50** - Views:
**21893**

### sorry

i got very stupid mistake.. :oops: sorry again. V < 10^20, thus we can't use only 64bit integers. and, the test cases I used to debug my program input: 1 1 1 1 20 1 3 9 1 4 3 3 8 1 4 3 1 1 31415926535897932384 5 11 99999999999999999999 99999999999999999999 99999999999999999999 99999999999999999999 9...

- Sun Oct 02, 2005 3:28 am
- Forum: Volume 109 (10900-10999)
- Topic: 10925 - Krakovia
- Replies:
**50** - Views:
**21893**

### tricky case

stupid mistake.

ignore it.

ignore it.

- Fri Sep 30, 2005 4:14 pm
- Forum: Volume 109 (10900-10999)
- Topic: 10907 - Art Gallery
- Replies:
**22** - Views:
**9702**

### a trouble

hi. i have a trouble. 5 0 0 50 50 100 0 100 100 0 100 the polygon above is as mf's data. in my program, i have a function is_visible(point P) , which returns wheter P is visible from LIGHT. at first, i thought it will return true if there are no intersecting line segments, but in this tricky case it...

- Mon Sep 26, 2005 1:16 pm
- Forum: Volume 109 (10900-10999)
- Topic: 10902 - Pick-up Sticks
- Replies:
**24** - Views:
**13553**

### qe

After my test, I'm sure that no more than 1000 sticks are on the top at anytime. I just use arrays[1001] and got A.C. I also agree that no more than 1000 sticks are on the top anytime, (it seems to sub-n^2 algorithm was problemsetter's mean) but in general case, i can't find efficient algorithms. b...

- Mon Sep 26, 2005 11:06 am
- Forum: Volume 109 (10900-10999)
- Topic: 10918 - Tri Tiling
- Replies:
**12** - Views:
**6167**

### dt

it is not difficult to guess.1

0

0

0

0

you should have been more careful about it.

- Sun Sep 25, 2005 3:37 pm
- Forum: Volume 109 (10900-10999)
- Topic: 10911 - Forming Quiz Teams
- Replies:
**33** - Views:
**32298**

### Re: dp..

about dp solution, whose complexity is about O(2^n * n^2)sohel wrote:is there any dp solution to this problem ?

dy[A] means the minimum cost for matching teams,

only considering the people in set A (note that |A| : even number)

- Sun Sep 25, 2005 12:14 pm
- Forum: Volume 109 (10900-10999)
- Topic: 10918 - Tri Tiling
- Replies:
**12** - Views:
**6167**

### an

our task is

output one integer number giving the number of possible tilings.

anyway, there is a case N is odd.

think more cafefully about it.

output one integer number giving the number of possible tilings.

anyway, there is a case N is odd.

think more cafefully about it.

- Sat Sep 24, 2005 2:45 pm
- Forum: Volume 109 (10900-10999)
- Topic: 10905 - Children's Game
- Replies:
**66** - Views:
**26097**

### data

some random tests input: 30 53 206 12 9 3271 17 1 18 2319 9 17445 1813 7486 530 2 6 3 207 484 5 15 2211 214 91 22 33 10163 27690 26267 831 26 17 20 20345 1715 141 2 241 6 10901 9 1382 13813 681 181 1784 31727 4405 1445 84 520 114 2285 22 30330 10 235 12 10 5934 2289 30363 45 232 10 1734 160 1206 102...

- Sat Sep 24, 2005 5:21 am
- Forum: Volume 109 (10900-10999)
- Topic: 10913 - Walking on a Grid
- Replies:
**23** - Views:
**12534**

### dp

yes, it's DP

time complexity is about o(k * n^2)

Hint :

think when there is no rule that :

You can step on at most k negative integers from source to destination.

then you'll get DP algorithm,

and add this rule to your algorithm.

it will be not difficult.

time complexity is about o(k * n^2)

Hint :

think when there is no rule that :

You can step on at most k negative integers from source to destination.

then you'll get DP algorithm,

and add this rule to your algorithm.

it will be not difficult.

- Thu Sep 22, 2005 5:42 pm
- Forum: Volume 109 (10900-10999)
- Topic: 10902 - Pick-up Sticks
- Replies:
**24** - Views:
**13553**

### hm...

it seems that o(n^2) algorithm with efficient cutting makes AC, if the number of top sticks is small. also waterloo's solution is o(n^2). BUT there can be worst case, by 1st~99999th stick, every sticks are top sticks, and 100000th stick crosses all of them; then answer is 1 < 1000, satisfying proble...