পুরো program: পাঁচ লাইন থেকে সত্যিকারের একটা tool পর্যন্ত

C track-এর Module 9-এ তুমি fixed array দিয়ে একটা marks report লিখেছিলে। তাতে ছিল #define MAX_S 100, প্রতিটা array-এর পাশে একটা count variable, আর 101 নম্বর ছাত্রকে ওটা ঢুকতেই দিত না। এই lesson একই report আবার লেখে, এবার vector দিয়ে, size-এর কোনো সীমা ছাড়া। ছয়টা program ধাপে ধাপে সেখানে পৌঁছায়, প্রতিটা আগেরটার চেয়ে একটু বড়, আর প্রতিটা একটা করে নতুন জিনিস যোগ করে। প্রতিটা program-এর উপরের "নতুন জিনিস" লাইনটা আগে পড়ো; program-টা ঠিক ওটার জন্যই।

Program 1: n-টা মান পড়ো, আবার print করো

নতুন জিনিস: for (int& x : a) cin >> x; সরাসরি element-গুলোর ভিতরে পড়ে, আর এমন একটা separator, যেটা লাইনের শেষে কখনো বাড়তি space রাখে না।

প্রায় সব contest input শুরু হয় n দিয়ে, তারপর n-টা মান। Vector-এর size n করে নাও, তারপর একটা reference দিয়ে প্রতিটা element-এ পড়ো, মানে Module 1-এর সেই বাক্সের দ্বিতীয় নাম।

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) {
        cin >> x;
    }

    for (int i = 0; i < n; i++) {
        cout << a[i] << (i + 1 < n ? ' ' : '\n');
    }
    return 0;
}

12 7 30 7 5

ওই output-টা input 5 আর 12 7 30 7 5-এর জন্য। প্রতিটা element-এর পরে একটা space বসে, শুধু শেষটা বাদে, ওর পরে বসে newline। int& x-এর বদলে int x লিখলে loop পড়ত copy-গুলোতে, আর vector-টা পুরোটাই 0 থেকে যেত। তাই পড়ার loop-টা কাজ করে int&-এর জোরেই।

Program 2: চলতি সর্বোচ্চ মান আর তার index

নতুন জিনিস: হাঁটতে হাঁটতে একসাথে দুইটা জিনিস মনে রাখা: সবচেয়ে বড় মানটা, আর সেটা কোথায় ছিল।

Alice সপ্তাহের প্রতিদিনের সর্বোচ্চ তাপমাত্রা লিখে রাখে। ও চায় সবচেয়ে গরম দিনটা আর তার index। দুই দিন সমান হলে ও চায় প্রথমটা।

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> temps(n);
    for (int& t : temps) {
        cin >> t;
    }

    int best = 0;
    for (int i = 1; i < n; i++) {
        if (temps[i] > temps[best]) {
            best = i;
        }
    }
    cout << "hottest " << temps[best] << " on day index " << best << '\n';
    return 0;
}

hottest 23 on day index 1

ওই output-টা input 7 আর 18 23 21 23 19 17 20-এর জন্য। শুধু index রাখলেই চলে, কারণ temps[best] মানটা ফেরত দেয়। Test-টা >, >= না, তাই পরের কোনো 23 প্রথমটার জায়গা নিতে পারে না। 0 ডিগ্রি থেকে শুরু না করে index 0 থেকে শুরু করায়, পুরো সপ্তাহ শূন্যের নিচে থাকলেও program ঠিক চলে।

Program 3: একটা frequency table

নতুন জিনিস: vector<int> count(k, 0), এমন একটা vector, যার index হলো একটা মান, আর element হলো সেই মান কতবার এসেছে।

David একটা ছক্কা দশবার চালে, আর প্রতিটা সংখ্যা কতবার পড়ল গোনে। ছক্কার সংখ্যা 1 থেকে 6, তাই vector-এ index লাগবে 6 পর্যন্ত, মানে 7টা element। Index 0 কখনো ব্যবহার হয় না, তাতে কোনো সমস্যা নেই।

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> count(7, 0);
    for (int i = 0; i < n; i++) {
        int face;
        cin >> face;
        count[face]++;
    }

    for (int face = 1; face <= 6; face++) {
        cout << face << ": " << string(count[face], '*') << (count[face] > 0 ? " " : "") << count[face] << '\n';
    }
    return 0;
}

