Invite the Heroes

There are nnn cities numbered from 111 to nnn in a country. Two consecutive cities are connected by a bidirectional road (City iii is connected with city i+1i+1i+1 for each 1≤i≤n−11 \leq i \leq n-11≤i≤n−1). There lives exactly one hero in each city. There are kkk types of heroes. The hero of the iii-th city has a type tit_iti​.

This is a companion discussion topic for the original entry at