Search found 519 matches

by sclo
Fri Dec 07, 2007 3:39 am
Forum: Volume 110 (11000-11099)
Topic: 11015 - 05-2 Rendezvous
Replies: 48
Views: 17038

Why do you think that 999 is large enough for infinity?
by sclo
Fri Dec 07, 2007 3:34 am
Forum: Volume 7 (700-799)
Topic: 727 - Equation
Replies: 156
Views: 35287

To solve this problem, do recursive descent parsing, then just do dfs on the parse tree. Trying to do it with a stack is a source of trouble.
by sclo
Fri Dec 07, 2007 3:30 am
Forum: Volume 113 (11300-11399)
Topic: 11365 - Copying DNA
Replies: 12
Views: 5424

The solution are posted at the NCPC 2007 website, so I think you can study their pruning strategies.
by sclo
Fri Dec 07, 2007 3:28 am
Forum: Volume 113 (11300-11399)
Topic: 11361 - Investigating Div-Sum Property
Replies: 16
Views: 6957

if you did the dp properly, you won't get TLE. Remember that there are no solution if K is too large.
by sclo
Fri Dec 07, 2007 3:25 am
Forum: Volume 113 (11300-11399)
Topic: 11305 - Chess on Planet X
Replies: 6
Views: 1927

it means the following is a valid placement: (Q is queen, P is pawn)

Code: Select all

QPQ
PP
Q
P
Q
by sclo
Thu Dec 06, 2007 4:58 am
Forum: C
Topic: stack / heap size limit
Replies: 3
Views: 7484

It is possible to get stack overflow. I got it when I tried doing dfs on a graph with more than 1 million vertices. Of course, it is easily fixable by using a stack to do dfs instead of doing dfs recursively.
by sclo
Sun Dec 02, 2007 8:08 pm
Forum: Volume 113 (11300-11399)
Topic: 11365 - Copying DNA
Replies: 12
Views: 5424

I did it with straight DP (BFS) with a bit of pruning.
by sclo
Sun Dec 02, 2007 8:04 pm
Forum: Volume 113 (11300-11399)
Topic: 11368 - Nested Dolls
Replies: 9
Views: 4784

Greedy. I used a multiset to implement it.
by sclo
Tue Nov 27, 2007 10:12 am
Forum: Algorithms
Topic: MinCost MaxFlow code
Replies: 20
Views: 15278

Use adjacency lists instead of matrix for the graph representation. The modification is quite trivial. But for that to work, for each edge from u->v with capacity c, and cost p, there must be a corresponding opposite edge from v->u with capacity 0 and cost -p. Also, it should be possible to look up ...
by sclo
Tue Nov 27, 2007 9:50 am
Forum: General
Topic: Speed difference
Replies: 1
Views: 2047

I think it is hard to say. I've gotten code that runs at least 3 times as fast on the new system. I also noticed that STL runs faster on the new judge.
by sclo
Tue Nov 27, 2007 4:54 am
Forum: Volume 113 (11300-11399)
Topic: 11359 - Guards, Imbecile Guards
Replies: 6
Views: 2831

I don't see why your algorithm can actually return the correct answer.
The correct states for the BFS should be (x,y,t) where (x,y) are the current position, and t is the time since beginning mod L, where L is the lcm of the guard's cycle lengths.
by sclo
Mon Nov 26, 2007 8:39 pm
Forum: Volume 113 (11300-11399)
Topic: 11361 - Investigating Div-Sum Property
Replies: 16
Views: 6957

sonyckson wrote:I cant get the "kind of DP" idea.... can anyone give me some hints?? thanks. eric
The dimensions for the DP:
length of number, first digit of number, sum of digit mod K, number mod K
by sclo
Mon Nov 26, 2007 11:24 am
Forum: Volume 5 (500-599)
Topic: 565 - Pizza Anyone?
Replies: 12
Views: 4274

Your line 6 is wrong. It should be:

Code: Select all

int n, req[2][12], i, sat, j, tp; 
by sclo
Mon Nov 26, 2007 12:26 am
Forum: Volume 113 (11300-11399)
Topic: 11354 - Bond
Replies: 13
Views: 6663

I would like to know how the query can be answered directly on the union find datastructure. I solved it by using the dividing the tree into sqrt(height) layers, and precompute the maximum edge weight to previous layer.
by sclo
Sun Nov 25, 2007 11:36 pm
Forum: Volume 113 (11300-11399)
Topic: 11358 - Faster Processing Feasibility
Replies: 8
Views: 4249

How about this case?

Code: Select all

2 5
0 1 1
2 2 4
2 2 4
0 1 2
0 2 4
According to your greedy: At time 0, you would schedule task 0 and 3. At time 1, only task 4 is available and one of the processor is idle, so the whole schedule is not feasible.
The correct solution is to schedule task 0 and 4 at time 0.

Go to advanced search