1

Тема: Завершився Кваліфікаційний раунд змагання Google Code Jam 2016

Завершився Кваліфікаційний раунд змагання Google Code Jam 2016 (варення з коду Ґуґла).
Я витратив багато часу (десь 6-7 годин), щоб розв’язати задачі, і врешті-решт виявилося, що я послав невірний розв’язок для великого набору вхідних тестових даних для четвертої задачі.
Було всього 27170 учасників. 1 710 учасників розв’язали правильно всі задачі, і навіть правильний розв’язока  для великого набору вхідних тестових даних для четвертої задачі відправили.
62 учасники, які представляли Україну, розв’язали правильно всі задач. Славнозвісний Василь Білецький (відомий як «Vasyl»), який виграв багато змагань, набрав 75 очок: схоже, що він не намагався відправити розв’язок для для великого набору вхідних тестових даних для четвертої задачі.

2

Re: Завершився Кваліфікаційний раунд змагання Google Code Jam 2016

Я от що подумав, чи варто створити якийсь вузькоспеціалізований блоґ, де записувати результати виступів учасників, що представляють Україну на цьому змаганні.

Я от порівнюю статистику по своїх блоґах

(мій професійний блоґ, де я пишу переважно про сейлзфорс англійською - колись пробував писати двома мовами - пост українською\пост англійською, але потім помітив, що пости українською ніхто не читає, і надалі писав лише англійською)
https://patlatus.wordpress.com/
дописи 131
перегляди 15913
відвідувачі 11969
найбільше переглядів 28 березня 2016 (83)

(особистий блоґ українською)
https://bdovhan.wordpress.com/
дописи 27
перегляди 1418
відвідувачі 775
найбільше переглядів 12 березня 2015 (41)

Блоґ англійською, де я збирався розбирати задачі цього змагання - багато часу в мене розбирати задачі і писати про них не було, тому постів тут мало - але видно, що мало людей відвідують цей блоґ
https://codejamanalysis.wordpress.com/
дописи 4
перегляди 218
відвідувачі 159
найбільше переглядів 16 серпня 2015 (11)

Блоґ українською, де я збирався розбирати задачі цього змагання - багато часу в мене розбирати задачі і писати про них не було, тому постів тут мало - але видно, що мало людей відвідують цей блоґ - навіть ще менше, ніж аналогічний блоґ англійською
https://analizvarennyazkodu.wordpress.com/
дописи 4
перегляди 127
відвідувачі 105
найбільше переглядів 20 травня 2014 (8)

Тоді чи варто створювати ще один вузькоспеціалізований блоґ з результатами виступів учасників, що представляють Україну на цьому змаганні, якщо його і так ніхто не буде читати? Або мало хто читатиме.

Подякували: raxp1

3

Re: Завершився Кваліфікаційний раунд змагання Google Code Jam 2016

До речі, задачі були досить цікаві, може варто про них написати. В третій і четвертій задачі треба було використовувати довгу арифметику. Я пробував створити багато ботів і сабмітити розв’язок на різних мовах програмування під різними ботами, хоча я знаю, що це офіційно заборонено. В результаті я багато чого навчився і виявив, що найкраще писати задачі з довгою арифметикою на пайтоні і рубі - там навіть заморочуватися з тим не треба, ці дві скриптові мови автоматично запускають довгу арифметику, коли треба. На Джаві чи Сі-шарпі треба використовувати спеціальні класи, якщо хочеш виконувати довгу арифметику. В Сі-шарпі ще при цьому депенденсі треба вмикати. А на Делфі чи Сі-плюсах якщо хочеш довгу арифметику, доводиться писати самому або шукати сторонні бібліотеки, з якими ще треба розбиратися і правильно їх заюзати.

Подякували: leofun011

4

Re: Завершився Кваліфікаційний раунд змагання Google Code Jam 2016

Коротше кажучи, вирішив таки завести такий блоґ - може комусь буде цікаво. http://gcj-ukraine.blogspot.com/

Подякували: raxp, leofun012

5

Re: Завершився Кваліфікаційний раунд змагання Google Code Jam 2016