1: ** 2
2: * 1
3: **** 4
4: 0
5: * 1
6: ** 2

ওই output-টা input 10 আর 3 6 1 3 3 5 6 2 3 1-এর জন্য। string(k, '*') বানায় k-টা তারার একটা সারি, মানে এক লাইনের একটা histogram। মানটা নিজেই index, তাই প্রতিটা চালের খরচ এক ধাপ, কিছু খুঁজতে হয় না। 7 পড়লে লেখা হতো শেষের বাইরে, তাই আসল input-এ আগে range check করে নাও, C track-এর count array-গুলোতে যেমন করতে।

Program 4: vector-এর vector দিয়ে একটা grid

নতুন জিনিস: vector<vector<int>> g(r, vector<int>(c)), মানে c-টা 0-এর r-টা সারি, পড়া আর কলাম মিলিয়ে print করা।

Maria-র দোকানে r-টা তাক, প্রতিটায় c-টা খোপ, আর প্রতিটা খোপে কয়টা জিনিস আছে তার হিসাব। বাইরের vector সারিগুলো ধরে রাখে। প্রতিটা সারি নিজেই একটা vector<int>, তাই g[i][j] হলো সারি i, কলাম j, ঠিক C-এর grid-এর মতো।

#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int r, c;
    cin >> r >> c;
    vector<vector<int>> g(r, vector<int>(c));
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> g[i][j];
        }
    }

    for (const vector<int>& row : g) {
        for (int x : row) {
            cout << setw(5) << x;
        }
        cout << '\n';
    }
    return 0;
}

    4   12    0
  150    7   33
    9    9 1000

ওই output-টা input 3 3, তারপর 4 12 0, 150 7 33 আর 9 9 1000-এর জন্য। <iomanip>-এর setw(5) পরের সংখ্যাটা পাঁচ ঘরের মধ্যে ডান দিক ঘেঁষে print করে, তাই কলামগুলো লাইনে লাইনে মিলে যায়। বাইরের range-for প্রতিটা সারি নেয় const& দিয়ে, তাই কোনো সারি copy হয় না।

C array-এর সব সারি সমান লম্বা। Vector-এর সারিগুলোকে সমান হতেই হবে, এমন কোনো কথা নেই। এখানে প্রতিটা সারি বানানো হয়েছে push_back দিয়ে, আর সারি i পায় i + 1টা seat, ছোট একটা theatre-এর মতো, যেখানে পেছনের দিকে সারি চওড়া হতে থাকে।

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<vector<int>> seats;
    int number = 1;
    for (int row = 0; row < 4; row++) {
        vector<int> this_row;
        for (int k = 0; k <= row; k++) {
            this_row.push_back(number++);
        }
        seats.push_back(this_row);
    }

    for (size_t i = 0; i < seats.size(); i++) {
        cout << "row " << i << " (" << seats[i].size() << " seats):";
        for (int s : seats[i]) {
            cout << ' ' << s;
        }
        cout << '\n';
    }
    return 0;
}

row 0 (1 seats): 1
row 1 (2 seats): 2 3
row 2 (3 seats): 4 5 6
row 3 (4 seats): 7 8 9 10

এমন আকারকে বলে ragged, বা jagged। Graph-এর প্রতিবেশীদের তালিকা, মানে Module 16-এর adjacency list, ঠিক এই আকারের: প্রতিটা node-এর জন্য এক সারি, যেটা ওই node-এর প্রতিবেশীর সংখ্যার সমান লম্বা। Program যা বানাল, ছবিতে সেটাই দেখো।

তাই g[i] একটা পুরো vector, আর g[i].size() হলো শুধু ওই সারিটার দৈর্ঘ্য।

Program 5: prefix sum দিয়ে range-এর প্রশ্নের উত্তর

নতুন জিনিস: চলতি যোগফলের একটা vector, যেটা একবার O(n)-এ বানানো হয়, তারপর যেকোনো "l থেকে r পর্যন্ত যোগফল"-এর উত্তর দেয় O(1)-এ।

