1. Problems
  2. classical
  3. Different Vectors
  1. Status
  2. Ranking

DIFFV - Different Vectors

no tags 

You are given set of N vectors, each vector consists of K integers. Vector ex equals ey iff there exists function bijection f and integer r, such that ex[i] = f( ey[(i+r)%K] ), for each i in range [0, K> Eg. (1, 2, 2, 3) == (22, 3, 4, 22), with r=2 and f(22)=2, f(3)=3 and f(4)=1. But (22,3,22,4) is not equal to (1, 2, 2, 3).

How many different vectors are there in set of N given vectors?

Constraints:

n <= 10000

k <= 100

vector values are from range [0, 10^9]

Input

First number contains T (T <= 10), number of test cases. Each test cases consists of following. First line consists of N and K. N lines follows, the i-th containing K integers describing i-th vector.

Output

Output one number, number of different vectors.

Input:
2
3 4
22 3 4 22
1 2 2 3
22 3 22 4
5 5
3 3 3 0 3
8 4 4 4 0
1 1 1 1 1
1 1 8 6 1
1 3 3 3 5

Output:
2
3
Submit solution!
hide comments
Lovro Puzar: 2018-01-01 14:26:00

Nice one!

In the spirit of speed competition, I too kept my solution at 100% correctness even though a heuristic would make it faster.

Last edit: 2018-01-02 12:53:38
Buda IM (retired): 2014-03-30 13:36:51

nema pitanja

(Tjandra Satria Gunawan)(曾毅昆): 2012-11-14 02:43:19

Question for all: is there other strategy to solve this problem other than linked list?

Re (by Buda IM) : I wouldn't say linked list is strategy, nor algorithm. It is just data structure that you have used. Yes, there is different way to solve this problem.

Last edit: 2012-11-14 08:10:42
:D: 2012-11-13 20:34:05

I added a fail-safe to my heuristics and disqualified the previous iffy top solution. So my best time is now from a legit solution.

I think it could still be faster, since one of vital part of my program seems to be sub-optimal. However, I'm out of ideas. Instead I would encourage other users to try to beat my time :)

Also Buda IM, one note: please add some constraint on vector values to description.
:D: 2012-11-13 20:34:05

It's a great problem. It's very subjective, but I love the analysis you need to do here and how it merges a lot of algos and still requires an original idea to keep it together. There's also a lot of room for optimizations on every stage of the program. Overall, one of my best problem solving experiences, highly recommended.

On my solution itself: I feel a little bad about one of the optimizations (worth about 0.17s). It's somewhat heuristic and works only in over 90% of pessimistic cases, not 100%. It was a nice idea, but feels a little like cheating. Maybe I'll revoke it later.

Also it's hard to compare with other online system, unless you run best solutions offline or something like that.

RE (by Buda IM) : You have no idea how happy I am to hear that, from such experienced problem solver :). And your solution is ~4x faster than mine, offline tested. But it uses same idea.

Last edit: 2012-11-13 19:06:45
(Tjandra Satria Gunawan)(曾毅昆): 2012-11-13 20:34:05

Finally AC after a lot of mistake! my first linked list problem :-)
EDIT: now, I can solve this problem under 1s :-D

Last edit: 2013-03-26 23:01:18

Added by:Buda IM
Date:2012-11-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.