1262

From Algorithmist
Jump to navigation Jump to search

Problem Number - Problem Name[edit]

1262 - Password

Explanation[edit]

The solution for this problem consists of 2 phases. 1. Extracting the characters that form possible combinations. 2. Sort possible combinations and get the kth password in the list.

Gotchas[edit]

Eliminate the redundant answers from the list while sorting.

Implementations[edit]

For each row in the two grid, create a set of the intersection between the 2 rows, e.g. if the input was:

AYGSU
DOMRA
CPFAS
XBODG
WDYPK
PRXWO
CBOPT
DOSBG
GTRAR
APMMS
WSXNU
EFGHI

Then the constructed sets should be:

ADCW
OPB
GMOX
AP
USG

Were each line is the intersection of 2 rows with the same index in input. Then we sort these sets.

ACDW
BOP
GMOX
AP
GSU

Finally we get the kth element by having 5 nested loops creating the all possible combinations in lexicographic order, notice that the nested loops approach is not bad as it sounds since the worst case will be 6^5 = 7776 possible iterations. Instead of creating all possible combinations we can create only the kth combination by counting number of iterations in the inner loop, then generating the resulting password.

Input[edit]

3
1
AYGSU
DOMRA
CPFAS
XBODG
WDYPK
PRXWO
CBOPT
DOSBG
GTRAR
APMMS
WSXNU
EFGHI
5
AYGSU
DOMRA
CPFAS
XBODG
WDYPK
PRXWO
CBOPT
DOSBG
GTRAR
APMMS
WSXNU
EFGHI
64
FGHIJ
EFGHI
DEFGH
CDEFG
BCDEF
ABCDE
WBXDY
UWYXZ
XXZFG
YYFYH
EZWZI
ZGHIJ

Output[edit]

ABGAG
ABGPS
NO