SnarkNews opened special project related to SEERC-2014, which is started at 10:00 Kyiv time in Vinnytsia (Ukraine) and Bucharest (Romania). For now it contains table of standings (main and separately by Vinnytsia and Bucharest sites), standings for Championship of Ukraine, and text translation (at the moment English is very poor).
Upd: standings are updated. Congrats to Lviv NU Penguins!
Who are in team LNU Penguins? Is it this team ?
What is the meaning of Dirt and SE in the scoreboard?
Dirt: number of submits on the all solved problems / number of the solved problems
SE: "average hardness". Problem, solved by N teams out of M, have hardness (M-N)/M.
Another special fields:
Jump — prediction of place after successful submit right now (or when it changes).
Idle — time after last attempt.
Will the problems from SEERC-2014 be used as an OpenCup contest?
It seems logical that contest named Grand Prix of SPb should be based on ХХХIX Championship of St. Petersburg State University (which is scheduled on tomorrow), but not on problemset from SEERC:)
Btw will you please tell how many problems did you solve finally ?
9 problems with time ~1139 (we solved G at ~4:10).
I guess that final standings will be published soon:)
I think it is good idea always to include last names of participants in team names like
SPb SU 4 (Kunyavskiy, Egorov, Suvorov). First, ITMO used it on NEERC and other contests and I really think that it is a great idea.List of participants arrived to me at last hour only.
First place: Lviv NU: LNU Penguins (Roman Bilyi, Vitaliy Herasymiv, Bohdan Pryshchenko) 9
Second place: Taras Shevchenko Kiev NU: Flawless (Roman Furko, Dmytro Ignatenko, Andrii Mostovyi) 9
Third place: Taras Shevchenko Kiev NU: Unicon (Maksym Bevza, Sergey Nagin, Yevgen Vasyliv) 9
Codeforces handle:
1: LNU Penguins (witua I_love_Tanya_Romanova RomaWhite)
2: Taras Shevchenko Kiev NU: Flawless (Fdg Furko M0sTik)
3: Taras Shevchenko Kiev NU: Unicon (yvasyliv Cenadar Sereja)
Может кто-нибудь в двух словах написать, что такое SEERC, NEERC. Это полуфиналы ACM ICPC? И кто куда и в каком количестве проходит. В википедии про это ничего не сказано ну и на icpc.baylor.edu мне ничего не ясно((
Да, это полуфиналы ACM ICPC.
Расскажу про систему отбора в Украине.
Есть 3 этапа отбора.
На первом этапе соревнуются команды вузов одной области. Проходит ориентировочно в апреле
На втором — команды из одного региона (Украина поделена на 5 регионов — Запад, Восток, Юг, Центр, Киев). Проходит ориентировочно в сентябре (один год было в мае)
На третьем этам уже соревнуются все команды из SEERC (там несколько стран, цитата с официального сайта: Regional Boundaries include the following countries: Albania, Bulgaria, Croatia, Greece, Moldova, Romania, Turkey, Lebanon, Israel, Macedonia, Cyprus, Ukraine, and Serbia). Этап проходит в октябре. Лучшие команды из SEERC выходят на финал. Квота каждый раз разная, окончательно все понятно в начале декабря
большое спасибо! и еще про количество команд:
правильно?
Про второй этап — точно не знаю, остальное вроде бы правильно
Can anyone share the solution for B?
Statement: You have a circular buffer of n ≤ 106 digits. You need to split that buffer somehow into k ≤ n consecutive parts. Out of all splits find the one whose maximum number is minimal.
Public discussion of the problems is bad idea, because they will be used in opencup.
UPD you can hide your comment by editing it.
Oh, I did not know that. Let's discuss them after Open Cup then. :)
Problems from SEERC will not be used at opencup at this year, as i mentioned before.
There is one important thing: we don't have zeros in buffer. So we know the length of answer, it will be LEN = (n + k - 1) / k.
Let's sort all sort all substring of length LEN (by building a suffix array, for example), and do binary search by answer.
So we fixed some number S as answer, how to check if we can split our string in such way, that all parts will be not greater than S? We can do it greedily. We need to iterate over start position of the first part, because we have a circular string. And after that try greedily to get a part of length LEN, if it's impossible then we need to take part of length LEN-1.
The total complexity will be O(nlogn).
That's right. We forgot that we could binary search there. Thanks for the solution. :)
Solution is clear, but how can we prove that we can greedily take part of length LEN?
I don't know formal proof. But if it's not true, it means that we need to take part of length LEN-1(while it's possible to take part of length LEN), and sometimes later take part of length LEN. But it's obvious that we can take part of length LEN, and after of length LEN-1, and it won't change anything.
if S is sorted and Si<=Sj,i<j. when we greedily know the Si can not be split that all parts whill be not greater than Si ,then what should we search next?
Дорешивание будет?
Any hints for "Most Influential Pumpkin"? https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=656&page=show_problem&problem=4872
1) After each query answer increases at most by 1.
2) Let current answer be equal to d. After each query we can calculate, how many numbers, that are strictly less then (d+1) are in our array right now. This knowledge helps us to calculate the answer after current query. One should use sqrt decomposition to be able to do all the calculations. O(N*sqrt(N)*log(n)) solution easily passes the system test.
Did you use tree<> from STL to find how many numbers are less than d+1 ?
For O(N * sqrt(N) * log(N)) simple sqrt-decomposition is OK.
You may set block size to sqrt(N). Now store sorted order for every block. For add query — update leftmost and rightmost block in naive way, and for all blocks between them — just remember that you made +1 over these blocks. And to find how many numbers are less than d — for every block you have to find how many numbers in this block are less than d - X, where X is your counter of +1's over whole given block, it can be done with binary search (for this purpose we are storing sorted blocks).
Carefully implemented, this solution works in O(N * sqrt(N)). This is the way we decided to do it during contest, and it took some more time :) When rebuilding block, you can merge 2 parts in linear time, instead of simply doing sort; and part with binary search may be improved by storing pointer to median in every block, instead of searching for it every time.
Thanks a lot! I got it accepted.
Do you know what the time limits were at SEERC? My O(N*sqrt(N)*log(N)) needed ~7.7s and the O(N * sqrt(N)) ~3.4s.
Time limits weren't mentioned in problem statements at SEERC; later in duscussion of contest maksay said that TL was set to 5s, and author's solution works 0.8-1.0s on C++ and 3.0-3.1s on Java — running time was almost same for O(N * sqrt(N)) and O(N * sqrt(N) * log(N)) solutions.
During the contest our O(N * sqrt(N) * log(N)) approach timed out. I'm not sure if it was possible to get accepted without O(N * sqrt(N)) complexity.
Could anyone sketch the solution for problem G and/or problem I ?
Thanks!
For problem G look at CYK algorithm, it will give you simple DP solution.
Finally AC! I had coded this algorithm, but it seems storing DP(low,high,char) was much slower than DP(char,low,high).
Thanks again!
BTW, you should be familiar with this problem, in case you are representing SWERC — it was used as A — Mixing Colours at SWERC-2013.
And CYK algorithm is mentioned in editorial as intended solution.
Yes! That problem is burned in my mind for unfortunate reasons :(
I had learned the CYK algorithm in an NLP course months before SWERC-2013, but problem A was the only problem I didn't read because my teammates told me it looked very hard and nobody had solved it... had I read it, we would probably have gone to the WF ^^'
From that moment, I always read all the problems