В пятницу, 17-го апреля, в 19:00 начнётся Раунд 2 чемпионата по программированию VK Cup 2015! Не забудьте зарегистрировать вашу команду на раунд, регистрация закроется за пять минут до его старта.
В этом раунде могут принять участие все те команды, которые отобрались в Раунде 1 или в Уайлд-кард раунде 1. Напомним, что из первого раунда допущены все те команды, что набрали не менее 796 баллов. В уайлд-кард раунде было достаточно решить не менее шести задач, либо решить пять задач со штрафным временем не более 415 минут. Таким образом, принять участие в Раунде 2 могут 400 + 50 = 450 команд!
Участников ждет соревнование по правилам классических раундов Codeforces. По сравнению с Раундом 1 вас ждут некоторые изменения. Во-первых, одновременно с основным раундом будет проведена интернет-трансляция, которая представляет из себя обычный рейтинговый div1-раунд по правилам Codeforces. В трансляции может участвовать любой div1-участник, не зарегистрированный на основной раунд в составе отобравшейся команды.
Во-вторых, вас, как и ранее, ждёт плавная динамическая система оценки задач, но сами задачи будут расположены в случайном порядке. Участникам будет предложено 6 задач.
Раунд подготовлен силами команды Codeforces, команды VK и пользователя Errichto, который предложил свою неоценимую помощь в рамках кампании "5 лет Codeforces". Большую помощь в тестировании задач оказал winger.
Напомним, что в Раунд 3 пройдут все те команды, которые наберут положительный балл, не меньший, чем у команды на 100-м месте. Также обращаем ваше внимание, что все команды, проходящие в Раунд 3, получат фирменную футболку Чемпионата. Помимо этого, фирменной футболкой будут награждены топ-50 участников интернет-трансляции Раунда 3.
Желаем удачи и интересной борьбы!
UPD: Благодарим всех за участие! Появился разбор задач. Ждём вас на Уайлд-кард раунде 2 и Раунде 3!
Shuffled Randomly.. this will be interesting :D
Not for all!
Футболочку бы..)
Is it a rated event?
For all unofficial participants there will be an online mirror that is a usual rated div1-round
Is that an official statement? Could you please point to the source?
EDIT: Thank you very much. I thought the text was the same as the one sent by email, but it isn't.
Just read this topic...This Friday, April 17th, 19:00 there will be Round 2 of VK Cup 2015! For all unofficial participants there will be an online mirror that is a usual rated div1-round. Any div1 contestant that does not participate in official Round 2 is able to compete in this mirror.
Here is the official statement
I hope that pro A will be the easist one, not pro E like last time.
Why I can't register for the round. Div1 participants can take part in only div2 rounds why we div2 participants can't take part in only div1 rounds unofficially ?!
because u can't even solve problem A div2
Actually he can. I know him personally. -_-
do not judge people by their rating!!!
Hey Sosiska, let's compete in Round #300. Are you in ?! Let's see who is unable to solve problem A !!!
The time is not so good for Chinese Coder... Because such a challenge contest will happen at 0:00 a.m. CST and until 2:30 a.m. CST. Maybe waiting for rating updated until 3:00 .. and 9:00 a.m. CST there is a google code jam Round 1A. I don't want to miss any one...
Оба участника нашей команды знают русский, но не очень хорошо. Поетому, наш производительность уменшается когда условия на русском. Хотел бы знать, можно ли условия задач читать из неофициальной трансляции (где наверное будет условия на английском), и участвовать на официальном раунде?
Думаю не так будет... Все задачи будет на русском. Удачи всем!
Вы можете читать и английские условия, но надо помнить следующее: на Финале будут только русские условия, официальными с точки зрения VK Cup являются русские условия (например, возможная ошибка в английских не будет влиять на подведение результатов этапа Чемпионата). Удачи!
Отлично, спасибо.
А сможет ли прошедшая на раунд 2 команда участвовать в следующем wild-card, если не зарегистрируется на этот самый раунд 2?
Да.
А я правильно понимаю, что регистрация на этот раунд доступна тем и только тем, кто прошел после раунда1/уайлд-кард1?
Если это не так, то зачем тогда раунд1/уайлд-кард1?
Просто я, например, могу зарегистрироваться. Но вроде бы не прошел раньше. Вот и не могу понять: мне радоваться, что пускают, писать и молчать в тряпочку — или накалякать багрепорт? =)
А вы уверены, что вы действительно можете зарегистрироваться? Форма регистрации предполагает жесткую валидацию в конце процесса.
Да, прошу прощения, поспешил.
If the team takes place in top 100, will they receive 2 t-shirts?
Only one XXXXL.
Yes
Thanks a lot
Случайный порядок только для официального соревнования? Или для зеркала тоже?
В обоих местах. Казалось бы, в чём тогда смысл случайного порядка в официальном соревновании, если порядок по сложности можно подглядеть в зеркале...
А где будет трансляция??
Здесь: /contests
И еще, если не лень, прочти это.
I just read two random problems and decided that don't want to compete in this match :(
Our team advanced to round 2 and I have no idea where is the original round 2.
I had to turn language to Russian. You could write the same post on English language. Nobody told me anything. You could email for example. What is the mean of turning off the registration? please at least turn it on!
>What is the mean of turning off the registration?
Allocation of participants to rooms.
You got to round 2 and only noticed that the official round is visible only there just now? How did you open the qualification round and round 1, then?
Yeah, there's probably no point in putting the Russian-only round to the English part of the site other than wanting to see blogs "I can't register in the official round, help!".
It is Russian-speaking only Championship and the rounds are visible in Russian interface only. The schedule has been published in the day of Chanpionship announcement ~7 weeks ago and never changed.
So hard! I will get down rating !
E хешами решается или это у меня руки такие кривые, что ТЛится (тест 22)?
Сабмит 10754440 Пока что код недоступен, http://paste.ubuntu.com/10840126/
Там всего 2 сравнения строк нужно сделать, хэши нужны разве что на антихэш-тест попасть.
Тем не менее я не понимаю, почему этот код, а также все его оптимайзы получают ТЛ22.
Так может как раз антихеш-тест? Не даром же Zlobober статью писал.
Так там кажется по модулю
Ну у меня стоит модуль 1e9+9, а антихештест вообще на WA ловит ведь.
Самое смешное, что я сам стараюсь подобный тест в тестсет без специальной надобности не добавлять, но вот сегодня посреди тура решение одной команды было почелленджено именно строчкой Туэ, поэтому в итоговом тестсете она всё-таки оказалась.
Я бы челенджил и решения с константным выбором точки в которой считаем хэш... :)
Складывать в set 5000000 записей — плохая идея.
Спасибо, понял, где собака зарыта.
P.S. unordered_set, где элемент это
(h1 << 32) | h2тоже не прошел :(How to solve E? I wasted all the time on it but my hashing+unordered_map solution didn't pass pretest 22...
Answer can either be 0, 1, or 2. Take the substring from the the first occurrence of different characters to the last occurrence and check to see how many original strings you could have had.
It's not true. If we have two equals strings the answer is not 0, 1 or 2.
Edit. Ouch, reading the statement twice don't help =)
and we can't have tho equal string according to statement.
That's what I was solving but the 'Input' section mentions that given strings are distinct. I noticed that only after trying to hack with similar strings.
And I don't understand why such essential information was only given in the input format.
Yeah, was going to whine about it. Turned out that I spent quite a lot of time solving a bit different problem. I agree, it should have been mentioned in the problem statement as well as in the input.
Same is true for B as well, the only part that confirms that the graph is indeed a tree is the input section where it says that pi < i
"Implement a program that can, given two distinct words S and T..."
That's main part of the statement.
Ok, you proved once again that I can't read:(
It's guaranteed that two string are different. :P
S and T will not be same strings.
Even if they could have been then it would be really hard to express the answer without modular arithmetic.Takeaway: It's OK to take part in contest at 2:00 AM — 4:30 AM but shouldn't have written comment at 4:30AM in the morning.
If the strings are equal, the answer is 25 * n + 26
I don't think the answer may exceed O(len) * 26
Why? Even if they are same max answer is approximately 26 * N since we care only about distinct original strings.
wouldn't in that case ans be 26 * (N + 1) ?
No, consider the case "aab". If you insert 'a' before the first char and before the second char, you'll get the same strings. The answer is 25 * N + 26, as I mentioned above.
In this case it depends on the string. For example
The answer here will be 25 + 25 + 26.
So you may not use hashes, just find first mismatch in the strings and define in which of them a symbol was deleted exactly in this position (e.x.
s[i+1]==t[i]if a symbol fromSwas deleted, next I will consider this case).Then create two copies
T1andT2ofTwith erased symbol inserted before and after position of deleting.Finally, you need just to check if erasing a symbol from the second position of mismatching will lead to a string which is equal to
S. If bothT1andT2may be equal —ans=2, if one of them —ans=1, if no one —ans=0.I hope it will pass system testing! :)
Отличный контест от вк, теперь пойду в вк посижу :D
Effect of shuffling and tricky questions: Only half out of all registered people submitted their solutions :/
My teammates message(20 min before end): "როდის იწყება ეს დედანატირები მე-2 რაუნდი" ("When vk cup 2nd round will be held?"), Fuck Him -_-
How to solve F?
For each possible position and each letter present in t find the candidate letter for the replacement (it might be the same letter). Change s so that these two letters will be swapped and the remaining characters will be replaced with some separate symbol ('*' for example) , it will be kind of mask. Then for each such pair and the possible position you need to check whether this mask from s matches similarly masked t. In valid positions masks for all letters should match. In order to check masks I computed z-function for each possible pair of characters in advance.
Thanks for the explanation! Link to marat.snowbear's implementation 10759593, which is very clean.
Which is also very slow and takes a lot of memory so I even had to avoid storing full z-function vectors. But I don't hash, so I had almost no choice.
In prob -B what is the ans of 7 -1 3 1 2 1 1 1 4 4 2 4 3 5 5
17 I suppose
No, the answer should be 14. Take 1, 2, 4, 5, 6.
EDIT: I misunderstood the problem. The correct answer is 17.
Our AC solution says that the answer is 17
Take 1,2,4,6,7
thnx .
If you take 1,2,4,6,7 won't that become disconnected since 7 is connected to 4 via 5?
answer can be disconnected . there is just one condition in the problem statement that if i take a node then i must take even number of node in its subtree . answer is 17 here
Thanks. Couldn't solve it just because of misunderstanding the problem :(
То самое чувство, когда исправляешь баг в F, смотришь на часы, а там меняется 21:29 на 21:30 >_<
I can't seem to submit offline. When will we be able to do this?
It's possible now.
Is there anything special about test case #35 in problem F? Seems like quite a lot of people failed on it.
Anti-hash?
Seems no. Our solution based on Z function also got WA on this test.
My guess is that it's for errors in pairing logic check, e.g. I add only one "edge" in letters map (forgot to add reversed one). But can't check it until the problem is opened for practicing..
You are right. I was just not completely clearing some array. Seems that everyone has it's own bug, and the 35-th test is just a good one.
For example my code failed on #35, and also fails on this simple test:
2 2 bc ab
(answer 0)
Almost all possible compilable codes fail both on #35 and your simple test :D.
System Testing is over . why cant we submit in practice.
My solution of F:
if we fix the substring of S (its first letter) to match T to, we can recover the pairing of letters: just remember one occurence of each letter (a-z) in T, look at the letters that are matched to them and here it is!
we can check if the given substring of S has the same hash (easily computable using polynomial hashes of prefixes) as T after the pairs of letters are swapped — the hash of T is just
, where ki is a constant dependent only on the letter i; specifically, if 
(letters s[i] are numbered from 1 to 26), then 
over all i such that s[i] = c.
for better accuracy, do it for two polynomial hashes
Same solution, just used big module instead of two hashes 10759121
We had similar solution, but from a bit different angle. For a string, let's assign a number to each character — the distance between the nearest same character on the left (or 0 if this character is the first occurrence in the string now). For T it will be constant, for S it's easy to see that we can modify the hash as we're sliding the window — potentially subtract some power if it becomes 0 after the window slides, and add new character (we do not have to remove old character since it's the first occurrence and it's 0 anyway).
Now, if the hashes match, we have a valid permutation in this position and only then we have to take first occurrences of 26 letters and check whether our permutation forms pairs.
По моему, давать С и Е в один контест была плохая идея. Какие-то случаи, что-то там разбирать.
Ну в Е динамику можно было написать.
Так а зачем разбирать?
В Е пишем полный перебор хешами, в С жадность — второй пытается идти к цели, первый пытается идти к диагонали, на которой стоит второй (чтобы заблочить его).
В Е красивая идея, по-моему. Ищем первый несовпадающий символ в обеих строках (s1[i] ≠ s2[i]). Понятно, что в одной из двух строк символ с индексом i пропущен. Рассмотреть эти два случая, и все.
Я так хотел футболку, что до систестов, попав на 51-ю строчку, очень надеялся на то, что у кого-нибудь что-нибудь упадет. Упало! У меня первая же сданная упала! Тем не менее, это все равно позволило подняться на одну строчку вверх и влезть в "футболки".
Не хочу портить радость, но получают же топ 100? :)
Я про неофициальных, официальные сто получают. Хм, пошел перечитал. А про неофициальных написано, что получают лучшие 50 раунда 3, т.е. следующего раунда. Как так? Господин ведущий, это опечатка?
gen попытался испортить радость, но у него не вышло.
Пробема слегка в другом. В анонсе не очень хорошо написано... но футболки раздаются не в интернет-трансляции этого раунда, а в интернет-трансляции раунда 3.
Условно говоря, все прошедшие в раунд 3 в официальном соревновании выигрывают её сейчас, а все не прошедшие плюс все неофициальные желающие имеют шанс побороться за неё в онлайн-трансляции третьего раунда.
Zlobober попытался испортить радость, и у него вышло.
Целый вечер все по диагонали читаю, то условия, то правила. Я правда не очень понимаю, зачем в этом анонсе (где глаза ищут "футболки") писать про футболки, которые будут потом. Ладно, зайду попозже.
Не понимаю, что, имелось в виду раунд 2?
deleted
Для тех кто не прошел, когда появится информация про wild-card round? Будет ли он действительно идти всю неделю, повлияют ли время отправки решений на итоговую таблицу?
Looking forward to upsolving!!
Zlobober, fix this, pls!
Enabled upsolving in the mirror contest.
Why tests for E problem can not be seen?
(upd) You can find it in Vk Cup Round 2 log
Зато теперь шапочка на авке под цвет подходит.
Did you simply forget to make submissions public? If not, what is the reason behind it?
The upsolving is available in the mirror contest.
I know, what I meant is I can not see other's solutions.
I was a bit surprised, this is a team contest but rated? http://codeforces.me/contest/532/ratings
Yes. It was a lot of posts and discussions about that at the russian side of CF.
tourist has not seen such a gain for quite some time. Maybe he should have gone in the same team with worse, he would gain even more :D.
WAT? На какой ЦФЕ?
CF — сокращение от Codeforces.
вроде все говорят "на КФ"
От bredor нахватался, должно быть.
Синие да зелёные повылазили.
Спасибо за оповещение в начале контеста о случайном порядке задач.
Tourist graph be like: Stop me if you can.
Could you please link to English version of editorial (or to both versions at once)?
Спасибо, было интересно!
Не получается отослать задачу в дорешивание, пишет что соревнование завершено, кто-то еще сталкивался с такой проблемой?
Solved — костылями добрался до интернет трансляции ( в списке соревнований у меня пусто), там сдавать можно.
Видимо, можно просто из архива послать.
Нашел , странный порядок задач в архиве.