PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: jay_1048576
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
For a plaintext P and encryption key K (both of length N), the encrypted array E_K(P) is generated as follows:
- For each i (1 \leq i \leq N), the i-th element of E_K(P) is obtained by starting with P_i, and then replacing it with the 3^{rd} next character in the alphabet; K_i times.
You’re given P and E_K(P). Find the lexicographically minimum K that satisfies them.
EXPLANATION:
Note that K_i operates on P_i and results in the i-th character of E_K(P).
So, we can solve for each index separately; each time finding the minimum valid K_i.
This gives us a subproblem: given two characters c_1 and c_2, what’s the minimum number of moves needed to transform c_1 into c_2?
There are various ways to solve this - perhaps the simplest is to just brute force it.
That is, while c_1 \neq c_2, shift c_1 by three.
This will definitely terminate within 26 steps (since performing the operation 26 times will put you back where you started), so it’s fast enough.
TIME COMPLEXITY:
\mathcal{O}(26\cdot N) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
p = input()
c = input()
ans = []
for i in range(n):
x, y = ord(c[i]) - ord('A'), ord(p[i]) - ord('A')
moves = 0
while x != y:
moves += 1
y = (y + 3) % 26
ans.append(moves)
print(*ans)