Привет, Codeforces!
Задачи сегодняшнего раунда были предложены вам пользователями roosephu и Sunayuki. Большую помощь в подготовке задач оказали Aksenov239, GlebsHP и команда Codeforces. В составлении и оформлении условий участвовали сотрудники компании ZeptoLab.
Вас ждет плавная динамическая стоимость задач (с шагом в 250 баллов).
В 2014 году мы провели свой первый контест по спортивному программированию совместно с Codeforces, и нам понравилось!
Контест состоял из 6 задач, на решение которых отводилось 2,5 часа (ознакомиться с задачами прошлого года и даже попробовать свои силы в их решении вы можете по ссылке).
Конечно же, даже на сугубо программистском мероприятии мы остались верны себе, поэтому задачи были придуманы по мотивам наших игр, и, разумеется, мы их заботливо проиллюстрировали:
Zepto Code Rush 2014 побил действующие рекорды Codeforces по популярности раундов, а задачи понравились участникам. К слову сказать, первые 3 места заняли разработчки из России, что не может не радовать. Кое-кто из них даже приехал забрать призы в офис, где их ждала мини-экскурсия и гвоздь программы: конечно же, игра в гигантский Cut The Rope и наше стандартное корпоративное "озеленение" на входе (озеленением мы называем вручение welcome-kit, полного забавных вещиц нашего корпоративно-зеленого цвета).
А кое-кому повезло еще сильнее: они задержались у нас чуть дольше, чем просто на экскурсию, и по-прежнему радуют нас своими рабочими успехами. Ниже пара мыслей от одного из них, Гриши WhiteCrow Назарова:
Изначально я пришел за леденцами (шутка), но сейчас, если делиться впечатлениями, — в первую очередь важно то, что я могу здесь быть собой до конца. Зептолабовцы толерантно относятся к моим странностям и ценят меня как человека. Кроме того, в Зептолаб руководители ставят задачи с учетом способностей каждого разработчика, в том числе передо мной. А когда руководитель тоже "в теме" алгоритмов, мне есть, где развернуться. Получилось, что я стал этаким client-side back-end разработчиком, чего, собственно, и хотелось. Да, я знаю некоторые структуры данных, которые в Зептолабе вряд ли скоро пригодятся (они бы больше пригодились, например, в разработке поисковика); к этой части своих знаний я практически не обращаюсь в ежедневной работе. Зато эти навыки мне полезны на внутренних алгоритмическиех контестах :) О рабочих моментах: моей последней задачей было улучшение упаковки атласов при подготовке игровых ресурсов – известная NP-трудная задача. Мне удалось добиться существенных успехов: улучшить известные и лучшие на 2013 год по разным метрикам алгоритмы. В результате потребление памяти во всех наших игровых проектах сократилось на мегабайты, и у сборок появился запас по memory-limit. С аппетитом наших художников, я думаю, это ненадолго :) Возможно, мою работу мы опубликуем на одной из ближайших конференций. В целом, навыки спортивного программирования здесь очень ценятся, а этому, по моему опыту, в других компаниях придают недостаточное значение.
Ну а цель сего поста проинформировать вас, уважаемые участники, вот о чем: 4-го апреля (в субботу) в 19:30 состоится наш второй контест Zepto Code Rush 2015.
Мы уже вовсю работаем над тем, чтобы снова удивить вас нетривиальными задачками и по результатам порадовать не менее крутыми призами, чем на прошлом контесте:
Кстати, кроме как поучаствовав в контесте, такую жилетку больше никак не отхватить. Жилетки крутые.
Ну и по-прежнему: у того, кто покажет неплохие результаты по конкурсу, будет возможность устроиться к нам по упрощенной схеме. Если вам интересно попробовать себя в команде ZeptoLab — поставьте соответствующую галочку при регистрации. О том, что такое работать у нас можно почитать тут: http://zeptoteam.ru/.
Чемпионат будет проводиться в один раунд. Формат соревнования — по правилам Codeforces. Раунд будет рейтинговым и общим для обоих дивизионов.
Все мимо — дорога в Архангельск занимает у нас 28 часов... И приехать надо к 5 апрелю... Не в курсе, о чем я? :)
Кстати да. ~240 сильных школьников отметается, ибо они будут в это время где-то на пути в Архангельск на всеросс!
А еще в это день в Самаре проводится контест.
Удачного вам прочтения условий в Самаре.
Помним, знаем) Задача про баржы с прошлого года уанлав
Чисто теоретически, вполне можно успеть написать раунд в гостинице после контеста и разбора.
P.S. Барж на чемпионате Поволжья не будет)
Был бы там интернет еще. ато с телефона на несколько ноутов не особо...
мы так пропустили VK cup 1 round, так как ехали в поезде после республиканской олимпиады
This contest will be rated ?? or get any editorial ??
it will be a rated round for the both divisions.
Div.1 vs Div.2
The vests are great! :))
Nice Jacket. I liked It :)
Rare! This is one of a few clothes you can win from a programming contest, and you can actually wear it in some not-programmatical place.
your games are full of fun! And they are so popular in my country.
No T-shirts =(
I agree, it's not that funny when there aren't T-shirts :( .Anyway, I hope the problems will be as interesting as last year or even better :)
There are 15 vests and 50 plush toys to win and you are complaining that there are no T-shirts (100th opportunity to get programming T-shirts?) -_-... Codeforces community can be so cruel sometimes ; d
Oh, c'mon, wasn't it a sarcasm?
It doesn't look like one, especially geniucos' comment.
I would kill to get that cute toy and vest!
Kill me, you'd do a big favor to codeforces
Maybe your first comment that get up votes... :|
Man I am depressed
I love ZeptoLab. The code rush will be good!
i really wonder if viktork is fake account or a specialist host the zeptolab code rush!
Well green matches well with the vests..
tourist would you leave the IPHONE 6 this time ?
No chance,tourist would participate and would win again.
Still waiting for last year's Tshirt..
I think You are Going to Get Two T-Shirt Simultaneously :) Best Of luck For All
your company's games are full of fun,and they are popular in my country!
How can we register guys?
The registration system is same as you register in codeforces round.....
I think After this contest Color me pink (magenta) will be
OMG
What a nice grammar..(plz don't edit your comment... ;D )
No this is not my grammar,this is google translate grammar
Try to learn english in appropriate way! google translate isn't such good tool :|
If you want to highlight both the upvote(green) and downvote(red) arrows simultaneously you should first click on the upvote arrow and then "very quickly" after clicking on the upvote arrow , click on the downvote arrow .
Other way around (firstly downvote and then upvote) works as well ;)
It worked. ;)
As long as you don't reload the page.( I'm disappointed ).
Hopefully there would not be many unknown giant-non-rated(div1 coder competing in div2) coders here!!!
Huh this is combined division contest. This only happens in div2 only contests. So no need to worry.
I thought that more than 6000 participant will join to the contest
But now it's only 3500...
Maybe it will be(I hope)
Now it's 5000. UPD : 5500
iPhone 6 is gone. tourist is participating. :)
you say that like tourist is the only one standing between you and iPhone 6 :)
-_- Very nice joke Mr. sepehr103. April fool is over though.
maybe ironman7453 is fake Petr's account
Hi cheater !
How are you? 9108491 && 9117330
Hi Majid :)
come on sorry_dreamoon !
iPhone 6 is waiting for you !
Edit: TY CF community, I know you wouldn't let me down :)
:|
why?
Still waiting starting the raund :))
Maybe "round"?
Good luck and have fun!
You too :)
tourist vs Petr ... I'm waiting :)
Are you waitimg?..
I moved the round 5 minutes forward just to be sure that everybody are ready and registered. May
the ForceOm Nom be with you!How did you manage to strike out letters ? Just curious, :)
just use
<s>test</s>.Its
greatamazingWelcome kit of Zepto Lab is "going green", but for codeforces, it is "going RED"!!
Wow, the prizes are awesome, and I'm sure the problems will be just as good. It's a shame that with >5000 participants a few people (including me) don't stand a chance at getting one of those cool vests. How about giving away a few vests or buttons to random participants besides the top 50, or better yet, a vest for someone random in the top 500, in the top 1000 (places 0-1000), and so on? That way the more skill you have the better the chances for getting a prize, but everyone still has a chance. But then again, prize or no prize, I'm sure we'll have a great time solving the problems :).
It's starting in 5 seconds...
Вангую, что много C упадут на систестах. UPD: так и вышло!
Надеюсь не у меня :)
Nice Contest thanks all :)
It Ended in before 10 minute
Can anyone give a hint about E?
It is similar to WF2014 Problem K. I used the same method I used to solve that problem, but it may TLE on system test.
Use greedy + dfs + binary search to solve it.
What is your complexity?
The O(N * log * Q) is quite obvious with the same method from WF2014 — K, but I think it'll TLE, so I didn't attempt..
I think it will TLE too. I did some pruning so I can past the pretest. Let's hope it will not TLE on system test. :D
UPD: It passed system test! [smiling face]
Nice — mine linear per query TLEed :(
My
also TLEd (rather understandably).
thanks :D
To solve this problem, first, you need to compute, for each level, how many levels starting from this one would fit in one group. Then, use dynamic programming to compute for each level, starting from the last one, two numbers:
Now, the answer is the smallest number of groups among levels where the groups include all levels, i.e. minimum of the first number among those i for which the second number is at least i.
Thanks guys
I tried that but I get TLE :(, I did many optimization but still no success :(
What's the time complexity of your solution? My solution has time complexity O(nq).
N*Q*log
Another solution with the same complexity:
If the answer for a query is equal to R, then if you start with the first element and do greedy, your answer will be at most R+1. So lets try to start with the first element and get some answer R', and after that check if R'-1 is also possible.
To check that, you can build an oriented tree with edges (P[i], i), where P[i] is largest position such that group [i, P[i]-1] fits. Now you have to find a path in this tree of some fixed length such that the difference between indices of the first and the last vertices of the path is at least N. Since the number of paths in O(N), you can easily check that using dfs.
why is it always at most R+1?
Because you can divide the group and the answer will increase by one.
Mine O(N·Q) approach calculates for every starting position how many groups are needed and what is the sum of leftover elements at the end, which can be eventually grouped with the elements in the beginning.
How do you do it in O(N.Q)??
Как решать С?
там ты берешь красных либо много, либо мало.(До 1000000 перебор сколько возьмешь красных и до 1000000 перебор сколько возьмешь синих(переборы не один внутри другого) ). Надеюсь не упадет)
**UPD:** упала... я 10^5 поставил и багу допустил... печаль
Я брал 10^7 на всякий случай. Надеюсь, пройдет.
UPD. Прошла :)
Брал Sqrt(C), тоже прошла:)
Я воспользовался тем фактом, что если надо набрать ровно НОК(Wr, Wb), то мы будем набирать только одним типом, а также тем, что если надо набрать хотя бы 2*НОК то там будет НОК набранный одним типом. Поэтому можно посчитать НОК, набрать этим НОК сколько входит в С минус один, чтобы у нас осталось от одного до двух НОК, и уже в этом остатке перебирать по кол-ву большего веса. Сложность О(min(C/Wmax, Wmin)). 10581578
Upd: НОК набирать, конечно, тем типом что выгоднее
Почему тернарка не правильна в С? И как сделать, чтоб не валились хеши на 10 тесте в D?
D — Z-функция
А я решал префикс-функцией. Точнее, двумя функциями: одна настоящая префикс-функция, и одна префикс-функция, которая учитывает только префиксы не длиннее
. Для пересчёта второй функции нужно начинать с прошлого значения второй функции, но дальше при переходах использовать первую функцию.
У меня хеши прошли претесты. Upd: зашло
Потому что функция дискретная: в точках M1 и M2 могут получиться одинаковые значения функции, на графике это выглядит как большое плато. Расстояние между M1 и M2 может получиться довольно большим, и между ними может где-то ещё лежать на самом деле максимум, а дойдём мы в него или нет зависит только от теста и ваших условий перехода. Поэтому для надёжности после получения ответа надо его ещё проверять на +-эпсилон влево и вправо, я проверял на 100000, надеюсь, этого хватит.
Только это решение неправильное, для +-40кк падает на 14 тесте, дальше уже TL.
Я ломал с переходами на миллион таким тестом: "100000001 3 100000000 3 100000001" Фиксится это переборами по обеим количествам.
Да, для моего решения это печально(
Понимаю... для моего тоже
вот я и фиолетовый)(Начинал писать прошлый коммент оранжевым) лол
Видимо, потому, что не выполняется требование, что слева/справа от максимума функция строго возрастающая/убывающая.
inb4 90% of submissions on C fail and the problem gets 2500 points, sending people who solved it waaay up the scoreboard :D
(just so it's clear: I know that mine should fail — I have at least a typo)
Does problem C have a tricky corner case?
Is C a DP? I tried but couldn't think hoe to minimize size of array.
How do you solve C? I failed pretty hard on that one :/ Was thinking of some binary search type algo to get logarithmic complexity but didn't work out... Any hints?
Splitting it into 2 cases:
and 
. The first case is trivial, you can try all possible numbers of candies of type A eaten and compute the max. number of candies of type B. For the second case, I tried all possibilities for the sum of weights of eaten candies that are worth trying (at least C - Wa); when it's fixed, the optimal solution is taking the max. possible number of candies of one type, which means solving a modular equation. Seems that it's unnecessarily complex, I saw simpler solutions when trying to hack.
thnx
I just did bruteforce, and it passes. Let's assume that w1 ≥ w2. Kill the cases w2 = 1 and w1 = w2 with "if"s. Then w1 ≥ 3 and now iterate over all possibile x1 — number of type 1 candies.
I have a feeling you dodged a bullet there! I tested your code against this 1000000000 4 3 4 3 and it just scrapes through the 1 second time limit :P
Result = 1000000000
=====
Used: 982 ms, 4 KB
I had used "custom invocation" option and had checked that it passes such tests, before I submited.
Woah I didn't know you can do that during the contest as well! Thanks! I usually code a solution and pray that it works :P
Here is the theory for a polynomial algorithm: http://www.ics.uci.edu/~dan/pubs/p147-hirschberg.pdf
It is possible, but very complex: http://www.csie.nuk.edu.tw/~cychen/Lattices/A%20Polynomial%20Algorithm%20for%20the%20Two-Variable%20Integer%20Programming%20Problem.pdf Code: http://pastebin.com/zSZ5vVWM
Сириусли, в первой
print "no"проходило претесты?
Не знаю как сейчас, но обычно первые претесты — сэмплы из условия. Сэмплы есть на каждый вариант ответа.
Странно, кажется, я взломал одного зелёного молодого человека, который не должен никогда выводить "yes". Видимо, я ошибся
Будет видно, когда решения с тестами откроются. А можно ссылку id его посылки?
http://mirror.codeforces.com/contest/526/submission/10588494
Ага, я понял. Этот парень сравнивал 2 числа за границами массива, они оказывались равными, и он радовался. Супер
Good Bye Div. 1 till 2 months later :-h
Is D a DP? How can I solve it?
I've solved using Z-Function.
It's funny, because the great post about it by paladin8 — http://mirror.codeforces.com/blog/entry/3107 is currently on top 5 of recent actions :)
It's extremely simple with KMP too: 10582275
Can you explain your solution, please?
Let's ignore K for a moment and focus on choosing A, B. We have that the whole string S must be periodic with period len(A + B). Therefore len(A + B) is a multiple of the smallest possible period P for the whole string.
Suppose len(S) = mP + q, with 0 <= q < P. The last q characters have to be in A (as len(A+B) is a multiple of P). Therefore, the necessary condition to write S as A + B + A + B + ... + A is that len(A) = xP + q, len(B) = yP — q, and x+y divides m.
Knowing all of this, which A, B to choose to get k repetitions? Suppose you choose A to have length L. After you remove the last A, you have to leave something which is (A+B) repeated K times. Therefore, you have that:
From the first condition, we want L = len(S) mod k, and from the second condition, we want L as small as possible. So try L = len(S) mod K and check if it's valid, otherwise print 0.
KMP indeed! How did you use the
posarray?Can you explain the idea behind your code, please?
what was the main idea?
Check all possible lengths L of block A + B. For each L use Z-function to find number t of equal blocks A + B (by checking z[L], z[2L], z[4L], z[8L]...). if t ≥ k, then fill min(z[L * k], L) indices with 1 (at position L * k). Complexity O(nlog(n))
Actually you can do it in O(N). In fact you only need to check if z[L]>=L*(K-1)
Thanks!
Some hints for problem C ,please!!
This is my solution
Divide case into 2
Wr > 1000000 : check all posible case
Wr <= 1000000 : In this case, number of blue candy is smaller than Wr so check all
I'm not sure this is right
Now I'm sure this is right
Why the number of blue candy is smaller than Wr?
So if number of blue candy is bigger than Wr, it can't be a best case.
(blue candy)*(Wr)can be replaced by(red candy)*(Wb), which has more enjoy unit.Thanks
Can i filter standings table by color?
Is the problem F only this? http://stackoverflow.com/questions/1824388/finding-sorted-sub-sequences-in-a-permutation I just didn't want to copy-paste the code, which is probably not even allowed...
I think code from SO is allowed: http://mirror.codeforces.com/blog/entry/8790
That's really interesting! I didn't know it, at least I will know for the next time!
ignore
Is D some kind of KMP? I was trying to figure out something from the mismatch array but failed.
D can be done using Z
How do you track the intermediate Bs? or may be thats not even required?
I've used Z-algorithm...
http://mirror.codeforces.com/blog/entry/3107 Epic!
A friend of mine used Z-algorithm. I'm not too familiar with that, so I used rolling hashes for string matching. As long as you have constant-time string matching, it can be solved in O(n lg n): for each value of m = 1...n/k, check if the first km characters is just k copies of the first m characters. If so, also check to see the longest prefix 1...i which matches km+1...km+i (using binary search). Then all strings from km...km+i will be regular (and with some minor details this gives you the output).
How to solve C ? Integer Programming seems too complex.
I will describe my algorithm but I don't know if it is correct since I haven't got the chance to submit its final version because CF was not available in the last seconds :@ :@ :@
We know that X * Wr + Y * Wb <= C.
If we have fixed Y, then X <= (C — Y*Wb) / Wr. As we want to have maximum X, let's say that X = (C — Y * Wb) / Wr.
Happines = X * Hr + Y * Hb. After replacing X, we get:
((C — Y * Wb) / Wr) * Hr + Y * Hb.
Now, using binary search we can find when F(Y) starts to be less than F(Y-1), where F(Y) = ((C — Y * Wb) / Wr) * Hr + Y * Hb.
I tried binary search and it failed.
I tried too but it was implemented wrong and when I found the bug, the contest was over because CF was unavailable.
Binary search will obviously fail because the function is not monotonic and even has several extremas. That's why ternary search is also not very good.
My bad :)
Кому-то удалось сдать С за О(C), D за O(
) или Е за О(Q * N * log(N))? Потому что у меня это все работало за ≤ 1.5 * TL, и серьезно напрягало.
С за O(10^6) (:
E за O(QNlog(N)) у меня около 4 секунд в запуске работало =( Ты двоичный подъем писал или что-то другое?
Именно его. Да, у меня тоже около того работало. Учитывая, что ТЛ был 3 — меня это очень смущало и я напрасно потратил кучу времени, пытаясь его оптимайзнуть:(
Я добавил пару хаков и зашло решение за O(QNlog(N)) в E.
Вместо двоичного подъема я написал два указателя на дереве — зашло за 1107 мс. Уж не знаю, почему =)
E решается динамикой за O(nq). Вначале для каждой позиции считаем, сколько нужно взять, начиная с неё, чтобы заполнить одну группу. Потом, для каждой позиции, считаем, сколько групп нужно взять, чтобы дойти до конца, а также сколько ещё элементов с начала можно добавить в последнюю группу. И то, и то считается за O(n). Затем, ответ находится достаточно тривиально.
Я C сдал за O(C/max(Wb, Wr))
Сдал C за O(C / Wr + C / Wb) с отсечением случая, когда Wr или Wb равны 1. Зашло за 810 мс на MSVC++.
what's the best time complexity of problem c? I have solved similar problem on http://mirror.codeforces.com/contest/519/problem/C but here it's 10^9, and I always tle..... Could anybody give me some hint?
How about problem D?
Thanks : )
Refer to my solution 10585701
Time complexity is O(sqrt(N)), as described in http://mirror.codeforces.com/blog/entry/17281.
It was duficult.
I couldn't hack from Firefox (Chrome worked fine).
Hi, could you prove that your solution on C works correct for all cases?
If Wr is big, the number of red candies must be small. If Wb is big, the number of blue candies must be small. If both Wr and Wb are small, there are two cases: use less than Wb red candies or use less than Wr blue candies.
To hack from firefox you would have to delete the browser's cookies
Thank you, I can hack now.
Problem C have been used in a regional contest in China.
http://acm.hdu.edu.cn/showproblem.php?pid=4091
Шикарно — в задаче B, судя по 10577708, не было ни одного макстеста в претестах
И что?
То, что вполне можно было дать претест на размеры массивов
Вполне можно было прогнать тест на размеры массивов перед отправкой =)
Вообще, оно могло и не упасть, если повезет. Массив размера 2010, 2047 не слиьно вылазит.
Problem E: http://main.edu.pl/en/archive/oi/21/doo
:(
Мой фэйл по задаче A:
:(
So whats the dreaded test case 3 in problem C
Here are two tricky test cases I used for hacks:
999999999 10 499999995 2 99999999
999999999 10000 494999 2 99
Now that it's over:
982068341 55 57 106 109
How to solve Problem B? I found out the path having maximum number of lights, but had problem in incrementing values of edges and distributing the increment among edges in a path. Maybe I complicated it too much.
Мда, в B можно было сделать макс тест, конечно, тогда б я понял, что размер массива нужно побольше делать, а та ошибка исполнения на систестах....
А как планируют передавать участникам призы? У меня просто в профиле указан адрес прописки в Карелии, а сам я в Москве живу.
Ok , since I didn't win anything I just have one question :
When will the ratings be updated ?
Откройте дорешку, пожалуйста %)
Кто-то понимает как валить следующее решение по D: (или доказывать, что оно быстро работает) 10587220
Перебираем j = pi(pi(...(i)..)), где pi — префикс-функция.
Далее, пытаемся использовать |a + b| = i — j. И если находим ответ — делаем break.
Зашло за четверть секунды.
Миллион символов
a, и поменьше k? А вообще, такое решение можно слегка изменить, чтобы оно работало за O(n).Да, спасибо n=1e6, k~=1e3 работает около 3с (я почему-то думал, что ограничения 1e5, когда сдавал), сам тестил на 'a' * 1e5, но оно не сломалось)
Почему нельзя смотреть уже взломанные решения по заблокированной задаче? Казалось бы, странное ограничение, учитывая то, что я теоретически могу сразу открыть все решения в разных вкладках и смотреть после того, как оно взломано. А если не открыл заранее — не могу. К чему это?
Ну вообще говоря, оно протухнет через некоторое время(потребует обновить)
Но ограничение неприятное, да.
Так или иначе, я могу хоть скрин сделать (кажется, это нигде не запрещено?)
Finally Division 1! :D
Good job, hacker! (I have only 1 hacked solution because you were faster :D)
Hahahaha thanks :P
Became orange after 1.5 years not doing programming competitions xD
Btw, I solved C using some hacky brute-force constantly checking time limit until 0.9 second passes. How bad am I for doing is that?
Very smart.
Actually, it's easier to gain a lot of rating in a combined division round than a div1 only round for some reason.
My wild guess: In div1 only round some fraction of participants prefer to skip the round, should they observe problem A is too hard. So you can't "steal" your rating points from them. Combined round has easy entrance problems, so much more skippers got trapped :) More people lose rating — more chances you get some
Впервые я стал желтым на Zepto Code Rush 2014, а красным на ZeptoLab Code Rush 2015. Спасибо! :)
Это еще не все, у красного есть еще один оттенок :)
Я надеюсь, что ZeptoLab будут проводить еще соревнования :)
I solved problem a like so many other people did,a very bad solution that works because n<=100 here's my solution anyone knows why it's wrong? 10579934
10593643
God damn me , what an awful mistake ;-(
Could anybody tell me why this solution of E is correct? It looks like magic. 10581607
Because it's wrong:
https://ideone.com/OKfcQJ (tourist)
https://ideone.com/ugCOlH (this one)
Test case:
Thank you!
Heh. I also submitted such solution (10589617), and wondered whether it works in the general case. Thank you for the test!
Please, take a look at this submission.
We can see that an array check with 100 elements(indexed from 0 to 99) is declared.
I tried to hack it with the following test:
100 *****...******Here "..." means a lot of '*'s, not dots.
Let's take a look at the following for loop:
Here, the variable i can be up to s.size()-1 which is 100 — 1 = 99. Then check[i+1] will be check[100] but it is indexed from 0 to 99. Then shouldn't this be a runtime-error because it cost me -50 instead of +100 :@
PS: Something similar happened during Codeforces #297. I tried to hack this code. As we can see, the guy is pushing some things in a vector ot. And what if ot is of odd size:
I think that if ot.size() is odd, then i+1 will be equal to ot.size() at some point which should be a runtime-error anyway but it wasn't...
It doesn't give runtime-error. It causes undefined behaviour and sometimes works correctly.
Ok, thanks! I thought that it should be RTE because usually on my computer it causes Segmentation fault and when I submit such code on lightoj it causes RTE :)
Can someone please explain the solution for problem E? I didn't understand it from the Editorial.
i wish i could won the jacket :(( its so nice :)
I really like the way in which testcases for E were generated.
All large tests are we'll give you 50 queires, but most of them will be same. Are you serious, guys? :) Looks like most of O(N * log(N) * Q) solutions can pass after adding memoization. My messy implementation (10587744) wasn't even able to pass pretest 10 during contest, and after adding memoization it runs in 1.6 seconds (10600918).
Omagad, what a shame. It is reasonable to create a maxtest with worst case repeated, but in ALL of them -_-...
What is more, there are some wrong submissions which passed (as pointed out above).
What's more, just 21 tests.
When I create tests, I usually also do something like "10 completely random tests" and variations of it several times. More tests won't kill anyone, especially on problems that won't have too many submissions. But this...
Is there any tutorial for this contest?
It looks like ZeptoLab has bad luck with repeating problems. As pointed above, C, E and F were already present in some places of the Internet and one year ago E was from Junior Polish Olympiad in Informatics (I watched editorial created by johnasselta during the contest :P) and F was used in Petr Mitrichev contest.
sorry, I misread
I'm not sure I understood. Didn't Petr clearly state that this problem was present on his contest?
Sorry, I missed "one year ago" in your post
Will this contest an editorial?I haven't see it.
Yes