wil93's blog

Help with a problem (hard implementation)
By wil93, 13 years ago, In English

Let's define an "expression" as a set composed only by number and brackets () [].

This is an expression: ( 18 4 [ 6 7 ( 4 ) 2 ] 6 8 )
Every expression starts with "(" and ends with ")".

There are N espressions in the input file, each is codified by M integers (N and M both aren't greater than 1000). Brackets are codified by negative integers. See this table:

( -1
) -2
[ -3
] -4

You can apply 2 basic operations to an expression to transform it into another:
1) You can permute the elements inside ()
2) You can reverse the elements inside []
By "element" we mean: a single number, or, an internal expression (see definition of expression, above).

For example, the above expression could be transformed into ( 8 [ 2 ( 4 ) 7 6 ] 18 6 4 ).
Two expressions A and B are equivalent only if you can obtain B starting from A, and vice-versa.

Your job is to classify the given N expression in K groups of equivalent expressions (K <= N).

INPUT:
First line contains N and M
N expressions follows (each is formed by M integers)

OUTPUT:
First line contains K (number of groups)
Follows K lines, each composed by Q+1 integers (where Q is the size of that group). These integers are respectively: Q, and the components of the group. See the sample output for clarity.

SAMPLE INPUT:
3 14
-1 18 4 -3 6 7 -1 4 -2 2 -4 6 8 -2
-1 8 -3 2 -1 4 -2 7 6 -4 18 6 3 -2
-1 8 -3 2 -1 4 -2 7 6 -4 18 6 4 -2

SAMPLE OUTPUT:
2
2 1 3
1 2
  • Vote: I like it
  • 0
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it +8 Vote: I do not like it
My first idea was to define a recursive data structure, like:

struct Sequence
{
vector<Sequence> content;
};

Once represented, you should "sort" each sequence (reducing it to a normalized form, i.e. the least lexicographic transformation). Then, you can do a simply O(N2*M) comparing, but this is too much, so maybe the answer is hashing.

Some better idea?
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Since elements of expressions are expressions themselves, we can classify all the elements, recursively substituting every sub-expression with a class number.

Parse each expression into a tree. Leaves of that tree are numbers, so you can easily assign a class number for each of them.

Now you have nodes of two types: permutation-insensitive and reverse-insensitive. For the first type you should fetch class numbers of each sub-node, then sort these numbers (just to fix an order, not to get lexicographically smallest sequence), and look for the class number of resulting sequence in some sort of dictionary. If nothing found in this dictionary, you should create a new class.

For the second type you should do nearly the same. You should look for the class number in another dictionary twice (since you don't know, which sequence is “reversed”, you should perform a pair of look-ups).

You can do the same without dictionaries, just by hashing.
→ Reply