CF 102697123 - Affine Cipher

CF 102697123 - Affine Cipher

Rating: -
Tags: -
Solve time: 45s
Verified: yes

Solution

Problem Understanding

The task is to encode a lowercase string using an affine cipher. The two integers a and b define the cipher. For every letter, we first convert a to z into the numbers 0 through 25, apply

[ y=(a x+b)\bmod 26, ]

and convert y back to a lowercase letter. Spaces are copied unchanged.

For example, if a = 7, b = 5, and the current character is x, its numeric value is 23. The encrypted value is (7 * 23 + 5) % 26 = 10, which corresponds to k.

The input contains the two cipher parameters on the first line and the plaintext on the second line. The output is the complete encoded string, including every original space.

The official problem gives a one second time limit and 256 MB of memory. The statement does not provide a separate explicit upper bound for the string length, so the natural target is linear time in the number of characters. An algorithm that repeatedly searches through the alphabet for every character would introduce an unnecessary factor of 26. A direct arithmetic transformation needs only constant work per character and is the appropriate approach regardless of the exact length bound.

There are a few cases where a careless implementation can silently produce the wrong string. Spaces must not be transformed. For example,

11 1
a b

becomes

l m

because a maps to b numerically and b maps to m, while the middle space remains a space. An implementation that processes every character with ord(c) - ord('a') would incorrectly treat the space as a negative alphabet index.

The modular operation also has to be applied to the whole expression. With

7 5
x

the value is (7 * 23 + 5) % 26 = 10, so the output is

k

A careless implementation that converts the multiplication result directly to a character without taking modulo 26 can produce a character outside a through z.

Finally, the first and last alphabet positions are ordinary values, not special cases. With

0 0
z

the value becomes (0 * 25 + 0) % 26 = 0, so the answer is

a

This catches implementations that accidentally preserve the input when a is zero or mishandle the wraparound at the end of the alphabet.

Approaches

The most direct brute-force approach would process each character and try every one of the 26 possible output letters until it finds the letter whose numeric value satisfies the affine formula. This is correct because every candidate output has a known value from 0 through 25, so testing all 26 possibilities must eventually find the required one. For a string of length n, however, this performs up to 26n candidate checks in the worst case. The work is still technically linear because 26 is a constant, but it is unnecessary and obscures the simple arithmetic structure of the problem.

The brute-force works because the alphabet is tiny, but the cipher itself already gives us the exact numeric value of the answer. Once a character has been converted to x, there is no search to perform. We can calculate (a * x + b) % 26 directly and convert that number back into a character.

The key observation is that the transformation is independent for every character. The encrypted value of one letter does not depend on the previous letter, the next letter, or the position of the letter in the string. That means we can scan the input once, transform letters immediately, and copy spaces unchanged.

The optimal solution therefore performs constant work per input character. Its running time is O(n), where n is the length of the input string, and it needs O(n) space if we construct the output as a new string.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(26n) = O(n)	O(n)	Accepted, but unnecessary work
Optimal	O(n)	O(n)	Accepted

Algorithm Walkthrough

1. Read a and b from the first line, then read the entire second line as the plaintext. Reading the whole line is necessary because spaces are part of the data.
2. Create an output buffer. Processing the string character by character lets us preserve spaces exactly while replacing only lowercase letters.
3. For each character, check whether it is a space. If it is, append the space unchanged because the cipher is applied only to letters.
4. For a lowercase letter, convert it to its numeric value with ord(c) - ord('a'). This maps a to 0, b to 1, and z to 25.
5. Calculate (a * x + b) % 26. The modulo operation puts the result back into the valid alphabet range 0 through 25, including cases where the arithmetic wraps around from z back to a.
6. Convert the resulting number back to a lowercase character with chr(value + ord('a')), then append it to the output buffer.
7. Print the completed output string. The characters appear in exactly the same order as the input, with only lowercase letters replaced by their encrypted values.

Why it works

For every input letter, the algorithm first obtains exactly its prescribed character code x. It then applies the cipher's defining formula (a * x + b) % 26, so the produced numeric value is exactly the required encrypted character code. Spaces are copied without modification, matching the rule that spaces are excluded from the cipher. Since the algorithm performs this correct transformation independently for every character and never changes their order, the resulting string is exactly the required encryption.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    a, b = map(int, input().split())
    s = input().rstrip('\n')

    result = []

    for c in s:
        if c == ' ':
            result.append(c)
        else:
            x = ord(c) - ord('a')
            y = (a * x + b) % 26
            result.append(chr(y + ord('a')))

    print(''.join(result))

if __name__ == "__main__":
    solve()

The first two values are read as integers because they directly participate in the affine formula. The second line is read with input(), rather than token-based input, because spaces must remain part of the plaintext.

The call to rstrip('\n') removes only the newline added by reading the line. It does not remove spaces, so leading, trailing, or consecutive spaces remain intact. This is preferable to strip(), which would also remove meaningful spaces from the plaintext.

The character test happens before the numeric conversion. Calling ord() on a space would not produce an alphabet index, so handling spaces separately prevents invalid transformations.

