Problem Summary

Given a tree with N nodes, find the maximum number of edges that can be removed from it to get a forest such that each tree of the forest contains an even number of nodes.

Read More

Problem Summary

Given a sequence of N integers, find

1. the length of the longest decreasing subsequence,
2. the number of sequences that have this length.

Read More

Problem Summary

Given a string T and an encrypted string S, determine whether S can be decoded as T.

Read More

Problem Summary

Given N boards and R rails and their lengths, find the maximal number of wanted rails that can be cut from the given boards.

Read More

Problem Summary

Given a sequence of integers, d[1],d[2],…,d[N] (1<=N<=100,000), find the consecutive subsequnce such that the bitwise XOR between the subsequence has the maximum value. (0<=d[i]<(2^21))

Read More

Problem Summary

Given a string S composed of L (5<=L<=100,000) letters, find the start position of the first letter of the sorted list of cyclic shifts of S.

Read More

Problem Summary

Given a N×M rectangular area with some 1×1 area damaged, find the biggest rectangular area without damages.

Read More

Problem Summary

Given a undirected graph, a source and a sink, find the minimal number of vertices needed to be taken away so that the source and sink are disconnected.

Read More

Problem Summary

Given a graph with vertices 1,2,…,N and M undirected edges, find the maximal length of a round trip.

The tour should have two parts. Let the first part be A[1]->A[2]->…->A[K], the second be B[1]->B[2]->…->B[P]. They should satisfy:

1. A[1]=B[P]=1, A[K]=B[1]=N.
2. The two parts have no common vertices except 1 and N, i.e. A[i]!=B[j], for any 1<i<K, 1<j<P.
3. A[i]<A[j], for any 1<=i<j<=K
4. B[i]>B[j], for any 1<=i<j<=P

Read More

Problem Summary

Given the volume of the big bottle (Q) and the volumes of P pails (p[1],p[2],…,p[P]), which are all integers, find the minimal sets of pails Farmer John needs to buy in order to measure out Q quarts of milk.

Read More