C++

Forum

 
Password Attacker problem

anup30 (968)
Problem:
Passwords are widely used in our lives: for ATMs, online forum logins, mobile device unlock and door access. Everyone cares about password security. However, attackers always find ways to steal our passwords. Here is one possible situation:

Assume that Eve, the attacker, wants to steal a password from the victim Alice. Eve cleans up the keyboard beforehand. After Alice types the password and leaves, Eve collects the fingerprints on the keyboard. Now she knows which keys are used in the password. However, Eve won't know how many times each key has been pressed or the order of the keystroke sequence.

To simplify the problem, let's assume that Eve finds Alice's fingerprints only occurs on M keys. And she knows, by another method, that Alice's password contains N characters. Furthermore, every keystroke on the keyboard only generates a single, unique character. Also, Alice won't press other irrelevant keys like 'left', 'home', 'backspace' and etc.

Here's an example. Assume that Eve finds Alice's fingerprints on M=3 key '3', '7' and '5', and she knows that Alice's password is N=4-digit in length. So all the following passwords are possible: 3577, 3557, 7353 and 5735. (And, in fact, there are 32 more possible passwords.)

However, these passwords are not possible: 
1357  // There is no fingerprint on key '1'
3355  // There is fingerprint on key '7',
         so '7' must occur at least once.
357   // Eve knows the password must be a 4-digit number.


With the information, please count that how many possible passwords satisfy the statements above. Since the result could be large, please output the answer modulo 1000000007(109+7).
Input

The first line of the input gives the number of test cases, T.
For the next T lines, each contains two space-separated numbers M and N, indicating a test case.
Output

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the total number of possible passwords modulo 1000000007(109+7).
Limits
Small dataset

T = 15.
1 ≤ M ≤ N ≤ 7.
Large dataset

T = 100.
1 ≤ M ≤ N ≤ 100.

Sample
Input 
4
1 1
3 4
5 5
15 15

Output
Case #1: 1
Case #2: 36
Case #3: 120
Case #4: 674358851
anup30 (968)
i need a mathematical equation to find, total permutation, of, say,

int n, m; condition: n<m;
there are n types of element. each turn take all and fill m empty places by them, each elements should be used at least once.

so, what would be the math equation? or code to find it without equation?
Smac89 (1727)
Look up combinations and permutations. Basically the question is asking:

Given m, and n, what are the total number of ways to pick n keys from m keys. Also look carefully; the condition states that m <= n not the opposite
anup30 (968)
Smac89 wrote:
Given m, and n, what are the total number of ways to pick n keys from m keys.




in my second post i used n and m differently than N and M in the question.

your quotation is commonly found in permutation, i could do that.
but, the problem asks the opposite, you'll take all keys and fill greater(or =) places by them.


i gave a glance at wikipedia Permutation page, but didn't find
MiiNiPaa (8886)
It is more math question than programming one. My combinatorics is a little rusty, but it seems that you will need to find all combinations of N characters from M keys satisfying that each key is there at least once (it would be (MN - M) combinations) and then find sum of number of multiset permutations for each combination.
However large dataset makes me think there might be another way (as something like 50! will not fit in any variable)
Last edited on
Smac89 (1727)
I say just use a programming language that has multiprescision integers built into it. Language like Java has the BigInteger library, Python's math library has a factorial function. Using python, 100! is:
933262154439441526816992388562667004907159682643816214685929638952175
999932299156089414639761565182862536979208272237582511852109168640000000
00000000000000000L

The formula to solve this is found here:
http://math.stackexchange.com/questions/260537/how-many-ways-are-there-to-choose-10-objects-from-6-distinct-types-when
Last edited on
anup30 (968)
thanks Smac89 for the link, i am reading it now.
big factorial in C++ won't be a problem as i coded that previously. 200! has 375 digits and it took 5.46 second.

as MiiNiPaa's idea, first find combinations:
1. fill N places by using all once.
2. fill remaining (M-N) places by all combinations by any of N elements.
then,
3. find all permutations from all combinations.

i think i can do step 1 and 3.
remaining part is step 2.
MiiNiPaa (8886)
remaining part is step 2.
It is the easiest part. All combinations can be found by finding all permutations of bitstring of (M - 1) ones and (M - N + M - 1) zeroes:
http://en.wikipedia.org/wiki/Stars_and_bars_%28combinatorics%29
PCrumley48 (173)
anup30:

