Давайте в цій гілці поділимося враженнями про перший раунд (можна і про кваліфікацію). Чи було просто, чи складно? Якщо хтось дивився до задач усіх перших раундів, то який з них на вашу думку нацпростіший/найскладніший? Яка задача найскладніша? Чи важко було писати змагання? Ділимося враженнями!
Я, особисто, брав участь в Round1A. Кваліфікувався відразу, тому решту раундів міг писати лише в practice.
В своєму раундів зайняв 100-те місце, зробивши все крім large-input останньої задачі.
Писав все попорядку.
На останню задачу розв'язку був так і не придумав. Для маленького інпуту писав симуляцію на java з використанням BigDecimal. Уявіть собі моє здивування, коли після контесту виявилося, що маленький інпут можна було порахувати на калькуляторі (навіть без використання scientific-режиму) ))
Всеж, цю задачу я вважаю найскладнішою зі всіх задач всіх перших раундів. Скажу чесно, що ідею розв'язку я підглянув в обговореннях в google-group, бо сам придумати не зміг.
Другий раунд писав в practice. В мене виникли труднощі з правильним читанням умов (пропустив слово prime в другій задачі) ) І тому на другій трохи застряг, таким чином не встигнувши зробити третю вчасно. Тобто загалом на розв'язування трьох задач мені знадобилося більше ніж 2 години. Цікаво, що мій розвязок для large-inрut третьої задачі (заснований на дереві відрізків) генерував відповідь близько 3 хв. Досить довго, як на мене... Ну це через те, що він не є найоптимальнішим для даної задачі. Але цікаво якраз те, що схема змагання Google Code Jam дозволяє використовувати різні підходи, та інколи не зовсім оптимальні розв'язки. До слова скажу, що читав на форумах, що хтось генерував відповідь 6,5 хв - оце справді круто!
Раунд 1С я писав теж в практісі. На ньому я випробовував стратегію "робити всі small а потім всі large". Детальніше про цю стратегію можете почитати в гілці форуму "Стратегія на змаганні". Такий спосіб мені дуже сподобався і надалі я буду використовувати тільки його.
Якщо вставити мій результат в practice Round1C у рейтингову таблицю змагання, то у мене було б 7-ме місце, 100 балів з 55 штрафними хвилинами. (Результат використання нової стратегї видно неозброєним оком )
Здавав я задачі в такому порядку:
1. A-small 00:11
2. B-small 00:31
3. C-small 00:51 +1 невдала спроба
4. C-large 01:06 (на неї модифікував розв'язок для small - замість перебору написав дерево відрізків)
5. B-large 01:09
6. A-large 01:10
Таким чином на всі крім третьої задачі писав відразу оптимальний розв'язок. Якби треба було на всі задачі міняти розв'язки, то мабуть би не встиг: 6 солюшнів за 2 години - як на мене, дуже важко, особливо в складніших раундах.
Якщо брати до уваги загальну складність раунда, то я вважаю, що найпростішим був 1С, найскладнішим - 1В.
Не помиляється той, хто нічого не робить!
Змінив(ла) webmaster, 31-07-2008 12:56
Ostap написав:
На останню задачу розв'язку був так і не придумав. Для маленького інпуту писав симуляцію на java з використанням BigDecimal. Уявіть собі моє здивування, коли після контесту виявилося, що маленький інпут можна було порахувати на калькуляторі (навіть без використання scientific-режиму) ))
Я із scientific-режимом.
Цікаво, що мій розвязок для large-inрut третьої задачі (заснований на дереві відрізків) генерував відповідь близько 3 хв. Досить довго, як на мене... ... До слова скажу, що читав на форумах, що хтось генерував відповідь 6,5 хв - оце справді круто!
Трохи не чесно, по відношенню до тих людей що мають слабші машини. Можливо деякі люди навіть мають доступ до кластерів. Ця тема обговорювалася по відношенню до проекту http://projecteuler.net/.
1В - найскладніший
Дуже негарний момент вийшов у раунді 1С.
Один учасник дістав АС на A-large. Я перетустував його розв'язок на тому інпуті, що дістався мені і його розв'язок дав неправильну відповідь (overflow). Зрозуміло, що були люди які зробили ту саму помилку, але їм дістався "кращий" тест і вони дістали ВА. Виходить на GCJ можна із везінням змагатися. Головне те, якщо робити все правильно тоді цей фактор майже не впливає.
На власному досвіді (1C A-large) переконався, що потрібно бути дуже-дуже (ДУЖЕ) уважним. Відправляти той файл, що потрібно.
ок, я теж відпишуся ))
не знаю як раунд 1А, я писав B і С. З цих двох найважчий, звичайно, B. На рахунок стратегії - я зразу використовував її, бо там специфічно штрафний час нараховується ))
І для Остапа: я останню задачу (C-Large) вже розв"язав після контесту за допомогою RMQ. Вона в мене видавала менше хвилини результат... Так що, очевидно, дерево відрізків тут не найоптимальніше... Ось так, завтра подивимося, що нам дадуть в другому раунді..
Torax написав:
І для Остапа: я останню задачу (C-Large) вже розв"язав після контесту за допомогою RMQ. Вона в мене видавала менше хвилини результат... Так що, очевидно, дерево відрізків тут не найоптимальніше...
2Ostap: не такий в мене і потужний комп"ютер, в будь-якому випадку, різниця в три рази не може бути за рахунок лише конфігурації наших комп"ютерів... ти ж не на целероні 466-му писав, хіба ні? )
Birthday(s):
))
![dixond[злий_пес]acm[на]lviv[на]ua](../themes/Brasil-Fusion/forum/msn.gif)
