Problem link: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&category=0&problem=3703&mosmsg=Submission+received+with+ID+25107707 Problem statement:

Shoulder-surfing is the behavior of intentionally and stealthily watching the screen of another person’s electronic device, such as laptop computer or mobile phone. Since mobile devices prevail, it is getting serious to steal personal information by shoulder-surfing.Suppose that we have a smart phone. If we touch the screen keyboard directly to enter the password,this is very vulnerable since a shoulder-surfer easily knows what we have typed. So it is desirable to conceal the input information to discourage shoulder-surfers around us. Let me explain one way to do this.You are given a 6X5 grid. Each column can be considered the visible part of a wheel. So you caneasily rotate each column wheel independently to make password characters visible. In this problem,we assume that each wheel contains the 26 upper letters of English alphabet.See the following Figure 1.Figure 1.6X5 window clips a valid grid representation for a password.Assume that we have a length-5 password such as p1 p2 p3 p4 p5. In order to pass the authentication procedure, we should construct a configuration of grid space where each pi appears in thei-th column of the grid. In that situation we say that the user password is accepted.Figure 2. A valid grid representation for password ‘COMPU’.Let me start with one example. Suppose that our password was set ‘COMPU’. If we construct the grid as shown in Figure 2 on next page, then the authentication is successfully processed.In this password system, the position of each password charac-ter in each column is meaningless. If each of the 5 characters in p1 p2 p3 p4 p5 appears in the corresponding column, that can be considered the correct password. So there are many grid configu-rations allowing one password. Note that the sequence of letter so n each wheel is randomly determined for each trial and for each column. In practice, the user is able to rotate each column andpress “Enter” key, so a should-surfer cannot perceive the passwordby observing the 6X5 grid since there are too many password candidates. In this 6X5 grid space, maximally 6^5= 7;776 cases arepossible. This is the basic idea of the proposed password system against shoulder-surfers.Unfortunately there is a problem. If a shoulder-surfer can observe more than two grid plate configurations for a person, then the shoulder-surfer can reduce the searching space and guess the correctpassword. Even though it is not easy to stealthily observe other’s more than once, this is one weakness of implicit grid passwords.Let me show one example with two observed configurations for a grid password. The user passwordis ‘COMPU’, but ‘DPMAG’ is also one candidate password derived from the following configuration.

Input:

Your program is to read from standard input. The input consists of T test cases. The number of testcasesTis given in the first line of the input. The first line of each test case contains one integer,K,the order of the password you should find. Note that 1 < K < 7 777. Next the following 6 lines showthe 6 rows of the first grid and another 6 lines represent the 6 rows of the second grid.

Output:

Your program is to write to standard output. Print exactly the k-th password (including ‘NO’) in one line for each test case.The following shows sample input and output for three test cases.

Explanation:

It is clear that for a password to be viable it should exist in both configs of the grid, with the same order of the characters.We can use backtracking to build a password gradually by picking up characters that are common in the i-th column in both configs,appending them to the string param and then moving on to the next column.If the last column is achieved then we add the formed string to a vector.After this process is finished we sort the vector and return the k-th element.

My code:

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

#include <bits/stdc++.h>
using namespace std;

vector<string> configs(12);
vector<string>ans;

void backtrack(int column,string str){
	if(column==5){if(find(ans.begin(),ans.end(),str)==ans.end())ans.push_back(str);}
	else{
		for(int i = 0;i<6;i++){
			for(int j = 6;j < 12;j++){
				if(configs[i][column]==configs[j][column])backtrack(column+1,string(str+configs[i][column]));
				}
			}
		}
	}

int main(int argc, char **argv)
{
	int t;
	cin>>t;
	while(t--){
		int k;
		cin>>k;
		ans.clear();
		for(int i = 0;i<12;i++)cin>>configs[i];
		backtrack(0,"");
		sort(ans.begin(),ans.end());
		if(k>(int)ans.size())cout<<"NO"<<endl;
		else cout<<ans[k-1]<<endl;
		}
	
	return 0;
}