Suhendry’s Blog

Untuk menyelesaikan problem ini, terlebih dahulu kita harus mengetahui cara menghitung luas sebuah regular polygon. Dengan sedikit analisa, kita dapat mengetahui bahwa regular polygon bersisi n dapat dibentuk dari n segitiga sama sisi yang identik.

Untuk menghitung luas segitiga, kita bisa menggunakan rumus:

Sehingga, luas regular polygon dengan n-sisi dapat dihitung dengan:

Dengan demikian kita bisa menghitung luas daerah delta dengan menselisihkan luas lingkaran dengan luas polygon tersebut.

Setelah kita mengetahui cara menghitung luas regular polygon, langkah berikutnya adalah melakukan bruteforce attack mulai dari n = 3 hingga n = 1000. Banyak peserta yang melakukan kesalahan dengan memulai bruteforce dengan n = 0 atau 1. Ini adalah suatu kesalahan, karena minimal tiga titik diperlukan untuk membentuk sebuah polygon.

const double pi = 2 * acos(0.0);
double circle = pi * r * r;
for ( int n = 3; n <= 1000; n++ ) {
    double polygon = 0.5 * r * r * sin(2.0*pi/n) * n;
    double delta = circle - polygon;
    if ( delta <= p ) return n;
}

Bagaimana jika constrain input n diperbesar hingga 10^9 atau lebih? Metode binary-search bisa mengatasinya dalam O(log(n))

Problem ini bisa diselesaikan dengan dua pendekatan: Dynamic Programming atau Greedy Algorithm.

Solusi Dynamic Programming:

DP untuk problem ini menggunakan tabel dua dimensi: posisi monyet (index pohon), dan jumlah pisang yang dimiliki monyet.

Kompleksitas: O(N.B), dimana N = jumlah pohon, B = jumlah pisang yang bisa dibawa.

int dp(int banana, int idx) {
    if ( memo[banana][idx] != -1 ) return memo[banana][idx];
    int &ret = memo[banana][idx];
    ret = infinite;
    int dist = tree[idx+1].pos - tree[idx].pos;
    int eat = tree[idx].banana;
    if ( banana - dist >= 0 )
        ret = min( ret, dp(banana-dist,idx+1) );
    if ( banana - dist + eat >= 0 )
        ret = min( ret, 1 + dp(banana-dist+eat,idx+1) );
    return ret;
}

Solusi Greedy:

Untuk dapat memahami property greedy di problem ini, mari kita bayangkan situasi seperti ini: misalnya terdapat dua pohon pada lokasi berbeda dengan jumlah pisang yang sama, dan asumsikan si monyet bisa mencapai kedua lokasi tersebut. Pada keadaan ini, mengambil pisang dari pohon-1 dan mengambil pisang dari pohon-2 akan menghasilkan jarak terjauh yang bisa ditempuh monyet yang sama besar. Dengan demikian apabila salah satu pohon tersebut memiliki lebih banyak pisang, maka jarak terjauh yang bisa dicapai monyet juga bertambah.

Dari properti greedy di atas, kita bisa mensimulasikan perjalanan si monyet ke tempat tujuan. Setiap pohon pisang yang dijumpai, kita simpan informasi jumlah pisang potensial yang bisa diambil ke dalam struktur data priority queue. Ketika kita kehabisan pisang di dalam perjalanan, ‘re-charge’ si monyet dengan pisang potensi yang sudah kita kumpulkan mulai dari terbesar hingga si monyet bisa kembali berjalan.

Kompleksitas: O(N.log(N)), dimana N adalah jumlah pohon pisang.

int ans = 0;
for ( int i = 0; i < tree.size(); i++ ) {
    banana -= tree[i].pos - tree[i-1].pos;
    while ( banana < 0 && !pq.empty() ) {
        banana += pq.top();
        pq.pop();
        ans++;
    }
    if ( banana < 0 ) {
        ans = -1;
        break;
    }
    pq.push(tree[i].banana);
}

Problem ini bisa direpresentasikan ke dalam graph (all-pair shortest path), sehingga bisa diselesaikan dengan Floyd-Warshall’s Algorithm. Tinggal mengubah pencarian shortest path dengan pencarian most-profit (highest rate).

Agak sulit untuk mendapatkan ACCEPTED di problem ini karena kita bisa terjebak precision error.

Ini akan saya ringkas maksud soalnya dalam bahasa indo, mudah2an dimengerti

Ada 11 pemain, mereka bisa saling oper bola. Bola pertama ada di kiper. Ke 11 pemain bisa tembak ke gawang musuh kapan saja kalau mereka
sedang pegang bola. Kamu disuruh cari berapa probability setiap orang mencetak gol. That’s it.

Jawabannya adalah tinggal di-bruteforce semua kemugkinan operan diantara 10 pemain tersebut. Kipernya selalu pegang bola pertama, ke 10 sisanya di-permutasi (cuma 10 faktorial). Untuk permutasi ke-i, kita dapat sequence operan dari kiper ke 10 pemain lainnya. Dari situ tinggal di cek probability orang ke-j dalam sequence tersebut menendang ke gawang, berapa probability gol nya? Update probability gol untuk orang tersebut. Setelah ke 10 faktorial sequences dicoba, kamu tahu kemungkinan terbaik setiap orang untuk mencetak gol, tinggal di-print.

Sort-nya kemungkinan bisa ada precision error, tapi kalau ada pun, juri-juri akan berbaik hati meng-Accepted solusinya. Kalau mau menghindari precision error, kamu harus bikin tipe data BigInteger, lalu sort hanya pakai integer Way too complex.

Ada yang nanya matrix 11×11 itu isinya apaan?

Jawabannya:

