Dərs 2: Acgöz alqoritmlər və metodlar

Bu dərsin qeydləri hələ tam deyil. Əlavə olunana qədər dərsin videosuna baxmağınız tövsiyə olunur. Sonda əlavə resurslar bölməsinə baxmağı da unutmayın.

İkinci dərsə xoş gəldiniz! Ümid edirəm, ilk dərsdə hamı C++ haqqında maraqlı bir şey öyrənə bildi. Piazza forumunda da çox əla söhbətlər oldu. Söz verdiyim kimi, onları da paylaşıram.

Ən maraqlı Piazza paylaşımları
@7, @14, @15, @16, @20, @21, @23, @24, @27, @28, @34, @35, @47

Piazza-da aktiv olanlar və başqalarına yardım edənlər
Bu adların hamısına təşəkkürlər! Əgər kimisə unutdumsa və ya gözümdən yayındısa, mənə Piazza-da bildirə bilər.
Royal Hasanov, Ali Qurbanli, al95ireyiz, Nizami Tağızadə, Aydin, Nizami Tağızadə, Muhammedali Ahmadov, Nasir Bashirov, Rasul Gasimli, Fatimə Əlizadə , Shahin Alekberli , Mete Namazov , Ali Aliyev , Shahin Alekberli, Mehman Karimov, Onur Rahimli , Akbar Habibullayev, Aylin Masiyeva

Sizin yazdıqlarınız
Etməli: Burada kampçıların qeydlərini paylaş.

Bu gün çox maraqlı mövzulara baxacağıq. İki hədəfim var: dərsin sonunda siz həm olimpiada üçün lazım olan C++ dilinin 95%-ni öyrənəcəksiniz (qalan 5%-i isə yalnız beynəlxalq olimpiadalara hazırlaşdıqda öyrənmək lazımdır, çünki onlara aid məsələlər olduqda, çox çətin olurlar), həm də olimpiadalarda düşən ən məşhur məsələ tipini həll etmək üçün çoxlu və ən önəmli metodları öyrənəcəksiniz. Söhbət "acgöz" adlandırdığımız alqoritmlərdən gedir. Əslində, bu tipli məsələlərin konkret mənasını tapmaq çətindir, amma məntiq budur ki, hansısa intuitiv yollarla cavaba çatırıq. Hətta, ən asan məsələləri belə acgöz tipində ifadə etmək olar. Tutaq ki, sizin qabağınızda n sayda tort var və hərəsi üçün obyektiv dad balları professional dad testi edənlər tərəfindən müəyyən olunmuşdur. Siz bu balları bilirsiniz və ən dadlı tortu yemək istəyirsiniz. Hansı tortu yeyəcəksiniz? Təbii ki, bu, verilmiş ədədlər arasında ən böyük ədədi tapmaq məsələsi ilə eynidir. Amma həm məsələnin şərti fərqli verilmişdir, həm də istifadə etdiyimiz seçim acgöz seçimdir, yəni, acgöz davranıb dad balı ən çox olan tortu yeyirik. Bəzən asan məsələlərin şərtləri bu tipdə verilir. Yalnızca çoxlu məsələ işləməklə şərtləri daha sürətli oxuya və daha tez başa düşə bilərsiniz.

Keçən dəfə dərsdə tiplərdən çox danışdıq. İndi isə struct mürəkkəb tip qurucusu haqqında danışaq. Bəzən məsələlərdə verilənlər arasında əlaqələr olur, məsələn, girişə müstəvi üzərində kordinatlar verilir. Bu nöqtələri daxil etmək üçün, məsələn, iki massiv və ya vector işlədə bilərdik, amma bu, onların arasında əlaqə yaratmır. Məsələn, bu nöqtələri x kordinatına görə sıralamalı olsaydıq, bunu necə edərdik? Bir həll olaraq, pair tipi işlədə bilərdik. Bəs kordinatlar 3-ölçülü olsaydı necə? Onda pair<int, pair<int, int>> tipindən istifadə edə bilərdik, amma bu həllərin arasında ən sadə və rahat olanı, məncə, struct istifadə etməkdir. İstifadəsi çox rahatdır:

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

