# Pembahasan Latihan 1
## A. Luas
### Pembahasan oleh Joshua James
Soal meminta anda mencari luas persegi panjang terbesar. Ini dapat dilakukan dengan mengiterasi semua persegi panjang dari $1$ hingga $N$ dan mencari nilai maksimal $P_i \times L_i$.
Kompleksitas waktu: $O(N)$
Kode:

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

int main(){
    int N; cin >> N;
    int ans = 0;
    for(int i = 0; i < N; i++){
        int a, b; cin >> a >> b;
        ans = max(ans, a*b);
    }
    cout << ans << endl;
}

## B. Menghitung Bola
### Pembahasan oleh Vincent Gaudeo Lie
Soal ini berfungsi sebagai pengenalan ke soal interaktif. Soal interaktif adalah soal dengan komunikasi dua sisi, artinya input tidak diberikan semuanya secara sekaligus dan kita akan membuat program yang berinteraksi bolak-balik dengan grader. Soal-soal interaktif lainnya bisa dicari di sini: https://tlx.toki.id/problems?page=1&tags=engine-interactive.
Untuk soal ini, kita cukup menyimpan jumlah bola saat ini. Jika jumlah bola saat ini benar, maka keluarkan BENAR. Jika salah, keluarkan SALAH. Soal ini sangat mudah.
Kompleksitas waktu: $O(Q)$

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

int main(){
    int Q; cin >> Q;
    int c = 1;
    for(int i = 0; i < Q; i++){
        int x; cin >> x;
        if(x == c) cout << "BENAR\n";
        else{
            cout << "SALAH\n";
            c = 0;
        }
        c++;
    }
}

## C. Ulang Tahun
### Pembahasan oleh Vincent Gaudeo Lie
Soal ini adalah soal yang ingin mengenalkan struktur data map.
Map adalah sebuah struktur data yang menyimpan pasangan kunci-hasil. Dengan kita memberikan kunci, map akan mengembalikan hasil yang cocok dengan kunci itu. Pastinya, satu kunci hanya bisa merujuk ke 1 hasil. Lebih lanjut bisa dibaca di https://www.programiz.com/cpp-programming/map.
Untuk mengakses sebuah hasil, atau *value*, kompleksitas waktunya adalah $O(log(T))$ dengan $T$ adalah banyaknya pasangan di dalam map itu.
Kompleksitas waktu total: $O((N+Q)logN)$
Kode:

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

int main(){
    int n, q; cin >> n >> q;
    map<string, string> mp;
    for(int i = 0; i < n; i++){
        string a, b; cin >> a >> b;
        mp[a] =  b;
    }
    for(int i = 0; i < q; i++){
        string x; cin >> x;
        cout << mp[x] << endl;
    }
}

## D. Pedang
### Pembahasan oleh Vincent Gaudeo Lie
Secara singkat, soal ini meminta berapa banyak $i (1 \le i \le N)$ berbeda sehingga tidak ada $j (1 \le i \le N)$ dengan $A_j \ge A_i$ dan $B_j \ge B_i$
Kita dapat mencari banyaknya pedang tidak berguna terlebih dahulu. Untuk memudahkan, kita bisa mengurutkan pedang-pedang yang ada berdasarkan $A_i$ dari kecil ke besar. Jika ada 2 pedang dengan $A_i$ yang sama, maka urutkan berdasarkan $B_i$ dari kecil ke besar.
Urutan $i$ awal tidak penting, kita hanya perlu mengetahui jumlahnya, tidak perlu tahu yang mana saja.
Setelah terurut, berarti semua $j$ dengan $j < i$ memiliki properti $A_j \le A_i$.
Jika ada $j$ dengan $j > i$ dan $B_j \ge B_i$, maka pedang $i$ tidak berguna.
Sehingga, untuk setiap $i$, kita perlu mencari maksimum $B_j$ untuk $i < j \le N$.
Hal ini bisa dilakukan dengan menyimpan suatu variabel untuk maksimumnya, dan melakukannya dari index $N-1$.
Kode:

