[Solution] Meta-set solution codeforces

Meta-set solution codeforces – You like the card board game “Set”. Each card contains 𝑘k features, each of which is equal to a value from the set {0,1,2}{0,1,2}. The deck contains all possible variants of cards, that is, there are 3𝑘3k different cards in total.

A feature for three cards is called good if it is the same for these cards or pairwise distinct. Three cards are called a set if all 𝑘k features are good for them.

For example, the cards (0,0,0)(0,0,0)(0,2,1)(0,2,1), and (0,1,2)(0,1,2) form a set, but the cards (0,2,2)(0,2,2)(2,1,2)(2,1,2), and (1,2,0)(1,2,0) do not, as, for example, the last feature is not good.

A group of five cards is called a meta-set, if there is strictly more than one set among them. How many meta-sets there are among given 𝑛n distinct cards?

[Solution] Meta-set solution codeforces

The first line of the input contains two integers 𝑛n and 𝑘k (1𝑛1031≤n≤1031𝑘201≤k≤20) — the number of cards on a table and the number of card features. The description of the cards follows in the next 𝑛n lines.

Each line describing a card contains 𝑘k integers 𝑐𝑖,1,𝑐𝑖,2,,𝑐𝑖,𝑘ci,1,ci,2,…,ci,k (0𝑐𝑖,𝑗20≤ci,j≤2) — card features. It is guaranteed that all cards are distinct.

Output

Output one integer — the number of meta-sets.

Examples

input

Copy
8 4
0 0 0 0
0 0 0 1
0 0 0 2
0 0 1 0
0 0 2 0
0 1 0 0
1 0 0 0
2 2 0 0

[Solution] Meta-set solution codeforces

Copy
1

input

Copy
7 4
0 0 0 0
0 0 0 1
0 0 0 2
0 0 1 0
0 0 2 0
0 1 0 0
0 2 0 0

[Solution] Meta-set solution codeforces

Copy
3

input

Copy
9 2
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

[Solution] Meta-set solution codeforces

Copy
54

input

Copy
20 4
0 2 0 0
0 2 2 2
0 2 2 1
0 2 0 1
1 2 2 0
1 2 1 0
1 2 2 1
1 2 0 1
1 1 2 2
1 1 0 2
1 1 2 1
1 1 1 1
2 1 2 0
2 1 1 2
2 1 2 1
2 1 1 1
0 1 1 2
0 0 1 0
2 2 0 0
2 0 0 2

output

Copy
0

[Solution] Meta-set solution codeforces

Let’s draw the cards indicating the first four features. The first feature will indicate the number of objects on a card: 112233. The second one is the color: red, green, purple. The third is the shape: oval, diamond, squiggle. The fourth is filling: open, striped, solid.

You can see the first three tests below. For the first two tests, the meta-sets are highlighted.

In the first test, the only meta-set is the five cards (0000, 0001, 0002, 0010, 0020)(0000, 0001, 0002, 0010, 0020). The sets in it are the triples (0000, 0001, 0002)(0000, 0001, 0002) and (0000, 0010, 0020)(0000, 0010, 0020). Also, a set is the triple (0100, 1000, 2200)(0100, 1000, 2200) which does not belong to any meta-set.

[Solution] Meta-set solution codeforces

In the second test, the following groups of five cards are meta-sets: (0000, 0001, 0002, 0010, 0020)(0000, 0001, 0002, 0010, 0020)(0000, 0001, 0002, 0100, 0200)(0000, 0001, 0002, 0100, 0200)(0000, 0010, 0020, 0100, 0200)(0000, 0010, 0020, 0100, 0200).

In there third test, there are 5454 meta-sets.

 

For Solution

“Click Here”

Leave a Comment