Привет всем.
Сегодня в Саратове проходит региональная командная олимпиада школьников по программированию. Мы решили сделать раунд с использованием задач этого соревнования. Задачи к раунду готовили: Gerald (Геральд Агапов), Fefer_Ivan (Иван Фефер), HolkinPV (Павел Холкин), Igor_Kudryashov (Игорь Кудряшов), IlyaLos (Илья Лось) и Nerevar (Дмитрий Матов). Условия на английский переводила Мария Белова (Delinur).
Раунд начнется сегодня, 15 октября, в 16:00 MSK. К участию приглашаются участники обоих дивизионов.
Разбалловка стандартная: 500-1000-1500-2000-2500.
Поздравляем победителей!
Первый дивизион:
Второй дивизион:
UPD: Опубликован разбор задач.
Неожиданный контест.
Неожиданный, но очень приятный.
today is "Eid al-Adha"
Happy feast to all muslims :D
Happy feast :) عيد سعيد عليك ان شاء الله :)
Хорошо-хорошо, только не взрывай.
A special day for a special round. Happy feast to you too :)
Kurban bayram mubarek olsun!
Happy "Eid Al- Adha" to you. :)
Happy Eid al-Adha!
Just want to remember that you CAN NOT fast in the next 3 days (4 if you count the Eid al-Adha), for you who fast routinely.
Happy feast to all of you :D
happy feast to you too :D
Really funny...
This is now 30 minutes after contest but still : "The scoring will be published later."...
4 hours for system testing...
30 second for ratings!!
thanks!
You should respect this rule:
You may edit your comment only for fixing grammar mistakes or small changes. Do not change the main idea of your comment.
Sometimes you made a mistake and after making the mistake you understand it... What should you do that times?
Just curious, why the scoring is published just before starting?
maybe It is different to "Scoring will be dynamic. Problems are sorted by increasing order of difficulty."
4 mins to go, yet no scoring!
what means 'school regional team competition'?
ACM regional competition ???
In Russia, we have team programming contests for schoolchildren: one All-Russia contest and several regional contests. Our region includes southern part of Russia.
middle school student, or college student ?
I'm not sure what do you mean, but I would say middle school.
yalishanda, thanks.
O~ thank you
it's very early!!!
this is the one of the earlist contests in CF(at 8:00pm in China) the timetable shows that students have to finish this contest at school, dont they i dont know about contests in Russia, perhaps it's an important one. do they feel excited? all in all, wish them good luck
If each round were arranged like the timetable of this round, it would be perfect for us Chinese participants.
you know it's an international website, so jet lag is a serious problem:) that's okey, for we can cherish each chance
How i can know the problems for the last school regional team competition ?
Анонсировать контест с необычным временем проведения за 4 часа до начала — оригинальное решение =)
Неужели все ждут анонс, чтобы узнать, когда начало? А что мешает зайти в "Соревнования" и посмотреть там?
Ну лично меня внезапная новость о том, что будет контест застала в школе, посреди урока информатики. Ещё позавчера, по окончанию прошлого раунда, новых раундов в очереди не было. Да и оповещение на e-mail пришло в час ночи. Сюрприз, конечно, был приятный, но вряд ли он был бы таковым, если бы я узнал об очередном раунде уже после его окончания :)
Странно это. Я как раз позавчера после контеста сразу увидел в очереди этот. А вообще стараюсь каждый день проверять нет ли чего нового в очереди и заранее планировать свое время :)
I hope everyone fails :D
That's very unkind of you!
I lost a bet and I had to post it :D
Finally, a contest that's not too late.
this round was previously arranged ahead of schedule maybe because of the TC.
" The scoring will be published later " . 4 minutes before the contest , yet not published . Well later does include after the contest :P
Score distribution is standard. The author of the post are involved into our Olympiad. So, he wasn't in time with announcing.
No hacks available?
The queue is really long!
I think some time should be added because of all this "In queue"..
And the site was down too for few minutes... :(
How solve problem D?
Как решать D? Мне кажется, или эта задача не проще рюкзака 70000*70000? Или тут подразумевалось какое-нибудь решение с битсетами?
Нет, не проще. Видимо, имелось в виду 70000 * 70000 / 32.
Ну на самом деле чуть более мелкого рюкзака кажется. Да, у меня 70000^2/32.
Мда. Я умею делать это за 35000^2/32, но побоялся такое писать. Там же нужно столько же памяти. Или ты за линейную память делал?
Так как нам нужно восстановить ответ, то просто за линейную память не получится. Я делал снапшоты каждые 4 элемента, а восстанавливал перебором
Восстановление ответа меня и смутило. Я хотел применить трюк, когда мы храним только среднюю строчку матрицы, а потом рекурсивно запускаемся от уголков, чтобы восстановить ответ, но побоялся, что это уже по времени не пройдет.
Да уж, пихалово решает.
можешь подробнее рассказать, что за трюк?
Можно. Просто надо переход подправить, получив дополнительные 70000*32 операций. А именно для каждого веса хранить номер такого предмета, что с ним этот вес набрать можно, а без него нет. Тогда тупой цикл с |= заменяется на проверку, а не получилось ли поставить еще один бит, а если получилось — то в лоб пробежались и поставили.
P.s. В этой задаче хотелось убить кого-нибудь за то, что запуск, так же как и тестирование сабмитов, выдает вердикты с 5-минутной задержкой.
О, тогда можно даже не пробежаться в лоб, а попрыгать прямо по новозаданным битам с использованием соответствующих инструкций. Вряд ли это сильно что-то изменит, правда.
да, можно, но это действительно не изменит ровным счетом ничего, а фразочки в коде вида __builtin_ctz((~u[j+off+1])&((u[j]&(~M[sd]))>>(32-sd))) мне все же не очень нравятся, потому что дебагать их можно только методом стирания и написания заново)
На 35000^2/32 памяти как раз хватает.
Прямо скажем, и не сложнее
За 249мс прошел обычный рюкзак, в котором x предметов одинакового веса переделываются в
предметов. Это довольно странно, потому что на тесте
он работает за квадрат; хотя в 2.5 секунды наверное укладывается.
Тут и обычный квадрат проходил. 4798621
Как решать E (Div2)?
Там через ифы решается, можешь потом мой код посмотреть. Но основная идея — запихать всех одиночек в купе где уже есть два школьника. После этого у нас в остальных купе точно не будет по 2 школьника, или точно не будет по 1 школьнику. Если первый вариант, то всех одиночек объединяем в тройки, за два перехода. Есть количество одиночек не делится на 3, то порисуй и поймешь что делать. Если второй вариант, то купе где 2 школьника так же нужно объединять в тройки, и за два перехода делать два купе из 3 школьников. Если количество 2-ек не делится на 3, то порисуй и поймешь как распихать остаток.
систесты ждать или можно пару часиков погулять?:D
СРМ же через час
Это пипец. "Более быстрые тестирующие сервера", ага.
It's very very hard to understand today's problem description!!!
I guess, I spent almost one hour trying to understand problems, this it's my second contest where I could say it have very poor description.
yeah i agree with u....
Я один упоролся и в А писал Декартово дерево?
в A div 1 / C div 2 просто сет!
Я бы сказал, двусвязный список.
Ох, точно!!!
Но все-таки мне как самое очевидное решение в голову взбрело ДД, дабы втупую все запросы выполнять.
Но писать его таки долговато.
Ну как сказать. Чего его писать — два массива завел, и все. Переходы явно не сильно сложнее, чем в сете.
Мне показалось проще всего написать СНМ туда
Не один. Потом еще в ступор вгоняет таблица — "он же печатает едва ли не одним пальцем, как он сдал RMQ за 5..6..7 минут?"
взломы решали
Сейчас системное тестирование порешает)
Веселая идея, давать АСМ-задачи на раунды по правилам codeforces, и при этом еще и украшать это, скажем так, не очень сильными претестами.
Это ведь так оригинально, когда в задаче С мое залоченное решение и 2 решения других участников дают попарно различные ответы на один и тот же тест, и при этом ни один из ответов не является правильным.
Сегодня какой-то контест под сишников. У нас и в А есть set — нате, пользуйся, и в D есть битсет — подключи и карай...
Эм... и как битсетом D делать с линией памяти? Или ты квадрат по памяти утолкнул?
А set так и в Java есть, не вижу тут никакого чита.
Запомнил каждый сотый столбец матрицы. Иду с конца по столбцам. Когда проходил через запомненный столбец восстанавливал очередные сто столбцов, заново прогоняя динамику от предыдущего запомненного.
Это же известный трик как писать рюкзак за
байт памяти, взяв вместо константы "сто" в моих словах выше 
.
01:59:59 MAMU D — Ксюша и Хемминг GNU C++ Претесты пройдены
Мои поздравления!
My Decision on opening a new problem depends on current problem result i can't start in another problem until i know the result of current problem (pretests) and Queue is toooooooooo Long :( :( and take long time to know if it pass pretests or not
Definitely it effects on a coder's coding... He has to keep an eye on his recent submission to know if it is passed or not... :/
скорость тестирования доставляет
Товарищи, вы все жалуетесь на очередь, на скорость тестированию и прочее. А я поблагодарить хочу Создателей за такой ресурс, где программисты со всего мира могут БЕСПЛАТНО соревноваться и совершенствовать свои навыки.
Forget about last round's C (div1), this round's C is much more deadly! Well, at least there are abundant hacks :D
A funny thing happened to me now: I sent a hack on a solution 1 minute before the end of the contest, and waited for the queue to settle (around 1-2 minutes after the end). But I found out it was ignored, because there was a successful hack around a minute before mine, but that hack was still in the queue when I sent mine :D
Well, C div1 is not very much hard , but you just need to be very careful to handle all cases
But being careful is hard! (for me, at least...)
That's exactly the point. With problems that rely on you finding a general algorithm, passing pretests usually equals passing the systemtest (as with Adiv1 this time). But it's easy to miss a special case (I hacked one guy on "5 1 1 1 1 1", for example).
So THAT was the case I missed! I was dying here trying to figure it out... :)
The scoring will be published later. later = never ever ? looooooooooooooooong Queue ! :|
today's div-2 contest was slightly harder than usual contests, but the problems were very interesting to solve! next time, try to increase the possibility of hacks! :)
I think the system testing can't be completed before TC start ...
Even before TC's end
That's why they began the contest so early.
dunno why, but i think this is the record for the slowest testing ever on Codeforces!
Hi I wanna ask about my A submission [LINK] Why my submission didn't passed time limit ? I saw that my idea is same with other submission that got accepted. Is that using (*it) many times make my submission slower or there's any other factor ? thanks
what is the purpose of the
hold;statement at the end?It just same as getchar(); twice. I'm sure it's not the problem because I got TLE on preetest 11
Probably because of the
lower_bound(s.begin(), s.end(), l)call. From the docs:On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average.
If you want log complexity, you have to call
s.lower_bound(l)instead.I think that this line:
while ((*it) <= r)
should be
while (it!=s.end() && (*it) <= r)
I think it's because you are erasing while you increment the iterator. IMO you should erase the whole range after you assigned the winner.
ffao gave the correct answer.
I got TLE for using lower_bound(s.begin(),s.end(),l) later i replaced it with s.lower_bound(l), i got accepted! so its really something to keep in mind.
25% system test = 30 min
100% system test = ???
Supposing linear behavior you can simply calculate it by a proportion xD
430 min?
50% system test = 115 minutes!
25% system test = 30 min 50% system test = 115 minutes what's about 100% system test ??? :P
400 mins
Whats that? quadratic interpolation?
I hope when I wake up tomorrow to find the system test has finished
LOL at least 140 testcases for div1 C well, at most 140 seconds (=more than 2min) are spent on each user.
Why today's judgement such slowly?
Because there are many test case to run (20-150 cases) for each submission, and each case is about 1-3s time limit.. and there are many submission too.
EDIT: here is a picture
is anybody else facing a problem opening the TopCoder arena? the SRM registration closes in 2 minutes, but i am unable to launch the arena! :(
Yes, me too
just when registration closed, the arena opened! how unlucky we are! :(
Did you update your Java version? I faced that problem some days ago.
i redownloaded the .jnlp file from the website just before trying to launch the arena, but still it wasn't opening!
I did the same but it was a problem with a jar file (logging.jar) So, I updated from Java 6 to Java 7 and it worked.
Same here.
always delete your cache by typing javaws -viewer in terminal and then restart the arena .. Even then if it doesn't work , restart your OS and then open the arena .. It has happened a lot of times with me .
Задача Div2-A просто эпична. Мне кажется, пора бы уже для таких задач делать мультитесты...
Ahh... Why the system testing is so slow? I really don't like when I have to wait few minutes for my solution being checked on pretests, especially when I have a stupid bug and have to resubmit it many times. Today I got RE because I've written ios_base::sync_with_stdio(0); and later used scanf. I submitted it 6 times and had to wait few minutes for each of them. Is it really necessary to put so many big pretests?
And now 40 minutes already passed and system testing is in 20% of its progress...
Hi, i wanna ask about my submission 4791878 , why i got WA on pretest 1 ? Thank you very much
Your check function doesn't return true.
Thankkk youu !
May somebody explain C, D, E (div. 2), please? C requires a segment tree, yep?
There's no need to implement a segment tree for C in Div 2, a disjoint set or simply a linked list would suffice.
Or a regular STL set. 4789501
Oh God, really. Thanks. And may you give some little tips for D & E, please? Don't know how to solve them :\
D: let gcd(length(x), length(y)) = d; i-th character in x will be paired
-times with every character in string y on position 
. Count how many chars equal to c in x and in y are 
, and then the answer is N·length(x) minus the number of all pairs of chars equal to c at every remainder modulo d (those are zeroes in the Hamming sum).
E is ugly, I don't want to write anything about it...
There is non-ugly solution for d2 E — d1 C
Could you explain your Div1 C solution? I think it's better than handling different cases.
Basically there is not that many ways to ditribute that many people between n compatments of 4, 3 and 0 in each. For each such variant we can use simple greedy
For E(Cdiv1), let iterate number of final happy compartments from 1 to n and check if it's possible to be our answer (and how many swap). Final number of compartments x is possible if and only if
Now, we will find minimum number of swap if we want to got x happy compartments in totals, we do as follows
our answer will be minimum ans over all suitable x
You can look at my submission 4801911
Could you explain why final[4] = S-3*x for a valid x?
We have x compartments, in these x there are final[4] compartments with 4 students. 3*x + final[4] = S (total number of students should be same), so final[4] = S — 3*x.
For E, first you should combine 1s and 2s to 3s, then some 1s OR 2s left. If 1s left , brute force how many 1s will not move while other 1s must move. That's easy to think. If 2s left , just do the same thing as 1s.
Hope my code easy to read and understand.4801885
A nice intuition the STL set indeed. How can we deduce if the set is enough in this problem or even in general, what is the border between set or list being enough compared to segment tree. I know the question is not so specific but I think also some advises (not necessarily related to this specific problem) from more experienced coders will be well appreciated from biggest part of the audience.
Thank you. PS: Congratulations for becoming a red coder for first time! :)
It's hard to say when sets could be "enough", all these data structures have their own usage. STL sets can do element existance queries in
time, and supports insertion and deletion with the same complexity, also it can find the element before or after another element. Linked lists can do insertion, deletion, and moving to next element in O(1) time, but takes O(n) to find an element. And as for segment trees, it has a totally different usage. For more information maybe you can check out wikipedia.
*Takes O(LogN) to find an element
... Sorry, my mistake
Does anybody have some idea of div1 B and C?
Slowest system testing I've ever seen.......
Most probably, fastest update of rating ... :D
what a system test!!! why Codeforces don't make system test faster permanently?
Eid mubarak to all muslims ..
system testing too slow !!!
I think system testing went to participate in TC srm and will come back.
Topcoder's contest and system testing will complete before CF's today :P
I think TC and this system testing finished together :D :D
tc finished and cf still running.
the TopCoder SRM started at 2300 IST and has finished system testing and rating updates, but the Codeforces round that finished at 2000 IST has only finished 90% system testing, and has probably broken the record for slowest system testing ever! i know this doesn't always happen, but Codeforces should really improve the speed of judging on both pretests and system tests!
lol nice pic
It would be so better if codeforces people could use extra servers for load distribution .. Cummon professionals , help mike with the funds .. after all we all benefit from the platform ..
TC srm finished and codeforces still has not finished system testing
TC srm finished and codeforces still has not finished system testing
I haven't seen system testing like that...! thanks!
First, happy feast to all muslims !
Second, I'd like all this problems. But can you tell me the reason why the result come late ??
Прошел топкодер, протестился топкодер.
Time limit exceeded on test 61 [final tests] → 4793492.
whats problem with BFS?
I have seen some other bfs solutions to be failed. I don't know the exact reason. My dfs solution passed but I have seen some other bfs solutions to be failed.The reason could be (not sure) same nodes are being queued multiple times.if a node is pushed into the que and marked as visited then it could be a little bit faster. You can try that.But TLE on CF server with bfs where other solution passes with dfs!!! well i am surprised ! Thank God I dont know bfs :p
It could be because you use memset everytime you expand a node.
I just leave it here : Yeputons comment about codeforces down
Actually, right now I don't know why judging is so slow. The possible reasons are:
Sorry for really slow testing.
Current submits are all 'in queue', any mistake?
seems it continues to work, ok
hey, if its not too much to ask, can u implement a way (if it doesn't already exist) by which we can sort the users in the standings by score in a particular problem, or by score on hacks? thanks in advance!
Аллилуйя! Теперь ждём рейтинг!
За 3,5 часа!
ну зато рейт обновили за 3,5 минуты!
Happy feast! Could someone explain me solution of problem C in Div2 or A in Div1?
You can do operations using Map, Linked list, disjoint set or Segment tree .. All will suffice ..
Could you explain one of them?
At first put all knights to the TreeSet, then sequentially for each fight take corresponding subset (for TreeSet it takes R*logN, where R is number of items in subset) and remove all elements of subset except winner. The total complexity will be N*logN
I got it. Thanks.
See maintain a map/set of all those who aren't defeated .. initially it will consist of all the knights as none is killed . now as you get the queries .. find the lower bound for l and delete elements from map/set except the one index which won .. and go on updating the loose array for those who have lost .. searching requires logn for set/map since map/set are a balanced rb tree and you will go to n-1 elements exactly once .. hence your complexity O(nlogn)== 5*10^5 which is within limits for 1 sec .. Apart from that you could have used Disjoint set DS as it is also ammotized O(Nlogn) or in the same way a segment tree ..
System testing was too slow...but ratings has been updated very fast instead!
Разбор скоро будет?
Пожалуйста объясните задачу D (div2)
Вот из-за нее-то я и хочу увидеть разбор :)
В задаче гарантируется, что строки, полученные повторением, имеют одинаковую длину, при этом число повторений целое. Значит, эта длина делится на длину строк x и y (|x| и |y|), а значит, и на НОК(|x|, |y|). При этом понятно, что в позиции НОК(|x|, |y|) будут находиться первые символы обеих исходных строк, а значит, дальше расстояние Хемминга будет считаться точно так же. Поэтому мы можем рассматривать результирующие строки только на участке от 0 до НОК(|x|, |y|), посчитаем расстояние Хемминга там, а дальше умножим его на
.
Получившийся участок всё равно может иметь достаточно большую длину (до 999 999 000 000), в лоб посчитать не получится. Итак, пусть, без ограничения общности, строка x не короче строки y.
Запишем повторения длины НОК(|x|, |y|) друг под другом. Заметим, что каждой букве xi верхней строки могут соответствовать только такие буквы yj нижней строки, что
. Например, для строк длины 9 и 6:
Под верхним
0внизу может быть только0и3, под верхней, скажем,4— только4и1.Мы гарантированно встретим все такие возможные позиции, причём ровно по одному разу. Это позволяет нам рассмотреть только позиции от 0 до НОД(x, y), дальше всё будет повторяться (см. пример: под
0, под3и под6одинаковое множество цифр). Для каждой такой позиции в верхней строке подсчитаем количество символовa,b, …,zнижней строки, которые могут там оказаться.После этого уже для всех символов строки x смотрим, какие символы могут быть под ним, и просто добавляем в ответ их количество.
4799337
Hi everyone. I don't understand why my code for Div2-C gets TLE. Here is my solution --> 4796407 I kept all the elements in a vector and when time came, erased it. I think it has complexity
MlogN + M + N. Please tell me where am I going wrong so that I can be careful not to make such mistakes in the future.Erasing an element from a vector takes O(vectorsize) time, imagine that it's because you need to re-number all elements after it. So you complexity is O(N2).
Hi! Your solution would have worked perfect with another container like set. Unfortunately the erase function from vector is ( almost ) linear in the size of the vector. So your complexity is not MlogN so that's why you are getting TLE. Try with set and you will get AC!
I don't usually use set. But I realize it's a pretty handy structure to use at times. I'll try what you said and get back to you. Thanks mate.
Yay! Coded with set and got AC. Runtime less than 1 sec. :)
Thanks a lot!
I have a confusion with you bsearch function. specially with this line hi = v.size()-1; Your M times bsearch will cost MlogN if and only if hi = v.size()-1 is an O(1) operation. But I am not sure that it is O(1). Also in the case of erasing vector elements. Erase operation is O(n) and M times O(n) is bad.
Thanks. I must have counted the complexity wrong. I'll try fixing the solution.
Жаль, совсем маленькая бага в Е, сдал в дорешке
Такое ощущение, что Вы оправдываетесь :)
P.S. Можете минусовать меня.
Я вроде бы ною скорее...
del
Nice joke.
I love this problemset, especially for problem 1D ;)
Could you explain how to solve D? Thanks
I got TLE #82, but assuming my solution was correct, the problem asks you to make a nesting with the given bags, such that the sum of the values of all top-level bags is s. The key observation is to note that any selection of top-level bags is actually possible, as long as the biggest bag is top-level. The trick is to nest each non-selected bag within the next-highest bag, which is always possible. In other words, you can reduce the problem to a subset sum problem.
Why "any selection of top-level bags is actually possible, as long as the biggest bag is top-level"? Under the condition that the total number of coins is fixed, I cannot understand this property. Could you elaborate on it? Thanks.
Let's sort the bags by decreasing ai. The necessary condition is: there's a set S of bags such that
, and 
(1st bag is the largest one). We can construct the solution now. Let's just take the bags in S and put ai coins into bag 
. Then, we have some bags left over, and we want to put those bags so that the constraints would be satisfied.
Let's process the remaining bags by decreasing ai. When adding ith bag into the configuration, we know that there's a bag j which contains aj ≥ ai coins and no bags (for the largest one of the remaining bags, it's the largest bag in total; for any later one, it's the bag that was added to the configuration just before it), so we remove ai coins from bag j, put them into bag i and put bag i into bag j. Notice that this doesn't change the total number of coins, and that there were enough coins in bag j for it to happen (there will be aj - ai left over directly in j after this). In this way, we can construct a solution.
The condition is also necessary, because the largest bag (if there are more of them, choose an arbitrary one) can't be nested in any other, and the number of coins (directly or indirectly) in bags of S (those that aren't nested in any other) must be equal to s.
DP and use bit set to make it faster.
why my C problem is MLE in test 19 ?(div 2) can some one help me?
Probably, stack overflow because of the infinite recursion.
problem: Round #207 B. Flag Day
example : 7 3 1 2 3 4 5 6 5 2 7 Who can tell me the answer ? Why many people who is accepted can't pass it ?
This is an illegal case — in the third dance, you have two dancers who already participated in dances before; 5 and 7. Problem statement indicates that in each dance, at most one dancer who have already danced can participate. This makes the problem way easier actually!
Without this constraint it would be a 3-Colorability problem which in fact is NP-Complete :)
Thank you very much, I see.
pls explain the scoring system ,i solved a question(A) in prev round at the same time as this time(in this contest) but last time i had an increase of +28 points but received a -48 this time
In previous contest, you were 1284th from 2158 participants. This contest, you took the same place, but number of participants were less than previous, so you lost rating.
Well, nice problem, especially C
I made WA on problem C, on the test 141...
I coded for(int i=0;i<num;i++) but I should code for(int i=0;i<=num;i++)...
I lost my rating by 67 points by the mistake and I failed to yellow. But for this mistake, I would be still red now and had gained rating...
All of us have made a silly mistake in some contest caused losing the ratings
Versatile problem set !! #loved it again <<>> #CF, the best.
0xCF round : ))