Anggep matrix 11×11 itu adalah m, maka m[i][j] adalah persentasi sukses pemain i oper bola ke pemain j.

Kalo sequence operannya seperti ini:

orang 1 oper ke orang 4 lalu oper ke orang 7, lalu tembak

maka probability orang 7 nge gol itu :

m[1][4] * m[4][7] * shoot[7]

shoot[x] itu adalah persentasi orang ke-x nge-cetak gol kalo dia menembak.

Seharusnya kalo ada yang kurang jelas, bisa minta clarification ke juri. Dengan senang hati saya akan menjelaskan saat lomba

Untuk menyelesaikan soal ini, jangan bekerja dengan nilai x^y sekaligus karena hal ini akan menyebabkan TIME LIMIT EXCEEDED. Pertama kita cari terlebih dahulu faktor-faktor prima yang menjadi komponen bilangan x. Setelah itu kita kalikan pangkat dari masing-masing faktor tersebut dengan y.

contoh: x = 72, y = 5

x = 2^3 . 3^2

x^y = (2^3 . 3^2)^5 = 2^15 . 3^10

Bilangan yang habis membagi x^y pasti merupakan bilangan yang faktor-faktornya adalah subset dari faktor x^y. Dengan demikian yang perlu kita cari hanyalah ada berapa banyak perkalian faktor prima x^y yang unique. Masalah ini cukup diselesaikan dengan mengalikan kombinasi pangkat dari masing-masing faktor prima.

pada contoh: ans = (15+1) x (10+1) = 176

{2^0 . 3^0}, {2^0 . 3^1}, {2^0 . 3^2}, …, {2^15 . 3^9}, {2^15 . 3^10}.

for ( int i = 2; i*i <= x; i++ ) {
    if ( n % i == 0 ) {
        int p = 0;
        while ( n != 0 && n % i == 0 ) {
            p++;
            n /= i;
        }
        ans *= (p*y + 1);
    }
}

Beberapa peserta salah ketika diminta untuk mencetak nilai x^y karena tidak menggunakan tipe data integer 64 bit. Nilai maksimal 1000^6 itu setara dengan 10^18 atau 1000000000000000000.

Problem ini tidak terlalu sulit dan bisa diselesaikan dengan sedikit analisa.

Kompleksitas O(N^2) sudah cukup untuk menyelesaikan problem ini. Jika ada yang tertarik mempelajari algoritma O(N.log(N)) nya, silahkan coba pelajari k-th elements dari misof.

void insert(int x) { for (int i=0; i<17; i++) { tree[i][x]++; x/=2; } }
void erase(int x) { for (int i=0; i<17; i++) { tree[i][x]--; x/=2; } }
int kThElement(int k) {
    int a=0, b=16;
    while (b--) { a*=2; if (tree[b][a]<k) k-=tree[b][a++]; }
    return a;
}

Problem ini bisa diselesaikan dengan menggunakan DP 3 dimensi: jumlah L tersisa, jumlah R tersisa, toogle giliran L/R. Dari setiap state, pilihannya hanya ada dua: tetap pada jalur (mobil di jalur lawan membunyikan klakson), atau pindah jalur (semua mobil + mobil di jalur ini membunyikan klakson). Jumlah klakson yang terjadi pada saat jumlah mobil yang tersisa adalah L atau R harus diprecompute terlebih dahulu agar kita tidak perlu melakukan iterasi lagi ketika menghitungnya di dalam DP. Jika tidak, kompleksitas algoritmanya akan menjadi O(N^3) yang pasti menghasilkan TIME LIMIT EXCEEDED.

Kompleksitas: O(N^2)

LL dp(int L, int R, bool toogle) {
    if ( L == 0 && R == 0 ) return 0;
    if ( flag[L][R][toogle] ) return memo[L][R][toogle];
    flag[L][R][toogle] = true;
    LL &ret = memo[L][R][toogle] = inf;
    if ( toogle ) {
        if ( L-1 >= 0 ) ret = min(ret,dp(L-1,R,toogle)+accR[R]);
        if ( R-1 >= 0 ) ret = min(ret,dp(L,R-1,!toogle)+accR[R]+accL[L]+accL[L]);
    }
    else {
        if ( L-1 >= 0 ) ret = min(ret,dp(L-1,R,!toogle)+accR[R]+accL[L]+accR[R]);
        if ( R-1 >= 0 ) ret = min(ret,dp(L,R-1,toogle)+accL[L]);
    }
    return ret;
}

Ini adalah seri kedua dari ‘novel’ Panda Land karya Evan Leonardy Di seri pertama (INC 2007), peserta dipusingkan dengan bagaimana cara menghitung banyaknya digit pada bilangan romawi dari 1 s/d n. Sedangkan di seri kedua ini, kita diminta untuk melakukan modifikasi pada simulasi Hanoi Tower

Problem ini bisa diselesaikan dengan cara rekursif yang mirip dengan cara penyelesaian Hanoi Tower. Bedanya, di Hanoi Tower kita sudah mengetahui bahwa batu terbesar pasti berada di tumpukan paling bawah menara awal. Sedangkan pada Panda Tower, kita harus terlebih dahulu mencari di altar mana batu paling besar itu berada (cek di semua altar).

Dengan pembuktian sederhana, jumlah langkah yang diperlukan untuk memindahkan semua batu ke salah satu altar tidak akan lebih dari 2^n - 1. Artinya, impossible ada jawaban yang “impossible”

Ini adalah soal paling mudah di kontes kali ini. Seharusnya peserta tidak kesulitan untuk mendapatkan ACCEPTED di problem ini. Beberapa peserta sepertinya terjebak dengan PRESENTATION ERROR karena kelebihan mencetak spasi di akhir output.