Google Code Jam

[Володимир Лісівка]

Сьогодні о 20:00 розпочинається змагання з програмування. Хто бажає, ще має час зареєструватися. Кожен учасник представляє свою країну.

На домашній сторінці є можливість ознайомитися і розв’язати завдання з попередніх змагань. Допускається використання будь-якої мови програмування.

Домашня сторінка: http://code.google.com/codejam

[Володимир Лісівка]

Порозв’язував усі приклади, які пропонуються для розминки, на bash-і.  

[Yury_Bulka]

Порозв’язував усі приклади, які пропонуються для розминки, на bash-і.  

Тоді вперед:)

Off-topic:

Ех, мені б так...

[Володимир Лісівка]

Кваліфікацію я точно пройшов — 3*10 балів точно є (потрібно 25). Одну задачу розв’язати на баші не можу тому що там використовуються дійсні числа, які у баші відсутні. Та і сама задача складна, а часу вже мало — я довго спав. :-)

[Володимир Лісівка]

Всі кваліфікаційні завдання мають складність o(n), а я для candy-splitting зробив рекурсивний пошук, на баші, з глобальними змінними.  

А маленький набір тестів взагалі повним переборором (O(2^n))   пройшов  (щоб отримати правильну відповідь для тестування рекурсивного алгоритму). (чітер   ) Добре хоч з 3-го разу правильно зрозумів завдання.  

Давненько я не брав участь у олімпіадах з інформатики (18-ть років).

PS.
Обігнав рівно половину учасників. На баші.  

[Володимир Лісівка]

П’ять програмістів використало bash: http://www.go-hero.net/jam/11/lang/Shell

[Re.]

Українців таки немало взяло участь.

[Володимир Лісівка]

Українців таки немало взяло участь.

В першій тисячі — 28 чоловік, тобто 2.8%. :-(

[Сергій Личко]

Там враховується час від початку змагань, так що місце, зайняте в кваліфікаційному раунді - справа п'ята.

P.S. До речі, наближається ICFPC. Хто-небудь збирається брати участь?

[blinkenlichten]

Тоді бажаємо удачі нашим учасникам  
Пане Володимир, а чому саме BASH?
Я б Python узяв, там із списками та стрічками легше гратись.

Також скажіть будь-ласка, до того як хтось завантажить "Input"  він може код проектувати скільки завгодно, а після звантаження вмикається секундомір і починається налагодження для отримання правильного Output за ~3 хвилини, чи-то як?

[Володимир Лісівка]

Тоді бажаємо удачі нашим учасникам  
Пане Володимир, а чому саме BASH?
Я б Python узяв, там із списками та стрічками легше гратись.

Ну а я б тоді писав би на perl-і — на CPAN є достатньо модулів і ставляться вони швидко. Напр. вже є досить корисний модуль ACME::Tools з функцією швидкої перевірки чи елемент є в наборі: http://search.cpan.org/~kjetil/Acme-Tools-0.13/Tools.pm#BLOOM_FILTER_SUBROUTINES, або напр. двовимірний grep: http://search.cpan.org/~thecramps/Acme-Grep2D-0.01/lib/Acme/Grep2D.pm, корисний для завдань про хрестики-нолики.

Але якщо знаєш алгоритм розв’язку, то його можна реалізувати на чому завгодно. Я, напр., скинув одне завдання повністю на плечі grep-у. :-) Мені цікаво було спробувати голий bash (навіть без своїх модулів), так як це дуже обмежена мова програмування і доводиться ломати собі голову над елементарними речами. :-)

Мені не цікаво.

Також скажіть будь-ласка, до того як хтось завантажить "Input"  він може код проектувати скільки завгодно, а після звантаження вмикається секундомір і починається налагодження для отримання правильного Output за ~3 хвилини, чи-то як?

Для маленького завдання правильний результат треба відвантажити через 4 хв. після натиснення на кнопку завантаження і кількість спроб не обмежена (але кожна невдала спроба понижує рейтинг), для великого завдання — 8 хв. і одна спроба.

Якщо завдання розв’язане правильно, то ці обмеження не суттєві.

[BM]

Я б Python узяв, там із списками та стрічками легше гратись.

Ну а я б тоді писав би на perl-і — на CPAN є достатньо модулів і ставляться вони швидко.

Кваліфікацію ISO ти 100% провалив: ставити модуль заради якоїсь дрєбєдєні, особливо коли Python around? Але-ж є й TCL...

[Володимир Лісівка]

А можна детальнiше? Що саме я провалив i чому? :-)

[Володимир Лісівка]

Не пройшов я в другий тур — 1112-е місце в 1C (а потрібно 1..1000). :-(

Bash виявився надто повільний на другій задачі — якби я писав на Сі, то програма була б в 100-1000 раз швидша, і я би пройшов із солідним запасом. Я вперся в банальний інкремент в циклі, який на Сі приблизно в 100 тисяч раз швидший. :-/

[blinkenlichten]

Сумно, звісно.
Цікаво. А скільки часу ваш скрипт виконував завдання?
Можна викласти сюди input-file та ваш скрипт?