Zadanie
V izbe si spokojne žije na kope \(n\) rôzne zafarbených ploštíc. Avšak, ich spokojné nažívanie prerušil príchod skupiny “Kynožíme Spolu Ploštice”, ktorá sa im nabúrala do ich domova a snaží sa ich zbaviť. Preto sa ploštice chcú skryť a byť nenápadné, v nádeji, že ich skupina nenájde.
Momentálne sú ploštice v jednom dlhom rade. Ploštice sú presvedčené, že čím viac homogénnejšie vyzerajú, tým skôr si ich nevšimnú. Preto by sa v rade chceli preorganizovať tak, že čo najmenej párov susediacich ploštíc má inú farbu.
Problém je, že ploštice a) nemajú čas na veľa presúvania a b) myslia centralizovane – centrálny mozog ploštíc vymyslí ako by sa mali pohybovať. Konkrétne, ploštice sa popresúvajú len v blokoch \(k\) ploštíc, a každý takýto blok \(k\) ploštíc sa presúva podľa rovnakého pravidla. Ako najlepšie sa vedia popresúvať?
Úloha
V izbe je vo veľkom rade usporiadaných \(n\) ploštíc. Ploštice majú \(26\) rôznych farieb (reprezentované písmenami a
až z
). Centrálny mozog ploštíc ich preusporiada nasledovne: najskôr si vyberie permutáciu \(k\) prvkov (teda nejaké preusporiadanie \(k\) pozícii), a nasledne podľa nej presporiadajú ploštice na poziciách \(1\) až \(k\), rovnako \(k + 1\) až \(2k\), a tak ďalej až po skupinu ploštíc na pozíciách \(n-k+1\) po \(n\) (môžete predpokladať že \(n\) je deliteľné \(k\)). Permutácia je vybraná, aby minimalizovala počet susediacich dvojíc ploštíc s rôznymi farbami.
Koľko najmenej takýchto dvojíc vie centrálny mozog ploštíc dosiahnuť?
Formát vstupu
Na prvom riadku vstupu je číslo \(k\geq 2\) - veľkosť permutovaných skupín ploštíc.
Na druhom riadku vstupu je reťazec zložený z písmen a
-z
reprezentujúci farby ploštíc v rade. Je garantované, že dĺžka reťazca je deliteľná \(k\).
Formát výstupu
Vypíšte jediné číslo: najmenší počet susediacich dvojíc, ktoré vie centrálny mozog ploštíc dosiahnuť.
Hodnotenie
Existujú 4 sady vstupov. Vo všetkých z nich platí, že \(k\leq 16\) a počet ploštíc nepresiahne \(5000\). V polovici vstupov navyše platí, že \(k\leq 5\) a počet ploštíc nepresiahne \(1000\).
Príklad
Input:
4
abcabcabcabc
Output:
6
V tomto prípade sú skupiný ploštíc abca
, bcab
a cabc
. Jedna z optimálnych permutácii je napríklad P = (2, 1, 4, 3), teda rad sa zmení z (abca)(bcab)(cabc)
(zátvorky sú len na vizualizáciu ktoré ploštice sú spolu v skupine) na (baac)(cbba)(accb)
– môžeme vidieť že je \(6\) susediacich dvojíc rôznej farby
Input:
3
abcabcabcabc
Output:
11
Toto je rovnaký rad ploštíc ako v predchádzajúcom príklade, ale s \(k=3\). Teraz ich nevie centrálny mozog ploštíc preorganizovať do lepšieho rozostavenia.
Táto osmička výnimočne je vlastne len o hrubeh sile. A ako ju robiť šikovne. Tak poďme na to.
Skúšame všetky permutácie
Prvé riešenie, ktoré vieme skúsiť je skúšanie všetkých možností. Čo sú v tomto prípade všetky možnosti? Permutácie \(k\)-tic. Pre každú \(k\)-ticu si vieme zistiť počet rôznofarebných susediacich dvojíc v linárnom čase. Teda vieme všetky možnosti poskúšať v čase \(O(n k!)\) a pamäti \(O(n+k)\), čo nám stačí na štyri body.
Hľadáme cestu
Na vyriešenie úlohy si úlohu preformulujeme ako úlohu na hľadanie najkratšie hamiltonovského cyklu1 vo vhodnom grafe.
Prvé pozorovanie je, že si počet odlišných susedov napísať ako súčet hodnôt pre ze sebou idúce pozície, teda ako súčet
- počtu úsekov kde má prvá a druhá ploštica rôznu farbu
- počtu úsekov kde má druhá a tretia ploštica rôznu farbu
- …
- počtu úsekov kde má predposledná a posledná ploštica rôznu farbu
- počtu úsekov kde má posledná ploštica rôznu farbu od prvej ploštice nasledovného úseku
Druhé pozorovanie, že ak sú pozície \(i\) a \(j\) spermutované vedľa seba, nezáležiac na tom, na ktorom mieste sa relatívne v \(k\)-tici nachádzajú. Túto hodnotu, si vieme spočítať, pre každú dvojicu jednoduchým prechodom cez všetky \(k\)-tice, a spočítaním v koľkých z nich majú pôvodne \(i\)-ta a \(j\)-ta ploštica rôznu farbu.
Rovnako vieme, pre každý pár pozícií \(i, j\), spočítať pre koľko \(k\)-tic je \(i\)-tá ploštica inej farby ako \(j\)-ta ploštica v nasledovnej k-tici.
Takto vlastne dostaneme kompletný ováhovaný graf – vrcholy sú pozície, a hrana medzi vrcholny \(i\), \(j\) má váhu “počet úsekov kde majú \(i\)-ta a \(j\)-ta ploštica rôznu farbu”.
Permutácia zodpovedá nejakej hamiltonovskej ceste^[ceste obsahuj[cej v3etky vrcholy] v tomto grafe, a hodnotu permutácie (výsledný počet rôznofarebných párov) vieme spočítať ako súčet váh použitých hrán a rôznofarebných dvojíc ktoré dostaneme použitím začiatku a konca cesty.
Takto vieme získať riešenie použítim algoritmu na hľadanie najkratšej hamiltonovskej cesty, raz pre každý možný začiatok, teda \(k\)-krát.
Vedeli by sme to ešte zrýchliť? Áno – vieme úlohu vyriešiť len s pomocou jediného vyhľadania hamiltonovskej kružnice (tú vieme nájsť v rovnakom čase ako cestu). A to tak, že si do grafu pridáme špeciálne orientované hrany – hrana z \(i\) do \(j\) indikujúca koľko rôznofarebných dvojíc na “rozmedzí \(k\)-tic” dostaneme ak \(i\)-ta pozícia bola na konci permutácie a \(j\)-ta na začiatku. Následne musíme implementovať len podmienku, že takúto hranu nevieme použiť dvakrát.
Ako na hamiltonovskú kružnicu
Ostáva už len nájsť dostatočne rýchly algoritmus na hľadanie najkratšieho cyklu obsajúceho všetky vrcholy (tak že špeciálne hrany nebudú použité viackrát).
Potrebujeme niečo rýchlejšie ako \(k!\). Síce nie polynomiálna2, ale zložitosť \(O(k^2 2^k)\) bude postačovať.
S technika ktorú použijeme sa môžte stretnúť pod menom bitmasková dynamika. Ide o dynamické programovanie, v ktorom sú stavy
- v ktorom vrchole sa nachádzame
- ktoré vrcholy sme už videli (reprezentované ako číslo s tým binárnym zápisom)
- použili sme už špeciálnu hranu?
Všimnite si, že týchto stavov je \(2n\cdot 2^n\), a v každom stave sa jednoducho vieme pozrieť na každý vrchol kde sme ešte neboli (normálnou aj špeciálnou hranou ak sme ju ešte nepoužili). Na zistenie finálnej hodnoty, vždy začíname dynamiku iba z jedného konkrétneho vrcholu (permutácia ho nemusí nutne dať na prvú pozíciu), a potom ku každému možnému koncu pripočítať váhu hrany do poťiatočného vrchola (používajúc špeciálnu hranu, ak v ceste nebola použitá).
Takto vieme v našom kompletnom grafe nájsť najkratšiu hamiltonovskú kružnicu s presne jednou použitou špeciálnou hranou v čase \(O(k^2 2^k)\).
Graf vieme vybudovať v čase \(O(k^2 (n / k)) = O(nk)\), a teda celková časová zložitosť algoritmu je \(O(nk + k^2 2^k)\). Pamätať si potrebujeme vstup, graf a hodnoty dynamiky, teda je pamäťová zložitosť \(O(n + k\cdot 2^k)\).
#!/usr/bin/python3
def constr_graph(k, s):
= len(s) // k
m = [[len(s) for _ in range(k)] for _ in range(k)]
E = [[len(s) for _ in range(k)] for _ in range(k)]
se
for i in range(k):
for j in range(k):
if i == j:
continue;
= 0
E[i][j] = 0
se[i][j] for l in range(m):
if s[l * k + i] != s[l * k + j]:
+= 1
E[i][j] if l > 0 and s[l * k + i] != s[(l - 1) * k + j]:
+= 1
se[i][j] return (E, se)
def solve(k, s):
= constr_graph(k, s)
E, se
# print(E, se)
= [[[len(s) for _ in range(2)] for _ in range(k)] for _ in range(1 << k)]
dp
1][0][0] = 0
dp[
for a in range(1 << k):
for v in range(k):
if ((1 << v) & a) == 0 or (a % 2 == 0):
continue
# print(a, v, dp[a][v])
for w in range(k):
if ((1 << w) & a) == 0:
# print(w)
| (1 << w)][w][0] = min(dp[a | (1 << w)][w][0], dp[a][v][0] + E[v][w])
dp[a | (1 << w)][w][1] = min(dp[a | (1 << w)][w][1], dp[a][v][1] + E[v][w], dp[a][v][0] + se[w][v])
dp[a = len(s)
res = (1 << k) - 1
en
for v in range(k):
= min(res, dp[en][v][1] + E[v][0], dp[en][v][0] + se[0][v])
res print(res)
= int(input())
k
input())
solve(k,
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,n) for(int i=0;i<(int)n;i++)
typedef complex<long double> point;
template<class T>
T get() {
T a;
cin >> a;return a;
}
template <class T, class U>
operator<<(ostream& out, const pair<T, U> &par) {
ostream& "[" << par.first << ";" << par.second << "]";
out << return out;
}
template <class T>
operator<<(ostream& out, const set<T> &cont) {
ostream& "{";
out << for (const auto &x:cont) out << x << ", ";
"}";
out << return out;
}
template <class T, class U>
operator<<(ostream& out, const map<T,U> &cont) {
ostream& "{";
out << for (const auto &x:cont) out << x << ", ";
"}"; return out;
out <<
}
template <class T>
operator<<(ostream& out, const vector<T>& v) {
ostream&
FOR(i, v.size()){if(i) out << " ";
out << v[i];
}
out << endl;return out;
}
bool ccw(point p, point a, point b) {
if((conj(a - p) * (b - p)).imag() <= 0) return false;
else return true;
}
int> >, vector<vector<int> > > construct_graph(int k, string &s) {
pair<vector<vector<int> > E(k, vector<int>(k, 0)), start(k, vector<int>(k, 0));
vector<vector<int m = s.size() / k;
FOR (i, k) {
E[i][i] = s.size();
start[i][i] = s.size();
FOR (j, k) {if (i == j) continue;
FOR (l, m) {if (s[l * k + i] != s[l * k + j]) E[i][j] ++;
if (l && s[l * k + i] != s[(l - 1) * k + j]) {
start[i][j] ++;
}
}
}
}return {E, start};
}
void solve() {
int k = get<int>();
string s = get<string>();int n = s.size();
auto blah = construct_graph(k, s);
auto E = blah.first, start = blah.second;
int res = n;
int> > > dp(k, vector<vector<int> >(1 << k, vector<int>(2, n)));
vector<vector<vector<
0][1][0] = 0;
dp[for (int a = 1; a < (1 << k); a ++) {
FOR(j, k) {2) {
FOR (b,
FOR(l, k) {if (a & (1 << l)) continue;
1 << l)][b] = min(dp[l][a | (1 << l)][b], dp[j][a][b] + E[j][l]);
dp[l][a | (if (!b) dp[l][a | (1 << l)][1] = min(dp[l][a | (1 << l)][1], dp[j][a][b] + start[l][j]);
}
}
}
}
FOR(j, k) {1 << k) - 1][0] + start[0][j]);
res = min(res, dp[j][(1 << k) - 1][1] + E[j][0]);
res = min(res, dp[j][(
}
cout << res << endl;
}
int main() {
false);
cin.sync_with_stdio(false);
cout.sync_with_stdio(
solve(); }
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.