Мы были вынуждены удалить регистрации, сделанные до 00:00, так как регистрационная форма на тот момент не поддерживала регистрацию команд. Пожалуйста, пройдите регистрацию вновь, если ваша регистрация была удалена.
Вчера завершился финал чемпионата VK Cup 2015, о котором вы могли прочитать в предыдущих наших постах. Осталось объявить последнее событие, связанное с прошедшим чемпионатом — онлайн-трансляцию, которая состоится в четверг 30 июля в 19:00 по Москве. К соревнованию допускаются как индивидуальные участники, так и команды из двух человек, которые желают почувствовать себя участниками финала соревнования. Трансляция продлится три часа, задачи будут перемешаны по сравнению с оригинальным порядком. Допускаются участники обоих дивизионом, но мы считаем своим долгом предупредить, что для участников из второго дивизиона набор задач, скорее всего, будет слишком сложным. Этот раунд является рейтинговым раундом Codeforces.
В заключение мы хотели бы поблагодарить всех людей, которые помогли чемпионату состояться. Придумывали и готовили задачи для вас сотрудники ВКонтакте, члены команды Codeforces и другие люди, любезно предложившие свою помощь: PavelKunyavskiy, burunduk3, Dmitry_Egorov, Kurpilyansky, dark_ai, MikeMirzayanov, Zlobober, MaximShipko, kuviman, Nickolas, Errichto, sankear и malcolm. Хочется сказать большое спасибо людям, прорешивавшим наши раунды, и дававшим ценные советы по поводу задач: winger и AlexFetisov. Также, мы благодарим всех работников ВКонтакте, с которыми вместе мы занимались проведением чемпионата: burunduk3, Burunduk2, KOTEHOK и многих других. Спасибо!
Всем удачи на онлайн-трансляции!
UPD: Обратите внимание, что во время раунда команде разрешается пользоваться только одним компьютером. Это значит, что программировать/пользоваться консолью/как-либо иначе продвигаться в решении задач в один момент времени можно только с одного компьютера. Единственное, что разрешается делать с двух компьютеров — это читать условия.
UPD2: Так как это командное соревнование, специально для вашего удобства мы выкладываем запароленный архив с pdf-условиями задач: vkcup2015-mirror-statements.zip. С началом тура мы опубликуем пароль к нему.
UPD3: В раунде будет использована динамическая разбалловка с шагом в 250 очков.
UPD4: По техническим причинам начало раунда переносится на 19:20 по Москве.
UPD5: Пароль на архив с условиями: vkcup4ever. Удачи!
UPD6: Онлайн-трансляция завершена! Поздравляем победителей:
- rng_58
- Zenith: I_love_Hoang_Yen, ngfam_kongu
- OrOrZZZ!: zld3794955, KFDong
- Petr team: Petr, ilyakor
- jcvb_matthew99: matthew99, jcvb
Мой персональный респектам команде Petr team: Petr, ilyakor за единственное решение по задаче Е в трансляции, пользователю rng_58 и команде Excited: YuukaKazami, jqdai0815 за два правильных решения по задаче С.
Также, поздравляем пользователя rng_58, который продемонстрировал, что одиночному пользователю есть что противопоставить командам, состоящим из двух людей!
Рейтинг будет пересчитан в ближайшее время.
UPD7: Разбор!
How it's going to be rated for teams?
Like this one I guess.
What is the rule for teamed participants?
UPD:Mike's comment on this topic
Why I can't register team?
Registration of teams will be available in 3-4 hours.
Thank you.
Would be pretty nice if CodeForces can start making some team contests every now and then. Maybe even make the rating effects lower if the CodeForces Team is worried about rating inflation. ( even unrated, but not sure how many people would participate).
Чувствую будет несколько человек которые будет возмущены отменой регистрации, например зайдя за пару минут до начала =(
UPD Как выяснилось я невнимательный, а у кф-а все схвачено =)
Именно поэтому я перенес раунд на 10 минут вперед.
I'd really like to take part in this contest but I'm afraid of this problems. Is my fear justified shuld I pass this one?
don't think too much about rating . Pleasure of participating with high rated coder is much higher than fear of losing rating :)
So not to cast stones or anything, but I was wondering why you guys consider rating team members individually a good idea. It feels like they're completely different skill sets. I remember TopCoder had a special SRM that lasted 4 hours and had super hard problems and they didn't rate it. I don't think they ever rated something else than a SRM-style contest. Codeforces ratings were already suffering from the fact that you can choose not to participate after reading the problems. This way it's easy for some people to only choose favorable problem sets. I know that it's their problem and all that, but it still undeniably affects rating relevance.
To me it feels that this move wouldn't do any favors to rating relevance. Again, you guys know better than me what you're doing and what you want the rating to reflect. I just wanted to know what your official reasoning is :).
Well, rating doesn't have any real relevance to begin with. Long-term, it's a good measure of one's skill, but that's it.
The thing with not being rated if you don't submit doesn't bother me much. If you don't try, your loss. But I'm thinking of skipping out on this round due to teams and individuals being rated together. A team simply has a huge advantage in time that the combined rating doesn't reflect properly. In a round for teams only/primarily, this isn't a problem, but I can't help but feel I'm at a big disadvantage to some people. I suppose I'll decide based on how teamy the registrants' list gets.
As far as I see, we didn't have big rated rounds with both teams and individual registrants. So, your words about:
aren't confirmed with any previous experience. For us this round is a good possibility to see how rating works in such combined conditions.
We do have a way to compete individually against teams, I've done so in many Gym trainings. It may not be the same thing, but it's something I can base my view on.
The type of problemset is also important. When the problems require more thinking, the difference between teams and individuals are bigger.
Xellos wrote his first comment when there was nothing about 1 PC per team rule. During VK Cup online rounds participants were allowed to use 2 PC, and in my opinion (and from my experience) it actually gives huge advantage. In this case "more coding" problemset is even worse comparing to "more thinking" one.
you said that problems will be hard can you compare the level, I mean for example the easiest problem will be harder that E div 2 ?
also it will be as usual if I didn't submit any problem score will not change ?
Yes, if you not submit any problem, score won't change.
The easiest problem here is like Div2 D, others are much harder.
Just curious, what is "much" harder? Is it Div1 D and harder?
Participate and you'll see ;)
Anyway, the final standings on the on-site are available for you, so you can make an estimation regarding the difficulty level of problemset.
MaximShipko Did anyone see this black man before ?
I've saw him before, cause I've worked with him in Codeforces for about 2 years :-)
Never
racist
I would like to joking with it, but i won't hurt someone ;)
stingray, codeforces
How many problems will be ? How about scoring ?
http://codeforces.me/spectator/contest/562/standings
Думаю при регистрации нужно сделать подтверждения второго участника команды, иначе можно с кем-то зарегистрироваться и он может об этом даже не знать.
Также, сейчас один человек может регистрироваться несколько раз: как индивидуальный участник, и в составе нескольких команд, если его регистрирует его сокомандник. И как в таком случае будет считаться рейтинг?
Maybe my question is stupid, but I cannot find the rules for teams anywhere: is it allowed to use more that one computer (i.e. write code in parallel)? I don't see it forbidden anywhere, but looking at the photos from onsite, there was only one computer per team...
Can you see any relevant way to control coding on more-than-one computer during online competition ? I think in this case it's free to be free :)
There are no relevant ways to prevent cheating in general, like 10 people participating from single account (some people do it, e.g. kutengine and black_horse2014), using multiple accounts, OCR'ing solutions for hacking, etc. Still, decent participants follow rules.
So, if organizers say that one team should use one computer (reasonable assumption, because these were the rules during the onsite), I will comply this rule.
Teams should use one computer. It will be a broadcast about it.
That's an extremely important information, which should be very well emphasized before start, broadcast at the beginning is definitely not sufficient. I bet vast majority of teams registered think that it will be possible to participate using 2 computers (being in completely different places, e.g. their own houses) and what do you think all those teams should do when they will see such a broadcast? They can't simply just use one computer if members are not in the same place.
Considering this and the fact that the onsite isn't at the same time as the online, I get the feeling that this contest is just begging people to cheat. I think I'll skip this one.
What does the fact you mentioned imply? I do believe that none of the finalists have spoiled problems to somebody participating in the mirror today because we explicitly asked them not to do that (and because I personally know more than a half of finalists, I really believe them). I don't see any other way how to use the fact that onsite isn't at the same time with the mirror.
Nonetheless, it's up to you whether to participate or not.
Come on, it's not like people who get to onsite rounds tend to help others cheat. I'm not exactly happy about teams+individuals (see my comment above), but screw it, I'm going to take it as a challenge.
Eh, sure, I like that logic. The only thing I have to lose is rating.
What's wrong with participating being in completely different places? They can still use Hangouts/Skype and coordinate who works with computer at any moment. Our OpenCup team (www.opencup.ru, it is mostly-russian ACM-like competition without age restrictions) does this all the time, and we never had any problems with coordinating, even with 3 people; with 2-people teams, it should be even easier.
(but yes, I agree that this should be announced more prominently; e.g. add it to this "You can register on the coming round individually or in 2-members team. It will be rated for all individuals and teams" green message displayed on top of the page)
to take part,or not to take part?!!that is the question...
I love that my presence in this contest but my rating :((
goodbye div1 and expert and Specialist and Pupil and Hello newbie for along time :((
Скажите, я могу сейчас отменить свою регистрацию, и зарегать новую команду, которая не участвовала в vk cup?
Да
По какой-то непонятной причине как раз команду, которая в vk cup участвовала, и нельзя регать...
Why am I not able to register? :/
This one has got to have the most bad-ass problemset this year!!! Am I crazy for participating?
Interesting, from registered list I can see that a lot of people preferred to participate individually
Some of us don't have a choice, because.
I don't have choice because of the same because :D
Будут ли задачи переставлены по сравнению с http://codeforces.me/spectator/contest/562/standings ?
Да, как упомянуто в основном посте, задачи будут перемешаны по сравнению с оригинальным порядком.
Упс, извини, я не умею читать.
Да, как упомянуто в основном посте
Я начал писать первую версию комментария, когда этой информации ещё не было.
Auto comment: topic has been updated by Zlobober (previous revision, new revision, compare).
Can I be reading my code trying to find bugs(as if it was printed) while my teammate is coding a different problem?
No, you can't.
Why? If he print his code by once computer, why not?
No, you can't!!!
I missed the registration because codeforces was temporarily unavailable :/
It is available ~1.5 minutes more. Hurry up!
I did now, Thank you
А в таблице результатов будут отображаться участники онсайта?
И будет ли для них раунд рейтинговым? =)
Very very nice problems. Big congrats ! Looking forward for the editorial.
Isn't the complexity of F n log n?
Yes, it is.
Then why did I get TLE :(
http://ideone.com/VTzU2z can anyone take a look and tell me why TLE?
Your method for taking input is too slow. Use scanf instead
Oh no!!! not this problem.....anything but this :(
Just make it a rule that whenever input size is around 106 use faster input
This is O(n*sqrt(n))
IDTS ...... for each a[i] you run the loop log(a[i]) times, at most
Very difficult contest (even the easiest one is already at Div1-A level, and the second easiest is at Div1-C level), but nice problemset nevertheless.
Anyway, how to solve problem A and G?
you can solve A with suffix array
first of all prove that this greedy approach is correct: select the two strings which have most lcp and match them
i think every matching that isnt max can be made into a max matching with 2-switches which the value of the matching increases everytime i cant really explain it really good just prove this i think it can be proved
anyway after that we know that maximum lcp is between adjacent elements in suffix array so just get a set and a linked list and do stuff :D
it can also be solved using trie, insert all strings(of both kinds) into the trie
then do dfs to trie when you are in a node and you already have visited all its children then if you find at least one string from each kind inside subtree of that node then match them
Well... now im depressed because i implemented my first suffix array and didn't think about the easier way :((
A — make trie of all strings from input. Then dfs and matching strings from the subtrees of vertices before leaving vertex.#em8kM5
I just saw this lmao
А D решается обычным деревом отрезков, не так ли?
DSU с сетом для выкидывания тех, кто внутри отрезков типа 2
Ну да, DSU у меня тоже есть, ок.
DSU для обычных объединений, а в set храним те вершины, которые не были внутри (строго) отрезков типа 2, их не надо дважды объединять, они точно будут вместе.
DSU + ДО на минимум + ДО на максимум, если пройдет систесты...
У меня какой-то стремный сет из отрезков со слиянием множеств за
суммарно. #dRjihv
А я пытался поддерживать для каждого элемент ближайший сверху элемент из другого множества. До сих пор слабо представляю, за сколько это работает =)
Но у Вас претесты прошло хотя бы! У меня свалилось на третьем претесте.
И не только претесты: 12278302
UPD. Я до сих пор не умею доказывать, что это работает быстро на всех тестах.
Кажется, эвристика сжатия путей (это ведь именно она здесь исполользуется, как я понял) сама по себе работает за логарифм...
Поиск next -то да, сжатие путей. Другой вопрос, что мне не сразу стало очевидно то, что обновлять next только у x и y — достаточно для любой комбинации запросов. Но да, это действительно так. Хех, забавную я вещь написал. И, кажется, многие так же писали.
Я писал 2 dsu (второй чтобы пропускать ненужные когда итерируемся слева направо). Должно пройти
У меня зашло со списком: для каждого человека поддерживаем ближайшего справа человек из другой комманды
Еще можно так:
Храним have[i] — правда ли, что весь отрезок [i; i + block_size — 1] находится в одной компоненте?
Используем эту информацию, чтобы не делать лишние merge-операции (в случае have = true, делаем прыжок размером block_size)
Ну и block_size = sqrt(N) :)
Я так и не придумал как делать за O(n·log(n))... :/
Вместо ДО зашел Фенвик + бинпоиск за O(n·log2(n)). А сет за такую же асимптотику упал :(
Долго решал F, несмотря на то, что вроде задачка эта где-то была. Потом пытался закодить D через ДО на минимум + DSU, но запутался в коде((
Какое соответствие между порядком задач в мониторе финала и порядком задач сегодня?
Случайное, описывалось в оригинальном посте.
UPD: Прошу прощения, только что понял суть вопроса:D
Меня постфактум интересует конкретная перестановка :)
Хотя можно более-менее догадаться, но хотелось бы какого-то проверенного подтверждения.
Can someone tell me what is the original problems order in the official contest?
I'll post it with an editorial in a few minutes, but you may try to figure it out by yourself =)
I think C — F — E — D — G — A — B.
I guess that G from mirror is E from onsite
Last hour I was thinking of B, had a very very simple greedy solution but cannot prove it's correct and not writing a byte for it (as so few ppl solving it, I was thinking well the solution should be very complicated), and in last 10 minutes, I thought that the time was running out and I just write it (in 2 or 3 minutes) and it passes systest lolz
Most solutions for G failed as expected (including my own)
Now me and jerry can say we solved a problem that YuukaKazami, jqdai0815 and scott_wu didn't solve. We're at the IOI right now and since we're obviously not good enough to beat them here, this is pretty much the closest thing to an IOI victory as we could have hoped for :D (and also nomnomnom delicious, delicious rating points)
Test cases were too weak for the last question!!
Be more specific, what wrong solution passes them?
EDIT: If you mean the pretests, that's working as intended.
OMG we are #2, I can not believe that I am not dreaming.. Now my life is complete. Thank you so much ngfam_kongu for coming up with solutions for most problems (I am just a coding monkey).
This "Convex Hull" passed the first 20 test cases :)
It is in my solution to G.
Я не могу посмотреть свои посылки с онсайта. Это нормально?
I failed G, because of I used int in cross product. I'm bored this stuff :(
How to deal with the range merging in D ?
For operation 1 and 3 let's use a standard dsu data structure. In order to handle unions in range operations, let's keep a data structure that stores intervals. When one interval [L,R] is added, remove all intervals that intersects it, i.e intervals [L1,R1],[L2,R2],...,[Lx,Rx] such that L<=Ri and R>=Li. This intervals are going to be merged into one, so in the dsu data structure, we have to join the vertices that are in those interval: join(L1,L2),...,join(Lx-1,Lx). Each interval is added and removed once, so the number of join operations in linear;
Это баг или фича, что некоторые пользователи(например palash012) получили + в рейтинг, решив 0 задач? :)
Ничего удивительного: при таком рейтинге достаточно не набрать отрицательное количество баллов, чтобы подняться в смешанном раунде.
You have thanked Errichto for his help in preparing the problemset . So shouldn't he have been restricted from participating in the contest ?
He gave us a great help while preparing an on-line round 2, not the Final round. So, there was nothing preventing him from participation in this round.
Соревнование было интересное,но у меня просьба к организаторам:можно на такие задачи как D поставить такое маленькое черное предупреждение "используете scanf вместо cin" а то я потерял 40 минут и все очки на эту задачу посылая с "ios::base sync_with_stdio(0)",думаю многие согласятся.
А почему не писать эту строчку всегда в начале кода?
я писал но ничего практически не изменилось,сколько методов не перебрал получилось только когда сделал с "scanf".