Domácí kolo

E: Evoluce

Řešení (Zadání úlohy)

Než úlohu začneme řešit, nejdříve si ji trochu zjednodušíme. Zaprvé, o řetězcích budeme jako správní programátoři uvažovat nikoliv jako o posloupnosti znaků a a b, nýbrž jako o posloupnosti nul a jedniček (kde a odpovídá nule a b jedničce). Později uvidíme, proč je to pro nás takto výhodnější. Označme tyto nové řetězce nul a jedniček jako st. Během textu budeme běžně používat zavedené značení, že s[i] značí i-tý znak řetězce s.

Zadruhé se zbavíme nutnosti vyrábět z jednoho řetězce nějaký druhý a pořídíme si rozdílový řetězec r: ten bude mít na i-té pozici nulu, pokud se s[i]t[i] rovnají, jinak tam bude mít jedničku. Určitě platí, že s je už stejné jako t, právě když jsou v r samé nuly. Podíváme se teď, jak naše dvě operace na s mění tento rozdílový řetězec:

  • první operace – překlopení znaku (0 → 1, 1 → 0) na nějaké libovolné pozici i: v s se i-tý znak prohodí za opačný. To samé se ale stane v r: pokud se s[i]t[i] rovnaly, teď už nebudou, a naopak.
  • druhá operace – překlopení znaků (0 → 1, 1 → 0) na všech pozicích 1, 2, …, i pro nějaké libovolné i: Pro každé j = 1, 2, …, i bude na s[j] opačný znak než předtím. Stejně tak bude ale na každém r[j] opačný znak než předtím (ze stejného důvodu, jako minule).

Takže operace provedená na s se v r projeví stejně, jako kdybychom tu samou operaci provedli rovnou na r (a naopak, operace provedená na r se stejně tak projeví v s). My tedy vůbec nemusíme pracovat s s a snažit se ho převádět na t. Místo toho můžeme pracovat s r a převádět ho na samé nuly – tehdy už totiž víme, že když na s provedeme ty samé operace, st se bude rovnat.

Třetí, poměrně snadné pozorování je, že na pořadí provedených operací nezáleží: hodnota každého políčka záleží jen na tom, kolikrát máme jeho znak podle nějakých operací změnit na opačný (pokud sudě-krát, bude výsledný znak stejný jako na začátku, pokud liše-krát, bude opačný), a tento počet operací se měněním jejich pořadí nemění.

Vyřešit lehkou variantu teď vůbec nebude těžké: zadání slibuje, že si vystačíme pouze s jedním typem operací. My tedy můžeme napsat dvě řešení: jedno, které bude používat pouze první operaci, a druhé, které bude používat pouze tu druhou, a pak si z nich pro každý vstup vybrat to, které dává lepší výsledek. Řešení, které využívá pouze první operaci, však určitě napsat umíme: stačí obrátit všechny jedničky na nuly, tedy počet provedených operací bude počet jedniček v r. Řešení využívající pouze druhé operace, můžeme napsat více způsoby, my si však v návaznosti na těžší variantu zvolíme ten, který využívá metodu dynamického programování, o kterém si můžete více přečíst v KSPí kuchařce.

Pořídíme si dvourozměrné pole dp a  v dp[i][b] pro i = 1, 2, …, nb = 0, 1 si spočítáme, na kolik nejméně operací druhého typu zvládneme změnit prvních i znaků na samé b (nuly nebo jedničky). Je zřejmé, že abychom se spočítaným polem dp leží odpověď v dp[n][0]. Jak ale spočítáme hodnotu dp[i][b] z předchozích? Předpokládejme, že počítáme dp[i][0], případ s jedničkou by se dělal podobně. Pokud je r[i] nula, pak dp[i][0] = dp[i - 1][0]: levněji, než že převedeme prvních i – 1 znaků na nuly a pak neuděláme nic, to určitě neumíme. Pokud je r[i] jedna, pak je dp[i][0] = dp[i - 1][1] + 1: nejprve převedeme všechny předchozí znaky také na jedničky a~pak na úsek [0…i] provedeme operaci druhého typu, čímž ho převedeme na samé nuly. Rozmyslíme si, že levněji to také neumíme.

A jak vyřešit těžší variantu? Úplně stejně, jen se nám trochu změní způsob, jak počítáme dp: díky tomu, že máme povoleny obě operace, nám přibydou další možnosti, ze ketrých budeme pro dp[i][b] vybírat nejlevnější. Rozebereme opět pouze počítání dp[i][0]. Pokud je na i-té pozici nula, nic se nezmění: dp[i][0] = dp[i - 1][0], protože levněji to stále neumíme. Zajímavý je případ, kdy r[i] = 1. Pak máme dvě možnosti: převést r[0 … i–1] na samé nuly a použít na r[i] operaci prvního typu, nebo převést r[0 … i–1] na samé jedničky a použít na r[i] operaci druhého typu. Z těchto dvou možností pak vybíráme tu levnější. Zapsáno vzorcem: dp[i][0] = min(dp[i – 1][0] + 1, dp[i – 1][1] + 1) = min(dp[i – 1][0], dp[i – 1][1]) + 1.

