## Search found 519 matches

Fri Dec 07, 2007 3:39 am
Forum: Volume 110 (11000-11099)
Topic: 11015 - 05-2 Rendezvous
Replies: 48
Views: 17701
Why do you think that 999 is large enough for infinity?
Fri Dec 07, 2007 3:34 am
Forum: Volume 7 (700-799)
Topic: 727 - Equation
Replies: 156
Views: 37553
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.
Fri Dec 07, 2007 3:30 am
Forum: Volume 113 (11300-11399)
Topic: 11365 - Copying DNA
Replies: 12
Views: 5598
The solution are posted at the NCPC 2007 website, so I think you can study their pruning strategies.
Fri Dec 07, 2007 3:28 am
Forum: Volume 113 (11300-11399)
Topic: 11361 - Investigating Div-Sum Property
Replies: 16
Views: 7149
if you did the dp properly, you won't get TLE. Remember that there are no solution if K is too large.
Fri Dec 07, 2007 3:25 am
Forum: Volume 113 (11300-11399)
Topic: 11305 - Chess on Planet X
Replies: 6
Views: 2019
it means the following is a valid placement: (Q is queen, P is pawn)

Code: Select all

``````QPQ
PP
Q
P
Q
``````
Thu Dec 06, 2007 4:58 am
Forum: C
Topic: stack / heap size limit
Replies: 3
Views: 7698
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.
Sun Dec 02, 2007 8:08 pm
Forum: Volume 113 (11300-11399)
Topic: 11365 - Copying DNA
Replies: 12
Views: 5598
I did it with straight DP (BFS) with a bit of pruning.
Sun Dec 02, 2007 8:04 pm
Forum: Volume 113 (11300-11399)
Topic: 11368 - Nested Dolls
Replies: 9
Views: 4991
Greedy. I used a multiset to implement it.
Tue Nov 27, 2007 10:12 am
Forum: Algorithms
Topic: MinCost MaxFlow code
Replies: 20
Views: 15763
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 ...
Tue Nov 27, 2007 9:50 am
Forum: General
Topic: Speed difference
Replies: 1
Views: 2103
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.
Tue Nov 27, 2007 4:54 am
Forum: Volume 113 (11300-11399)
Topic: 11359 - Guards, Imbecile Guards
Replies: 6
Views: 2919
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.
Mon Nov 26, 2007 8:39 pm
Forum: Volume 113 (11300-11399)
Topic: 11361 - Investigating Div-Sum Property
Replies: 16
Views: 7149
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
Mon Nov 26, 2007 11:24 am
Forum: Volume 5 (500-599)
Topic: 565 - Pizza Anyone?
Replies: 12
Views: 4459
Your line 6 is wrong. It should be:

Code: Select all

``int n, req[2][12], i, sat, j, tp; ``
Mon Nov 26, 2007 12:26 am
Forum: Volume 113 (11300-11399)
Topic: 11354 - Bond
Replies: 13
Views: 6850
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.
Sun Nov 25, 2007 11:36 pm
Forum: Volume 113 (11300-11399)
Topic: 11358 - Faster Processing Feasibility
Replies: 8
Views: 4396
``````2 5