Search found 63 matches

by Hadi
Fri Jan 25, 2008 5:32 pm
Forum: Algorithms
Topic: becoming a maestro of DP
Replies: 7
Views: 4473

You might also try practicing at topcoder: DP Problems at topcoder.
There is also a problem classification at acm.zju.edu.cn/forum.

Enjoy ^_^
by Hadi
Sun Jan 20, 2008 6:29 pm
Forum: Volume 114 (11400-11499)
Topic: 11402 - Ahoy, Pirates!
Replies: 45
Views: 15466

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...
by Hadi
Sun Jan 20, 2008 6:24 pm
Forum: Volume 113 (11300-11399)
Topic: 11396 - Claw Decomposition
Replies: 12
Views: 4476

mpi wrote:P.D.: Sorry, I didn't want to spoil the party
I think you still have the chance to edit your post 8)
by Hadi
Sun Jan 20, 2008 8:52 am
Forum: Volume 113 (11300-11399)
Topic: 11396 - Claw Decomposition
Replies: 12
Views: 4476

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.
by Hadi
Sun Jan 20, 2008 8:49 am
Forum: Volume 113 (11300-11399)
Topic: 11396 - Claw Decomposition
Replies: 12
Views: 4476

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...
by Hadi
Tue Jul 10, 2007 4:01 pm
Forum: Volume 112 (11200-11299)
Topic: 11235 - Frequent values
Replies: 35
Views: 15896

cmd wrote:
Hadi wrote: The solution I used during the contest: O(n log n) preprocessing -> O(1) query answering.
Can you tell about your solution?
This may give some ideas: http://www.topcoder.com/tc?module=Stati ... onAncestor

See the topic "Sparse Table (SP) Algorithm"
by Hadi
Sun Jul 08, 2007 5:12 pm
Forum: Volume 112 (11200-11299)
Topic: 11235 - Frequent values
Replies: 35
Views: 15896

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(...
by Hadi
Wed Jul 04, 2007 1:10 am
Forum: Other words
Topic: Optimal Algorithms
Replies: 3
Views: 2801

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 ;)
by Hadi
Wed Feb 28, 2007 7:33 am
Forum: Volume 111 (11100-11199)
Topic: 11176 - Winning Streak
Replies: 18
Views: 12697

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)
by Hadi
Mon Feb 26, 2007 4:50 pm
Forum: Volume 111 (11100-11199)
Topic: 11184 - Joyful Ride
Replies: 11
Views: 7140

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! :roll:
by Hadi
Mon Feb 26, 2007 4:27 pm
Forum: Volume 111 (11100-11199)
Topic: 11183 - Teen Girl Squad
Replies: 28
Views: 12954

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...
by Hadi
Mon Feb 26, 2007 4:18 pm
Forum: Volume 111 (11100-11199)
Topic: 11184 - Joyful Ride
Replies: 11
Views: 7140

You might like to try to find a pattern for 4*k and 4*k+3 :wink:
by Hadi
Fri Feb 23, 2007 1:21 pm
Forum: Volume 111 (11100-11199)
Topic: 11171 - SMS
Replies: 8
Views: 5154

I got Accepted using int as data type and 999999999 as infinity value.
by Hadi
Thu Feb 22, 2007 3:36 pm
Forum: Volume 111 (11100-11199)
Topic: 11171 - SMS
Replies: 8
Views: 5154

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 ...
by Hadi
Mon Feb 19, 2007 6:20 pm
Forum: Volume 111 (11100-11199)
Topic: 11167 - Monkeys in the Emei Mountain
Replies: 30
Views: 15315

"Yes"/"No"'s are the same with mine.

Go to advanced search