Головна Обговорення Лінки Пошук Prykladna СС Прикладна _КОЛЕДЖ 06.12.2019 23:05:17 (EEST=GMT+2)
ACM -
Навігація -
Теми форуму +
Чи знали ви, що... ? (beta) -
Коти махають своїми хвостами, коли стоять перед вибором, при цьому одне бажання блокує інше. Наприклад, якщо кіт стоїть в дверному отворі, і хоче вийти, а на вулиці йде дощ, хвіст гойдатиметься із-за внутрішнього конфлікту. Кіт хоче вийти, але не хоче промокнути. Як тільки він прийме рішення (залишитися удома, або вийти під дощ), хвіст негайно припинить розгойдуватися.
Події
ПнВтСрЧтПтСбНд
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31

Birthday(s):
AVATARLissak258
AVATARSheloth
AVATARLord
AVATARJekooo

Перегляд теми
ACM Контестер | Змагання | Онлайн змагання
Сторінка 4 з 11 < 1 2 3 4 5 6 7 > >>
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

Аватар користувача

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 24-04-2010 12:36
Я вже декілька разів отримав на задачі 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
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 24-04-2010 13:24
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 LeBron Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

Аватар користувача

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 24-04-2010 14:12
LeBron написав:
P.S. Як добре, що почали проскакувати "дуже-дуже класичні" (тобто нагло свічені) задачі. 4В я точно робив, і точно знаю, як вона робиться, бо мав АС, тільки западло в тому, що я не можу знайти, де її робив і не маю того сорса... Тому не можу протестити свій код:) Правда, там було 100000 обмеження і не було розмірів карти, але це все не принципово. N*LogN в 3 секунди має влазити і для мільйона.

врезультаті я вирішив не "випендрюватись" із готовими структурами даних, хоча то б було дуже зрочно, все зробив через масиви, навіть не економив, спробував на макс тесті у них і мені показало: 0.30s/3.00s .
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 24-04-2010 14:36
webmaster написав:спробував на макс тесті у них і мені показало 0.30s/3.00s .

Це як? Забиваєм в код програми генератор тесту, створюєм собі макстест, розв'язуєм, а в кінці просто щось там виводим - і дивимось, який воно в них покаже час?.. зараз теж попробую.

В мене на паскалі на рендом-тесті повинно б показати десь 1.6-1.8. Зараз спробую.

Мене тут А зацікавила, я розумію, що Василь нам зараз скаже, що там опимальний розв'язок за loglogN, але я чогось його ще не побачив. Вона дуже нагадує задачу, яку Павло після ВсеУкри придумав, тільки там була дана кількість ребер, які треба було викинути, і треба було порахувати максимальний мінімальний шлях, який можна залишити, а тут навпаки - дано мінімальний шлях, а треба викинути ребра... В поїзді Шеф сказав про наш варіант задачі, що він "досить цікавий". Надіюсь, цей простіший.

І ось ще новина в тему:
Szczęśliwymi posiadaczami koszulek zostają: karo9, shef, fingon, mksn, chilikk, rav89, grzesiek, h4wk, txv, sk88, wiktor.
- я правильно зрозумів, що це той самий Шеф, котрий знає розв'язок за LogLogN і хорошу евристику за (1/N)*LogLogN?


Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
LeBron LeBron Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

Аватар користувача

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 24-04-2010 15:09
Так, привильно, перед виконанням програми у коді є генератор тесту, і він не рандомний, бо рандомний не дасть максимальний тест.

Задача 4А.
Прочитав умову і не ясно як робити її взагалі, намалював абстрактний граф на листочку і відразу стало зрозуміло, що і як її робити. Тільки у мене точно буде ТЛ, ну це дрібниці.

П.С. коли згадуєте якусь задачу по буквам, то пишіть і номер раунду, бо "А" не зрозуміло, що значить, а вже "4А" значно зрозуміліше, хоча вже "5А" знову не зрозуміло, але вони використовують кодування задач "KOZ".
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

Аватар користувача

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 24-04-2010 16:08
прочитав задачу 5B-MAA
я щось не розумію, вони, що переплутали умови і вийшли дві однакові задачі 5B та 4B
або, що найбільш правдиво, я погано прочитав умову. Перечитав ще раз, не помогло.
Допоможіть хтось.
Дякую.
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 24-04-2010 16:10
webmaster написав:
Так, привильно, перед виконанням програми у коді є генератор тесту, і він не рандомний, бо рандомний не дасть максимальний тест.

0.41s/3.00s - непогано, на домашньому працює довше.

Цікаво, чому рендомний не буде найгіршим? найвужче місце - сортування, а при максимальному розмірі масиву, який треба посортувати дуже нічого не придумаєш. Хіба що взяти стандартні тести, які "валять" певні реалізії qsort'у.

webmaster написав:
Задача 4А.
Прочитав умову і не ясно як робити її взагалі, намалював абстрактний граф на листочку і відразу стало зрозуміло, що і як її робити. Тільки у мене точно буде ТЛ, ну це дрібниці.

