⛓️ 😶 🏾 Keluar dari roda Sansara, ekstremisme, dan beberapa hal hijau - penguraian tugas dari buklet GridGain di konferensi Joker 2018 🙉 👩🏿‍🏭 😤

Konferensi Joker diadakan pada tanggal 19 dan 20 Oktober di St. Petersburg - acara terbaik bagi mereka yang menyukai hal-hal yang sama seperti kita: laporan keren, komunikasi dengan para ahli dan tugas-tugas Jawa tingkat lanjut. Kami tidak akan memuji masalah ketiga tugas dari GridGain ( 1 , 2 ), kami lebih baik mengutip umpan balik dari para peserta:

“Tugas mereka tampak bodoh dan tidak terkait dengan IT”
“Tugas luar biasa, seperti biasa (meskipun saya belum menguasainya)”
"Kecanduan dalam tugas"
“Tugas teratas, seperti biasa”

Kami menerbitkan, seperti yang dijanjikan, solusi terperinci. Mereka membawanya keluar di bawah spoiler sehingga mereka yang melewatkan konferensi dapat mencoba tangan mereka.

Tugas 1

Tiga bulan lalu, kami menulis tugas ini, tetapi pada Oktober 2018, presiden datang dengan inisiatif untuk mendekriminalisasi 282 artikel, yang sangat kami sukai, tetapi kami bosan mengulangi teks. Jadi biarkan semuanya tetap dalam tugas ini seperti sebelumnya. *

Center-on-a-letter memantau penempatan meme ofensif, serta suka dan repost mereka di jejaring sosial. Sebagai bagian dari transformasi digital, seluruh kantor departemen pemantauan telah digantikan oleh kecerdasan buatan. Inovasi membantu dengan cepat menghitung kemungkinan pengguna beralih dari suka ke posting ulang agar berhasil membawa kasus ini ke pengadilan. Sebelumnya, hukuman satu huruf dikeluarkan dengan probabilitas 90% dalam 192 hari. Otomatisasi proses membawa indikator menjadi 12 hari dengan probabilitas 99,9%.

Pertanyaan: berapa kali berkat pendekatan inovatif ini, konversi dari pasangan ke kalimat bersalah meningkat 282, jika frekuensi kalimat memiliki distribusi eksponensial?

Solusi untuk Masalah 1

* Memiliki kutipan kutipan dan sebuah karya di stan penulis kami, Anda dapat segera menerima hadiah. Tentu saja, ini Yuri Khoy (Klinsky), "Sektor Gas" dan lagu "Tunawisma"

Sesuai dengan kondisi awal, sejak frekuensi kalimat memiliki distribusi eksponensial, kemudian sebelum pengenalan robot dan setelah kami memiliki ekspresi berikut untuk menilai kemungkinan kalimat diucapkan dalam waktu ≤ t:

$F_1 (t) = 1 - e ^ {- \ lambda_1 * t} \\ F_2 (t) = 1 - e ^ {- \ lambda_2 * t}$

dimana

$\ lambda_1, \ lambda_2$ - ini adalah parameter yang tidak diketahui yang menentukan frekuensi kalimat, t adalah parameter waktu, sesuai dengan kondisi yang ternyata:

$F_1 (192) = 0,9 \\ F_2 (12) = 0,999$

Dari persamaan ini parameter sangat mudah dinyatakan

$\ lambda_1, \ lambda_2$

$\ lambda_1 = - \ ln (1 - 0,9) / 192 \ sim = 0,012 \\ \ lambda_2 = - \ ln (1 - 0,999) / 12 \ sim = 0,576$

Dari asumsi bahwa jumlah kalimat dan jumlah memasik berhubungan linier, kita dapat menyimpulkan bahwa rasio

$\ lambda_1, \ lambda_2$ hanya memberikan nilai yang diinginkan:

$\ lambda_2 / \ lambda_1 \ sim = 48$

Tugas 2

Dari sudut pandang Buddhis Vasily, kode ini sempurna bukan ketika tidak ada yang ditambahkan, tetapi ketika tidak ada yang bisa dihapus. Termotivasi oleh gagasan ini, Vasily kami memutuskan untuk meningkatkan EpsilonGC dan mengungkapkan kepada dunia Dzen-GC - produk pemikiran sempurna yang tidak hanya dapat menghapus memori tumpukan, tetapi bahkan tidak mengizinkannya dialokasikan. Jelas, alokasi dalam JVM dengan GC inovatif ini hanya dimungkinkan pada stack dan hanya untuk tipe primitif.

Untuk menguji fungsionalitas baru, Vasily memutuskan untuk menulis fungsi di Java yang menemukan mode untuk 6 nilai (mode adalah nilai dalam set pengamatan yang paling sering terjadi), yaitu, ia memiliki tanda tangan berikut:

public static int mode(int n0, int n1, int n2, int n3, int n4, int n5)