V obou případech máme celkem O(N) stavů a každý dokážeme spočítat v konstantním čase. Všimneme si, že pole dp si nemusíme pamatovat celé – pro výpočet dp[i] nám stačí jen hodnoty dp[i – 1]. Nicméně stále musíme do paměti načíst vstup, takže pamětová složitost je také O(N).

Ukázkový program (C++)

#include <bits/stdc++.h>
// "magický" include načítající celou standardní knihovnu
using namespace std;

/* Vyřeší jeden testovací vstup. */
void solve(void)
{
	// Načteme N
	int N;
	cin >> N;

	// Načteme naše dva stringy
	string s, t;
	cin >> s >> t;

	// Trik: budeme se znaky 'a' a 'b' pracovat jako s čísly
	// Navíc v kódování ASCII platí, že 'a' + 1 = 'b', takže odečtením 'a' od
	// všech prvků s a t získáme dvě posloupnosti nul a jedniček
	for (int i = 0; i < N; i++)
		s[i] -= 'a', t[i] -= 'a';

	// Naše rozdílové pole
	vector<bool> r;
	// Převedeme na ekvivalentní úlohu, kdy chceme, aby r = s XOR t bylo nulové
	for (int i = 0; i < N; i++)
		r.push_back(s[i] ^ t[i]);

	/* Minimální počet operací potřebných na změnění prvních `i` znaků řetězce
	 * na samé nuly resp. jedničky (odpovídá dp[i][0] a dp[i][1]) */
	int cena_nuly = 0, cena_jednicky = 0;
	for (int i = 0; i < N; i++) {
		int mi = min(cena_nuly, cena_jednicky);
		if (r[i]) {  // na i-tém políčku je jednička
			cena_nuly = 1 + mi;
			// cena_jednicky se nezmění
		} else {  // na A[i] je nula
			// analogicky
			cena_jednicky = 1 + mi;
			// cena_nuly se nezmění
		}
	}

	// Vypíšeme cenu za vynulování prvních N znaků, tedy všech
	cout << cena_nuly << "\n";
}

int main(void)
{
	int T;
	cin >> T;
	while (T--)
		solve();
	return 0;
}

Ukázkový program (C)

#include <stdio.h>
#include <malloc.h>
#include <assert.h>
#include <string.h>

/* Vyřeší jeden testovací vstup. */
void solve(void)
{
	// Načteme N
	int N;
	scanf("%d", &N);
	
	// Naalokujeme si pole pro oba řetězce (+1 za ukončovací \0)
	char *s = malloc((N + 1) * sizeof(*s));
	char *t = malloc((N + 1) * sizeof(*t));
	assert(s && t);  // Spadneme, pokud nám systém nepřidělil paměť

	// Načteme oba řetězce
	scanf("%s", s);
	scanf("%s", t);

	// Trik: budeme se znaky 'a' a 'b' pracovat jako s čísly
	// Navíc v kódování ASCII platí, že 'a' + 1 = 'b', takže odečtením 'a' od
	// všech prvků s a t získáme dvě posloupnosti nul a jedniček
	for (int i = 0; i < N; i++)
		s[i] -= 'a', t[i] -= 'a';

	// Převedeme na ekvivalentní úlohu, kdy chceme, aby r = s XOR t bylo nulové.
	// Pole s a t už nepotřebujeme, takže můžeme s přepisovat a nemusíme pro r
	// alokovat další paměť
	for (int i = 0; i < N; i++)
		s[i] ^= t[i];

	char *r = s;  // kvůli korespondenci s popisem řešení

	// t už (také) nepotřebujeme
	free(t);

	/* Minimální počet operací potřebných na změnění prvních `i` znaků řetězce
	 * na samé nuly resp. jedničky, odpovídá dp[i][0], dp[i][1] */
	int cena_nuly = 0, cena_jednicky = 0;
	for (int i = 0; i < N; i++) {
		int min = (cena_nuly < cena_jednicky) ? cena_nuly : cena_jednicky;
		if (r[i]) {  // na i-tém políčku je jednička
			cena_nuly = 1 + min;
			// cena_jednicky zůstává stejná
		} else {  // na A[i] je nula
			// analogicky
			cena_jednicky = 1 + min;
			// cena_nuly se nemění
		}
	}

	// Vypíšeme cenu za vynulování prvních N znaků, tedy všech
	printf("%d\n", cena_nuly);
	free(r);  // Uvolní i s, protože oba ukazují na stejné místo v paměti
}

int main(void)
{
	int T;
	scanf("%d", &T);
	while (T--)
		solve();
	return 0;
}

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)