Min Cost String
Contest: Educational Codeforces Round 107 (Rated for Div. 2)
Difficulty rating: 1600
Tags: brute force, constructive algorithms, graphs, greedy, strings

Let's define the cost of a string $$$s$$$ as the number of index pairs $$$i$$$ and $$$j$$$ ($$$1 \le i < j < |s|$$$) such that $$$s_i = s_j$$$ and $$$s_{i+1} = s_{j+1}$$$.

You are given two positive integers $$$n$$$ and $$$k$$$. Among all strings with length $$$n$$$ that contain only the first $$$k$$$ characters of the Latin alphabet, find a string with minimum possible cost. If there are multiple such strings with minimum cost — find any of them.

Input format:
The only line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5; 1 \le k \le 26$$$).

Output format:
Print the string $$$s$$$ such that it consists of $$$n$$$ characters, each its character is one of the $$$k$$$ first Latin letters, and it has the minimum possible cost among all these strings. If there are multiple such strings — print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
9 4

Example output:
aabacadbb

Example input:
5 1

Example output:
aaaaa

Editorial:
Consider all possible strings of length $$$2$$$ on the alphabet of size $$$k$$$ (there are $$$k^2$$$ of them). Let $$$cnt_i$$$ be the number of occurrences of the $$$i$$$-th of them in the string $$$s$$$. The cost of the string $$$s$$$ by definition is $$$\sum \limits_{i} \frac{cnt_i(cnt_i - 1)}{2}$$$. Now, let's suppose there are two strings $$$i$$$ and $$$j$$$ such that $$$cnt_i - cnt_j \ge 2$$$. Then, if we somehow reduce the number of occurrences of the string $$$i$$$ by $$$1$$$ and increase the number of occurrences of the string $$$j$$$ by $$$1$$$, the cost will decrease. So, in the optimal answer all the strings of length $$$2$$$ should appear the same number of times (and if it's impossible, the difference in the number of appearances should not be greater than $$$1$$$).
Let's suppose that $$$k^2 = n - 1$$$, then our goal is to build a string where each string of length $$$2$$$ on the alphabet of $$$k$$$ characters appears exactly once. The construction of this string can be modeled using Eulerian cycles: build a directed graph with $$$k$$$ vertices, where each vertex represents a character, each arc represents a string of length $$$2$$$, and for every pair of vertices $$$(i, j)$$$, there is an arc from $$$i$$$ to $$$j$$$ (it's possible that $$$i = j$$$!). Then, by finding the Eulerian cycle in this graph (it always exists since the graph is strongly connected and, for each vertex, its in-degree is equal to its out-degree), we find a string of length $$$k^2 + 1$$$ such that all its substrings are different (so each string of length $$$2$$$ appears there once as a substring).
Okay, what about the cases $$$k^2 > n - 1$$$ and $$$k^2 < n - 1$$$? Since the string we build for the case $$$k^2 = n - 1$$$ represents a cycle, we can make it "cyclical" and repeat the required number of times, then cut last several characters if it's too big. For example, if $$$n = 8$$$, $$$k = 2$$$, then the string for $$$k = 2$$$ is abbaa (it's not the only one, but we can use it). We can expand this string to abbaabbaa (by repeating the last $$$k^2$$$ characters), and delete the last character so its length is $$$8$$$.
By the way, in this problem, you don't have to implement the algorithm that finds Eulerian cycles. The graph where we want to find the Eulerian cycle has a very special structure, and there are many different constructive ways to find the cycle in it. But if you can't use them, you always can rely on the straightforward solution that explicitly searches for the Eulerian cycle.