Я вже декілька разів отримав на задачі 4B - MAP
Example test case: runtime error
process exited due to signal 6 Aborted (SIGABRT)
і ніяк не можу зрозуміти, що це може бути
хоча тепер наклюнувся варіант, що може бути Меморі ліміт, буду зараз це досліджувати
поекспериментува трохи, спробував потестувати на локальній версії Контестера, і мені сказало, що я використовую 39мб памяті, при дозволених 32, от западло знову
наступне дослідження:
set<pair<int,int> >
multiset<int>
використовують однакову кількість пам'яті, а я надіявся, що ні
до цього ж списку додалась і
map<int,int>
Змінив(ла) webmaster, 24-04-2010 13:18
webmaster написав:
і ніяк не можу зрозуміти, що це може бути
хоча тепер наклюнувся варіант, що може бути Меморі ліміт, буду зараз це досліджувати
поекспериментува трохи, спробував потестувати на локальній версії Контестера, і мені сказало, що я використовую 39мб памяті, при дозволених 32, от западло знову
наступне дослідження:
set<pair<int,int> >
multiset<int>
використовують однакову кількість пам'яті, а я надіявся, що ні
до цього ж списку додалась і
map<int,int>
В мене там вистачає 20мб, а можна ще оптимальніше зробити, бо в мене наприкінці обчислень є один непотрібний масив - я міг би ту пам'ять використати 2 рази, тоді навіть 16мб буде.
Адміністраторам вже написав на ту пошту (2 години тому, ламаною англійською), поки що нема реакції.
Дивно, що після третього туру так мало людей залишилось з максимумом балів. 3А що, була досить складна? Бо я в такому ще не дуже орієнтуюсь...
Для чого в 4В дано розмір мапи? я так собі зрозумів, що він вказує лише на обмеження на координати на вході, правильно? P.S. Як добре, що почали проскакувати "дуже-дуже класичні" (тобто нагло свічені) задачі. 4В я точно робив, і точно знаю, як вона робиться, бо мав АС, тільки западло в тому, що я не можу знайти, де її робив і не маю того сорса... Тому не можу протестити свій код Правда, там було 100000 обмеження і не було розмірів карти, але це все не принципово. N*LogN в 3 секунди має влазити і для мільйона.
P.P.S. Оскільки я переключився на В-задачі, то сів її потестити, трохи доробити... В результаті в мене зараз 12 мб, і це без всяких "економій".
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
Змінив(ла) LeBron, 24-04-2010 20:01
LeBron написав: P.S. Як добре, що почали проскакувати "дуже-дуже класичні" (тобто нагло свічені) задачі. 4В я точно робив, і точно знаю, як вона робиться, бо мав АС, тільки западло в тому, що я не можу знайти, де її робив і не маю того сорса... Тому не можу протестити свій код Правда, там було 100000 обмеження і не було розмірів карти, але це все не принципово. N*LogN в 3 секунди має влазити і для мільйона.
врезультаті я вирішив не "випендрюватись" із готовими структурами даних, хоча то б було дуже зрочно, все зробив через масиви, навіть не економив, спробував на макс тесті у них і мені показало: 0.30s/3.00s .
webmaster написав:спробував на макс тесті у них і мені показало 0.30s/3.00s .
Це як? Забиваєм в код програми генератор тесту, створюєм собі макстест, розв'язуєм, а в кінці просто щось там виводим - і дивимось, який воно в них покаже час?.. зараз теж попробую.
В мене на паскалі на рендом-тесті повинно б показати десь 1.6-1.8. Зараз спробую.
Мене тут А зацікавила, я розумію, що Василь нам зараз скаже, що там опимальний розв'язок за loglogN, але я чогось його ще не побачив. Вона дуже нагадує задачу, яку Павло після ВсеУкри придумав, тільки там була дана кількість ребер, які треба було викинути, і треба було порахувати максимальний мінімальний шлях, який можна залишити, а тут навпаки - дано мінімальний шлях, а треба викинути ребра... В поїзді Шеф сказав про наш варіант задачі, що він "досить цікавий". Надіюсь, цей простіший.
Так, привильно, перед виконанням програми у коді є генератор тесту, і він не рандомний, бо рандомний не дасть максимальний тест.
Задача 4А.
Прочитав умову і не ясно як робити її взагалі, намалював абстрактний граф на листочку і відразу стало зрозуміло, що і як її робити. Тільки у мене точно буде ТЛ, ну це дрібниці.
П.С. коли згадуєте якусь задачу по буквам, то пишіть і номер раунду, бо "А" не зрозуміло, що значить, а вже "4А" значно зрозуміліше, хоча вже "5А" знову не зрозуміло, але вони використовують кодування задач "KOZ".
прочитав задачу 5B-MAA
я щось не розумію, вони, що переплутали умови і вийшли дві однакові задачі 5B та 4B
або, що найбільш правдиво, я погано прочитав умову. Перечитав ще раз, не помогло.
Допоможіть хтось.
Дякую.
webmaster написав:
Так, привильно, перед виконанням програми у коді є генератор тесту, і він не рандомний, бо рандомний не дасть максимальний тест.
0.41s/3.00s - непогано, на домашньому працює довше.
Цікаво, чому рендомний не буде найгіршим? найвужче місце - сортування, а при максимальному розмірі масиву, який треба посортувати дуже нічого не придумаєш. Хіба що взяти стандартні тести, які "валять" певні реалізії qsort'у.
webmaster написав:
Задача 4А.
Прочитав умову і не ясно як робити її взагалі, намалював абстрактний граф на листочку і відразу стало зрозуміло, що і як її робити. Тільки у мене точно буде ТЛ, ну це дрібниці.
Я про першу очевидну ідею (M^4) можу сказати те саме.
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
webmaster написав:
прочитав задачу 5B-MAA
я щось не розумію, вони, що переплутали умови і вийшли дві однакові задачі 5B та 4B
або, що найбільш правдиво, я погано прочитав умову. Перечитав ще раз, не помогло.
Допоможіть хтось.
Дякую.
В 4В (MAP) треба порахувати, скільки є підходящих стартових точок на карті, серед названих на вході. А в 5B-MAA треба порахувати, скільки є підходящих точок, при умові, що стартовою можна робити не лише точку, дану у вхідних даних.
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
також маю проблему із задачою
5B - WYS
от нехай маємо тест
1
1 2 1
тобто, довжина 2, а світиться 1.
То воно як там? Насправді світиться "01", чи щось інше?
Дякую
leading zeros
are allowed - оце наводить на думку, що там будуть саме нулики, а не неактивні елементи. Але не знаю, я ще за неї не брався. На форумі ще ніхто не питає таке. А про різницю між двома меп-задачами вже питали, зараз побачив, що темка така є. edit - полазив форумом, повзнавав... Спірне питання, можуть бути ведучі нулі - тоді так і писатиме не вході (012 наприклад), а в протилежному випадку - не знаю.
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
Змінив(ла) LeBron, 24-04-2010 19:50
Оскільки адміністрація не відповідає на мейл, то повторив свою проблему, як технічне питання в укр.варіанті сайту. Може там щось скажуть, хоч чітко видно "є/нема відповіді", тобто щось вони просто зобов'язані відповісти.
А ще я нарешті прочитав правила, і побачив, що футболки дають за В-рейтингом, тому А можна і не здавати (якщо нема бажання їхати на очний тур). Тепер міняю свою ціль з 4А на 5В Нема чого час на дурниці тратити. Краще бали відсуджувати (В поки що були такі прості, що там майже всі все здали, і я без тих 10 балів, які висять на укр.варіанті, знаходжусь настільки низько, що аж соромно, бо 25 балів це середина першої тисячі, и 15 - троха нижче середини, і то навіть не троха...), розв'язувати В в надії на сувенір, вчити фізику в надії на нормальні результати ЗНО...
У мене дещо не в тему запитання, але задам його тут, бо ідейно пов'язано, флуджу і так всюди, а нової теми воно не заслужило. Отже, я тут в пошуках важливого досвіду участі в змаганнях (і халявних футболок - щоб були сувеніри і щоб мені не дорікали, що я даремно це все роблю) натрапив на Google Code Jam. Почитав їхні правила, і там пише, що до участі в змаганнях допускаються у віці не менше 13 років, а на очний тур - не менше 18 (чи щось таке). Як це виглядає, якщо я потрапляю на очний тур, то просто беруть замість мене першого з тих, хто не потрапляє, а решта все так, як було б, якби мені було 18? Чи є якісь нюанси?
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
Повідомлень: 167 Звідки: ЛНУ ім. Івана Франка Зареєстрований: 21.10.06
Опубліковано 24-04-2010 21:37
webmaster написав:
також маю проблему із задачою
5B - WYS
от нехай маємо тест
1
1 2 1
тобто, довжина 2, а світиться 1.
То воно як там? Насправді світиться "01", чи щось інше?
Дякую
webmaster написав:
також маю проблему із задачою
5B - WYS
от нехай маємо тест
1
1 2 1
тобто, довжина 2, а світиться 1.
То воно як там? Насправді світиться "01", чи щось інше?
Дякую
Судячи з умови такий тест некоректний
а як у такому випадку може бути?
має записуватись саме "01" на вході, чи просто довжина має відповідати
LeBron написав:
У мене дещо не в тему запитання, але задам його тут, бо ідейно пов'язано, флуджу і так всюди, а нової теми воно не заслужило. Отже, я тут в пошуках важливого досвіду участі в змаганнях (і халявних футболок - щоб були сувеніри і щоб мені не дорікали, що я даремно це все роблю) натрапив на Google Code Jam. Почитав їхні правила, і там пише, що до участі в змаганнях допускаються у віці не менше 13 років, а на очний тур - не менше 18 (чи щось таке). Як це виглядає, якщо я потрапляю на очний тур, то просто беруть замість мене першого з тих, хто не потрапляє, а решта все так, як було б, якби мені було 18? Чи є якісь нюанси?
Відповідь на флуд.
На ТСО були випадки, що на фінал проходили учасники, які не мали права проходити, бо їм мало років було, то тих учасників здається дискваліфіковували, то тому планка посувалась далі, Остап краще знає . А також можливі випадки, якщо учасник відмовляється від поїзди на фінал, або йому візу не дали, або ще щось, то планка також посувається. Це все стосується ТСО, бо вони вже багато років то проводять і мають гарний досвід. А з КодДжемом було трохи важко хлопцям, запрощення здається довго відправляли.
І щоб був не тільки флуд.
То про задача 4B-MAA цікава ідея. Дивимось, який буде результат задачі 5B-МАР і потім тільки підправляємо свій код на нову задачу. Звісно якщо алгоритм це позволяє.
Змінив(ла) webmaster, 24-04-2010 21:51
Повідомлень: 167 Звідки: ЛНУ ім. Івана Франка Зареєстрований: 21.10.06
Опубліковано 24-04-2010 22:02
webmaster написав:
DixonD написав:
webmaster написав:
також маю проблему із задачою
5B - WYS
от нехай маємо тест
1
1 2 1
тобто, довжина 2, а світиться 1.
То воно як там? Насправді світиться "01", чи щось інше?
Дякую
Судячи з умови такий тест некоректний
а як у такому випадку може бути?
має записуватись саме "01" на вході, чи просто довжина має відповідати
...and ai is a number, which is li digits long...
Тобто довжина має відповідати. Якщо 1, то буде в тесті 01 писати при довжині 2
Змінив(ла) webmaster, 24-04-2010 22:47
webmaster написав:
І щоб був не тільки флуд.
То про задача 4B-MAA цікава ідея. Дивимось, який буде результат задачі 5B-МАР і потім тільки підправляємо свій код на нову задачу. Звісно якщо алгоритм це позволяє.
В мене для неї треба в поточний алгоритм (для 4В) доліпити ще 2 масиви і дописати ще рядків 50 коду, поки нічого кращого не придумав. Але логіка в цих словах є, якщо буде 2/10, то алгоритм явно не дуже.
А ще похвалюсь, що я достукався до організаторів:
Be careful and submit only at the ua contest. We will move the solutions from the Polish site to ua.
webmaster написав:
То про задача 4B-MAA ... 5B-МАР
Ти трохи наплутав з номерами...
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
Змінив(ла) LeBron, 24-04-2010 23:58
Дякую! Піду ще годину тестити В. Але я і так трохи переживаю, що там буде - сабміти ще не перенесли, вони мені можуть вернути мій останній сабміт на Польщі (поверх останнього на Україні, зробленого пізніше), якщо будуть дуже старатись.
Для чого така система - розділена і трохи неповноцінна? Я на польській версії за 2 дні, які я нею користувався, так і не знайшов посилання на українську (і ще собі думав: "хм... так здається в перший день було на англійській... а зараз на польській... " ).. І рейтинг могли б зробити спільний з можливістю фільтру. Про те, що в українців відсутній рейтинг за задачами В - взагалі окрема розмова. Ну а що, ми ж круті, нащо нам мірятись балами на задачах для початкових класів , на яких вічно чомусь недобираєм оцих самих балів. А обговорення і питання до задач можна і на польській почитати, якщо здогадатись, як на них втрапити, угу, так і має бути...
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
Змінив(ла) LeBron, 25-04-2010 00:01
Ну що... Вітаю всіх із завершенням увілейного 4го раунду захоплючих змагань.
Цього разу не буде повноцінного розбору завдань, оскільки задача 4В-MAP, точніше її брат близнюк, є у 5му раунді, а задачу 4А я зробив, хоча дуже сумніваюсь у правильності, подивлюсь які будуть результати на тестах.
Змінив(ла) webmaster, 25-04-2010 01:09
Результатів ще нема, але тур вже закінчився. Розкажіть хтось, як робити А, бо я навіть не старався дуже щось там придумати і написати, спинився на жадних евристиках та експоненціальному переборі... Навіть не сабмітив Про В я буду говорити, коли свої результати побачу. P.S
Algorithmic Engagements for Ukraine, Fourth round 10 pokaż raport
В пройшла, я ніде не допустив якоїсь тупенької помилки... В Україні зарахована. В Польщі ще або не виклали результати, або це вже складова їхньої політики депортації мене з Польщі.
webmaster написав:
Цього разу не буде повноцінного розбору завдань, оскільки задача 4В-MAP, точніше її брат близнюк, є у 5му раунді
Там є відмінність, і вона трохи додає складності. Вже так не вийде, як в 4В, просто туди-сюди масивом побігати, провірити всі точки і порахувати, скільки підійшло Але суть не надто міняється, тому певна логіка в такій політиці є.
Birthday(s):
Правда, там було 100000 обмеження і не було розмірів карти, але це все не принципово. N*LogN в 3 секунди має влазити і для мільйона.
![dixond[злий_пес]acm[на]lviv[на]ua](../themes/Brasil-Fusion/forum/msn.gif)
