EQUIPASS - Equivalent Passwords

no tags 

Yesterday you arrived at the hotel, and you kept all your valuable stuff in your room's safe. Unfortunately, you forgot the password. But you have a very long list of passwords (each password is at most 5 digits), and you are sure that your password is one of them. 

The safe will consider some passwords equivalent. Two passwords A and B are considered equivalent, if they are of the same length, and |A[i] - B[i]| is the same for all possible values of i, where X[i] is the i-th digit of X and |Y| is the absolute value of Y. 

You will go through the list of passwords in the given order. For each password, you will do the following: 

If the same password or any of its equivalent passwords were typed before, skip this password. 
Otherwise, type this password into the safe. 
If it's the correct password (or any of its equivalent passwords), the safe will open and you will stop any further processing. 
Now given the list of all passwords, you would like to know, in the worst case scenario, what is the maximum number of passwords you will have to type?

Input Format:
Your program will be tested on one or more test cases. The first line of the input will be a single integer T (1 ≤ T ≤ 50) representing the number of test cases. Followed by T test cases. Each test case starts with a line will containing an integer N (1 ≤ N ≤ 100,000) representing the number of passwords, followed by N lines, each one will contain a non-empty string of at most 5 digits (from '0' to '9'), representing a password (might contain leading zeros).


Output Format:
For each test case print a single line containing "Case n:" (without quotes) where n is the test case number (starting from 1) followed by a space then the maximum number of passwords you will have to type.


Sample Input:
3
000 
111 
222 
1111 
123 
214 
2222 
43434 
54545 
45454


Sample Output:
Case 1: 1 
Case 2: 2 
Case 3: 2


Notes:
In the first test case: all passwords are equivalent to each other. This means that the first password will open the safe for sure. 

In the second test case: 

- If the first password is the correct one, you will type 1 password. 
- If the second password is the correct one, you will type 2 passwords. 
- If the third password is the correct one, you will type 2 passwords (because the second password is equivalent to the third one). 
- If the fourth password is the correct one, you will type 1 password (because the first password is equivalent to the fourth one). 

In the third test case: 

- If the first password is the correct one, you will type 1 password. 
- If the second password is the correct one, you will type 1 password (because the first password is equivalent to the second one). 
- If the third password is the correct one, you will type 2 passwords. Even though the third password is equivalent to the second password, the second password was skipped, and therefore you should type the third password.


hide comments
preet_t: 2018-12-06 17:11:04

@Tensor can you tell what's wrong in my submission, id: 22833964

રચિત (Rachit): 2015-08-10 15:17:11

Last rank on this problem with 14.26s time! Guess I should improve my algo quite a lot... :D
(edit): The awkward moment when the time taken increases with every improvement of the algo -_-

Last edit: 2015-08-10 15:25:15
nadal17: 2015-07-10 13:41:35

Is an O(c*n) algorithm with c = 50*2^5 effective enough for this problem? Such algorithm with Java is giving TLE atm. Guess this requires constant factor optimization...

Last edit: 2015-07-10 13:42:44
abdelkarim: 2015-05-29 03:09:48

why "All except: SCM chicken" are you kidding me ?!
reply (Tensor): i've changed it to checked and keeps telling all except scm chicken :D
"el 3otl ms mn 3ndy b2 xD' "

Last edit: 2015-06-16 22:08:04
gamer496: 2015-03-18 04:04:26

@Tensor could you tell what's wrong with this code submission_id 13886002
reply(tensor)-> i just think that you need to reread the output specification again.. good luck!

Last edit: 2015-03-20 23:22:04
MaHmOuD.: 2015-03-09 11:42:33

@Tensor, Could you give me another test case after checking what's wrong with my code (13814725) , please?
3shan yb2a fair m3 ba2y al nas w kda :D ;)
@MaHmouD. i'm sorry no more test cases :P
@Tensor, You're very kind
yhoon 3leek al3ee4 w alml7 :D

Last edit: 2015-03-09 12:56:48

Added by:Tensor
Date:2015-03-08
Time limit:5s-15s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:ACPC 2014