Your three steps are good, but there is a problem:

For example, using the M = 3, N = 4 values:

There are 6 permutations of M - no problem.

There are 4 combinations of "optional" single spaces within password length N.

6 permutations times 4 combinations = 24.

But if you create the table

ABC_
AB_C
A_BC
_ABC

Etc for all permutations of ABC you will find that half of them are duplicates when a member of {A,B,C} is substituted for _.

A_BC (AABC) = _ABC (AABC)

You'll have to revise your steps to weed out unrequired duplicates, I'm afraid. I haven't worked out the math for this yet. . .but I'm trying.

Want to try to solve in 256 byte program?? :)

I haven't carried this out to other sets, but it gets worse as the ratio between N and M increases.
anup30 (968)
its a very perplexing problem.

for simple example of M=3 = {a,b,c} and N=4;
the 3 steps are this way,
1. a b c _

step 2 is 3 (M) types
2i) a b c a
2ii) a b c b
3iii) a b c c

in step 3, all 2 sets will be ordered(say by enums) then all permutation of all sets will be pushed back to a vector.(i'll probably need a class to compare them to prevent duplicates). this is ok.

but for large inputs say, M=40 and N=100; the coding seems complicated.
because, filling 41th to 100th places by all combinations of M seems challenging.
MiiNiPaa (8886)
filling 41th to 100th places by all combinations of M seems challenging.
It is pretty easy. I posted link to "stars and bars" method. Finding all combinations of bistring is as easy as calling std::next_prtmutation in loop:

1
2
3
4
5
6
 
std::string comb(2*M - N - 1, '0');
comb += std::string(M - 1, '1');

do {
    handle_combination(comb);
} while(std::next_permutation(comb.begin(), comb.end()));
PCrumley48 (173)
Finding all combinations of bistring is easy as calling. . .


But I think {all combinations} contains more ineligible duplicate passwords than valid ones. I ran a non-c version, that created all possibilities for a 3 letter 15 character password, and out of almost 10,000,000 combinations only about 5700 were unique. I'm going to recreate that tomorrow and confirm it, but increasing the difference between the password length and the number of characters used decreases the proportion of valid passwords to all possible combinations dramatically.

By the way, anup: your factorial horse is pretty slow. . .this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
#include <vector>
#include <iostream>
#include <ctime>

int main()
{
	clock_t t0, t1;
	t0 = clock();
	std::vector<int> factorial;
	factorial.push_back(1);
	int carry = 0, msd = 0, lsd = 0; //msd is most significant, lsb is last non-zero digit in result

	for (int i = 0; i < 15000 ; i ++)
	{
		carry = 0;
		for (int j = lsd; j < factorial.size() ;j++) // ignores trailing zeros
		{
			carry = (i + 1) * factorial[j] + carry;
			factorial[j] = carry % 10;
			if(factorial[j] == 0 && j == lsd) lsd++;
			carry /= 10;
			if( msd == j && carry > 0) 
			{ 
				msd++; 
				factorial.push_back(0);
			}
		}
	}
	for (int i = factorial.size()-1; i >= 0; i--) std::cout << factorial[i];
	std::cout << std::endl;
	std::cout << factorial.size() << std::endl;
	t1 = clock();
	std::cout << "\nTime Test:\n"
	<< "Running time     " << double(t1-t0) / CLOCKS_PER_SEC << " sec\n"<< std::endl;
	system("Pause");
	return 0;
}

runs on my system in debug mode in 5.07 seconds, with a 56130-digit result.
MiiNiPaa (8886)
But I think {all combinations} contains more ineligible duplicate passwords than valid ones
Did you mix combinations and permutations? Even there are permutation calculation formulas which aware abour element repetition.

Also note that digit position does have meaning: passwords 12 and 21 are different, unique and should be counted as such.
anup30 (968)
those who are wrecking your brain in this - it worth it!
https://code.google.com/codejam/contest/4214486/dashboard

however, the sample output shown in the website has error(?): for
15 15

output:
Case #4: 674358851

is wrong
because, 15! = 1307674368000
anup30 (968)
my program needs fixing, shows some incorrect values:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
 
// Password Attacker Problem // ...
#include <iostream>
#include <fstream> 
using namespace std;

bool callF (int ar[], int M, int N) {
	int i, j;
	for( i=M+1; i<N; i++) {
		if(ar[i] < M ) {
			ar[i]++;
			for(j=i-1; j>=M; j--) {
				ar[j] = ar[i];
			}
		break;				
		}
		//else continue;
	}

	if(i<N) return true;
	else return false;	
}


unsigned long long int fact (int x) {
	unsigned long long int p = 1;
	for(int i=2; i<=x; i++) {
		p *= i;
	}
return p;	
}

int main () {  ////////////////////////// main ///////////

	ifstream in;
	ofstream out;
	in.open("A-small-practice.in");
	out.open("output2.txt");
	
	if(!in || !out){
		cout << "file error!\n";
		exit(-1);
	}
	
	int *ar;
	int *arr;
	int *arc;
	
	int T;
	int M;  
	int N;  //N >= M
	bool b=1;
	unsigned long long int count=0;
	unsigned long long int Nf, fM;
	
in >> T;
cout << "T= " << T << endl;
for(int t=1; t<=T; t++)
{
	in >> M;
	in >> N;
		
	ar = new int[N];
	arr = new int[N];
	arc = new int[N];	

	for(int i=0; i<M; i++)	{
		ar[i] = i;
	}
		
	for(int j=M; j<N; j++) {
		ar[j] = 0;
	}	

	count = 0;
	Nf= fact(N); 

	while(M>1) { /////////
	
		if(M==N) break;
		
		for(int i=0; i<N; i++) {
			arr[i] = ar[i];
		}

		for(int i=0; i<N; i++) {
	 		arc[i] = 1;
		}	

		for(int i=0; i<M; i++) {
			for(int j=M; j<N; j++) {
				if(arr[i]==arr[j] ) {
					arc[i]++;
				}				
			}
		}

		fM =1;
		for(int i=0; i<M; i++) {
			if(arc[i]>1){
				fM *= fact(arc[i]);
			}			
		}	
			
		count += Nf / fM; ////
		
		ar[M]++;
		if( ar[M] >= M ) {	
			b =	callF(ar, M, N);
			if(b==false) break; /////
		}
		
		//count += Nf / fM; ////
				
	}
	
	if(M==1) out << "Case #" << t << ": " << 1 << endl;
	else if(M==N) out << "Case #" << t << ": " << Nf << endl;
	else if(M>1) out << "Case #" << t << ": " << count << endl;
	
	delete[] ar;
	delete[] arr;
	delete[] arc;

}	

in.close();
out.close();

return 0;	
}


count += Nf / fM; in line 104 or 112, each position shows correct value for one of the following
3 4 > 36
2 4 > 14
Last edited on
Konstantin2 (142)
Can anyone check this formula:
cnt = sumi=0M(-1)iM!/(i! * (M-i)!)(M-i)N
Konstantin2 (142)
It looks like work
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
#include <fstream>

using namespace std;

long long fct(int i)
{
    long long res = 1;
    while (i > 1) res *= i--;
    return res;
}

long long pow(const int a, int b)
{
    long long res = 1;
    while (b--) res *= a;
    return res;
}

long long calc(const int M, const int N)
{
    long long res = 0;
    const long long fM = fct(M);
    for (int i = 0; i < M; i++) {
	const long long x = fM / (fct(i) *  fct(M - i)) * pow(M - i, N);
	res += (i & 1) ? -x : x;
    }
    return res;
}

int main()
{
    ifstream in;
    ofstream out;
    in.open("A.in");
    out.open("A.out");
    if (!in || !out) return;
    int T, M, N;
    in >> T;
    for (int i = 1; i <= T; i++) {
	in >> M >> N;
	out << "Case #" << i << ": " << calc(M, N) << endl;
    }
}
MiiNiPaa (8886)
It looks like you mageged to simplify recursive addition/substraction formula. It seems correct, but it will not work as-is because of
please output the answer modulo 1000000007(109+7).
As some entries will not fit in 64 bit, it might be tricky to adapt this solution.
Konstantin2 (142)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
#include <map>
#include <fstream>

using namespace std;
const long long mdl = 1000000007;
// This is a form of representation big numbers as product of prime numbers
typedef map<int, int> factors;

long long pow(const int a, int b)
{
    long long res = 1;
    while (b--) {
	res *= a;
	res %= mdl;
    }
    return res;
}

void operator *=(factors& f, int x)
{
    while (x > 1) {
	for (int i = 2; i <= x; i++) {
	    if (x % i) continue;
	    x /= i;
	    f[i]++;
	    break;
	}
    }
}

void operator /=(factors& p1, factors& p2)
{
    for(auto p = p2.cbegin(); p != p2.cend(); p++)
	p1[p->first] -= p->second;
}

// Number of combinations
long long C(const int M, int x)
{
    // C(n, k) = C(n, n - k), but quicker if k is small
    if (x > M/2) x = M - x;
    factors p1, p2;
    for (int i = M - x + 1; i <= M; i++) p1 *= i;
    for (int i = 2; i <= x; i++) p2 *= i;
    p1 /= p2;

    long long res = 1;
    for(auto p = p1.cbegin(); p != p1.cend(); p++) {
	for (int i = 0; i < p->second; i++) {
	    res *= p->first;
	    res %= mdl;
	}
    }
    return res;
}

long long calc(const int M, const int N)
{
    long long res = 0;
    for (int i = 0; i < M; i++) {
	const long long x = C(M, i) * pow(M - i, N) % mdl;
	res += (i & 1) ? -x : x;
    }
    res %= mdl;
    if (res < 0) res += mdl;
    return res;
}

int main()
{
    ifstream in;
    ofstream out;
    in.open("A.in");
    out.open("A.out");
    if (!in || !out) return 0;
    int T, M, N;
    in >> T;
    for (int i = 1; i <= T; i++) {
	in >> M >> N;
	out << "Case #" << i << ": " << calc(M, N) << endl;
    }
}
Last edited on
anup30 (968)
solved at last!
the hardest problem in my few months programming experience.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
 
// Password Attacker Problem // ...
#include <iostream>
#include <fstream> 
using namespace std;

bool callF (int ar[], int M, int N) {
	int i, j;
	for( i=M+2; i<=N; i++) {
		if(ar[i] < M ) {
			ar[i]++;
			for(j=i-1; j>M; j--) {
				ar[j] = ar[i];
			}
		break;				
		}
		//else continue;
	}	
	if(i<=N) return true;
	else return false;	
}

unsigned long long int fact (int x) {
	unsigned long long int p = 1;
	for(int i=2; i<=x; i++) {
		p *= i;
	}
return p;	
}

int main () {  ///// main //////////////
	
	int *ar;
	int *arr;
	int *arc;
	
	int T;
	int M = 3;  ////////////////////
	int N = 4;  // N >= M //////////
	cout << "M,N = " << M << ", " << N << "\n";
	bool b=1;
	unsigned long long int count=0;
	unsigned long long int Nf, fM;
		
	ar = new int[N+1];
	arr = new int[N+1];
	arc = new int[N+1];

	for(int i=1; i<=M; i++)	{
		ar[i] = i;
	}
		
	for(int j=M+1; j<=N; j++) {
		ar[j] = 1;
	}	

	count = 0;
	Nf= fact(N); 

	while(N>M) { /////////
	
		for(int i=1; i<=N; i++) {
			arr[i] = ar[i];
			arc[i] = 1;
		}

		for(int i=1; i<=M; i++) {
			for(int j=M+1; j<=N; j++) {
				if(arr[i]==arr[j] ) {
					arc[i]++;
				}				
			}
		}

		fM =1;
		for(int i=1; i<=M; i++) {
			if(arc[i]>1){
				fM *= fact(arc[i]);
			}
		}
	
		count += Nf / fM;
		ar[M+1]++;
		if( ar[M+1] > M ) {	
			b =	callF(ar, M, N);
			if(b==false) break; /////

		}		
	}

if(N==M) cout << "COUNTS = " << Nf << endl;
else cout << "COUNTS = " << count << endl;

	delete[] ar;
	delete[] arr;
	delete[] arc;

return 0;	
}


M N output
1 1 1
3 4 36
5 5 120
7 7 5040
4 7 8400
4 4 24
6 6 720
1 7 1
1 2 1
1 6 1
2 4 14
1 5 1
6 7 15120
5 5 120
3 4 36



yet to learn for situations outside variable capacities .)
Topic archived. No new replies allowed.