Головна Обговорення Лінки Пошук Prykladna СС Прикладна _КОЛЕДЖ 18.01.2020 05:40:06 (EEST=GMT+2)
ACM -
Навігація -
Теми форуму +
Чи знали ви, що... ? (beta) -
Котяче вухо повертається на 180 градусів. У кожному вусі у кота 32 мускули, щоб управляти вухом вони використовують дванадцять або більше м’язів.
Події
ПнВтСрЧтПтСбНд
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):
AVATARMisha
AVATARZdebyman
AVATARPrototype
AVATARsuhanov
AVATARArtem Halushko
AVATARAntonrom00

Перегляд теми
ACM Контестер | Online Judge System | acm.tju.edu.cn
Автор Longest Increasing Subsequence
stostap
Користувач

Повідомлень: 41
Звідки: Київський національний університет ім. Т. Шевченка
Зареєстрований: 07.02.07
Опубліковано 07-11-2009 18:24
Як порахувати кількість усіх зростаючих послідовностей за час nlogn або щоб вмістився в час 10 сек

P.S. кому не складно, заходіть на форум
http://cybportal.univ.kiev.ua/forum/index.php/board,33.0.html

і помагайте ще там :)


http://cybportal.univ.kiev.ua/forum/index.php/board,33.0.html - help, please
stostap Надіслати приватне повідомлення
Автор RE: Longest Increasing Subsequence
Ostap
Адміністратор

Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06
Опубліковано 08-11-2009 01:26
Jakscho korotko, to kil'kist' usih zrostajuchyh poslidovnostej mozhna porahuvaty za O(1) - jih bezlich ;)
A jakscho serjozno:
Jakscho hochesh, schob tobi tut dopomogly, to abo daj bil'sh konkretnu umovu, abo link na neji, abo link na konkretnu gilku forumu de obgovorjujut' zadachu.
Ja, napryklad, ne zrozumiv, chy treba rahuvaty vsi chy lyshe najdovshi pidposlidovnosti. Krim togo, jakscho treba schob rozvjazok pracjuvav ne dovshe 10s, to bazhano znaty hoch jakus' ocinku dlja N (kil'kosti elementiv poslidovnosti).


Не помиляється той, хто нічого не робить!
Ostap 200-738-699 Ostap Korkuna (Lviv NU) Надіслати приватне повідомлення
Автор RE: Longest Increasing Subsequence
stostap
Користувач

Повідомлень: 41
Звідки: Київський національний університет ім. Т. Шевченка
Зареєстрований: 07.02.07
Опубліковано 08-11-2009 11:20
sorry
але сайт tju в мене зараз лежить
задача з передостаннього тому
називається "щось там Speed"
n<=500000;


http://cybportal.univ.kiev.ua/forum/index.php/board,33.0.html - help, please
stostap Надіслати приватне повідомлення
Автор RE: Longest Increasing Subsequence
Ostap
Адміністратор

Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06
Опубліковано 08-11-2009 12:02
"щось там Speed"


O! Nu ce vzhe nabagato konkretnishe! :)))
Nu jakscho htos' sche ne zdogadavsja, zadacha tut: http://acm.tju.edu.cn/toj/showp3349.html

Nu po pershe, nemaje obmezhennja na chysla, ale jih kil'kist' ne bil'sha za 500K, tomu persh za vse masyv vsih chysel potribno peretvoryty v chysla vid 1 do N.
Nu a dali treba perebyraty chysla poslidovnosti po cherzi i rahuvaty, do skil'koh poslidovnostej jih mozhna dopysaty. Tobto, jakscho potochne chyslo X, to treba znaty skil'ky pidposlidovnostej z poperednih chysel zakinchujet'sja na chyslo Y < X. Tobto jakscho F(Y) - kil'kist' pidposlidovnostej, scho zakinchujut'sja na Y, to nam treba znaty sumu F(Y) dlja vsih Y < X - ce i bude kil'kist' novyh poslidovnostej, scho zakinchujut'sja na X (+ treba dodaty odnu poslidovnist', scho skladajet'sja lyshe z chysla X). Pidkazka: tut dopomozhe Range Sum Querry (RSQ).


Не помиляється той, хто нічого не робить!
Ostap 200-738-699 Ostap Korkuna (Lviv NU) Надіслати приватне повідомлення
Перейти на форум:
Банери
Голосування
Що Ви б хотіли отримати в якості подарунку на змаганні з програмування?

Медалі

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

торт

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

квитки в кіно

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

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

книги

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

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

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