Kenji-র game প্রতি round-এর point লিখে রাখে। Player-রা বারবার জিজ্ঞেস করে, round l থেকে r-এ মোট কত point হয়েছে। প্রতিবার নতুন করে যোগ করলে প্রতিটা প্রশ্নে n ধাপ পর্যন্ত লাগে। তার বদলে বানাও prefix, যেখানে prefix[k] হলো প্রথম k-টা round-এর মোট। এর element n + 1টা, আর prefix[0] হলো 0।

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> points{4, -2, 7, 1, 3};
    int n = points.size();

    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + points[i];
    }

    cout << "prefix:";
    for (long long p : prefix) {
        cout << ' ' << p;
    }
    cout << '\n';

    // rounds counted from 1: the sum of rounds l..r is prefix[r] - prefix[l - 1]
    int questions[3][2] = {{1, 3}, {2, 5}, {4, 4}};
    for (auto& q : questions) {
        int l = q[0], r = q[1];
        cout << "rounds " << l << " to " << r << ": " << prefix[r] - prefix[l - 1] << '\n';
    }
    return 0;
}

prefix: 0 4 2 9 10 13
rounds 1 to 3: 9
rounds 2 to 5: 9
rounds 4 to 4: 1

Round 2 থেকে 5 মানে 5 পর্যন্ত সব round, তা থেকে বাদ 1 পর্যন্ত round-গুলো: 13 - 4 = 9। সামনের বাড়তি element-টার জন্যই l = 1 নিরাপদ: prefix[l - 1] হয় prefix[0], যেটা 0, কখনো prefix[-1] না। যোগফলগুলো long long, কারণ অনেকগুলো বড় মান যোগ করলে একটা int overflow করে।

খরচ একবার O(n), তারপর প্রতি প্রশ্নে O(1)। n = q = 200,000 হলে সেটা প্রায় 400,000 ধাপ, অথচ নইলে লাগত 4,000 কোটি ধাপ পর্যন্ত। তাই prefix sum একবারের প্রস্তুতির বদলে দেয় সাথে সাথে উত্তর, আর এই track-এ এটাই প্রথম ধারণা, যেটা contest সত্যিই পরীক্ষা করে।

Program 6: marks reportIntermediate

নতুন জিনিস: pair-এর একটা vector, যার প্রতিটা pair-এ একটা নাম আর ওই ছাত্রের নিজের marks-এর vector, কোথাও কোনো সীমা ছাড়া।

Input-এর প্রতিটা লাইনে একটা নাম, তারপর ওই ছাত্রের নম্বরগুলো, শেষে -1, কারণ সবাই সমান সংখ্যক পরীক্ষা দেয়নি। Report print করে প্রতিটা ছাত্রের গড়, ক্লাসের সেরা জন, আর গড়ের band ধরে একটা histogram। left, right, fixed আর setprecision(1) আসে <iomanip> থেকে: alignment, আর দশমিকের পরে একটা অঙ্ক।

#include <iomanip>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Each line: a name, then that student's marks, ended by -1.
    vector<pair<string, vector<int>>> students;
    string name;
    while (cin >> name) {
        vector<int> marks;
        int m;
        while (cin >> m && m != -1) {
            marks.push_back(m);
        }
        students.push_back({name, marks});
    }

    const vector<string> band_name{"90+", "80-89", "70-79", "60-69", "below 60"};
    vector<int> band_count(band_name.size(), 0);
    string best_name;
    double best_avg = -1;

    cout << fixed << setprecision(1);
    for (const auto& [who, marks] : students) {
        int total = 0;
        for (int m : marks) {
            total += m;
        }
        double avg = marks.empty() ? 0.0 : (double)total / marks.size();
        cout << left << setw(8) << who << right << setw(3) << marks.size()
             << " marks, average " << setw(5) << avg << '\n';

        int band = avg >= 90 ? 0 : avg >= 80 ? 1 : avg >= 70 ? 2 : avg >= 60 ? 3 : 4;
        band_count[band]++;
        if (avg > best_avg) {
            best_avg = avg;
            best_name = who;
        }
    }

    cout << "best: " << best_name << " (" << best_avg << ")\n";
    for (size_t b = 0; b < band_name.size(); b++) {
        int k = band_count[b];
        cout << setw(8) << band_name[b] << " | " << string(k, '#') << (k > 0 ? " " : "") << k << '\n';
    }
    return 0;
}

Alice     3 marks, average  85.0
Bob       4 marks, average  58.5
Maria     3 marks, average  90.7
Zara      2 marks, average  69.5
Kenji     4 marks, average  80.5
Amara     3 marks, average  94.7
David     2 marks, average  60.5
best: Amara (94.7)
     90+ | ## 2
   80-89 | ## 2
   70-79 | 0
   60-69 | ## 2
