CAESAR - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: notsoloud
Tester: jay_1048576
Editorialist: iceknight1093

DIFFICULTY:

1232

PREREQUISITES:

None

PROBLEM:

You’re gIven strings S, T, U all of length N.
You know that T is a ROT-K Caesar cipher of S.
Find the ROT-K Caesar cipher of U.

EXPLANATION:

K isn’t given to us in the input, so we first need to find it.

We know that T is a ROT-K cipher of S; which in particular means that the first character of T equals the first character of S shifted K times.
Knowing their first characters, K can thus be found by just computing T_1 - S_1; or more specifically, the difference between the ascii values of S_1 and T_1.

In C++ you can directly subtract characters (subtraction is performed directly using their ascii values).
In Python, you’ll need to use the ord function to obtain ascii values.

Once K is known, it’s easy to compute the ROT-K cipher of U — just shift each of its characters cyclically by K.

TIME COMPLEXITY

\mathcal{O}(N) per testcase.

CODE:

Tester's code (C++) 
/*...................................................................*
 *............___..................___.....____...______......___....*
 *.../|....../...\........./|...../...\...|.............|..../...\...*
 *../.|...../.....\......./.|....|.....|..|.............|.../........*
 *....|....|.......|...../..|....|.....|..|............/...|.........*
 *....|....|.......|..../...|.....\___/...|___......../....|..___....*
 *....|....|.......|.../....|...../...\.......\....../.....|./...\...*
 *....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
 *....|.....\...../.........|....|.....|.......|.../........\...../..*
 *..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
 *...................................................................*
 */
 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
#define MOD 1000000007

void solve(int tc)
{
    int n;
    cin >> n;
    string a,b,c;
    cin >> a >> b >> c;
    for(int i=0;i<n;i++)
        cout << (char)('a'+(b[i]-a[i]+c[i]-'a'+26)%26);
    cout << '\n';
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc=1;
    cin >> tc;
    for(int ttc=1;ttc<=tc;ttc++)
        solve(ttc);
    return 0;
}
Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    t = input()
    u = input()
    
    k = ord(t[0]) - ord(s[0])
    if k < 0: k += 26
    
    ans = ''
    for c in u:
        nxt = ord(c) - ord('a') + k
        if nxt >= 26: nxt -= 26
        ans += chr(ord('a') + nxt)
    print(ans)
2

@iceknight1093 Can you explain why do we need to calculate Ti - Si for every character pair in T & S, as was mentioned that - In the ROT-K cipher, each character in the string is shifted a fixed number of positions down the alphabet.

Like if ROT-2, each character is shifted 2 positions, and we needed to find Rot-k of String U

1 Like
3

Oh that’s a typo, it’s supposed to be T_1 - S_1 (since the line just before that mentions the first characters, after all), not $T_i - S_i. I’ll fix it.
Though tbh you can take any random i instead of 1 and it’ll still work.