struct point { // point yaratdığımız tipin adı olacaq
  int x, y;
}; // burada nöqtə-vergülü unutmayın

int main() {
  int n;
  cin >> n;
  vector<point> v(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i].x >> v[i].y;
  }
  // kodun davamı...
}

Bu tip bizə həm işləyəndə rahat olur (məsələn, x və y kimi dəyişən adları daha rahat başa düşülür, nəinki first and second ifadələri), həm də koddakı qarışıqlığı aradan qaldırır. İndi isə sual yaranır: bəs biz bu nöqtələri necə sıralayırıq? sort(v.begin(), v.end()) yazsaq nə baş verir? C++ iki point tipini müqayisə edə bilmir, ona görə də, kodu icra edə bilmir. Bu sıralamaları etmək üçün isə iki önəmli metod göstərəcəm və ikisini də bilmək lazımdır. Bu yollardan biri müqayisə əməlini təyin etməkdir, bu əməl üçün isə yalnız < operatorunu nəzərdə tuturuq. Bunu xüsusi operator funksiyası yazmaqla edirik:

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

struct point { // point yaratdığımız tipin adı olacaq
  int x, y;
}; // burada nöqtə-vergülü unutmayın

bool operator<(point &p1, point &p2) {
  if (p1.x == p2.x) {
      return p1.y < p2.y; // əgər x kordinatları bərabərdirsə, y-ə görə sıralayaq
  }
  return p1.x < p2.x;
}

int main() {
  int n;
  cin >> n;
  vector<point> v(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i].x >> v[i].y;
  }
  sort(v.begin(), v.end());
  for (auto &p: v) {
    cout << p.x << " " << p.y << endl;
  }
}

Funksiyalar haqqında danışmamışıq, amma onlar haqqında bilmirsinizsə, bu keçiddən oxumağı və öyrənməyi tövsiyə edirəm. Nəzərə alın ki, bu funksiyanın tipi bool olmalıdır, çünki keçən dəfə dediyimiz kimi, müqayisə ifadələri məntiqi ifadələr sayılır. Daha sonrasında isə operator < yazmaqla, həmin əməli təyin etdiyimizi bildirmiş oluruq. Daha sonra isə funksiya iki point tipi alır. Nəzərə alın ki, dəyişənlərin adının qabağında & işarəsi var. Bu, o deməkdir ki, bu funksiyaya dəyişən daxil etdikdə, o, kopyalanmır, birbaşa ötürülür. Bunu etməyimizin səbəbi isə zamana qənaət etməkdir. Adi funksiyalarda və primitiv tiplərdə kopyalama çox zaman almır, amma daha mürəkkəb tiplərdə bu referans adlandırdığımız işarəni qoymaqla proqramın zaman itirməsinin qarşısını alırıq. İçəridə yazdığımız dəyəri isə p1 və p2 dəyişənlərinin aldığı sıra kimi başa düşmək olar. Bu hissəni daha yaxşı anlamaq üçün dərsin videosuna baxmağı çox tövsiyə edirəm, orada daha geniş izah var.

Sən də yaz
Funksiyalar haqqında Piazza-da yazın. void tipi haqqında yazmağı da unutmayın. Dəyişənlərin önünə & işarəsi yazmağın nə mənaya gəldiyini və onun başqa istifadələrini də göstərin (məsələn, funksiyaya vector daxil etdikdə).

Sıralamağın ikinci yolu isə sort funksiyasını komparator ilə təmin etməkdir. Biz bu funksiyaya hazırda iki dəyər veririk (v.begin() və v.end()), amma məcburi olmayan 3-cü dəyər də verə bilərik. Həmin dəyər funksiya olmalıdır. Mən bu dəyəri lambda funksiyası kimi yazmağı daha çox sevirəm.

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

struct point { // point yaratdığımız tipin adı olacaq
  int x, y;
}; // burada nöqtə-vergülü unutmayın

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector<point> v(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i].x >> v[i].y;
  }
  sort(v.begin(), v.end(), [&](auto &p1, auto &p2) {
    if (p1.x == p2.x) {
      return p1.y < p2.y; // əgər x kordinatları bərabərdirsə, y-ə görə sıralayaq
    }
    return p1.x < p2.x;
  });
  for (auto &p: v) {
    cout << p.x << " " << p.y << endl;
  }
}

