TopCoder problem "TheSquares" used in SRM 381 (Division I Level Three)

Problem Statement

Little John does a lot of programming, and is therefore very strange. Recently, he started talking with some geometrical figures. Squares are his favorite ones, and he gives names to them. Yes, it is very strange, but don't forget that John is a programmer!

John has drawn many squares on a big sheet of paper and each square has its own name. Now John is looking for a sequence of k squares such that each square except the first one lies inside the previous square in the sequence.

One square lies inside another one if all its points are inside the bigger square, possibly on a boundary.

You are given String[]s x, y, lengths and names, and an int k. For each String[], concatenate all its elements to produce a single string. The concatenated versions of x, y and lengths contain single space separated lists of integers, where the i-th integers represent the x-coordinate and y-coordinate of the bottom left corner and side length, respectively, of the i-th square. The concatenated version of names contains a single space separated list of strings, where the i-th string represents the name of the i-th square.

Return a String[] containing exactly k elements - the names of the squares in the sequence. If there are multiple such sequences, return the one among them that comes first lexicographically. If there is no such sequence, return an empty String[].

Definition

Class:	TheSquares
Method:	findSequence
Parameters:	String[], String[], String[], String[], int
Returns:	String[]
Method signature:	String[] findSequence(String[] x, String[] y, String[] lengths, String[] names, int k)
(be sure your method is public)

Notes

Each square can be used only once in the resulting sequence.

String[] A comes lexicographically before String[] B if the i-th element of A comes lexicographically before the i-th element of B and the j-th element of A is equal to the j-th element of B for all j less than i.

Constraints

x, y, lengths and names will each contain between 1 and 50 elements, inclusive.

Each element of x, y, lengths and names will contain between 1 and 50 characters, inclusive.

x, y, lengths and names, when concatenated, will each contain a single space separated list of items without leading or trailing spaces, and each list will contain the same number of items.

x, y and lengths, when concatenated, will each contain a single space separated list of integers, where each integer is between 1 and 1000, inclusive, with no leading zeroes.

names, when concatenated, will contain a single space separated list of strings, where each string contains between 1 and 50 uppercase letters ('A'-'Z'), inclusive.

k will be between 1 and 1000, inclusive.

Examples

{"1 1 1 4 7 8 1000"}

{"1 1 1 4 7 8 1000"}

{"1 2 3 4 5 1 1000"}

{"X Y Z ALPHA BETA GAMMA DELTA"}

Returns: {"BETA", "GAMMA" }

There are several valid sequences of squares but (BETA, GAMMA) comes first lexicographically.

{"1 1 1 4 7 8 1000"}

{"1 1 1 4 7 8 1000"}

{"1 2 3 4 5 1 1000"}

{"X Y Z ALPHA BETA GAMMA DELTA"}

Returns: {"Z", "Y", "X" }

Same example but with k = 3. This time there is no choice.

{"4 4 4 4"}

{"7 7 7 7"}

{"47 47 47 47"}

{"GLUK GLUKA GLUKOVI GLUKOM"}

Returns: {"GLUK", "GLUKA", "GLUKOM", "GLUKOVI" }

Squares may coincide.

{"1 15 27 39"}

{"3 13 22 36"}

{"8 3 5 974"}

{"ACB DEF GHI JKL"}

Returns: { }

There are no squares that lie inside other squares.

{"123 453 754"}

{"119 487 874"}

{"1000 500 1"}

{"SQUARE SQUARE SQUARE"}

Returns: {"SQUARE", "SQUARE", "SQUARE" }

Names of squares are not necessarily distinct.

{"3 5 10 1"}

{"5 8 10 1"}

{"974 990 1 1000"}

{"X Y X Y"}

Returns: {"Y", "X", "X" }

There are two pairs of squares with equal names.

{"1 1 1 1"}

{"1 1 1 1"}

{"1 1 1 1"}

{"A A A A"}

Returns: { }

The sequence John is looking for is too long.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8418

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10804&pm=8418

Writer:

Vasyl[alphacom]

Testers:

PabloGilberto , Olexiy , ivan_metelsky , ged

Problem categories:

Dynamic Programming