int N; cin >> N;
vector<pair<int, int>> v(N);
for(int i = 0; i < N; i++){
    cin >> v[i].first >> v[i].second;
}
sort(v.begin(), v.end());
int mx = 0, ans = N;
for(int i = (int)v.size()-2; i >= 0; i--){
    mx = max(mx, v[i+1].second);
    if(v[i].second <= mx) ans--;
}
cout << ans << endl;

## E. Bermain Sudut
### Pembahasan oleh Joel Gunawan
Kita diminta untuk melakukan pengurutan titik-titik yang ada dengan menggunakan pertanyaan perbandingan yang diberikan. Oleh karena itu, kita dapat menggunakan algoritma sorting pada umumnya untuk melakukan ini, akan tetapi kita melakukan perbandingan dengan menggunakan pertanyaan interaktif.

Untuk melakukan perbandingan pengurutan, pertama pilih sebuah titik terlebih dahulu sebagai titik acuan (misalnya $1$) lalu melakukan perbandingan dengan format $1 \space X \space Y$, dari situ kita bisa tahu posisi $X$ relatif terhadap $Y$. Posisi $1$ di akhirnya akan berada di antara awal/akhir array yang dihasilkan dari perbandingan-perbandingan sebelumnya.

Untuk melakukan perbandingan dengan mudah dapat membuat custom comparator function dan dimasukkan dalam fungsi $\textit{sort}()$, contohnya ada di [sini](https://www.geeksforgeeks.org/how-to-sort-vector-using-custom-comparator-in-cpp/)

Perhatikan bahwa algoritma sorting biasa membutuhkan $O(N\textit{log}N)$ operasi. Oleh karena itu, algoritma ini akan menggunakan kurang lebih $N\textit{log}N$ operasi yang masih kurang dari $K$ (batas pertanyaan perbandingan).

## F. Pasangan Elok
### Pembahasan Oleh Matthew Hutama Pramana

Perhatikan bahwa untuk suatu bilangan $i$ dalam range $[L, R]$, nilai $|i − j| \equiv 0 \textit{ mod } K$ terpenuhi jika dan hanya jika $i \textit{ mod } K = j \textit{ mod } K$.

Definisikan $\textit{count}(m)$ sebagai banyaknya nilai $i$ dalam range $[L, R]$, yang memenuhi $i \textit{ mod } K = m$.

Sehingga banyaknya pasangan elok yang memenuhi $i \textit{ mod } K = j \textit{ mod } K = m$ adalah $\frac{\textit{count}(m)×(\textit{count}(m)−1)}{2}$

Untuk subtask 2 kita bisa mengiterasi semua $i$ dalam range $[L, R]$.

Perhatikan bahwa nilai $|\textit{count}(m1) − \textit{count}(m2)| \le 1$. Lebih detailnya, dalam range $[L, L + K − 1]$ bisa terdapat $i$ sehingga $count(a \textit{ mod } K) = \textit{count}(b \textit{ mod } K) + 1$ untuk semua $L \le a \le i, i + 1 \le b \le L + K − 1$. Lebih tepatnya nilai $i$, jika ada, pasti sama dengan $L + ((R − 1) \textit{ mod } K)$.

Jangan lupa perhatikan kasus ketika $\textit{count}(m1) = \textit{count}(m2)$ untuk $0 \le m1, m2 \le K − 1$, yaitu ketika $L \textit{ mod } K = (R − 1) \textit{ mod } K$.

## G. Djo, Djo, dan Toserba

Kita bisa menghitung secara terpisah jumlah uang yang akan dikeluarkan oleh Djowen dan Djonatan. Berikut adalah langkah-langkahnya:

#### Kasus Djowen
Djowen harus membeli $X$ barang dari toko A terlebih dahulu untuk mendapatkan hadiah yang ditawarkan. Strategi optimal yang dapat dilakukan Djowen adalah memprioritaskan pembelian $X$ barang tersebut dari toko A dengan nilai $A_i - B_i$ terbesar. Kemudian, ia bisa membeli sisa barang $N - X$ di toko mana pun yang menjualnya dengan harga lebih mahal.

Langkah-langkah:
1. Urutkan barang berdasarkan $A_i - B_i$ dari yang terbesar ke yang terkecil.
2. Pilih $X$ barang pertama dari urutan ini dan beli dari toko A.
3. Pilih sisa $N - X$ barang dan beli dari toko dengan harga yang lebih mahal (toko B).

#### Kasus Djonatan
Djonatan juga harus membeli $X$ barang terlebih dahulu dari toko A. Strategi optimal yang dapat ia lakukan adalah kebalikan dari strategi Djowen - Djonatan perlu memprioritaskan pembelian $X$ barang dari toko A dengan $A_i - B_i$ terkecil, lalu membeli sisa $N - X$ barang di toko mana pun yang menjualnya dengan harga lebih murah.

Langkah-langkah:
1. Urutkan barang berdasarkan $A_i - B_i$ dari yang terkecil ke yang terbesar.
2. Pilih $X$ barang pertama dari urutan ini dan beli dari toko A.
3. Pilih sisa $N - X$ barang dan beli dari toko dengan harga yang lebih murah (toko B).

#### Menghitung Selisih
Setelah kita memiliki jumlah uang yang akan dibelanjakan setiap orang, kita perlu mencari selisih dari keduanya untuk memperoleh jawaban terakhir kita.

Kompleksitas waktu: $O(N \log N)$

## H. Topik
### Pembahasan oleh Joel Gunawan

Perhatikan bahwa urutan penyelesaian modul tidak penting, melainkan seharusnya lebih baik kita menyelesaikan semua modul selama kita bisa menyelesaikan modul.

Kita dapat membuat $K$ vektor, sebut saja $A$. Vektor ke $i$ menyipman pengetahuan yang dibutuhkan untuk menyelesaikan tiap modul untuk topik ke $i$.

Setelah itu, kita dapat membuat sebuah array berukuran $N$ yang berisi angka, sebut saja $B$. Angka ke-$i$ menandakan banyak topik yang sudah terpenuhi kebutuhan pengetahuannya untuk menyelesaikan modul ke-$i$.

Pertama, kita urutkan setiap vektor secara tidak menurun, lalu selama ada modul yang dapat diselesaikan, maka kita akan mengerjakan modul tersebut. Untuk mengetahui apakah sebuah modul dapat diselesaikan, kita dapat merujuk ke array $B$ yang menyimpan jumlah topik yang pengetahuannya sudah cukup.

Setelah menyelesaikan sebuah modul, kita dapat memperbarui nilai array $B$ dengan mencari modul mana saja yang tingkat pengetahuannya menjadi terpenuhi setelah penambahan pengetahuan dari $A$.

## I. Freedom Dive
### Pembahasan oleh Joel Gunawan
Pernyataan "bilangan terbesar yang habis membagi setiap kekuatan prajurit yang tersisa" berarti FPB/GCD dari sisa kekuatan prajurit.

Solusi $𝑘=1$
Coba serang masing-masing prajurit lalu cari GCD sisa kekuatan terbesar.

Untuk mencari GCD sisa dengan cepat, kita bisa menggunakan prefix dan suffix GCD array. Simpan sebuah prefix GCD array, misalnya
$𝑝𝑟𝑒𝑓_𝑖=gcd(a_0,a_1,...a_i)$. Simpan juga sebuah suffix GCD array, misalnya $𝑠𝑢𝑓_𝑖=gcd(a_i,a_{i+1},...,a_n)$. Ketika kita mencoba menyerang prajurit ke-$𝑖$, GCD sisanya adalah $𝑔𝑐𝑑(𝑝𝑟𝑒𝑓_{𝑖−1},𝑠𝑢𝑓_{𝑖+1})$.

Kompleksitas waktu: $𝑂(𝑁𝑙𝑜𝑔𝐴_𝑖)$

Solusi $𝑘=2$
Coba setiap kemungkinan pasangan untuk diserang, sehingga ada $𝑁∗(𝑁−1)/2$ percobaan. Cari GCD sisa kekuatan terbesar dari semua percobaan.

Kita bisa memanfaatkan prefix dan suffix GCD array. Misalnya pasangan yang kita coba adalah $𝑖$ dan $𝑗$ dengan $𝑖<𝑗$, GCD sisanya adalah $𝑔𝑐𝑑(𝑝𝑟𝑒𝑓_{𝑖−1},𝑎_{𝑖+1},𝑎_{𝑖+2},...,𝑎_{𝑗−1},𝑠𝑢𝑓𝑓_{𝑗+1})$. Tantangan kita adalah mencari $𝑔𝑐𝑑(𝑎_{𝑖+1},𝑎_{𝑖+2},...,𝑎_{𝑗−1})$ dengan cepat.

Jika kita mencoba-coba pasangan dengan melakukan iterasi secara berurutan, kita bisa mencari nilai $𝑔𝑐𝑑(𝑎_{𝑖+1},𝑎_{𝑖+2},...,𝑎_{𝑗−1})$ sembari melakukan iterasi.

Anggap kita sudah selesai mencoba $𝑖$ dan $𝑗$, sehingga sudah mengetahui nilai GCD dari rentang $[𝑖+1,𝑗−1]$. Jika selanjutnya kita mencoba $𝑖$ dan $𝑗+1$, kita perlu mencari GCD dari rentang $[𝑖+1,𝑗]$. Daripada melakukan iterasi lagi dari $𝑖+1$ sampai $𝑗$, kita bisa memanfaatkan GCD rentang $[𝑖+1,𝑗−1]$ yang sudah diketahui. Ingat bahwa $𝑔𝑐𝑑(𝑎_{𝑖+1},𝑎_{𝑖+2},...,𝑎_𝑗)=𝑔𝑐𝑑(𝑔𝑐𝑑(𝑎_{𝑖+1},𝑎_{𝑖+2},...,𝑎_{𝑗−1}),𝑎_𝑗)$.

Kompleksitas waktu: $𝑂(𝑁^{2}𝑙𝑜𝑔𝐴𝑖)$
## J. Dihantam Pandemi
### Pembahasan oleh Vincent Gaudeo Lie
Untuk mempermudah penjelasan, anggap $dist(x,y)$ sebagai rute terpendek dari $x$ ke $y$.
Bila soal kita sederhanakan, kita akan mendapat seperti ini:
Diberikan sebuah undirected graph dan dua titik $A$ dan $B$.
Untuk semua titik $i$, berapa kemungkinan shortest path (rute terpendek) dari $A$ ke $B$ melewati $i$?

Banyaknya rute terpendek berbeda bisa mencapai $2^{33333}$ jika konfigurasinya seperti ini:
Namun, kita dibantu oleh salah satu batasan soal ini, yaitu banyaknya rute terpendek berbeda dari $A$ ke $B$ tidak melebihi $10^{6}$.
Hal ini mempermudah kita, karena mengartikan bahwa mungkin bagi kita untuk menghitung berapa banyak rute terpendek berbeda yang mungkin.

Secara logika, apabila $[dist(A,B) \ne dist(A,i) + dist(i,B)]$, maka tidak ada rute terpendek yang melewati $i$, dan kemungkinannya adalah $0$.
Observasi lain adalah bahwa jumlah rute terpendek berbeda dari $A$ ke $B$ yang melewati $i$ adalah banyaknya rute berbeda dari $A$ ke $i$ dikali dengan banyaknya rute berbeda dari $i$ ke $B$.

Berarti, tugas kita sekarang adalah:
Untuk setiap $i$ dimana $dist(A,B) = dist(A,i) + dist(i,B)$, cari berapa banyak rute berbeda dari $A$ ke $i$ sepanjang $dist(A,i)$ dan berapa banyak rute berbeda dari $i$ ke $B$ sepanjang $dist(i,B)$.

Untuk mencari jarak dari $A$ ke semua titik lain dan jarak $B$ ke semua titik lain, kita cukup menggunakan algoritme dijkstra.
Bagi yang belum mengerti algoritme dijkstra, bisa dipelajari di buku pemrograman kompetitif dasar halaman 128. Tautan untuk buku tersebut adalah https://osn.toki.id/arsip/download-pkd.
Ada pula laman berikut bagi anda yang lebih nyaman membaca bahasa inggris: https://cp-algorithms.com/graph/dijkstra.html.

Setelah memperoleh jarak-jarak yang kita butuhkan, kita akan mencari banyaknya rute terpendek berbeda menggunakan dynamic programming.
Definisikan $f(i)$ sebagai banyaknya rute dari $A$ ke $i$ sepanjang $dist(A,i)$.
Agar memudahkan, definisikan juga $f(A)$ sebagai $1$.
Nilai $f(i)$ bisa dicari dengan menjumlahkan semua $f(x)$ untuk setiap $x$ yang memenuhi syarat berikut:
1. $dist(A,i) - dist(A,x) = dist(i,x)$.
2. Ada *edge* atau koneksi yang menghubungan $i$ dengan $x$.

Lakukan pula hal yang sama untuk $B$.
Selesai sudah.

Kode bisa dilihat dibawah ini. Namun, sangat dianjurkan untuk mengerjakan dan menulis kode sendiri tanpa melihat kode dibawah ini untuk latihan. Bila merasa sangat butuh, baru lihat kode ini.

#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int nx = 1e5 + 1;
int N, M, A, B;
vector<long long> way(nx), way2(nx);
vector<bool> done(nx, 0), done2(nx, 0);
long long f(int x, vector<int> &dist, vector<vector<pii>> &graph){
    if(x == B) return 1;
    if(done[x]) return way[x];
    long long t = 0;
    for(pii p: graph[x]){
        if(dist[x] - dist[p.fi] == p.se) t += f(p.fi, dist, graph);
    }
    done[x] = 1;
    return way[x] = t;
}
long long g(int x, vector<int> &dist2, vector<vector<pii>> &graph){
    if(x == A) return 1;
    if(done2[x]) return way2[x];
    long long t = 0;
    for(pii p: graph[x]){
        if(dist2[x] - dist2[p.fi] == p.se) t += g(p.fi, dist2, graph);
    }
    done2[x] = 1;
    return way2[x] = t;
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M >> A >> B;
    B--, A--;
    way[B] = 1, way2[A] = 1;
    vector<vector<pii>> graph(N);
    for(int i = 0; i < M; i++){
        int u, v, w; cin >> u >> v >> w;
        u--, v--;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, B});
    bool vis[N];
    vector<int> dist(N, -1), dist2(N, -1);
    memset(vis, 0, sizeof(vis));
    while(!pq.empty()){
        pii now = pq.top();
        pq.pop();
        if(vis[now.se]) continue;
        vis[now.se] = true;
        dist[now.se] = now.fi;
        for(pii p: graph[now.se]){
            if(!vis[p.fi]) pq.push({now.fi + p.se, p.fi});
        }
    }
    priority_queue<pii, vector<pii>, greater<pii>> fa;
    fa.push({0, A});
    memset(vis, 0, sizeof(vis));
    while(!fa.empty()){
        pii now = fa.top();
        fa.pop();
        if(vis[now.se]) continue;
        vis[now.se] = true;
        dist2[now.se] = now.fi;
        for(pii p: graph[now.se]){
            if(!vis[p.fi]) fa.push({now.fi + p.se, p.fi});
        }
    }
    bool used[N];
    for(int i = 0; i < N; i++){
        if(dist[i] == -1){
            used[i] = 0;
            continue;
        }
        if(dist[i] + dist2[i] != dist[A]){
            used[i] = 0;
        }
        else used[i] = 1;
    }
    f(A, dist, graph);
    g(B, dist2, graph);
    cout << fixed << setprecision(10);
    long double master = way[A] * way2[A];
    for(int i = 0; i < N; i++){
        if(!used[i]){
            cout << "0\n";
            continue;
        }
        long double now = way[i] * way2[i];
        now *= 2.0;
        cout << now / master << endl;
    }
}