Bu, çətin görünə bilər, amma bayaqkı funksiyanın eysini yazırıq. Bayaqkı funksiyada dəyişənləri point olaraq qeyd etməli idik, amma burada auto da işlədə bilərik, çünki C++ başa düşür ki, bu v-nin elementləri arasında müqayisədir və həmin elementlər point tipindədir. Lambda funksiyanın əvvəlində isə [&] var. Oradakı referans işarəsini də yazmağı unutmayın (bu halda, fərq etmir, amma başqa hallarda kodu sürətləndirə bilər). Bu haqda da daha çox dərsin videosunda var, amma Piazza-da sual yaza bilərsiniz.

Sən də yaz
Lambda funksiyaları haqqında daha geniş öyrənin və Piazza-da yazın. Onları nə vaxt istifadə edə bilərik? Adi funksiyalar ilə sürət fərqi varmı?

İndi isə C++-da ən güclü tiplər haqqında öyrənəcəyik. priority_queue tipi ilə başlayaq. Ona biz elementlər əlavə etdikdə, onları avtomatik olaraq sıralayır, amma vector-da edə bildiyimiz kimi istənilən indeksdəki elementi oxuya bilmirik. Bu, bizə ən böyük və ya kiçik elementlərdə dinamik şəkildə işləməyə icazə verir.

priority_queue<int> pq;

pq.push(x); // x elementini artır

pq.top(); // başdakı elementi oxu

pq.pop(); // başdakı elementi sil

pq.size(); // elementlərin sayı

Başdakı element ən böyük element olur, amma bunu dəyişə bilərik. Ən kiçik element olması üçün belə təyin edirik:

priority_queue<int, vector<int>, greater<int>> pq;

Bu tip bizə ən böyük və ya ən kiçik elementləri tapmağa kömək edir, amma biz bunu vector tipi ilə də edə bilərdik. Bəs niyə priority_queue işlədək? Bunun səbəbi alqoritmin işləmə sürətidir. vector tipində biz ən böyük və ya ən kiçik elementi tapmaq üçün xətti sayda əməl edirik. Xətti dedikdə, vectorun ölçüsünə nəzərən deyilir. Məsələn, ölçü n-dirsə, onda vectorda axtarış n-dən xətti asılı olacaq. Buna $O(n)$ zaman çətinliyi deyirik. Məsələn, n dəfə ən böyük ədədi axtarsaq, onda zaman çətinliyi $O(n\cdot n) = O(n^2)$ olar. Kompüterlər isə hazırda təxminən $10^9$ əməliyyatı bir saniyəyə görürlər. Yəni, $n=10^5$ halında ümumi əməliyyatlar üçün sərf olunan zaman çox təxminən 10 saniyə çəkəcək. Bu təxminlər çox kobuddurlar, çünki bəzən kompilyatorlar bizim üçün optimizasiyalar edirlər. Bəzən isə bir əməliyyat xətti olsa da, onun əmsalı böyük olur (məsələn, $10n$ əməliyyat edir, amma bu da $O(n)$ sayılır). priority_queue-də isə element əlavə etmək və silmək loqarifmik çətinlikdə (loqarifmik dedikdə, 2 əsasda nəzərdə tuturuq), ən başdakı elementi tapmaq üçün isə konstant zaman lazımdır. Konstant zaman adətən çox sürətli deməkdir (məsələn, 5 əməliyyat). Loqarifmik də çox sürətlidir. Nəzərə alın ki, milyon ədədinin 2 əsasda loqarifması təxminən 20 edir. Yəni, milyon əvəzinə 20 əməliyyat edirik. Dediyim kimi, bu hesablamarın hamısı çox təxminidirlər, amma məsələ üçün alqoritmik çətinlik düşünəndə kömək olurlar.

Önəmli tövsiyə (+sən də yaz)
Zaman çətinlikləri haqqında bu linkdəki kitabın ikinci fəsilindən (Chapter 2) oxuyun. Mövzunun qısa izahını Piazza-da qeyd kimi paylaşa bilərsiniz.

