Всем привет!
Второй раунд соревнования MemSQL start[c]up состоится 3-его Августа в 21:00 MSK. Одновременно будет два контеста: для тех, кто участвует онсайт, и для тех, кто участвует онлайн. Набор задач в двух контестах будет одинаковый, и за них будет начислен рейтинг на основе общего монитора.
Участники, участвующие в онсайт раунде, получат специальные призы за первые три места. Все участники онсайт раунда и топ 100 участников из онлайн раунда получат специальные футболки start[c]up.
Участники, не прошедшие во второй раунд, могут участвовать неофициально. При этом раунд будет рейтинговым для таких участников.
На соревновании будет предложено шесть задач, длительность соревнования -- три часа. Распределение баллов 500-1000-1000-2000-2500-3000.
Задачи приготовлены разработчиками MemSQL pieguy, nika, exod40, SkidanovAlex и dolphinigle.
Удачи и отличного кодинга!
UPDATE: Опубликован разбор задач (на английском)
А в онлайн трансляции можно участвовать, если не писал первый раунд?
Можно регистрироваться вне конкурса.
Update: При этом вне конкурса тоже начисляется рейтинг
UPD: Прежде чем заминусуеш, прочитай все правки выше и здесь. UPD2: Зачем читать...
А для тех, кто вне конкурса, контест будет рейтинговым или нет?
да
are other people allowed to join unofficially for fun? maybe in a separate room?
Will be div2 edition?
Div2 participants are welcome to register for the round unofficially, but the problemset might be too hard for them. Expect problems A and B to be comparable to Div2-C and problem C to be as hard as Div2-D or E.
It's ok, I think most of Div.2 participants could solve at least two problem in this contest.
Yes, it will be possible to participate unofficially.
is it rated for Div2 participants?
Yes
That's not exactly the answer to the Haghani's question. AlexSkidanov only stated, that round will be rated for those not advanced from round 1
I hope all the commentators could give your reasonable comments. I don't know why this comment(just contains a "Yes", and it's a fact) got two "down"s.
It will be rated for all the users.
We welcome Div2 users to participate, but if you register for the round, please be advised that this problemset is not designed for Div2 participants, and you might end up with 0 problems, which will result in a significant loss of rating.
if i register but don't attempt any problem, then will i loss point? is there pretest as usual cf?
Edit: (i asked about rating, cz, there was a notification while registering, it said something like:- "it will not easy for div2, u may loose point, do u still wish to register?" )
u won't...but the rating isn't the most important thing.Just have fun. at least you can do better than me,LOL
Hello I have a question.
How can I register the online contest officially if I have advanced to the round two?
According to the statement above, both official and unofficial online participators need to register the online version. I assume the system will automatically recognize the official particpator (who passed the round 1), am I correct?
Thank you
Yes, it automatically registers those who have not advanced to round 2 for the unofficial track. After you register, please double check, than in the list of registrants you do not have a star symbol next to your handle (star symbols means registered for the unofficial track).
Можно задать вопрос? Как будет считаться рейтинг для участников онлайн раунда? Для всех вместе или для официальных и неофициальных участников отдельно?
Отдельно.
все, разобрался!
уже не актуально :)
Are unofficial participants competing for T-shirts?
No
Баг или фича? Я зарегистрировался на этот контест (как неофициально Див-2), но кнопка "Зарегистрироваться" не пропала.
Hope a good contest for div 2 participants ;)
I'm sure it will be too hard for many participants from Div2.
What does the "Unofficial participation" mean? What kind of participants will be considered as unofficial participants.
If you register for an online round, but you have not advanced to round 2, your participation will be unofficial (in the dashboard and the scoreboard such participants are marked with a star).
Thank you.And Will there be round-3? If so, a man who have not advanced to the round 2 but get a high rank in round 2 unoffically, can he participant in round 3 as an offical participant?
is it for sql language,
or we can participate in any language
You can use one of these languages.
Can you solve problems using sql? XD
either this is not funny joke or you don't know what is sql
Chuck can solve all these problems even using HTML.
or you don't know who is chuck
А результаты онлайн раунда сразу будут? Или какого-нибудь закрытия онсайта надо ждать?
Надо будет подождать.
А сколько приблизительно нужно ждать?
Как решалась C?
Делим на куски вида прямоугольники N*2, бывает 4 вида кусков в зависимости от того, с какой стороны (слева/справа) прололжение воды. Дальше Гранди.
Я забыл написать мемоизацию, но понятно, что если ее написать, то будет не более 4х100 различных состояний
Может лучше Гранди?:)
fixed:)
Теорема Махатма Ганди.
Ну или можно просто считать гранди для поля динамикой dp[mask][l][r], где l и r границы рассматриваемого подполя а mask показывает какие клетки свободны в l-том и r-том столбиках
Хм... Соревнование ведь завершилось. А код других участников смотреть нельзя.
И даже если это ещё можно как-то понять, то почему, собственно, нельзя просматривать профили пользователей?
UPD: Пользуясь случаем, выказываю своё фе участникам, которые зарегистрировались, но не стали отправлять задачи на проверку.
Про твое "фе": Просто участников из див2 сильно пугали для того, чтобы система на онсайте не заглючила.
Условие в F-ке такое простое и, казалось бы, знакомое, но...
Мне кажется, что это задача от dolphinigle, у него уже когда-то была очень крутая задача на жадник.
This is pieguy's problem, and the solution is dynamic programming, not greedy.
Anyone know why profile page says "The page is temporary blocked by administrator." ?
Edit: after system tests it keeps msg as before..
Because when a contest is running they blocked some pages that are not necessary at this moment.
I think it block it until the rates change completely
В Д разве не заходит 3000*N?
Не всякая 3000 * N заходит. У меня не зашла (зря я не тестировал на сервере время работы).
Не хорошо это :(
We did our best to prevent NK solutions, if some of them passed, I apologize in advance. The expected solution was either KK or NlogN
It seems that you did your best to make us write it T_T
Стыдно спрашивать, но как решалась В?
Если букв больше, чем 2600, то есть какая-то буква, которая встречается 100+ раз (принцип Дирихле). Иначе — квадратная динамика f[i][j] — длина максимального подпалиндрома в подстроке от i до j.
Один я, как идиот, написал динамику за N*100*26?
Нет, я тоже, как идиот.
А какая динамика?
dp[i][j] — где заканчивается "палиндромно-хорошая" строка, содержащая палиндром длины i, который начинается в позиции j. Переход — перебираем, какую букву алфавита мы припишем к этой строке с обеих сторон.
Не один :-)
Ахаха :) Ну, у меня динамика за 100*N: [какой суффикс строки смотрим, какую длину палиндрома хотим] = в каком минимальном месте закончим.
Я вообще по-моему какое-то палево сдал. Кто-нибудь умеет объяснять почему это быстро работает? 4223118
Без
if(best.length() >= rest) return best;— TL.Я сперва считал, что каждым из концов может быть не более 50 позиций каждой буквы(первые 50 для левого конца, последние 50 для правого), но теперь понял, что это не правда на тесте
baaabaaaaaaaaaaaaa...часть a-шек между b-ками тоже бывают правыми концами. Или может кто-то умеет валить?Такое простое решение, круто! А у меня адская динамика dp[i][j] = длина минимального суффикса строки, такого что у него и у реверса префикса длины i длина максимальной общей подпоследовательности равна j.
Для N>2600, ответ всегда есть, так как хотя бы одной буквы будет больше либо равно 100(доказывается по принципу Дирихле)...а для меньших N пускаем динамику за квадрат.
http://neerc.ifmo.ru/wiki/index.php?title=Задача_о_наибольшей_подпоследовательности-палиндроме
when is the rating changed
В D 3000n отсекалось специально (и не проходят все реализации), или такое решение не предполагалось и что-то проходит, а что-то нет?
Could anybody tell me some smaller input so that I could figure out the mistake in my code for B. It was hacked on some large random test case when it was possible to have a subsequence of length 100. http://mirror.codeforces.com/contest/335/submission/4223108
In that case my code prints out some non printable character. I am unable to figure out why ?? Any help would be appreciated !!
Small inputs: "a" "aa" "aaa" "aaaa" "ab" "abc" "aba" "abac" "abcbabcc". (This isn't meant as a joke, I really used that to debug my solution :D)
Just write a random generator and make your own input(s). It's hard to find a tricky case here, anyway, so any random string should do.
Oh, it was a silly kind of mistake.
string t;
t += s1;
t += s2;
where s1 and s2 are two characters
is not equivalent to
t += s1 + s2;
"abababababababababababababababababababababababababcbababababababababababababababababababababababababa"
(101 characters in the string, 100 characters in the solution)
Why doesn't multiset in STL have such common operations? Just to find the maximum and the second largest number?
What's wrong with
*--st.end()and*----st.end()?Multiset, not the set. And many numbers will be same.But I want the second largest number strictly. For example, 5 5 4 4 3 2 1 MAX 5 The Second Largest 4
You can use map with values equal to the number of occurences of each key.
Good idea! Thx
I din't think you need element strictly lower.
In that case you may use
*--st.lower_bound(*--st.end()).So we must use BBT
It does.
no one solved problem F. I am curious to know the approach of this problem. btw it was very gud contest. :) :)
When will we be able to register for practice?
i dont know why this comment was ratting +.while my comment is usefull more
Возможность отправить на проверку после соревнования есть?
Уже можно.
i solved B in O(n^2) by using the fact that there are only 26 variety of characters. if n >= 3000 then there is a character that has occurred more than (3000/26) >= 100 times.
so I print a string with length 100 with only this character if n < 3000 then the problem would be the same as LPS (longest palindrome subsequence) which is solvable in O(n^2) if don't think this was the intended solution
and problem C is very similar to problem SGU 328. but with lower constraints (it is solvable in O(R))
I think your solution for problem B is the intended solution, that's why the 100 constraint is there.
Probably. I didn't come up with that solution but a different one with complexity O(100n) that doesn't depend on the number of types of characters.
Sounds like your idea is better than quadratic. Because with 500 types of symbols it would be necessary to process whole length of string (50000). Could you explain in short words?
Let F(i, j) is the maximum index k > i such that we can obtain a palindrome of length 2 * j from characters in [1, i] and [k, n] (j characters in each part).
Actually, we also need to know the maximum index of occurrences that is less than k for each type of characters. In my submission 4225240, I construct a table in O(26n) for finding in O(1). In case the number of character types is large, this can be handled in O(log(n)).
So, overall complexity is O(100n + 26n) or O(100n log(n)).
Ken Ichi Kawarabayashi would say: "100 is a constant, alphabet's size is a constant, so B can be solved in constant time" :P
Thanks a lot for these nice, short and clear problems.
Why the problem-setters' nicks point to topcoder profiles instead of codeforces profiles?
Thank you for onsite competition!
It was perfect!
And congratulations to Seikang who won poker tournament!
Thanks for the contest and the onsite event! (great problems, awesome people, and tasty pies) Thanks for the poker lessons. I finally learnt! (and for the prize XD)
I'm glad you liked the pies (that was the true prize, of course).
+1 key lime pie, ping pong and beer :) Thanks MemSQL !
Damn! I missed the pies while walking around San-Francisco :(
BTW, I also enjoy the event very much but I still think that my performance was quite poor and I got the prize spot only by luck.
The onsite event was great indeed! Thanks a lot.
can you give me some hint on problem F?
Yes, it was great! I played the poker first time and it was funny :)
А как узнать какое место среди учасников, которые не вне конкурса?
Галочку сними)
А, ясно. Спасибо)
Will any editorial be published? I would gladly read solutions to E and F.
any idea to problem F?
It will be published on Monday.
"топ 100 участников из онлайн раунда получат специальные футболки start[c]up."<--в эти топ 100 неофициальные участники входят?
Надеюсь, что нет. Да и было бы логично, что нет.
Неофициальные не входят в эти топ100
Вот черт... Если бы я не слил первый раунд, то сейчас я бы получил футболку :(
Где разборы?
Thanks to MemSQL engineers for your contest. I was an offical participant (passed round 1) and finish the online contest with rank 74 (solved 2 problems). So when and how can I receive a T-shirt?
We will be sending them out shortly. Someone will contact you to confirm your t-shirt size and address very soon.
when would the editorial be published？
Yes, dolphinigle is polishing it up right now and will publish it as soon as it is ready.
Any news about the T-shirt?
Наконец-то разборы! Ура-ура-ура!!!
is there anybody knows something abouth T-shirts?
Has anyone received their t-shirt yet?
and now?
nope! anyone else?
Received mine today. Anyone else?
I've received my shirt now as well. Thanks for this!