А на Делфі чи Сі-плюсах якщо хочеш довгу арифметику, доводиться писати самому

чи використовувати вже реалізовані модулі, наприклад цьому був присвячений цикл матеріалів Utkin-а в виданнi ПРОграмміст "Довга арифметика. Частина 1, 2" №№12-13.

Cамі завдання викладайте звичайно )

6 Востаннє редагувалося Patlatus (10.04.2016 11:29:04)

Re: Завершився Кваліфікаційний раунд змагання Google Code Jam 2016

Самі завдання є тут: https://code.google.com/codejam/contest … /dashboard. Не знаю, чи є сенс перекладати українською? Якщо буду писати розбір задач українською, то і самі завдання перекладу.

Подякували: raxp1

7

Re: Завершився Кваліфікаційний раунд змагання Google Code Jam 2016

Не можу знайти помилки в своєму алгоритмі чи коді.
Ось версія на пайтоні: http://pastebin.com/QX8tEQYE
Виглядає так, наче цей код повертає правильний результат для малого набору тестових даних і
повертає неправильний результат для великого.
Я не розумію, чому мій великий вихідний набір даних вважається неправильним. Може хто-небудь знайти помилку в своєму коді або мій алгоритму? Мій код може повертати надлишкові плитки для перевірки, але він не повертає більше, ніж S плиток і індекс кожної плитки знаходиться в діапазоні 1..K ^ C.

8 Востаннє редагувалося Patlatus (10.04.2016 13:16:31)

Re: Завершився Кваліфікаційний раунд змагання Google Code Jam 2016

Мабуть, таки доведеться перекласти ту задачу, що мені не повністю зарахували, українською.

Задача.

Давним давно, фрактальна цивілізація витворила художній твір, що складається з лінійних рядів плиток. У них було тільки два типи плитки, які вони могли б використовувати: золото (G) і свинець (L).

Кожна частина фрактальної твору заснована на двох параметрах: оригінальна послідовність K плиток і складність C. Для даної вихідної послідовності, художній твір зі складністю 1 це просто вихідна послідовність, і витвір зі складністю X + 1 визначається рекурсивно з художнього твору зі складністю X за наступним правилом:

  • замінити кожну плитку L у витворі мистецтва складності X іншою копією вихідної послідовності

  • замінити кожну плитку G у витворі мистецтва складності X повторенням K плиток типу G

Наприклад, для вихідної послідовності LGL, витворами мистецтва зі складністю з 1 по 3 є:

  • C = 1: LGL (що є просто вихідною послідовністю)

  • С = 2: LGLGGGLGL

  • C = 3: LGLGGGLGLGGGGGGGGGLGLGGGLGL

Ось ілюстрація того, як витвір зі складністю 2 генерується з художнього твору зі складністю 1:

https://code.google.com/codejam/contest/images/?image=fractiles.png&p=5636311922769920&c=6254486

Ви щойно виявили шматок фрактальної мистецтва з дуже забрудненими плитками, щоб дізнатися, чи з золота вони чи зі свинцю. Оскільки Ви експерт археолог знайомий з місцевою фрактальною культури, ви знаєте значення K і C для художніх робіт, але ви не знаєте вихідну послідовність. Оскільки золото є захоплюючим, ви хотіли б знати, чи є принаймні одна плитка G в художньому творі. Ваш бюджет дозволяє найняти S аспірантів, кожен з яких може очистити одну плитку за вашим вибором (із плиток K^C  в художньому творі), щоб побачити чи ця плитка G або L.

Чи можливо вибрати набір не більше, ніж S конкретних плиток для очищення, таким чином, що незалежно від того, якою була оригінальна послідовність була, можна буде визначити точно, чи присутня в художньому творі, щонайменше одна плитка G? Якщо так, то які плитки треба очистити?

Вхідні дані

Перший рядок вхідного файлу містить кількість тестових випадків T, за ним T тестових наборів даних. Кожен складається з одного рядка з трьома цілими числами: K, C і S.

Вихід