İndi isə priority_queue-dən daha güclü bir tipə baxaq. set tipi elə bir strukturdur ki, ora element əlavə edib, istənilən elementi silə bilərik, həm də eyni zamanda həm ən böyük, həm də ən kiçik elementi oxuya bilərik. Bundan əlavə, iki çox maraqlı lower_bound və upper_bound metodları da var, amma onlar haqqında daha sonra danışacağıq. Bu tiplə çalışmaq daha çətindir, amma praktika ilə daha rahat olacaq. Nəzərə alın ki, set tipi yalnız fərqli ədədləri özündə saxlayır. Əgər əlavə etdiyimiz ədəd set-də var idisə, heç nə dəyişmir.

set<int> s;

s.insert(x); // x elementini əlavə et

s.erase(x); // x elementini sil

s.find(x); // x elementinə uyğun gələn iteratoru tap (yoxdursa, s.end() olur)

s.begin(); // başlanğıc iterator (ən kiçiyə uyğun gəlir)

s.end(); // son iterator (burada heç bir element uyğun gəlmir)

s.size(); // set-in ölçüsü

s.count(x); // x elementinin set-də sayı (setdə 0 və ya 1 olur)

(burada iteratorları və onlardan elementin özünü almaqla bağlı danış)

Özünü yoxla
Müxtəlif-müxtəlif məsələsini həll et.

Özünü yoxla
Qiymət nişanları məsələsini həll et.

set tipindəki demək olar ki, bütün əməliyyatlar loqarifmik zamana işləyirlər. Bəs niyə bu tip ola-ola priority_queue işlədirik, axı bu daha güclüdür? Səbəbi isə zaman çətinlikləri eyni olsa da, set tipində əməliyyatların konstant əmsalı daha çoxdur, yəni praktikada daha çox zaman aparır. Dediyimiz kimi, set ancaq fərqli ədədləri özündə saxlayır. Bəs bir ədəddən çoxlu olmağını istəsək necə? Onda bütün əməlləri set ilə eyni olan multiset tipi istifadə etmək olar.

map tipi haqqında danış.

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

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  map<int, int> mp;
  mp[1] = 5;
  mp[4] = 10;
  // C++11 və yuxarı
  for (auto &p: mp) {
    cout << p.first << " " << p.second << endl;
  }
  cout << endl;
  // C++14 və yuxarı
  for (auto &[k, v]: mp) {
    cout << k << " " << v << endl;
  }
  // ...
}

Özünü yoxla
Girişə n ədədi və n ədəd söz verilir. Ən çox rast gəlinən sözü necə taparıq?

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

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  map<int, int> mp;
  mp[1] = 5;
  mp[4] = 10;
  cout << mp.count(1) << endl;
  cout << mp.count(3) << endl;
  if (!mp[3]) {
    cout << "3 yoxdur" << endl;
  }
  cout << mp.count(3) << endl; // ???
  return 0;
}

Bu tiplərdə struct istifadə edəndə nə etməli haqqında danış.

İki indeks (two pointers) metodu haqqında danış.

Özünü yoxla
Apartments məsələsini həll et.

Özünü yoxla
Playlist məsələsini həll et.

Binary search (ikili axtarış) haqqında danış. lower_bound, upper_bound metodları və funksiyaları haqqında danış.

Özünü yoxla
İki dəfə böyük məsələsini həll et.

Özünü yoxla
Towers məsələsini həll et.

Özünü yoxla
Sal məsələsini həll et.

Özünü yoxla
Subarray Sums I məsələsini həll et.

Prefix sum haqqında danış.

Özünü yoxla
Subarray Sums II məsələsini həll et.

Özünü yoxla
Forest Queries məsələsini həll et.

Əlavə faydalı resurslar

• USACO Guide Bronze səhifəsində Introduction to Sorting, Introduction to Sets & Maps və Introduction to Greedy Algorithms bölmələri.
• USACO Guide Silver səhifəsində Prefix Sums və Sorting and Searching bölmələri.
• CSES Kitabında 2-ci (Time complexity), 3-cü (Sorting), 4-cü (Data structures) və 6-cı (Greedy algorithms) fəsillər.