## Search found 63 matches

Fri Jan 25, 2008 5:32 pm
Forum: Algorithms
Topic: becoming a maestro of DP
Replies: 7
Views: 4363
You might also try practicing at topcoder: DP Problems at topcoder.
There is also a problem classification at acm.zju.edu.cn/forum.

Enjoy ^_^
Sun Jan 20, 2008 6:29 pm
Forum: Volume 114 (11400-11499)
Topic: 11402 - Ahoy, Pirates!
Replies: 45
Views: 14986
Can you tell me how to do the "inversion" fast with segment tree? You don't need to do the inversion to all nodes in the subtree. Storing some information in each node: At query time, you can decide what extra actions you should do for a node to find the correct result for that node based on the in...
Sun Jan 20, 2008 6:24 pm
Forum: Volume 113 (11300-11399)
Topic: 11396 - Claw Decomposition
Replies: 12
Views: 4327
mpi wrote:P.D.: Sorry, I didn't want to spoil the party
I think you still have the chance to edit your post
Sun Jan 20, 2008 8:52 am
Forum: Volume 113 (11300-11399)
Topic: 11396 - Claw Decomposition
Replies: 12
Views: 4327
DP wrote:Output:

Code: Select all

``````YES
YES
``````
Well, a program which gets accepted would output 'YES' for both graphs, but none of those graphs are eligible to appear in the test-data, and If their shape is not claw.
Sun Jan 20, 2008 8:49 am
Forum: Volume 113 (11300-11399)
Topic: 11396 - Claw Decomposition
Replies: 12
Views: 4327
NO NO . Although none of your graphs would appear in the test-data. because the problem statement says all graphs has only vertices of degree 3. HINT: All vertices has degree 3. So, If a vertex is the center of a claw, what can we conclude about its neighbors? What about the neighbors of a vertex wh...
Tue Jul 10, 2007 4:01 pm
Forum: Volume 112 (11200-11299)
Topic: 11235 - Frequent values
Replies: 35
Views: 15541
cmd wrote:
Hadi wrote: The solution I used during the contest: O(n log n) preprocessing -> O(1) query answering.
This may give some ideas: http://www.topcoder.com/tc?module=Stati ... onAncestor

See the topic "Sparse Table (SP) Algorithm"
Sun Jul 08, 2007 5:12 pm
Forum: Volume 112 (11200-11299)
Topic: 11235 - Frequent values
Replies: 35
Views: 15541
Think about Range Maximum Query(RMQ), then you can answer each query in O(lg N) operation after O(N lg N) for build the tree. You must transform the problem to RMQ first ^_^. O(n log n) preprocessing -> O(log n) query answering? If you use binary trees, I think the preprocessing part is O(n) not O(...
Wed Jul 04, 2007 1:10 am
Forum: Other words
Topic: Optimal Algorithms
Replies: 3
Views: 2761
Why is the name "Optimal Algorithms"?
If you define an "optimal algorithm" as an algorithm that has the optimal time / memory complexity; I should say some of algorithms you have described might not be optimal
Wed Feb 28, 2007 7:33 am
Forum: Volume 111 (11100-11199)
Topic: 11176 - Winning Streak
Replies: 18
Views: 12471
The O(n^2) method is fundamentally the same as O(n^3) one. the difference is that it uses an extra array to avoid unnecessary calculations. (Just think about what your function does and how can you store it in an array)
Mon Feb 26, 2007 4:50 pm
Forum: Volume 111 (11100-11199)
Topic: 11184 - Joyful Ride
Replies: 11
Views: 7000
arsalan_mousavian wrote:i think i solved the problem in O(N^2) but i've got TLE, does anybody know any faster algorithm?
I know!
Mon Feb 26, 2007 4:27 pm
Forum: Volume 111 (11100-11199)
Topic: 11183 - Teen Girl Squad
Replies: 28
Views: 12831
For this problem, using "Prim" or "Kruskal" is not correct. they are for undirected graphs. you can find a counter-example easily if you try. You should use Chu,Liu/Edmonds algorithm to solve this problem. for a brief description see http://www.ce.rit.edu/~sjyeec/dmst.html But implementing it they w...
Mon Feb 26, 2007 4:18 pm
Forum: Volume 111 (11100-11199)
Topic: 11184 - Joyful Ride
Replies: 11
Views: 7000
You might like to try to find a pattern for 4*k and 4*k+3
Fri Feb 23, 2007 1:21 pm
Forum: Volume 111 (11100-11199)
Topic: 11171 - SMS
Replies: 8
Views: 5041
I got Accepted using int as data type and 999999999 as infinity value.
Thu Feb 22, 2007 3:36 pm
Forum: Volume 111 (11100-11199)
Topic: 11171 - SMS
Replies: 8
Views: 5041

### 11171 - SMS

I build two tries (one is digit based, the other is letter based) and find minimum key sequence for each word using these tries. Then, I use dynamic programming to find the minimum sequence for typing the given query. But It seems that my solution cannot find any key seqeunce for some queries. Some ...
Mon Feb 19, 2007 6:20 pm
Forum: Volume 111 (11100-11199)
Topic: 11167 - Monkeys in the Emei Mountain
Replies: 30
Views: 14900
"Yes"/"No"'s are the same with mine.