Expert.
Put your skills to the test.

Problem summary

Construct the largest base-q integer whose consecutive length-k digit windows are all different. Digits0..q−1 are used.

Constraints

2≤q≤10; 1≤k≤14; the requested answer has fewer than20000 digits.

Worked example

Original statement sample.

2 3

1110100011

Solution analysis

1. There are only q^k possible length-k words, so an answer has at most q^k+k−1 digits. Model each(k−1)-digit word as a vertex. A k-digit word is a directed edge from its first k−1 digits to its last k−1 digits; the edge label is its last digit.
2. Every vertex has q incoming and q outgoing edges, and the graph is connected. An Euler circuit uses every k-word exactly once, attaining the upper bound. Start at the largest(k−1)-digit prefix and use the lexicographically largest Euler trail, obtained by Hierholzer traversal with outgoing digits considered from q−1 down to0.
3. For q=2,k=3, prefix11 and Euler labels10100011 produce1110100011. Its eight windows are111,110,101,010,100,000,001,011, each once. For k=1, the graph has one vertex and the answer is simply the digits in decreasing order.

Why it works

A trail without repeated edges is exactly a digit string without repeated k-windows. Euler traversal uses all q^k edges, giving maximum length. Hierholzer’s sorted-edge traversal postpones dead ends and gives the largest feasible next digit at every position; the starting prefix is also the largest possible. Thus the maximum-length representation is lexicographically, and hence numerically, largest.

Watch out. A plain greedy walk may stop before using all words. Reverse the postorder edge labels from Hierholzer. Keep the initial k−1 prefix. k=1 must work with a single empty-prefix vertex.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<string>
#include<utility>
#include<vector>
using namespace std;
int main(){
    int q,k;
    cin>>q>>k;
    int vertices=1;
    for(int i=1;i<k;i++){
        vertices*=q;
    }
    vector<int>nextDigit(vertices,q-1);
    vector<pair<int,int>>stack{{vertices-1,-1}};
    string labels;
    while(!stack.empty()){
        int vertex=stack.back().first;
        if(nextDigit[vertex]>=0){
            int digit=nextDigit[vertex]--;
            stack.push_back({(vertex*q+digit)%vertices,digit});
        }
        else{
            int digit=stack.back().second;
            stack.pop_back();
            if(digit>=0){
                labels.push_back(static_cast<char>('0'+digit));
            }
        }
    }
    // Completed Euler edges were collected in reverse traversal order.
    reverse(labels.begin(),labels.end());
    cout<<string(k-1,static_cast<char>('0'+q-1))<<labels<<'\n';
}