Search found 519 matches

by sclo
Sun Nov 25, 2007 12:24 pm
Forum: Volume 113 (11300-11399)
Topic: 11354 - Bond
Replies: 13
Views: 6729

I think that works, but I haven't solved that problem yet.
by sclo
Sun Nov 25, 2007 11:02 am
Forum: Volume 113 (11300-11399)
Topic: 11354 - Bond
Replies: 13
Views: 6729

11354 - Bond

Looking at the problem, I think the solution can be found by kruskal's algorithm. The problem is how to answer the queries fast enough? In the worst case, the tree can be linear, each query takes O(n) time.
by sclo
Sun Nov 25, 2007 9:10 am
Forum: Volume 113 (11300-11399)
Topic: 11358 - Faster Processing Feasibility
Replies: 8
Views: 4278

I thought that it was NP-hard problem, so greedy doesn't work. I tried network flow, and it is correct. This problem is actually almost exactly like 11167 - Monkeys in the Emei Mountain, except the output is easier here. It was decided that greedy was incorrect for that problem, so greedy shouldn't ...
by sclo
Sun Nov 25, 2007 4:03 am
Forum: Volume 113 (11300-11399)
Topic: 11358 - Faster Processing Feasibility
Replies: 8
Views: 4278

11358 - Faster Processing Feasibility

I tried solving this problem using a greedy method, but get WA. How did other people solved this problem? My greedy choice is to always process the available jobs with sooner deadlines first. I now have a feeling that earliest deadline first is not optimal for multiprocessor case. It is optimal only...
by sclo
Sun Nov 25, 2007 3:59 am
Forum: Volume 113 (11300-11399)
Topic: 11361 - Investigating Div-Sum Property
Replies: 16
Views: 7014

You need some kind of DP solution if you want to get this problem.
The dimensions are 10x10xKxK. But that is way out of bound, you need something more clever :)
by sclo
Fri Nov 23, 2007 11:20 am
Forum: C++
Topic: How to single 8 bit Varialbles Store in Single Bytes
Replies: 3
Views: 2323

Sorry, I don't understand your problem, can you explain more clearly?
by sclo
Wed Nov 21, 2007 10:54 am
Forum: Volume 113 (11300-11399)
Topic: 11351 - Last Man Standing
Replies: 7
Views: 3566

There are different ways to dp it. The most obvious way is O(n).
I don't think there is any explicit formula, but I could be wrong.
by sclo
Tue Nov 20, 2007 9:43 pm
Forum: Volume 113 (11300-11399)
Topic: 11337 - Greatest Hits!
Replies: 4
Views: 1539

I was stupid for not thinking about the dp. Anyway, I think the backtrack is quicker to code than dp anyway.
by sclo
Tue Nov 20, 2007 9:40 pm
Forum: Volume 113 (11300-11399)
Topic: 11352 - Crazy King
Replies: 32
Views: 12245

Here's another way to reduce even more code.
For the knight's move:

Code: Select all

int dx[] = {1,1,2,2,-1,-1,-2,-2};
int dy[] = {2,-2,1,-1,2,-2,1,-2};

for(k=0; k<8; k++) {
  r=i+dx[k], c=j+dy[k];
  if(inside(r,c) && Inp[r][c]=='.') color[r][c]='b';
} 

// inside(r,c) is true iff (r,c) is inside the board
by sclo
Tue Nov 20, 2007 9:33 pm
Forum: Java
Topic: Java 1.6.0 supported? YES!!!
Replies: 7
Views: 8523

Eiger Yap wrote:Thanks 4 instruction. I am Newbie here. I wanna ask how about use file in Java?? So what different between 1.5.0 n 1.6.0 ???
There's no need to use files on UVa. All problems takes input from stdin and output to stdout.
by sclo
Tue Nov 20, 2007 9:29 pm
Forum: General
Topic: How to know wich problem I solved, in the new server?
Replies: 3
Views: 2542

898989 wrote:Thanks so much. What other colors means, from where i can know?
Use your common sense.
by sclo
Sat Nov 17, 2007 1:46 am
Forum: Volume 113 (11300-11399)
Topic: 11337 - Greatest Hits!
Replies: 4
Views: 1539

I just looked at the bound and thought about backtracking. I never really consider any dp. Actually now I don't see how it can be done using dp.
by sclo
Thu Nov 15, 2007 7:46 pm
Forum: Volume 113 (11300-11399)
Topic: 11345 - Rectangles
Replies: 27
Views: 9095

what happens when r.x1>r.x2 or r.y1>r.y2 in your algorithm? I think I handle all of these: 1) r.x1 > r.x2 => r2.x1 > min(r1.x2, r2.x2) we know r2.x1 < r2.x2 so we must have r1.x2 < r2.x1 that I handle this. 2) r.y1 > r.y2 => max(r1.y1, r2.y1) > min(r1.y2, r2.y2) suppose that min(r1.y2, r2.y2) = r1....
by sclo
Thu Nov 15, 2007 3:58 am
Forum: Volume 113 (11300-11399)
Topic: 11322 - Romeo and Juliet
Replies: 4
Views: 1451

The regions where Romeo and Juliet can meet is actually a circle with a circular hole. (except for a boundary case where one circle is a halfplane) The entire problem can be reduced to finding intersections of circles. I was about to think, that area is an ellipse, how did you find out that the are...
by sclo
Wed Nov 14, 2007 11:16 pm
Forum: Volume 113 (11300-11399)
Topic: 11345 - Rectangles
Replies: 27
Views: 9095

what happens when r.x1>r.x2 or r.y1>r.y2 in your algorithm?

Go to advanced search