Search found 76 matches

by wook
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...
by wook
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 + ...
by wook
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...
by wook
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...
by wook
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);
is enough.


btw, using gets, just ignoring non-digit characters, it works also :)
by wook
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...
by wook
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. :oops:
by wook
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...
by wook
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...
by wook
Mon Sep 26, 2005 11:06 am
Forum: Volume 109 (10900-10999)
Topic: 10918 - Tri Tiling
Replies: 12
Views: 6167

dt

1
0
0
0
0
it is not difficult to guess.
you should have been more careful about it.
by wook
Sun Sep 25, 2005 3:37 pm
Forum: Volume 109 (10900-10999)
Topic: 10911 - Forming Quiz Teams
Replies: 33
Views: 32298

Re: dp..

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


dy[A] means the minimum cost for matching teams,
only considering the people in set A (note that |A| : even number)
by wook
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.
by wook
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...
by wook
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.
by wook
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...

Go to advanced search