below 60 | # 1

ওই output-টা এই সাতটা input লাইনের জন্য: Alice 78 85 92 -1, Bob 55 61 48 70 -1, Maria 90 94 88 -1, Zara 67 72 -1, Kenji 81 79 85 77 -1, Amara 95 91 98 -1 আর David 58 63 -1।

const auto& [who, marks] হলো Module 1-এর structured binding: copy না করেই pair-এর দুই অর্ধেককে নাম দেয়। এখানে তিন রকম type-এর তিনটা vector একসাথে কাজ করছে, আর কোনোটারই size-এর সীমা নেই। 101 নম্বর ছাত্র, বা 100,001 নম্বর, মানে শুধু আরেকটা push_back।

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> marks{72, 45, 90, 38, 66, 49};
    vector<int> retake;
    for (size_t i = 0; i < marks.size(); i++) {
        if (marks[i] < 50) {
            retake.push_back(i);
        }
    }

    if (retake.empty()) {
        cout << "nobody needs a retake\n";
    } else {
        cout << retake.size() << " retakes, at indexes:";
        for (int i : retake) {
            cout << ' ' << i << " (" << marks[i] << ")";
        }
        cout << '\n';
    }
    return 0;
}

3 retakes, at indexes: 1 (45) 3 (38) 5 (49)

#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> sales{12, 15, 9, 20, 18, 25, 30};
    int n = sales.size();
    int w = 3;

    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + sales[i];
    }

    cout << fixed << setprecision(2);
    for (int end = w; end <= n; end++) {
        double avg = (double)(prefix[end] - prefix[end - w]) / w;
        cout << "days " << end - w + 1 << "-" << end << ": " << avg << '\n';
    }
    return 0;
}

days 1-3: 12.00
days 2-4: 14.67
days 3-5: 15.67
days 4-6: 21.00
days 5-7: 24.33

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<vector<int>> mine{
        {0, 1, 0, 0},
        {0, 0, 0, 1},
        {1, 0, 0, 0},
    };
    int r = mine.size();
    int c = mine[0].size();
    int dr[4] = {-1, 1, 0, 0};
    int dc[4] = {0, 0, -1, 1};

    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (mine[i][j] == 1) {
                cout << '*';
                continue;
            }
            int near = 0;
            for (int d = 0; d < 4; d++) {
                int ni = i + dr[d], nj = j + dc[d];
                if (ni >= 0 && ni < r && nj >= 0 && nj < c) {
                    near += mine[ni][nj];
                }
            }
            cout << near;
        }
        cout << '\n';
    }
    return 0;
}

1*11
111*
*101

vector<vector<int>> g(r);
g[0][0] = 5;

vector<int> p(a.size());
p[0] = a[0];
for (size_t i = 1; i < a.size(); i++) {
    p[i] = p[i - 1] + a[i];
}
int l = 0, r = 2;
cout << p[r] - p[l - 1] << '\n';

vector<int> sales(3, 1000000000);
int total = 0;
for (int s : sales) {
    total += s;
}

for (vector<int> row : g) {
    row[0] = 0;
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<vector<int>> g(3, vector<int>(3, 0));
    const int* start = &g[0][0];
    cout << "g[0][2] is " << &g[0][2] - start << " boxes along\n";
    cout << "g[1][0] is " << &g[1][0] - start << " boxes along\n";
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> scores(n);
    for (int& s : scores) {
        cin >> s;
    }

    // Count each score from 0 to 100 in a vector,
    // then print "score count" for every score that appears.

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<int> points(n);
    for (int& p : points) {
        cin >> p;
    }

    // Build the prefix sums once, then answer each question with one subtraction.

    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        // print the sum of rounds l..r
    }
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int r, c;
    cin >> r >> c;
    vector<vector<int>> g(r, vector<int>(c));
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> g[i][j];
        }
    }

    // Print the r row sums on one line, then the c column sums on the next.

    return 0;
}

এরপর lesson 04 জানতে চায়, কখন vector ঠিক জিনিস না, আর ওর বদলে কোন প্রতিবেশীকে নেবে, সেটা বেছে দিতে আঁকে একটা chart আর একটা flowchart।