OJ Board

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

Enjoy ^_^

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...

mpi wrote:P.D.: Sorry, I didn't want to spoil the party

I think you still have the chance to edit your post

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.

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...

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"

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(...

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

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)

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!

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 im...

You might like to try to find a pattern for 4*k and 4*k+3

I got Accepted using int as data type and 999999999 as infinity value.

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 ...

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