The forgotten code
The gate of a country house has a keypad lock with k keys, the digits from 0 to k − 1. It has no “enter” key: the lock opens as soon as the last n digits pressed match the code. You have forgotten the code. You could try all codes in turn, pressing each in full: that is n · kn presses. But neighbouring attempts can share digits: after the presses 0 1 2 3 a lock with n = 3 has checked both 012 and 123.
Print the shortest sequence of presses after which the lock is certain to open, whatever the code: every one of the kn codes must occur in it as consecutive digits. If there are several such sequences, any will do.
Input
Two numbers k and n (2 ≤ k ≤ 10, 1 ≤ n, kn ≤ 106).
Output
One line of digits from 0 to k − 1 without spaces: the sequence of presses.
Examples
Example 1
2 3
0001011100
Example 2
10 2
00102030405060708091121314151617181922324252627282933435363738394454647484955657585966768697787988990
Limits
- Time · Python
- 4000 ms
- Time · Go
- 2000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
How many presses are needed at least? The first code needs n digits, and each further digit gives at most one new code.
2Hint 2
The state of the lock is the last n − 1 digits pressed. Each press moves it to a new state and checks one code along the way. In such a graph, is a code a vertex or an edge?
3The idea
The vertices are strings of n − 1 digits, kn−1 of them. From vertex v, pressing digit d leads to the vertex “v without its first digit, plus d” and checks the code “v, then d”. Each code is exactly one edge. A sequence that checks every code exactly once is a path going along every edge exactly once, that is, an Eulerian one. This is the de Bruijn graph: every vertex has k outgoing and k incoming edges, the graph is connected, so an Eulerian circuit exists. Its length is kn edges, and the presses are n − 1 more: first one has to get into the starting vertex.
4Walkthrough
A vertex is conveniently stored as a number in base k: the move by digit d is (v · k + d) mod kn−1. The edges out of a vertex need not be stored at all: they are just the digits 0, 1, …, k − 1, and the pointer ptr[v] remembers which digit to press next. Then Hierholzer for a directed graph: a stack of pairs “vertex, the digit by which it was reached”; if the vertex on top of the stack has digits left, press the next one, otherwise pop it and write its digit into the answer. The answer is n − 1 zeros (the way into the starting vertex 0…0) followed by the digits in the reverse of the popping order.
The lower bound from the first hint coincides with the length of the circuit: n − 1 + kn. So the answer is not just good but the shortest. For k = 10, n = 4 it is 10,003 presses instead of 40,000.
4+Solution
5Complexity
O(kn): each edge is walked once. Memory is an array of pointers for kn−1 vertices and a stack of up to kn elements.
6Common mistakes
- Greed without a graph. “Press the smallest digit that gives a new code” soon runs into a state from which all codes have already been checked, and stops or goes round in circles. The rule “the largest digit”, starting from zeros, works (this is Martin's construction of 1934), but proving it is noticeably harder than building an Eulerian circuit.
- A recursive traversal. The depth reaches kn = 106; recursion in Python will crash.
- A one-digit code. With n = 1 there is one vertex, and all edges are loops; the answer is all k digits in a row, without leading zeros.