Untuk mendekati pencerahan, Vasily tidak mendeklarasikan variabel lokal tambahan dan metode dalam kodenya, dan juga diprogram hanya dengan jari kelingking kaki kirinya.

Tugas: bantu dengan mudah dalam penerapan fungsi ini (diizinkan menggunakan semua jari).

Solusi untuk Masalah 2

Mari kita coba mencari tahu bagaimana masalah ini bisa diselesaikan jika tidak ada batasan ketat seperti itu. Katakan saja bahwa nilai-nilai ditransfer dalam array, dan disarankan untuk tidak menggunakan memori tambahan (tetapi sedikit mungkin).

Kemudian kita akan mencatat opsi yang menggunakan Map <Integer, Integer>, dan perhatikan bahwa mode ini paling mudah dicari dalam array yang diurutkan: jika nilainya diulang, semua duplikat berada di dekatnya. Kami mengurutkan array dan dalam satu pass (dan dua variabel) kami menemukan nilai dengan jumlah pengulangan maksimum.

Sekarang perhatikan bahwa:

1) Anda dapat mengurutkan nilai secara rekursif.

 // Expectation: if there are more than one mode, we are free to return any of them. // 2,2,3,3,4,4 has 3 modes : 2,3,4. I expect that 3 is correct answer. public static int mode (int a, int b, int c, int d, int e, int f){ // If arguments are not sorted, let's sort them with bubble sort :) if (a > b) return mode(b,a,c,d,e,f); if (b > c) return mode(a,c,b,d,e,f); if (c > d) return mode(a,b,d,c,e,f); if (d > e) return mode(a,b,c,e,d,f); if (e > f) return mode(a,b,c,d,f,e);

2) Kami hanya memiliki 6 nilai yang diurutkan.
3) Jika nilainya diulang 3 kali (setengah dari semua nilai) - ini sudah mod!
3.1) Jika tidak, tetapi ada 2 pengulangan - maka ini adalah mod!
3.2) Jika tidak ada nilai duplikat, maka nilai apa pun adalah mode.

 // Check for mode with 3+ repeats. 3 repeats is enough to say value is a mode (3 is half of 6). // Since args are sorted, a == b && b == c is the same as a == c; if (a == c) return a; if (b == d) return b; if (c == e) return c; if (d == f) return d; // Check for 2 repeats. if (a == b) return a; if (b == c) return b; if (c == d) return c; if (d == e) return d; if (e == f) return e; return f; }

Sebenarnya, masalah dapat memiliki banyak solusi, tetapi kami menyukainya sebagai yang paling sederhana dan paling harmonis.

Tugas 3

Dua pecandu narkoba memutuskan untuk keluar dari Matrix dan memahami yang mana dari mereka yang Terpilih. Untuk melakukan ini, mereka mendapat 1 bungkus pil biru dan 4 bungkus pil merah (kemasan dengan ukuran yang sama), dan untuk meningkatkan efeknya, mereka memutuskan untuk meminumnya dengan warna hijau.

Tiba-tiba, ternyata karena kesalahan Matrix (seperti dugaan pecandu narkoba), wajah mereka, yang awalnya memiliki warna RGB # 2D241D dan # F4E3E1, mulai berubah tergantung pada jumlah tablet dan teh hijau yang digunakan: setiap tablet (atau 1 ml teh hijau) secara linear meningkatkan jumlah yang sesuai warna-warna di wajah pecandu.

Pada saat yang sama, nilai setiap komponen RGB tidak dapat melebihi #FF, yaitu, penggunaan lebih lanjut tablet atau warna hijau tidak berpengaruh. Zelenka awalnya memiliki beberapa botol penuh masing-masing 20 ml, total 2 kali lebih sedikit dalam ml daripada jumlah total tablet dalam potongan. Setelah acara keluar dari Matrix, di mana pecandu kedua makan
54 lebih banyak tablet merah daripada biru pertama, pecandu narkoba tidak memiliki apa pun yang tersisa.

Pertanyaan: berapa banyak pil dan greenback yang digunakan masing-masing pecandu, jika akibatnya wajah mereka adalah # F0FF6B dan #FFFEFF, dan diketahui bahwa greenback 3 kali lebih kuat dari pil merah, yang, pada gilirannya, adalah 2 kali
lebih lemah dari biru?

Solusi untuk Masalah 3

Untuk memulainya, kita akan memilih di antara nilai akhir untuk warna hanya yang benar-benar kurang dari 0xFF, karena, berdasarkan kondisi, untuk nilai 0xFF kita hanya dapat memberikan batas bawah dari penambah warna yang digunakan. Ini adalah nilai 0xF0, 0x6B dan 0xFE. Kami memperoleh persamaan berikut:

$r_1 * k = (0xF0 - 0x2D) = 195 \\ b_1 * 2k = (0x6B - 0x1D) = 78 \\ g_2 * 3k = (0xFE - 0xE3) = 27 \\$

atau

$r_1 * k = 195 \\ b_1 * k = 39 \\ g_2 * k = 9 \\$