Для кожного тесту вивести один рядок, що містить Case #X: у, де х позначає номер тестового прикладу (починаючи з 1) і у має значення або "IMPOSSIBLE" (неможливо), якщо не можна вибрати такого набору плиток, щоб визначити чи є хоча б одна плитка G у даному витворі мистецтва, або список додатніх цілих чисел, кількістю між 1 і S, які є положеннями плиток, які треба перевірити. Позиції плиток пронумеровані від 1 для крайньої лівої плитки до K^C для крайньої правої плитки. Ваші обрані позиції можуть бути в будь-якому порядку, але всі вони повинні бути різними.

Якщо існує декілька допустимих наборів плитки, ви можете вивести будь-який із них. Пам'ятайте, що як тільки ви відправите відповідь на малий набір даних і він буде прийнятий, ви не зможете повторно завантажити інший варіант і відправити його. Дивіться FAQ: https://codejam.withgoogle.com/codejam/faq.html#5-2 для більш докладного пояснення. Це нагадування НЕ буде з'являтися в задачах у більш пізніх раундах.

Обмеження

1 ≤ T ≤ 100.
1 ≤ K ≤ 100.
1 ≤ C ≤ 100.
K^C ≤ 10^18.

Малий набір даних

S = K.
Великий набір даних

1 ≤ S ≤ K.

Зразок


Вхідні дані
 
5
2 3 2
1 1 1
2 1 1
2 1 2
3 2 3


Вихідні дані
 
Case #1: 2
Case #2: 1
Case #3: IMPOSSIBLE
Case #4: 1 2
Case #5: 2 6

Примітка: для деяких з цих прикладів випадків, існують інші коректні розв’язки.

У випадку №1, існує чотири можливих вихідних послідовностей: GG, GL, LG і LL. З них можуть бути створені наступні твори мистецтва, відповідно:

Оригінальна послідовність GG : GGGGGGGG
Оригінальна послідовність GL : GGGGGGGL
Оригінальна послідовність LG: LGGGGGGG
Оригінальна послідовність LL: LLLLLLLL
Один коректний розв’язок - це просто подивитися на плитку №2. Якщо плитка №2 виявляється G, то ви будете знати напевно, що художній твір містить принаймні одну плитку G. (Ви не будете знати, чи вихідна послідовність була GG, GL, або LG, але це не має значення.) Якщо плитка №2 виявляється L, то ви будете знати, що вихідна послідовність повинна бути LL, тому в художньому творі немає плиток G. Таким чином, 2 є коректним розв’язком.

З іншого боку, це не було б коректно, просто перевірити плитку №1. Якщо виявиться там L, ви будете тільки знати, що вихідна послідовність може бути або LG або LL. Якщо вихідна послідовність LG, є принаймні одна плитка G в художньому творі, але якщо вихідна послідовність є LL, то плиток G немає. Таким чином, число 1 не буде коректним розв’язком.

Зверніть увагу, що 1 2 також є правильним розв’язком, тому що плитка №2 вже містить всю необхідну інформацію. 1 2 3 не є правильним розв’язком, оскільки він використовує занадто багато плитки (дозволено тільки 2 плитки перевірити).

У випадку №2, твір повинен складатися тільки з однієї плитки: або G або L. Дивлячись на цю плитку буде тривіальним визначити, чи присутня плитка G у ньому.

У випадку №3, який не буде доступний в малому наборі даних, твір повинен бути або GG, GL, LG або LL. Ви можете дивитися тільки на одну плитку, і жодної із них самої по собі не досить, щоб відповісти на це питання. Якщо ви бачите L для плитки №1, ви не будете знати, чи це твір  LG або LL, так що ви не будете знати, чи присутня тут хоча б одна плитка G. Якщо ви бачите L для плитки №2, ви не будете знати, чи цей твір GL або LL, так що ви не будете знати, чи присутні тут плитки G.

Прикладі №4 схожий на випадок №3, але з доступом до ще однієї плитки. Тепер ви можете просто подивитися на всю картину.

У випадку №5, існує вісім можливих оригінальних послідовностей, і вони будуть створювати наступні твори мистецтва:

