TopCoder problem "TablePartitions" used in TCCC '04 Semifinals 2 (Division I Level Two)



Problem Statement

    

A table in a database consists of rows and columns. Rows correspond to elements in the table, and columns correspond to fields in the elements. In this problem we will only deal with elements that have integer fields in the range 0 to 100, inclusive. The columns will be named sequentially with lower case letters, starting with 'a', then 'b' and so on. So an element in a table with 4 columns may be described like this: "a=3, b=10, c=15, d=0". Note that all fields in an element must contain an integer value in the valid range, i.e. no field may be omitted.

A large table in a database can be a performance hog. One way to avoid this is to logically partition the table into several smaller tables. This is done by giving each partition a set of constraints on the columns, specifying which rows in the large table should go to which partition.

Given the constraints for the partitions of a table, write a class that determines whether the partitions are well formed (see below). The constraints will be given as a String[] where each element corresponds to one partition. Each element contains a space separated list of constraints, where each constraint is in the form "<column><operator><value>" (quotes for clarity only) where <column> is a table column, <operator> is one of the relational operators '=', '<', '>', '<=', '>=', and <value> is an integer between 0 and 100, inclusive (without leading zeros). The constraints for each partition represents a conjunction, i.e. all constraints must hold (see example 1).

For instance, if we have 3 partitions and a table with 2 columns, the constraints might look like this: {"a>3", "a<=3 b>5", "b<6 a<=3"}. Element "a=4, b=3" would then go to the first partition, element "a=3, b=9" would go to the second partition and element "a=0, b=5" would go to the third partition.

The partitioning is badly constructed if one or more of the criteria below holds:

  • Empty partition: A partition is empty if the constraints are constructed so that no valid element can fulfill them (see example 1). If one or more partitions are empty, return the String "EMPTY".
  • Overlapping partitions: If there exists a valid element that satisfies the constraints for two or more partitions (see example 2), return the String "OVERLAP".
  • Incomplete partitioning: If there exists a valid element that satisfies none of the constraints (see example 4), return the String "INCOMPLETE".

If several of the criteria above holds for the partitions, return the first that holds (i.e. "EMPTY" has highest priority, followed by "OVERLAP" and finally "INCOMPLETE").

Otherwise the partitioning is well formed; that is, an arbitrary valid element can go into exactly one partition and no partition is empty. In this case you should return the String "OK".

Create a class TablePartitions containing the method validate which takes an int n, the number of columns in the table, and a String[] partitions containing the constraints for each partition in the format above. The method should "EMPTY", "OVERLAP", "INCOMPLETE" or "OK" (the meanings of these Strings are explained above).

 

Definition

    
Class:TablePartitions
Method:validate
Parameters:int, String[]
Returns:String
Method signature:String validate(int n, String[] partitions)
(be sure your method is public)
    
 

Notes

-A partition might have no constraints, meaning that all elements can go into this partition (see example 6).
-Remember that the integer fields in a valid element is always between 0 and 100, inclusive.
-There can be multiple constraints on the same column in one partition, see example 0.
-All quotes around the return Strings above are for clarity only.
 

Constraints

-n will be between 1 and 8, inclusive.
-partitions will contain between 1 and 50 elements, inclusive.
-Each element in partitions will contain between 0 and 50 characters, inclusive.
-Each element in partitions with more than 0 characters will contain a space separated list of constraints in the format specified above.
-There will be no leading or trailing spaces in the elements in partitions.
-Each constraint in the elements in partitions will be separated with exactly one space.
 

Examples

0)
    
2
{"a>3 a>2",
 "a<=3 b>5",
 "b<6 a<=3"}
Returns: "OK"
This is the example in the problem statement with the addition of a redundant constraint in the first partition. This doesn't affect the partitioning though, so the method returns "OK" since all elements with a>3 go into the first partition, while the other two partitions require that a is no more than 3 and that b is 6 or greater (second partition) or 5 or less (third partition).
1)
    
1
{"a=0 a=1",
 "a>=2"}
Returns: "EMPTY"
The first partition requires that a is both 0 and 1 which obviously is a contradiction. Thus no element can go into this partition and therefore it's an empty partition. The method returns "EMPTY".
2)
    
2
{"a>=5",
 "b<=6"}
Returns: "OVERLAP"
The element "a=10, b=0" satisfies the constraints in both partitions, so there clearly is an overlap.
3)
    
4
{"d<17 b<40",
 "d>=17 d<65 b<39",
 "d>=65 b<39",
 "d>=17 d<22 b=39",
 "d>=22 d<47 b=39",
 "d>=47 b>=39 b<61",
 "d<9 b>=40 b<61 a<51",
 "d<9 b>=61 b<89 a<51",
 "d<28 d>=9 b>=40 b<75 a<=50",
 "d<28 d>=9 b>=75 b<89 a<=50",
 "d>=28 d<47 b>=40 b<97",
 "d<28 b>=89",
 "d>=28 d<65 b>=97",
 "d>=47 d<65 b>=61 b<97",
 "d>=65 d<=100 b>=61",
 "d>=0 d<28 b>=40 b<89 a>50"}
Returns: "OK"
4)
    
4
{"d<17 b<40",
 "d>=17 d<65 b<39",
 "d>=65 b<39",
 "d>=17 d<22 b=39",
 "d>=22 d<47 b=39",
 "d>=47 b>=39 b<61",
 "d<9 b>=40 b<61 a<51",
 "d<9 b>=61 b<88 a<51",
 "d<28 d>=9 b>=40 b<75 a<=50",
 "d<28 d>=9 b>=75 b<89 a<=50",
 "d>=28 d<47 b>=40 b<97",
 "d<28 b>=89",
 "d>=28 d<65 b>=97",
 "d>=47 d<65 b>=61 b<97",
 "d>=65 d<=100 b>=61",
 "d>=0 d<28 b>=40 b<89 a>50"}
Returns: "INCOMPLETE"
Element "a=0, b=88, c=0, d=0" doesn't satisfy any constraint, and there are no overlaps nor empty partitions, so the method returns "INCOMPLETE".
5)
    
6
{""}
Returns: "OK"

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5077&pm=2434

Writer:

Yarin

Testers:

zoidal , lbackstrom , brett1479

Problem categories:

Advanced Math