# 1262

## Problem Number - Problem Name[edit]

## 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