#include <bits/stdc++.h>
using namespace std;
int main() {
// Complexity - Big O
// Seberapa banyak operasi yg dilakukan/runtime berubah
// saat ada perubahan input
// Rule of Thumb: 10^8 op = 1s
/*
int n, data[1000001]; // O(1)
cin >> n; // O(1)
for(int i = 0; i < n; i++) // O(n)
cin >> data[i];
for(int i = 0; i < n; i++) // O(n^2)
for(int j = 1; j < n; j++)
if(data[j] < data[j-1]) {
int tmp = data[j];
data[j] = data[j-1];
data[j-1] = tmp;
}
*/
// Big O = O(n^2)
/*
O(n)
n = 10 -> rt = 1ms
n = 100 -> rt = 10ms
n = 1000 -> rt = 100ms
..
O(n^2)
n = 10 -> rt = 100ms
n = 100 -> rt = 10000ms
n = 1000000 -> rt = 10^12ms
*/
// 4 Paradigm overview
/*
int data = {10, 7, 3, 5, 8, 2, 9}, n = 7;
// ^ ^ ^ ^
// 3, 5, 8, 9
for(int i = 0; i < n; i++)
if(data[i] > maks)
maks = data[i];
// n <= 200000, data[i] <= 10^6
// 1. Cari bilangan terbesar & terkecil dari array data. O(n)
// 2. Cari bilangan terbesar urutan ke-k dari array data. (k<=n)
// Pendekatan pertama: sort O(n^2) -> Time Limit Exceeded
// Pendekatan kedua: Cari bil terbesar, lalu hapus.
// Cari bil kedua terbesar, lalu hapus.
// Ulangi sampai bil ke-(k-1) terbesar & hapus.
// Cari bil ke-k terbesar. -> O(n*k) = O(n^2)
for(int i = 0; i < k; i++)
for(int j = 0; j < n; j++)
// Yang bener: sort O(n log n)
// 3. Cari selisih terbesar dalam array data.
// Pendekatan complete search -> O(n^2) -> TLE
// Greedy -> O(n)
// 4. Cari LIS = Longest Increasing Subsequence di array data.
// Dynamic Programming
*/
// Complete Search
// Iterative = loop
// Recursive = fungsi rekursif
// Pruning -> tidak melanjutkan proses yang pasti gagal
/* 8 ratu di papan catur -> 8 Queens problem
o..o..o.
.o.o.o..
..ooo...
oooQoooo
..ooo...
.o.o.o..
o..o..o.
...o...o
1.......
..2.....
> ....3...
........
........
........
........
........
8^7
*/
// Divide & Conquer -> harus terurut
// linear search -> per langkah -1 -> O(n)
// binary search -> per langkah /2 -> O(log n)
// search space
// {1, 1, 2, 2, 2, 4, 5, 6, 6, 9, 10, 13, 17, 22, 23}
// |--------------------|-------------------------|
// |----------|-----------|
// |--|---|
// |
// dalam x langkah -> search space berkurang 2^x kali
// ukurang search space = n -> banyak langkah = log2 n = log n
// cari 10
/*
int data[] = {1, 1, 2, 2, 2, 4, 5, 6, 6, 9, 10, 13, 17, 22, 23}, n = 15;
// i1 <= i2 -> data[i1] <= data[i2]
int cari = 10;
// linear search
for(int i = 0; i < n; i++)
if(data[i] == cari)
cout << cari << " ditemukan di index: " << i << endl;
// binary search
int lo = 0, hi = n-1, mid;
while(lo < hi) {
mid = (lo+hi)/2;
if(data[mid] > cari)
hi = mid-1;
else if(data[mid] < cari)
lo = mid+1;
else
lo = hi = mid;
}
cout << cari << " ditemukan di index: " << lo << endl;
*/
// Bisection method / Binary Search The Answer
// 0 <= x < PI/2, sin(x) = increasing
// x1 < x2 -> sin(x1) < sin(x2)
double PI = acos(-1);
double y = 0.75;
double lo = 0, hi = PI/2, mid;
while(hi-lo > 1e-4) {
mid = (lo+hi)/2;
cout << lo << " " << mid << " " << hi << endl;
if(sin(mid) > y)
hi = mid;
else if(sin(mid) < y)
lo = mid;
}
cout << "arcsin(" << y << ") = " << lo << endl;
// buat arcsin(y)
// Dynamic Programming
// - banyak subsoal yang overlap -> jangan dihitung berulang2
// - pakai memo -> memo[200][20] -> memoization
// top down vs bottom up
// classical
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpIHsKCS8vIENvbXBsZXhpdHkgLSBCaWcgTwoJLy8gU2ViZXJhcGEgYmFueWFrIG9wZXJhc2kgeWcgZGlsYWt1a2FuL3J1bnRpbWUgYmVydWJhaAoJLy8gc2FhdCBhZGEgcGVydWJhaGFuIGlucHV0CgkvLyBSdWxlIG9mIFRodW1iOiAxMF44IG9wID0gMXMKCS8qCglpbnQgbiwgZGF0YVsxMDAwMDAxXTsJCQkJCS8vIE8oMSkKCWNpbiA+PiBuOwkJCQkJCQkJLy8gTygxKQoJZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykJCQkJLy8gTyhuKQoJCWNpbiA+PiBkYXRhW2ldOwoJZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykJCQkJLy8gTyhuXjIpCgkJZm9yKGludCBqID0gMTsgaiA8IG47IGorKykKCQkJaWYoZGF0YVtqXSA8IGRhdGFbai0xXSkgewoJCQkJaW50IHRtcCA9IGRhdGFbal07CgkJCQlkYXRhW2pdID0gZGF0YVtqLTFdOwoJCQkJZGF0YVtqLTFdID0gdG1wOwoJCQl9CgkqLwoJLy8gQmlnIE8gPSBPKG5eMikKCS8qCglPKG4pCgluID0gMTAgLT4gcnQgPSAxbXMKCW4gPSAxMDAgLT4gcnQgPSAxMG1zCgluID0gMTAwMCAtPiBydCA9IDEwMG1zCgkuLgoJCglPKG5eMikKCW4gPSAxMCAtPiBydCA9IDEwMG1zCgluID0gMTAwIC0+IHJ0ID0gMTAwMDBtcwoJbiA9IDEwMDAwMDAgLT4gcnQgPSAxMF4xMm1zCgkqLwoJCgkvLyA0IFBhcmFkaWdtIG92ZXJ2aWV3CgkvKgoJaW50IGRhdGEgPSB7MTAsIDcsIDMsIDUsIDgsIDIsIDl9LCBuID0gNzsKCS8vICAgICAgICAgICAgICAgICBeICBeICBeICAgICBeCgkvLyAzLCA1LCA4LCA5Cglmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKQoJCWlmKGRhdGFbaV0gPiBtYWtzKQoJCQltYWtzID0gZGF0YVtpXTsKCS8vIG4gPD0gMjAwMDAwLCBkYXRhW2ldIDw9IDEwXjYKCQoJLy8gMS4gQ2FyaSBiaWxhbmdhbiB0ZXJiZXNhciAmIHRlcmtlY2lsIGRhcmkgYXJyYXkgZGF0YS4gTyhuKQoJLy8gMi4gQ2FyaSBiaWxhbmdhbiB0ZXJiZXNhciB1cnV0YW4ga2UtayBkYXJpIGFycmF5IGRhdGEuIChrPD1uKQoJLy8gUGVuZGVrYXRhbiBwZXJ0YW1hOiBzb3J0IE8obl4yKSAtPiBUaW1lIExpbWl0IEV4Y2VlZGVkCgkvLyBQZW5kZWthdGFuIGtlZHVhOiBDYXJpIGJpbCB0ZXJiZXNhciwgbGFsdSBoYXB1cy4KCS8vICAgICAgICAgICAgICAgICAgIENhcmkgYmlsIGtlZHVhIHRlcmJlc2FyLCBsYWx1IGhhcHVzLgoJLy8gICAgICAgICAgICAgICAgICAgVWxhbmdpIHNhbXBhaSBiaWwga2UtKGstMSkgdGVyYmVzYXIgJiBoYXB1cy4KCS8vICAgICAgICAgICAgICAgICAgIENhcmkgYmlsIGtlLWsgdGVyYmVzYXIuIC0+IE8obiprKSA9IE8obl4yKQoJZm9yKGludCBpID0gMDsgaSA8IGs7IGkrKykKCQlmb3IoaW50IGogPSAwOyBqIDwgbjsgaisrKQoJLy8gWWFuZyBiZW5lcjogc29ydCBPKG4gbG9nIG4pCgkvLyAzLiBDYXJpIHNlbGlzaWggdGVyYmVzYXIgZGFsYW0gYXJyYXkgZGF0YS4KCS8vIFBlbmRla2F0YW4gY29tcGxldGUgc2VhcmNoIC0+IE8obl4yKSAtPiBUTEUKCS8vIEdyZWVkeSAtPiBPKG4pCgkvLyA0LiBDYXJpIExJUyA9IExvbmdlc3QgSW5jcmVhc2luZyBTdWJzZXF1ZW5jZSBkaSBhcnJheSBkYXRhLgoJLy8gRHluYW1pYyBQcm9ncmFtbWluZwoJKi8KCQoJLy8gQ29tcGxldGUgU2VhcmNoCgkvLyBJdGVyYXRpdmUgPSBsb29wCgkvLyBSZWN1cnNpdmUgPSBmdW5nc2kgcmVrdXJzaWYKCS8vIFBydW5pbmcgLT4gdGlkYWsgbWVsYW5qdXRrYW4gcHJvc2VzIHlhbmcgcGFzdGkgZ2FnYWwKCS8qIDggcmF0dSBkaSBwYXBhbiBjYXR1ciAtPiA4IFF1ZWVucyBwcm9ibGVtCglvLi5vLi5vLgoJLm8uby5vLi4KCS4ub29vLi4uCglvb29Rb29vbwoJLi5vb28uLi4KCS5vLm8uby4uCglvLi5vLi5vLgoJLi4uby4uLm8KCQoJMS4uLi4uLi4KCS4uMi4uLi4uCj4JLi4uLjMuLi4KCS4uLi4uLi4uCgkuLi4uLi4uLgoJLi4uLi4uLi4KCS4uLi4uLi4uCgkuLi4uLi4uLgoJOF43CgkqLwoJCgkvLyBEaXZpZGUgJiBDb25xdWVyIC0+IGhhcnVzIHRlcnVydXQKCS8vIGxpbmVhciBzZWFyY2ggLT4gcGVyIGxhbmdrYWggLTEgLT4gTyhuKQoJLy8gYmluYXJ5IHNlYXJjaCAtPiBwZXIgbGFuZ2thaCAvMiAtPiBPKGxvZyBuKQoJCgkvLyBzZWFyY2ggc3BhY2UKCS8vIHsxLCAxLCAyLCAyLCAyLCA0LCA1LCA2LCA2LCA5LCAxMCwgMTMsIDE3LCAyMiwgMjN9CgkvLyAgfC0tLS0tLS0tLS0tLS0tLS0tLS0tfC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS18CgkvLyAgICAgICAgICAgICAgICAgICAgICAgICAgfC0tLS0tLS0tLS18LS0tLS0tLS0tLS18CgkvLyAgICAgICAgICAgICAgICAgICAgICAgICAgfC0tfC0tLXwKCS8vICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgfAoJLy8gZGFsYW0geCBsYW5na2FoIC0+IHNlYXJjaCBzcGFjZSBiZXJrdXJhbmcgMl54IGthbGkKCS8vIHVrdXJhbmcgc2VhcmNoIHNwYWNlID0gbiAtPiBiYW55YWsgbGFuZ2thaCA9IGxvZzIgbiA9IGxvZyBuCgkvLyBjYXJpIDEwCgkvKgoJaW50IGRhdGFbXSA9IHsxLCAxLCAyLCAyLCAyLCA0LCA1LCA2LCA2LCA5LCAxMCwgMTMsIDE3LCAyMiwgMjN9LCBuID0gMTU7CgkvLyBpMSA8PSBpMiAtPiBkYXRhW2kxXSA8PSBkYXRhW2kyXQoJaW50IGNhcmkgPSAxMDsKCS8vIGxpbmVhciBzZWFyY2gKCWZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspCgkJaWYoZGF0YVtpXSA9PSBjYXJpKQoJCQljb3V0IDw8IGNhcmkgPDwgIiBkaXRlbXVrYW4gZGkgaW5kZXg6ICIgPDwgaSA8PCBlbmRsOwoJLy8gYmluYXJ5IHNlYXJjaAoJaW50IGxvID0gMCwgaGkgPSBuLTEsIG1pZDsKCXdoaWxlKGxvIDwgaGkpIHsKCQltaWQgPSAobG8raGkpLzI7CgkJaWYoZGF0YVttaWRdID4gY2FyaSkKCQkJaGkgPSBtaWQtMTsKCQllbHNlIGlmKGRhdGFbbWlkXSA8IGNhcmkpCgkJCWxvID0gbWlkKzE7CgkJZWxzZQoJCQlsbyA9IGhpID0gbWlkOwoJfQoJY291dCA8PCBjYXJpIDw8ICIgZGl0ZW11a2FuIGRpIGluZGV4OiAiIDw8IGxvIDw8IGVuZGw7CgkqLwoJCgkvLyBCaXNlY3Rpb24gbWV0aG9kIC8gQmluYXJ5IFNlYXJjaCBUaGUgQW5zd2VyCgkvLyAwIDw9IHggPCBQSS8yLCBzaW4oeCkgPSBpbmNyZWFzaW5nCgkvLyB4MSA8IHgyIC0+IHNpbih4MSkgPCBzaW4oeDIpCglkb3VibGUgUEkgPSBhY29zKC0xKTsKCQoJZG91YmxlIHkgPSAwLjc1OwoJZG91YmxlIGxvID0gMCwgaGkgPSBQSS8yLCBtaWQ7Cgl3aGlsZShoaS1sbyA+IDFlLTQpIHsKCQltaWQgPSAobG8raGkpLzI7CgkJY291dCA8PCBsbyA8PCAiICIgPDwgbWlkIDw8ICIgIiA8PCBoaSA8PCBlbmRsOwoJCWlmKHNpbihtaWQpID4geSkKCQkJaGkgPSBtaWQ7CgkJZWxzZSBpZihzaW4obWlkKSA8IHkpCgkJCWxvID0gbWlkOwoJfQoJY291dCA8PCAiYXJjc2luKCIgPDwgeSA8PCAiKSA9ICIgPDwgbG8gPDwgZW5kbDsKCS8vIGJ1YXQgYXJjc2luKHkpCgkKCS8vIER5bmFtaWMgUHJvZ3JhbW1pbmcKCS8vIC0gYmFueWFrIHN1YnNvYWwgeWFuZyBvdmVybGFwIC0+IGphbmdhbiBkaWhpdHVuZyBiZXJ1bGFuZzIKCS8vIC0gcGFrYWkgbWVtbyAtPiBtZW1vWzIwMF1bMjBdIC0+IG1lbW9pemF0aW9uCgkvLyB0b3AgZG93biB2cyBib3R0b20gdXAKCS8vIGNsYXNzaWNhbAoJcmV0dXJuIDA7Cn0=