Szczegółowe omówienie zadania Mutating DNA:

Link do powyższego omówienie zadania Mutating DNA: https://youtu.be/sed5wUYVHd0?t=1050
Omówienie kodu zadania Mutating DNA: https://youtu.be/sed5wUYVHd0?t=4800

Link do treści zadania Mutating DNA: https://mirror.ioi2021.sg/statement/dna-ISC.pdf
Wrzucanie rozwiązań zadania Mutating DNA: https://loj.ac/p/3526

Zadanie Mutating DNA jest zadaniem na pomysł i wykorzystanie sum prefiksowych.

Zadanie Mutating DNA  z IOI – International Olympiad in Informatics. Międzynarodowa Olimpiada Informatyczna, to najbardziej prestiżowe zawody informatyczna i algorytmiczne na świecie.
Posiada w swoim CV takiego zadania to wielka motywacja, wartość i potwierdzenie własnych umiejętności. Warto myśleć, kodować, walczyć z tym zadaniem.

–
Jak się uczyć na podstawie tego zadania? https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz: https://youtu.be/pkLXuuOe_qA?t=3625

Lista zadań z rozwiązaniami: https://oki.org.pl/lista-zadan-materialy.php
Samouczek – przygotowanie do Olimpiad: https://oki.org.pl/tutorial/

Zajęcia przygotowujące do Olimpiady Informatycznej: https://oki.org.pl/harmonogram-zajec/

Warto startować w Olimpiadzie Informatycznej!
https://youtu.be/K7fZfJ8nN6A?t=109

–
Kod C++ programu Mutating DNA, który jest omówiony w powyższym filmie i który otrzymuje 100%

–

#include <bits/stdc++.h>
#include "dna.h"
using namespace std;
const int MAXN = 100*1000 + 7;
int slowo1[MAXN];
int slowo2[MAXN];
int pref[MAXN][3][3];
void init(string a, string b)
{
int n = a.size();
// zamiana znakow na liczby
for (int i = 0; i < n; ++i) {
if (a[i] == 'A')
slowo1[i + 1] = 0;
if (a[i] == 'T')
slowo1[i + 1] = 1;
if (a[i] == 'C')
slowo1[i + 1] = 2;
if (b[i] == 'A')
slowo2[i + 1] = 0;
if (b[i] == 'T')
slowo2[i + 1] = 1;
if (b[i] == 'C')
slowo2[i + 1] = 2;
}
// liczenie sum prefiksowych
for (int i = 1; i <= n; ++i) {
for (int c1 = 0; c1 < 3; ++c1) {
for (int c2 = 0; c2 < 3; ++c2) {
// jezeli mamy c1 w slowo1 oraz c2 w slowo2
if ((slowo1[i] == c1) && (slowo2[i] == c2))
pref[i][c1][c2] = pref[i - 1][c1][c2] + 1;
else
pref[i][c1][c2] = pref[i - 1][c1][c2] + 0;
}
}
}
}
int get_distance(int x, int y)
{
x = x + 1;
y = y + 1;
int AT = pref[y][0][1] - pref[x - 1][0][1];
int TA = pref[y][1][0] - pref[x - 1][1][0];
int TC = pref[y][1][2] - pref[x - 1][1][2];
int CT = pref[y][2][1] - pref[x - 1][2][1];
int CA = pref[y][2][0] - pref[x - 1][2][0];
int AC = pref[y][0][2] - pref[x - 1][0][2];
// jezeli mamy tyle samo A, T, C w obu podslowach
if ((AT + AC == TA + CA) && (TA + TC == AT + CT)) {
int wynik = min(AT, TA) + min(TC, CT) + min(CA, AC);
wynik += 2 * abs(AT - TA);
return wynik;
}
else {
return -1;
}
}
// int main()
// {
// 	ios_base::sync_with_stdio(0), cin.tie(0);
// 	int n, q;
// 	cin >> n >> q;
// 	string a, b;
// 	cin >> a;
// 	cin >> b;
// 	init(a, b);
// 	for (int i = 1; i <= q; ++i) {
// 		int x, y;
// 		cin >> x >> y;
// 		cout << get_distance(x, y) << '\n';
// 	}
// 	return 0;
// }

–
Analogiczny kod w języku Python programu Mutating DNA:

MAXN = 100*1000 + 7
pref = [[[0, 0, 0], [0, 0, 0], [0, 0, 0]] for i in range(MAXN)]
def init(a, b):
slowo1 = [0 for i in range(MAXN)]
slowo2 = [0 for i in range(MAXN)]
n = len(a)
# zamiana znakow na liczby
for i in range(n):
if (a[i] == 'A'):
slowo1[i + 1] = 0
if (a[i] == 'T'):
slowo1[i + 1] = 1
if (a[i] == 'C'):
slowo1[i + 1] = 2
if (b[i] == 'A'):
slowo2[i + 1] = 0
if (b[i] == 'T'):
slowo2[i + 1] = 1
if (b[i] == 'C'):
slowo2[i + 1] = 2
# liczenie sum prefiksowych
for i in range(1, n+1):
for c1 in range(0, 3):
for c2 in range(0, 3):
# jezeli mamy c1 w slowo1 oraz c2 w slowo2
if ((slowo1[i] == c1) and (slowo2[i] == c2)):
pref[i][c1][c2] = pref[i - 1][c1][c2] + 1
else:
pref[i][c1][c2] = pref[i - 1][c1][c2] + 0
def get_distance(x, y):
x = x + 1
y = y + 1
AT = pref[y][0][1] - pref[x - 1][0][1]
TA = pref[y][1][0] - pref[x - 1][1][0]
TC = pref[y][1][2] - pref[x - 1][1][2]
CT = pref[y][2][1] - pref[x - 1][2][1]
CA = pref[y][2][0] - pref[x - 1][2][0]
AC = pref[y][0][2] - pref[x - 1][0][2]
# jezeli mamy tyle samo A, T, C w obu podslowach
if ((AT + AC == TA + CA) and (TA + TC == AT + CT)):
wynik = min(AT, TA) + min(TC, CT) + min(CA, AC)
wynik += 2 * abs(AT - TA)
return wynik
else:
return -1
if __name__ == '__main__':
_ = input()
n, q = input().split()
a = input()
b = input()
init(a, b)
print("7abbcd01962faf1b2655df14ab1e12")
print("OK")
for i in range(int(q)):
x, y = input().split()
print(get_distance(int(x), int(y)))