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()