Hi!
I'm glad to invite you to my short contest on codechef.com on Sunday, 18th. (Check your time zone here.) I also want to note that Anton_Lunyov help my a lot in preparing of the contest, thanks to him.
In order to take part in the contest you should be registrated on the site, you don't need a separate registration for the contest. The competition will consist of 5 problems for 2.5 hours, using the standard ACM-ICPC rules.
After the contest you can discuss problems here and public all your wishes for the next contests.
Good Luck!
P. S. Please also note that CodeChef is now using much faster judging server!
I didn't know about this site(codechef), thank you.
Nice to see you as an author of Cook-Off again. Waiting for a good contest, as always:)
I enjoyed the contest. Thank you :) Those "Lucky" problems are becoming classics :D
How to solve "Little Elephant and Lucky Segment". Does anyone has any ideas? :)
My approach is to divide into several cases.
The number of pairs (C4, C7) is quite small when C7 > 2.
C7 = 0 is trivial.
C7 = 1 is probably the most tricky part. Let S4[i] is sum of F4 of the first i numbers. For each i, we need to count how many j in some segments [L, R] such that
S4[i] - S4[j] <= i - j
. LetT[i] = S4[i] - i
, the condition becomesT[i] <= T[j]
. This can be done by using Binary Indexed Tree (Fenwick Tree).Опять тупые задачи. Ни одной интересной так для себя и не нашел(
Little Elephant and Lucky Segment — такая классная ИДЕЙНАЯ задача на разбор 100500 случаев, я просто тащусь.
Ну что прям так критично. Там фактически два принципиально разных случая. Когда C7=1, там надо за логарифм решать, например, деревом отрезков или можно обычной сортировкой и бинпоиском, если подумать. Если С7!=1, то совсем тупо, перебираем все пары (С4, С7), которые подходят. Ну да, надо аккуратно разобрать случаи C4=0,1, С7=0. Но в этом же ничего такого нет. Если правильно кодить, то получается очень нормально. А 2-ку убрали, потому что N * sqrt(N) медленно работает.
ну спорить с вами не стану, останусь при мнении, что не самая подходящая задача для одной из самых сложных.
быстрота сервера порадовала, однако
Я даже пофиксил template.
На самом деле, в том, что есть и медленный сервер есть свои плюсы. Когда на задачу предполагается решение за линиюю, то можно поставить такой ТЛ, что только линия проходить и будет. Для кук-оффов не очень весело, но на длинных контестах иногда нужно.
Эх. Если б все так просто было. Когда решение за линию то самым тормозным местом становится считывание и с помощью всяких fread можно и log проталкивать. А переход к генераторам инпутов внутри входных данных усложняет подготовку.