Szczegółowe omówienie zadania Cute Chef Gift:

Link do powyższego omówienia zadania Cute Chef Gift: https://youtu.be/rhz5sEdxHQE?t=791
Omówienie kodu zadania Cute Chef Gift: https://youtu.be/rhz5sEdxHQE?t=4751
Kroki algorytmu: https://youtu.be/rhz5sEdxHQE?t=4196
Złożoność algorytmu: https://youtu.be/rhz5sEdxHQE?t=4448

Link do treści zadania Cute Chef Gift i możliwości umieszczania rozwiązań:
https://www.codechef.com/problems/COPAR

Zadanie Cute Chef Gift pokazuje zastosowanie Rozszerzonego Sita Eratostenesa: https://youtu.be/rhz5sEdxHQE?t=2409
Jak rozłożyć liczbę na czynniki pierwsze przy pomocy Rozszerzonego Sita Eratostenesa: https://youtu.be/rhz5sEdxHQE?t=2948
Złożoność rozkładu liczby na czynniki pierwsze przy pomocy Rozszerzonego Sita Eratostenesa:https://youtu.be/rhz5sEdxHQE?t=3087
Kod Rozszerzonego Sita Eratostenesa: https://youtu.be/rhz5sEdxHQE?t=4815

–
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: https://oki.org.pl/harmonogram-zajec/

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

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

–

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 7;
// dzielnik[i] = dowolny dzielnik pierwszy liczby i
int dzielnik[MAXN];
// gdzieLewo[p] = pierwszy indeks,
// na ktorym liczba jest podzielna przez p (pierwsze)
int gdzieLewo[MAXN];
// gdziePrawo[p] = ostatni indeks,
// na ktorym liczba jest podzielna przez p (pierwsze)
int gdziePrawo[MAXN];
int ilePrzedzialow[MAXN];
void sito()
{
for (int i = 2; i*i < MAXN; ++i) {
if (dzielnik[i] == 0) {
for (int j = i*i; j < MAXN; j += i)
dzielnik[j] = i;
}
}
for (int i = 2; i < MAXN; ++i) {
if (dzielnik[i] == 0)
dzielnik[i] = i;
}
}
void solve()
{
// zerowanie tablic
for (int i = 0; i < MAXN; ++i) {
gdzieLewo[i] = MAXN - 1; // [MAXN-1, 0]
gdziePrawo[i] = 0;
ilePrzedzialow[i] = 0;
}
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
int a;
cin >> a;
// rozklad liczby a na czynniki pierwsze
while (a > 1) {
int p = dzielnik[a];
gdzieLewo[p] = min(gdzieLewo[p], i);
gdziePrawo[p] = max(gdziePrawo[p], i);
a /= p;
}
}
for (int i = 2; i < MAXN; ++i) {
int l = gdzieLewo[i];
int r = gdziePrawo[i];
if (l <= r) {
ilePrzedzialow[l] += 1;
ilePrzedzialow[r] -= 1;
}
}
for (int i = 1; i <= n; ++i)
ilePrzedzialow[i] += ilePrzedzialow[i - 1];
for (int i = 1; i < n; ++i) {
if (ilePrzedzialow[i] == 0) {
cout << i << '\n';
return;
}
}
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0);
sito();
int T;
cin >> T;
for (int i = 0; i < T; ++i)
solve();
return 0;
}

–
Kod Python programu Cute Chef Gift , który otrzymuje 100%:

MAXN = 100000 + 7
# dzielnik[i] = dowolny dzielnik pierwszy liczby i
dzielnik = [0]*MAXN
def sito():
i = 2
while (i*i < MAXN): if (dzielnik[i] == 0): for j in range(i*i, MAXN, i): dzielnik[j] = i i = i + 1 for i in range(2, MAXN): if (dzielnik[i] == 0): dzielnik[i] = i def solve(): # gdzieLewo[p] = pierwszy indeks, # na ktorym liczba jest podzielna przez p (pierwsze) gdzieLewo = [MAXN]*MAXN # gdziePrawo[p] = ostatni indeks, # na ktorym liczba jest podzielna przez p (pierwsze) gdziePrawo = [0]*MAXN n = int(input()) liczby = list(map(int, input().split())) for i in range(n): a = liczby[i] # rozklad liczby a na czynniki pierwsze while (a > 1):
p = dzielnik[a]
gdzieLewo[p] = min(gdzieLewo[p], i+1)
gdziePrawo[p] = max(gdziePrawo[p], i+1)
a //= p
ilePrzedzialow = [0]*(n + 1)
for i in range(MAXN):
l = gdzieLewo[i]
r = gdziePrawo[i]
if (l <= r):
ilePrzedzialow[l] += 1
ilePrzedzialow[r] -= 1
for i in range(1, n):
ilePrzedzialow[i] += ilePrzedzialow[i - 1]
for i in range(1, n):
if (ilePrzedzialow[i] == 0):
print(i)
return
sito()
T = int(input())
for i in range(T):
solve()