Я про першу очевидну ідею (M^4) можу сказати те саме.


Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
LeBron LeBron Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 24-04-2010 16:12
webmaster написав:
прочитав задачу 5B-MAA
я щось не розумію, вони, що переплутали умови і вийшли дві однакові задачі 5B та 4B
або, що найбільш правдиво, я погано прочитав умову. Перечитав ще раз, не помогло.
Допоможіть хтось.
Дякую.

В 4В (MAP) треба порахувати, скільки є підходящих стартових точок на карті, серед названих на вході. А в 5B-MAA треба порахувати, скільки є підходящих точок, при умові, що стартовою можна робити не лише точку, дану у вхідних даних.


Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
LeBron LeBron Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

Аватар користувача

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 24-04-2010 16:19
також маю проблему із задачою
5B - WYS
от нехай маємо тест
1
1 2 1
тобто, довжина 2, а світиться 1.
То воно як там? Насправді світиться "01", чи щось інше?
Дякую
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 24-04-2010 16:49
leading zeros
are allowed - оце наводить на думку, що там будуть саме нулики, а не неактивні елементи. Але не знаю, я ще за неї не брався. На форумі ще ніхто не питає таке. А про різницю між двома меп-задачами вже питали, зараз побачив, що темка така є.
edit - полазив форумом, повзнавав... Спірне питання, можуть бути ведучі нулі - тоді так і писатиме не вході (012 наприклад), а в протилежному випадку - не знаю.


Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
Змінив(ла) LeBron, 24-04-2010 19:50
LeBron LeBron Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 24-04-2010 19:37
Оскільки адміністрація не відповідає на мейл, то повторив свою проблему, як технічне питання в укр.варіанті сайту. Може там щось скажуть, хоч чітко видно "є/нема відповіді", тобто щось вони просто зобов'язані відповісти.

А ще я нарешті прочитав правила, і побачив, що футболки дають за В-рейтингом, тому А можна і не здавати (якщо нема бажання їхати на очний тур). Тепер міняю свою ціль з 4А на 5В:) Нема чого час на дурниці тратити. Краще бали відсуджувати (В поки що були такі прості, що там майже всі все здали, і я без тих 10 балів, які висять на укр.варіанті, знаходжусь настільки низько, що аж соромно, бо 25 балів це середина першої тисячі, и 15 - троха нижче середини, і то навіть не троха...), розв'язувати В в надії на сувенір, вчити фізику в надії на нормальні результати ЗНО...

У мене дещо не в тему запитання, але задам його тут, бо ідейно пов'язано, флуджу і так всюди, а нової теми воно не заслужило. Отже, я тут в пошуках важливого досвіду участі в змаганнях (і халявних футболок - щоб були сувеніри і щоб мені не дорікали, що я даремно це все роблю) натрапив на Google Code Jam. Почитав їхні правила, і там пише, що до участі в змаганнях допускаються у віці не менше 13 років, а на очний тур - не менше 18 (чи щось таке:)). Як це виглядає, якщо я потрапляю на очний тур, то просто беруть замість мене першого з тих, хто не потрапляє, а решта все так, як було б, якби мені було 18? Чи є якісь нюанси?


Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
LeBron LeBron Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
DixonD
Адміністратор

Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06
Опубліковано 24-04-2010 21:37
webmaster написав:
також маю проблему із задачою
5B - WYS
от нехай маємо тест
1
1 2 1
тобто, довжина 2, а світиться 1.
То воно як там? Насправді світиться "01", чи щось інше?
Дякую

Судячи з умови такий тест некоректний
DixonD 427265719 dixond[злий_пес]acm[на]lviv[на]ua DixonD (Lviv NU) http://dixond.blogspot.com/ Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

Аватар користувача

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 24-04-2010 21:41
DixonD написав:
webmaster написав:
також маю проблему із задачою
5B - WYS
от нехай маємо тест
1
1 2 1
тобто, довжина 2, а світиться 1.
То воно як там? Насправді світиться "01", чи щось інше?
Дякую

Судячи з умови такий тест некоректний

а як у такому випадку може бути?
має записуватись саме "01" на вході, чи просто довжина має відповідати
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

Аватар користувача

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 24-04-2010 21:48
LeBron написав:
У мене дещо не в тему запитання, але задам його тут, бо ідейно пов'язано, флуджу і так всюди, а нової теми воно не заслужило. Отже, я тут в пошуках важливого досвіду участі в змаганнях (і халявних футболок - щоб були сувеніри і щоб мені не дорікали, що я даремно це все роблю) натрапив на Google Code Jam. Почитав їхні правила, і там пише, що до участі в змаганнях допускаються у віці не менше 13 років, а на очний тур - не менше 18 (чи щось таке:)). Як це виглядає, якщо я потрапляю на очний тур, то просто беруть замість мене першого з тих, хто не потрапляє, а решта все так, як було б, якби мені було 18? Чи є якісь нюанси?

