Szczegółowe omówienie zadania Breed Counting:

Link do powyższego omówienie zadania Breed Counting: https://youtu.be/_gLUezRAW0s?t=823
Omówienie kodu zadania Breed Counting: https://youtu.be/_gLUezRAW0s?t=3899
Link do treści zadania Breed Counting: http://www.usaco.org/index.php?page=viewproblem2&cpid=572

Zadanie Breed Counting jest ćwiczeniowym zadaniem na sumy prefiksowe – możliwość policzenia sumy liczb na dowolnym przedziale przy pomocy jednej operacji odejmowania (czas stały).

Zadanie Breed Counting  pochodzi z dywizji Silver Amerykańskiej Olimpiady Informatycznej USACO – odpowiednika naszej Olimpiady Informatycznej Juniorów: https://youtu.be/KI7un-HU_Hk?t=49
Daje piękny wpis do CV: https://youtu.be/P2sLFZBjOmM?t=7223
Dlaczego warto brać udział w Amerykańskiej Olimpiady Informatycznej USACO? https://youtu.be/K7fZfJ8nN6A?t=6848
Co to jest USACO? https://youtu.be/nvA92I5nU0c?t=1414

–
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/

Bezpłatne zajęcia OKI: https://oki.org.pl/harmonogram-zajec/

Informacje o zajęciach: https://oki.org.pl/newsletter.php

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

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

–

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100*1000 + 7;

int krowy1[MAXN];
int krowy2[MAXN];
int krowy3[MAXN];

int pref1[MAXN]; // sumy prefiksowe dla krow o id = 1
int pref2[MAXN]; // sumy prefiksowe dla krow o id = 2
int pref3[MAXN]; // sumy prefiksowe dla krow o id = 3

int main()
{
	ifstream in("bcount.in");
	ofstream out("bcount.out");

	int n, q;
	in >> n >> q;
	for (int i = 1; i <= n; ++i) {
		int idKrowy;
		in >> idKrowy;

		if (idKrowy == 1)
			krowy1[i] = 1;

		if (idKrowy == 2)
			krowy2[i] = 1;

		if (idKrowy == 3)
			krowy3[i] = 1;
	}

	// obliczamy sumy prefiksowe dla kazdego id
	for (int i = 1; i <= n; ++i) {
		pref1[i] = pref1[i - 1] + krowy1[i];
		pref2[i] = pref2[i - 1] + krowy2[i];
		pref3[i] = pref3[i - 1] + krowy3[i];
	}

	// odpowiadamy na zapytania, kazde w czasie stalym
	for (int i = 1; i <= q; ++i) {
		int l, r;
		in >> l >> r;

		int ileKrowId1 = pref1[r] - pref1[l - 1];
		int ileKrowId2 = pref2[r] - pref2[l - 1];
		int ileKrowId3 = pref3[r] - pref3[l - 1];
		out << ileKrowId1 << ' ' << ileKrowId2 << ' ' << ileKrowId3 << '\n';
	}
	return 0;
}

–
Kod Python programu Breed Counting, który otrzymuje 100%

MAXN = 100*1000 + 7

krowy1 = [0 for i in range(MAXN)]
krowy2 = [0 for i in range(MAXN)]
krowy3 = [0 for i in range(MAXN)]

pref1 = [0 for i in range(MAXN)] # sumy prefiksowe dla krow o id = 1
pref2 = [0 for i in range(MAXN)] # sumy prefiksowe dla krow o id = 2
pref3 = [0 for i in range(MAXN)] # sumy prefiksowe dla krow o id = 3

inFile = open("bcount.in", 'r')
outFile = open("bcount.out", "w")

n, q = inFile.readline().split()
n = int(n)
q = int(q)

for i in range(1, n+1):
	idKrowy = int(inFile.readline())

	if idKrowy == 1:
		krowy1[i] = 1

	if idKrowy == 2:
		krowy2[i] = 1

	if idKrowy == 3:
		krowy3[i] = 1

# obliczamy sumy prefiksowe dla kazdego id
for i in range(1, n+1):
	pref1[i] = pref1[i - 1] + krowy1[i]
	pref2[i] = pref2[i - 1] + krowy2[i]
	pref3[i] = pref3[i - 1] + krowy3[i]

# odpowiadamy na zapytania, kazde w czasie stalym
for i in range(1, q+1):
	l, r = inFile.readline().split()
	l = int(l)
	r = int(r)

	ileKrowId1 = pref1[r] - pref1[l - 1]
	ileKrowId2 = pref2[r] - pref2[l - 1]
	ileKrowId3 = pref3[r] - pref3[l - 1]
	outFile.write(str(ileKrowId1) + ' ' + str(ileKrowId2) + ' ' + str(ileKrowId3) + '\n')