Editorial Codeforces 1516C

C. Baby Ehab Partitions Again

Diberikan sebuah array $A$ berukuran $n$, partisi sedemikian sehingga tidak ada subsequence yang jumlahnya $\frac{\sum_{a \in A} a}{2}$.

Observasinya lumayan unik, awalnya aku kira tadi pertama setelah mengecek dengan subset sum, bisa langsung dapet jawabannya, karena cuma tepat satu yang pasti di remove.

Ternyata ada counter

5
2 3 4 5 6

Partisi $[2, 3, 5]$ sebelum di remove bisa diganti dengan partisi $[3, 6]$ setelah $2$ di remove, artinya kita tidak bisa membuang yang paling kecil.

Perhatikan bahwa saat sebuah bilangan ganjil di-remove, maka tidak akan ada cara untuk mempartisinya lagi, karena jumlah ganjil yang awalnya genap kini tidak genap lagi.

Observasi selanjutnya kita ketahui bila ada yang ganjil, maka buang yang ganjil, selain itu maka pasti tidak bisa dipartisi. Ternyata masih salah juga.

Case

4
2 2 2 2

Kemudian aku coba pick smallest, bila tidak ada yang ganjil.

Ada case yang tidak ada $a$ ganjil tapi diremove smallest pun dia masih bisa dipartisi. Casenya sendiri aku masih belum ketemu.

5
4 6 8 6 8

Bisa dipartisi menjadi $[4,6,6]$, setelah $4$ di remove, maka $[6,8]$ masih bisa.

Apa yang mesti diremove? Aku awalnya mikirnya second largest, tapi pasti ini masih ada counternya lagi.

6
4 8 8 10 8 10 8

Sumnya $56$

$[4, 8, 8, 8]$ Remove $8$, sumnya menjadi $48$ masih bisa dipartisi menjadi $[10, 10 ,4]$.

Jadi berbagai cara masih mengcounter solusiku.

Solusi ini bisa disederhanakan lebih jauh, kita bisa bagi semuanya dengan $2$?

6
2 4 4 5 4 5 4

Sekarang kita ketemu ada yang ganjil! Apa maksudnya ini?

Bisa dibuktikan bahwa sebenarnya pembagian dengan $2$ mengakibatkan revelation. observasi bahwa kini bukan masalah genap ganjil tapi masalah part of $2$ dari $10$ yang tidak bisa dipartisi lagi setelah dibagi $2$. Sehingga kita bisa cari yang ganjil, kemudian bagi $2$, dan seterusnya. Ini sebenarnya cukup pure intuisi dan hampir ga ada observasi yang bisa diambil karena ini lumayan adhoc.