For a letter, ord(c) - ord('a') gives a value from 0 to 25. Python integers do not overflow, so even unusually large values of a and b would not create an integer overflow problem. The modulo 26 operation is applied after the complete affine expression, exactly as specified.

The output is accumulated in a list and joined once at the end. This avoids repeatedly constructing larger intermediate strings and gives linear total construction time.

Worked Examples

Sample 1

The input is

7 5
xavier

The key is a = 7, b = 5. The transformation for each character is (7x + 5) % 26.

Character	x	7x + 5	Encrypted value	Output
x	23	166	10	k
a	0	5	5	f
v	21	152	22	w
i	8	61	9	j
e	4	33	7	h
r	17	124	20	u

Joining the transformed characters gives kfwjhu, which is the required output. The trace shows that every character uses the same formula, with no state carried from one character to the next.

Sample 2

The input is

11 1
coderams club

Here the transformation is (11x + 1) % 26.

Character	x	11x + 1	Encrypted value	Output
c	2	23	23	x
o	14	155	25	z
d	3	34	8	i
e	4	45	19	t
r	17	188	6	g
a	0	1	1	b
m	12	133	3	d
s	18	199	17	r
	none	none	none
c	2	23	23	x
l	11	122	18	s
u	20	221	13	n
b	1	12	12	m

The resulting string is xzitgbdr xsnm. The space is copied directly instead of entering the arithmetic transformation, which demonstrates why the input must be processed as a full line.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every character of the plaintext is examined exactly once.
Space	O(n)	The output buffer stores one resulting character for every input character.

Here n is the length of the plaintext line. Since the algorithm performs only a constant amount of arithmetic and character handling per input character, it scales linearly with the actual input size and comfortably fits the stated 1 second and 256 MB limits.

Test Cases

import sys
import io

def solve():
    a, b = map(int, input().split())
    s = input().rstrip('\n')

    result = []

    for c in s:
        if c == ' ':
            result.append(c)
        else:
            x = ord(c) - ord('a')
            y = (a * x + b) % 26
            result.append(chr(y + ord('a')))

    print(''.join(result))

def run(inp: str) -> str:
    old_stdin = sys.stdin
    old_stdout = sys.stdout

    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()

    try:
        solve()
        return sys.stdout.getvalue()
    finally:
        sys.stdin = old_stdin
        sys.stdout = old_stdout

# Provided sample 1
assert run("7 5\nxavier\n") == "kfwjhu\n", "sample 1"

# Provided sample 2
assert run("11 1\ncoderams club\n") == "xzitgbdr xsnm\n", "sample 2"

# Minimum-size style case, one character, zero coefficients
assert run("0 0\nz\n") == "a\n", "zero coefficients"

# Boundary wraparound, z -> a
assert run("1 1\nz\n") == "a\n", "alphabet wraparound"

# Spaces must be preserved, including consecutive spaces
assert run("1 1\na  z\n") == "b  a\n", "space preservation"

# Every letter maps to the same character when a = 0
assert run("0 5\nabcdefghijklmnopqrstuvwxyz\n") == "ffffffffffffffffffffffffff\n", "constant mapping"

# Large practical input, checks linear processing and repeated characters
large_input = "1 0\n" + "z" * 100000 + "\n"
assert run(large_input) == "z" * 100000 + "\n", "large input"

Test input	Expected output	What it validates
0 0 with z	a	Minimum-size input and zero multiplier
1 1 with z	a	Wraparound from 25 back to 0
1 1 with a z	b a	Spaces and consecutive spaces are preserved
0 5 with the full alphabet	26 copies of f	All characters receiving the same transformed value
100000 copies of z with 1 0	100000 copies of z	Large input and linear-time behavior

The final stress case uses a large practical input rather than claiming a specific official maximum, because the published problem statement does not specify a maximum plaintext length.

Edge Cases

A space must never be treated as a letter. For the input

11 1
a b

the algorithm converts a to 0, producing (11 * 0 + 1) % 26 = 1, or b. It leaves the space untouched, then converts b, whose value is 1, to (11 * 1 + 1) % 26 = 12, or m. The output is

b m

The affine expression can wrap around the alphabet. For

1 1
z

the numeric value of z is 25, so the encrypted value is (1 * 25 + 1) % 26 = 0. The algorithm converts zero back to a, producing

a

This is the boundary that exposes implementations that forget the modulo operation.

A zero multiplier is also valid. With

0 5
abc

every letter has encrypted value (0 * x + 5) % 26 = 5, so the output is

fff

The algorithm handles this naturally because it does not assume that the transformation is one-to-one or that a has an inverse modulo 26.

An input can contain consecutive spaces. For

1 1
a  z

the first a becomes b, both spaces remain spaces, and z wraps around to a. The output is

b  a

Reading the plaintext as a complete line and checking spaces explicitly preserves the exact spacing.

The endpoints of the alphabet require no special branch. With

25 25
az

a has value 0 and maps to (25 * 0 + 25) % 26 = 25, which is z. The value of z is 25 and maps to (25 * 25 + 25) % 26 = 0, which is a. The result is

za

This demonstrates the main advantage of the arithmetic solution: all alphabet boundaries and wraparound cases are handled by the same formula, so there is no collection of special cases that can become inconsistent.