Оригінальна послідовність GGG: GGGGGGGGG
Оригінальна послідовність GGL: GGGGGGGGL
Оригінальна послідовність GLG: GGGGLGGGG
Оригінальна послідовність GLL: GGGGLLGLL
Оригінальна послідовність LGG: LGGGGGGGG
Оригінальна послідовність LGL: LGLGGGLGL
Оригінальна послідовність LLG: LLGLLGGGG
Оригінальна послідовність LLL: LLLLLLLLL
Один із правильних розв’язків - це перевірити плитки №№ 2 і 6. Якщо вони обидва виявляються плитками L, то твір мусить складатися лише із плиток L. В іншому випадку, принаймні, один плитка G присутня. Слід зазначити, що вивід 1 2 для цього випадку не буде правильним розв’язком, оскільки навіть якщо ці плитки і виявляються плитками L, це не виключає оригінальну послідовність LLG. Вивід 6 2 буде правильним  розв’язком, тому що порядок позицій у вашому розв’язку не має значення.

Подякували: leofun011

9

Re: Завершився Кваліфікаційний раунд змагання Google Code Jam 2016

Чорт, коли переклав умову задачі, знайшов свою помилку.

але всі вони повинні бути різними.


Test case 27...
Number: 1323268795855992 repeated 4 times.
Number: 331173555013152 repeated 4 times.
Number: 475141398872 repeated 4 times.
Number: 1653967209470272 repeated 4 times.
Number: 661871968627432 repeated 4 times.
Number: 2315364036698832 repeated 3 times.
Number: 992570382241712 repeated 4 times.
Number: 1984665623084552 repeated 4 times.
Number: 2646062450313112 repeated 3 times.
Number: 3307459277541672 repeated 3 times.
Number: 2976760863927392 repeated 3 times.

Test case 38...
Number: 89908245428992 repeated 2 times.
Number: 107882011284152 repeated 2 times.
Number: 35986947863512 repeated 2 times.
Number: 125817040574970 repeated 2 times.
Number: 39416153192 repeated 2 times.
Number: 18013182008352 repeated 2 times.
Number: 53960713718672 repeated 2 times.
Number: 71934479573832 repeated 2 times.

Test case 45...
Number: 42715504740 repeated 4 times.
Number: 37970826774 repeated 4 times.
Number: 28481470842 repeated 5 times.
Number: 23736792876 repeated 5 times.
Number: 9502758978 repeated 5 times.
Number: 4758081012 repeated 5 times.
Number: 13403046 repeated 5 times.
Number: 14247436944 repeated 5 times.
Number: 18992114910 repeated 5 times.
Number: 33226148808 repeated 5 times.

Test case 49...
Number: 244268607896528 repeated 6 times.
Number: 81518379995968 repeated 6 times.
Number: 143266045688 repeated 7 times.
Number: 569769063697648 repeated 6 times.
Number: 162893493946248 repeated 6 times.
Number: 325643721846808 repeated 6 times.
Number: 651144177647928 repeated 6 times.
Number: 407018835797088 repeated 6 times.
Number: 488393949747368 repeated 6 times.

Test case 65...
Number: 67142 repeated 2 times.

Test case 77...
Number: 50214204 repeated 4 times.
Number: 361254 repeated 4 times.
Number: 100067154 repeated 4 times.
Number: 149920104 repeated 4 times.

ех, завжди треба уважно читати умову :( :( :(

Подякували: leofun011

10

Re: Завершився Кваліфікаційний раунд змагання Google Code Jam 2016

Можливо комусь буде цікаво - два тижні назад вночі відбувся раунд 1А, я там розв’язав 2 задачі з трьох, але цього виявилося мало: 1056 учасників з більш, ніж 10000, розв’язали правильно усі 3 задачі, і лише 1000 учасників з них вже гарантовано пройшли у раунд 2. А всі решта, як і я, мають ще шанси на раундах 1Б і 1Ц. Раунд 1Б буде сьогодні о сьомій вечора, раунд 1Ц буде на провідну неділю зранку.

Цікаво, чому я не зміг розв’язати третю задачу: в тій задачі на графи я не передбачив альтернативного edge-case розв’язку, який може бути оптимальним для деяких тест кейсів