Відповідь на флуд.
На ТСО були випадки, що на фінал проходили учасники, які не мали права проходити, бо їм мало років було, то тих учасників здається дискваліфіковували, то тому планка посувалась далі, Остап краще знає :) . А також можливі випадки, якщо учасник відмовляється від поїзди на фінал, або йому візу не дали, або ще щось, то планка також посувається. Це все стосується ТСО, бо вони вже багато років то проводять і мають гарний досвід. А з КодДжемом було трохи важко хлопцям, запрощення здається довго відправляли.

І щоб був не тільки флуд.
То про задача 4B-MAA цікава ідея. Дивимось, який буде результат задачі 5B-МАР і потім тільки підправляємо свій код на нову задачу. Звісно якщо алгоритм це позволяє.
Змінив(ла) webmaster, 24-04-2010 21:51
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
DixonD
Адміністратор

Повідомлень: 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
DixonD 427265719 dixond[злий_пес]acm[на]lviv[на]ua DixonD (Lviv NU) http://dixond.blogspot.com/ Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 24-04-2010 23:20
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
LeBron LeBron Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

Аватар користувача

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 24-04-2010 23:29
LeBron написав:
А ще похвалюсь, що я достукався до організаторів:

Be careful and submit only at the ua contest. We will move the solutions from the Polish site to ua.

Вітаю, ти тепер знову з нами
:)
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 24-04-2010 23:51
webmaster написав:
Вітаю, ти тепер знову з нами
:)

Дякую! Піду ще годину тестити В. Але я і так трохи переживаю, що там буде - сабміти ще не перенесли, вони мені можуть вернути мій останній сабміт на Польщі (поверх останнього на Україні, зробленого пізніше), якщо будуть дуже старатись.
Для чого така система - розділена і трохи неповноцінна? Я на польській версії за 2 дні, які я нею користувався, так і не знайшов посилання на українську (і ще собі думав: "хм... так здається в перший день було на англійській... а зараз на польській... " ).. І рейтинг могли б зробити спільний з можливістю фільтру. Про те, що в українців відсутній рейтинг за задачами В - взагалі окрема розмова. Ну а що, ми ж круті, нащо нам мірятись балами на задачах для початкових класів , на яких вічно чомусь недобираєм оцих самих балів. А обговорення і питання до задач можна і на польській почитати, якщо здогадатись, як на них втрапити, угу, так і має бути...


Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
Змінив(ла) LeBron, 25-04-2010 00:01
LeBron LeBron Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

Аватар користувача

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 25-04-2010 01:08
Ну що... Вітаю всіх із завершенням увілейного 4го раунду захоплючих змагань.
Цього разу не буде повноцінного розбору завдань, оскільки задача 4В-MAP, точніше її брат близнюк, є у 5му раунді, а задачу 4А я зробив, хоча дуже сумніваюсь у правильності, подивлюсь які будуть результати на тестах.
Змінив(ла) webmaster, 25-04-2010 01:09
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 25-04-2010 01:09
Результатів ще нема, але тур вже закінчився. Розкажіть хтось, як робити А, бо я навіть не старався дуже щось там придумати і написати, спинився на жадних евристиках та експоненціальному переборі... Навіть не сабмітив:) Про В я буду говорити, коли свої результати побачу.
P.S
Algorithmic Engagements for Ukraine, Fourth round 10 pokaż raport

В пройшла, я ніде не допустив якоїсь тупенької помилки... В Україні зарахована. В Польщі ще або не виклали результати, або це вже складова їхньої політики депортації мене з Польщі.
webmaster написав:
Цього разу не буде повноцінного розбору завдань, оскільки задача 4В-MAP, точніше її брат близнюк, є у 5му раунді

Там є відмінність, і вона трохи додає складності. Вже так не вийде, як в 4В, просто туди-сюди масивом побігати, провірити всі точки і порахувати, скільки підійшло:) Але суть не надто міняється, тому певна логіка в такій політиці є.

через декілька хвилин

Potyczki Algorytmiczne 2010, Runda czwarta 10 pokaż raport

Вже і Польщу бачу.


Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
Змінив(ла) LeBron, 25-04-2010 01:16
LeBron LeBron Надіслати приватне повідомлення
Сторінка 4 з 11 < 1 2 3 4 5 6 7 > >>
Перейти на форум:
Банери
Голосування
Що Ви б хотіли отримати в якості подарунку на змаганні з програмування?

Медалі

настільні ігри

торт

клавіатура, навушники, флешки і т.д.

квитки в кіно

квитки в аквапарк

квитки на пейнтбол

книги

футболки з логотипом змагання

Для участі в голосуваннях Ви повинні залогуватись.
Міні-чат +
Зараз на сайті -
Гостей: 2
На сайті немає зареєстрованних користувачів

Користувачів: 4,407
новачок: Vodylupe
Powered by PHP-Fusion © 2003-2006
LNU ACMania © 2004-2011 e-mail: webmaster@acm.lviv.ua
21,919,214 унікальних відвідувачів
Our projects: ACM Contester, _College.
  пїЅпїЅпїЅпїЅпїЅпїЅпїЅ Orphus     bigmir)net TOP 100