Di sini k adalah koefisien aksi pil merah,

col_i, col \ in \ {r, g, b \}, i \ in \ {1, 2 \}

$col_i, col \ in \ {r, g, b \}, i \ in \ {1, 2 \}$ , - jumlah amplifier yang digunakan (tablet diukur dalam satuan keping, hijau - dalam mililiter) dengan warna yang sesuai oleh konsumen yang bersangkutan. Lebih jauh, kita tahu bahwa yang kedua mengonsumsi 54 pil merah lebih banyak daripada pil biru pertama, semuanya sederhana:

$r_2 = 54 + b_1$

Persamaan lain diperoleh dari kondisi pada rasio antara jumlah tablet dan mililiter hijau:

$2 * (g_1 + g_2) = (r_1 + b_1 + r_2 + b_2)$

Kami juga memiliki rasio antara tablet merah dan biru:

$(r_1 + r_2) = 4 (b_1 + b_2)$

Selain itu, kita tahu bahwa ada beberapa kali 20 ml greenback:

$(g_1 + g_2) = 20 z$ di mana z adalah bilangan bulat non-negatif.

Dari asumsi bahwa k adalah utuh dan pil dimakan utuh (Anda dapat minum greenback sesuka Anda), satu-satunya jawaban yang sesuai dengan yang berikut:

$r_1 = 195 \\ g_1 = 171 \\ b_1 = 39 \\$

$r_2 = 93 \\ g_2 = 9 \\ b_2 = 33 \\$

Ini dapat diperoleh secara sederhana, misalnya, dengan metode yang dijelaskan di bawah ini.
Kami memiliki rasio

$b_1 * k = 39$ . Satu-satunya faktorisasi dari 39 adalah {1, 39}, {3, 13}. Dengan demikian, k dapat mengambil nilai hanya dari set {1, 3, 13, 39}. Mari kita coba nilai "3".

$r_1 = 195/3 = 65, \\ b_1 = 39/3 = 13, \\ g_2 = 9/3 = 3, \\ r_2 = 54 + b1 = 54 + 13 = 67, \\ b_2 = ((r1 + r2) - 4 * b1) / 4 = (65 + 67 - 4 * 13) / 4 = 20, \\ g_1 = ((r1 + b1 + r2 + b2) - 2 * g2) / 2 = (65 + 13 + 67 + 20 - 2 * 3) / 2 = 79 / 2.$

Tetapi pada saat bersamaan

$g_1 + g_2$ harus kelipatan 20, yang tidak benar untuk nilai (79,5 + 3).

Dengan cara yang sama nilai-nilai "13" dan "39" dihilangkan. Satu-satunya nilai yang tersisa untuk k adalah satu. Menggantinya, kita tidak sampai pada kontradiksi dan mendapatkan jawaban.

Bahkan, karena tidak ada masalah dalam hal ini dikatakan bahwa koefisien kenaikan linear k dari komponen RGB merah adalah bilangan bulat, solusinya adalah seluruh keluarga, * bahkan * jika kita mengasumsikan bahwa hijau hanya dikonsumsi dalam kelipatan 1 ml, dan tablet dikonsumsi secara keseluruhan (yang juga tidak ditentukan secara terpisah):

$r_1 = 1040n + 195 \\ g_1 = 732n + 171 \\ b_1 = 208n + 39 \\$

$r_2 = 208n + 93 \\ g_2 = 48n + 9 \\ b_2 = 104n + 33 \\$
n adalah bilangan bulat non-negatif.

Untuk mendapatkan keluarga ini, Anda harus menyingkirkan k dalam 3 persamaan pertama dengan menulis ulang mereka, misalnya, sebagai:

$3 r_1 - 15 b_1 = 0, \\ 3 r_1 - 65 g_2 = 0, \\ 15b_1 - 65g_2 = 0, \\$

kemudian menyelesaikan sistem persamaan Diophantine linier (secara alami, termasuk sisa persamaan dikurangi ke bentuk yang tepat). Jika kita tidak berasumsi bahwa hijau hanya dikonsumsi oleh volume yang merupakan kelipatan mililiter, kita memperoleh sistem persamaan Diophantine nonlinier, menggunakan g1 dan g2 (yang jelas harus rasional) untuk seluruh pembilang dan penyebut yang tidak diketahui. Jika kita memecahkan masalah dalam bentuk yang paling umum (semua nilai kontinu), maka ada lebih banyak solusi.

Pemenang

Benar, semua tugas diselesaikan oleh Alexey Ryzhikov dan Valentin Shipilov. Hadiah juga diterima oleh Alexey Galkin, Anton Blinov, Ilya Perevozchikov dan beberapa peserta lainnya. Selamat!

Keluar dari roda Sansara, ekstremisme, dan beberapa hal hijau - penguraian tugas dari buklet GridGain di konferensi Joker 2018

Tugas 1

Tugas 2

Tugas 3

Pemenang

More articles: