В понедельник, 28-го марта, в 19:35 будет дан старт Раунду 1 чемпионата по программированию VK Cup 2016! Я (Radewoosh) и Kamil Dębowski (Errichto) подготовили для вас комплект задач к этому раунду.
Не забудьте зарегистрировать вашу команду на раунд, регистрация закроется за пять минут до его старта (но позже будет продлена в дополнительное время).
В этом раунде могут принять все те команды, которые прошли квалификацию. Напомним, что из первой квалификации допущены все те команды, что набрали не менее 4800 баллов. Таких оказалось 505. Вторую квалификацию прошли 956 команд, все те, что набрали не менее 500 баллов. Таким образом, принять участие в Раунде 1 могут 1461 команды!
Участников ждет соревнование по правилам классических раундов Codeforces с некоторыми адаптациями:
- в Раунде 1 будут участвовать команды по 1 или 2 человека, разрешается любая коммуникация внутри команды, но какое-либо общение с другими лицами по прежнему, конечно, запрещено;
- каждая команда может использовать один или более компьютеров по своему усмотрению (напомним, что в Финале команде будет дана возможность использовать только один компьютер);
- для членов команды рейтинг будет пересчитан одинаково, исходя из рейтинга команды (учитываются зарегистрированные на раунд члены команды), о подсчете рейтинга команды можно почитать здесь.
Отметим, что одновременно с официальным раундом чемпионата будут проведены онлайн-трансляции: VK Cup 2016 — Round 1 (редакция для Div. 1) и VK Cup 2016 — Round 1 (редакция для Div. 2). Фактически это будут классические Codeforces-раунды для всех тех из вас, кто не участвует в VK Cup 2016 или не прошел квалификацию.
Все три варианта проведения будут рейтинговыми.
Мы хотим поблагодарить GlebsHP за помощь в подготовке задач и MikeMirzayanov, потому что без него бы не было замечательной платформы Codeforces, где мы соревнуемся и тренируемся.
В понедельник вам предстоит снова помочь Лимаку, вашему любимому медведю. В этот раз это, возможно, будет чуть сложнее, ведь злой Радевуш будет пытаться мешать Лимаку.
Напомним, что в Раунд 2 пройдут все те команды, которые наберут положительный балл не меньший, чем у команды на 400-м месте.
Желаем удачи и интересного соревнования!
UPD Разбалловка:
For VK: 500 — 750 — 1000 — 1500 — 2000 — 3000
For Div.2: 500 — 1000 — 1500 — 2000 — 2500
For Div.1: 500 — 1000 — 1500 — 2000 — 3000
UPD Разбор уже готов.
UPD Поздравляем победителей!
В чемпионате VK Cup:
1.Never Lucky: subscriber и tourist
2.SobolevTeam: Seyaua и sdya
3.LNU Penguins: witua и RomaWhite
4.Dandelion: Um_nik и sivukhin
5.uıɟɟnɯ ɐuɐuɐq ǝɥʇ ɟo uɹnʇǝɹ╰(º o º╰): enot110 и romanandreev
В Div.1
1.dotorya
2.kcm1700
3.JoeyWheeler
4.KrK
5.Swistakk
И в Div.2
1.osmanorhan
2.nhho
3.fudail225
5.agaga
4.alanM
Отдельное спасибо qwerty787788 и AlexFetisov за тестирование задач, ценные советы и рекомендации!
Standard important question — are people from one team allowed to use more than 1 computer / are they allowed to use more than 1 computer simultaneously (in case they are far from each other and they literally need to use two computers)?
EDIT: Not valid anymore.
Yes, it's allowed during all rounds except final:
http://codeforces.net/blog/entry/43757#comment-284079
To participate individually or To participate with your friend, that's the question!
UPD: To participate individually it is!
How would rating change be calculated with both teams and individuals in the same contest ?
Yeah!I have increased 154, and I am very lucky as for having 7 successful hacking attempt.
I'm sorry if this question seems silly or repetitive, but will 2 person teams be allowed for the unofficial version too?
Blog was updated, now it seems like we have to compete individually.
A shame, and I was looking forward to doing a rated contest as a team too.
We consider the possibility to make such an experiment in the nearest future! :-)
I am kinda afraid that all those contests with individuals + teams will make even greater mess with rating system than what it is right now. Hope I'm mistaken.
EDIT: Yay :)
Auto comment: topic has been updated by Radewoosh (previous revision, new revision, compare).
Why did this get downvoted? :D
Check
А давайте перенесем соревнование еще на 2 часа вперед. Ведь писать парные контесты ночью так удобно!
For how long this round will last?
Both official and unofficial version will be 2-hour long.
I feel old when such young people are problemsetters.
Will all the problems be the same for the three contests?
when div1 and div2 contests are separated, it usually means that problems will be the same
Will the problem statements be available in English?
Yes
А менее одного компьютера использовать запрещено?
смартфон/планшет
Мозг-лучший компилятор, а листок-среда разработки!
Will the problems be sorted by difficulty? In VK Cup 2015 the problems were not sorted.
If not, will the ordering be the same for all 3 versions of the contest?
It says "Div.1 and Div.2 editions will look like normal CF round". So answer is yes i guess, at least for unofficial versions.
Why does this answer get downvotes, can anybody explain? I confirm what muratt wrote — yes, problems will be sorted. And you will see the number of points for each problem. Just a normal CF round (without any dynamic scoring).
Yay!
Looking forward to Bear and Forgotten Tree 3
and it comes true
Hour 16. Still nobody asked whether this contest is rated or not. Something isn't right.
All 3 contests are rated
I know but by tradition someone asks anyway.
why dont you ask :)
I don't want negative contrbution. :D
"ведь злой Радевуш попробует будет пытаться мешать Лимаку."
Поправьте там.
Ignore this comment
Limak = reverse(Kamil).
Finally life makes sense!
I thought Errichto is his name lmao
That is not true origin of that bear's name. Errichto really likes trees (those growing from bottom to up :P) and "limak" is a name of type of tree, namely "water elm, Ulmus laevis (Eurasian elm closely resembling the American elm thrives in a moist environment)"
And why is Limak a polar bear (or any bear, for that matter)?
This will be my first VK cup....looking forward to it :-) Btw thanks to MikeMirzayanov for allowing registration during contest feature. It will be great.
There is no register option for the contests
If I had 500 points can I write it?
For the love of tradition
Is it rated?
No downvotes? This is becoming less fun these days
Just kidding :D ... I hate downvotes just as much as the next guy
YOOOO Limak is back! HYPE THIS UP GUYS ♡♡♡
Can we participate in Div2/Div1 rounds if we haven't participated in the qualification rounds?
Yes
"so everybody is invited to take part in the competition!"
Я на сайте не так давно и мне непонятно, что обозначают дивизионы. Кто в них входит?
Div1: все участники с рейтингом ≥ 1900.
Div2: все остальные (включая новобранцев).
Почему тогда ты не Div1?
Ой, ошибся. Конечно, не 1700, а 1900, так что спасибо :)
В чём разница между регистрацией как "Индивидуальный участник" и как "Команда из 1 человека"? VK Round 2
Неважно, я написал фигню.
А чем тогда отличается "Индивидуальный участник" от 2х редакций идущих параллельно с основным соревнованием?
Похоже, я опять ошибся. Я подумал, что "Индивидуальный участник" = неофициальная редакция раунда.
Just 260 people registered for Div1 edition, from which not all will participate. Isn't it better to make the round (the div1 and div2 edition) combined?
It won't be changed now.
Btw. the situation wasn't that different one year ago. There were 438 div1 pariticpants with at least one submission. There is still a couple of hours left here so I guess there will be enough competitors to make it fun and interesting.
Either way it will be fun solving the problems :)
I just taught if there are less participants it could mess up the rating a bit.
I thought I was mistaken about the starting time when I read this, so I went to see the starting time and I turned out to be correct, so I used dictionary to translate "couple" to make sure I know the correct meaning of that word :D
I used google translate but it only showed "two individuals of the same sort considered together." anyway when the comment is posted there was about 7 hours left, which is not that small and not near 2
Couple: 2 (always)
Pair: 2 (of the same type)
A Few: 3-6
A Handful: 3-6, but most often 5
Several: 3-7 (and not identical)
Some: 2-10+, can be used with continuous quantities
Gotta write this on a cheat sheet.
Hasn't tweety posted an image from dictionary that positively proves that "couple" is not always "two"? By the way I should not be an authority when it comes to English correctness, but I use "couple", "a few" and "several" (but not "pair") in more or less the same meaning.
Colloquially, its used loosely as few but literally, couple means two
I won't count on this holding in any formal problem statement. Specifically, "several" usually means "0 or more".
Obligatory xkcd
I can't believe noone posted this... :D
(https://xkcd.com/1070/)
Edit: And after 9 HOURS, somebody posts it WHILE I'M WRITING? Seriously? :D:D
People are fighting over couple >.<
Seriously, nobody posted this before and someone posts it epsilon seconds after me and complains about it? :D
Thanks people, nice English lesson. You guys should do it more often. :P
Ссылка
Is this contest writing in English?
Problems will be in English and in Russian as usual.
oh,thanks
Задачи будут располагаться в порядке возрастания предполагаемой сложности?
да
Почему я не могу у отредактировать команду? Когда регистрация только открылась, я не думал, что второй член нашей команды не сможет участвовать. Поэтому я зарегистрировал команду из двух человек. Теперь получается странная ситуация: с одной стороны я хочу участвовать, однако с другой я буду в заведомо проигрышном положении (я пишу один, но рейтинг считается как будто нас двое). Можно ли это как-нибудь исправить?
Уже понял, как отменить регистрацию, извиняюсь)
Возможно тупой вопрос, но у div. 2 версии ведь часть задач будет отличаться?
What's the scoring distribution for the division 2 contest?
Ahhh... I want to get green today. :/ Huh !
Участников постоянно перекидывает из комнаты в комнату. Я, например, то в 8 комнате, то в 12. Проблематично в таких условиях взламывать.
Да, были с этим какие-то проблемы. Пока не понятно почему. Будем разбираться.
Так можно же зато в обеих повзламывать :)
When I'm on hacking at problem A, at first I'm on room 1, then I moved to room 10 unexpectedly! While reading other submission code, then I moved again to room 1! And again moved to room 10!
Not only that, sometimes I can't even open another submission (for problem A which I had locked before). And other than that, the notice of "The solution has been hacked or resubmitted" popped out most of the time, while they aren't!
Bug?
Actually, I do not know reason right now, but I'll investigate it. Sorry about it.
Thanks MikeMirzayanov, :D
Anyway, I got AC on problem A. But somehow on my room standing (now it's room 1), it shows 0 AC. Same case with matthew99 and sleepyhunt.
Am I the only one that travels through different rooms and cannot hack properly?
You can only hack in your room
I meant that after clicking my room, I am sometimes sent to room 6, sometimes to room 8 (where I am). Moreover, I can see some solutions from both rooms and some of them I cannot see at all.
Ok, now I moved to room #6 :]
I am also getting "This solution has been resubmitted or hacked." a lot (just like athin), but it is also invalid...
При взломе плохо отображается код: то съезжает, то нельзя прокрутить его до конца :(
Раунд!
Hackerfest again. Spent last 40 minutes F5ing the room... :-\
What was hack for C?
3 1 1
The answer is -1.
Two Solutions in my room which looked "hacky" but I couldn't hack due to spending time on C too much fails in this case. (just tested now)
With a rush of fear, I opened my code. And it gives -1 (Thanks Almighty)
I only hope there isn't more like that on system tests.
I hacked 7 times with 3 1 1.
I hacked a solution with : 5 1 1
100 1 1
Also, any idea of pretest 5?
I had 3 WA before passing pretest 5. My code was failing on cases such as 6 3 3 (ans is not -1)
why ans is not -1 , can you give an example ?
isn't d=4 for this example.
d = 4 -> 3 -> 2 -> 1 -> 2 -> 6
No, because the diameter doesn't have to go through the root(1). It's:
d = 4 -> 3 -> 2 -> 6
or
d = 4 -> 3 -> 2 -> 1
you have gone through "2" twice.
1 2
2 3
3 4
3 5
3 6
edges 1 2
2 3
3 4
2 6
2 5
5 2 2
8 6 6
try 10 5 5
ans:
1 2
2 3
3 4
4 5
5 6
5 7
5 8
5 9
5 10
I am pretty sure some people disappeared and then appeared again in my room — http://i.imgur.com/05MyTRC.png, http://i.imgur.com/kTZ7xFB.png :)
What is wrong with my code for DIV2 C : code
check out the case h==d. when n >= h+1 there is a solution and otherwise there is not
For this case :
4 2 2Your solution gives:
As far as I can see
You first create a path of length H and then a path of length D-H . then attach the remaining nodes to the root .
If D==H you can't attach the remaining nodes to the root because that just increases the diameter . Instead you should attach them to node 2.
Hope this helps!
C...
EDIT: this post contained some doubts about div1-D, but everything is clear now.
Maybe someone can find this useful: a proof that c does not matter when choosing an optimal order.
We're maximizing the score, which is
where xi is when we are done with problem i. To maximize this, we should clearly minimize 
, which does not depend on c. (To minimize this weighted completion time, we should sort the problems by the so-called Smith's ratio 
. We have freedom when these ratios are tied, but again this does not depend on c.)
Your proof is correct. However, in case of several optimal solving plans, some of them might produce paradox, while others do not.
Will BigInteger work for Div2 D ? Got 5 seconds late in submitting solution :'(
got tl on test 8 with BigInteger. http://pastebin.com/zMQbDyL1
I don't think so but I think we can solve it visualising the bits in the coefficients everytime they get multiplied by 2 there is a left shift of 1. We can easily see whether the a_k will be an integer or not!
I think we can similarly find when will the co efficient exceed k. I didn't even tried it just because I was so busy in hacking !
+9 hacks :D
I don't think you should evaluate the whole thing. I think that only the last 30 or so coefficients matter (something depending on log2(k)).
My idea was to work only with the last coefficients, If I had more time I would have tried a binary search on each one of the last coefficients to know if the coefficient can make 2 a root. Can someone confirm this idea?
It's not necessarily the last 30, consider the following polynomial:
1 0 0 ... 0 0 0 ... 0 0 -2 1
I solved it the following way. First, bring the polynomial into the following normal form: write
where 
. This is a simple preprocessing step (push ai / 2 (integer division) to ai + 1).
After this, let k be the smallest value such that bk ≠ 0. That is, |bk| = 1. This means we either add or subtract 2k. Clearly then, changing some coefficient k' > k will change the value of the polynomial by steps of size 2k' > |bk 2k|, so all these coefficients are irrelevant. Similarly, if k' < k - 30 then we cannot change ak sufficiently to shift the value of the polynomial by more than 2k. So we will consider changing the values k - 30, k - 29, k - 28, ..., k.
Suppose we have fixed the coefficient we want to change, say k. We have already established that the current value of the polynomial is divisible by 2k (since k is smaller than or equal to the smallest index i such that bi is nonzero). Therefore, we certainly can change ak such that the polynomial becomes zero, the only question is whether we won't violate the constraint that |ak| ≤ K (K is the input value, k is the index we are considering).
We can solve this problem in a really nice way: the current value of the polynomial is either positive or negative. This is only determined by the largest nonzero index in the bi. Suppose the current value is negative. Then we simply add K - ak to bk, propagate this, and check if the polynomial is now positive or zero. If it is, increase the answer by 1. You can implement this last check in such a way that you only have to consider the indices k, k + 1, k + 2, ..., k + 30.
If we say that the 30 we used above comes from
, then the final complexity is 
.
Solution: 17002298
Thanks for the great explaination and for the counterexample !
Explanation: I code a solution with complexity
because I see TL is 4s, but it TLs by a small amount. It seems that intended solution should run in well under 1s.
Edit: I coded an optimized version after, and get WA. The bug?
instead of I don't even...Feature request: переключатель на таблицу, где не учитываются хаки.
writing for(int i = n — 1 ; i > 0 ; i -- ) instead of for(int i = n — 1 ; i >= 0 ; i -- ) is the worst reason to get your A failed :(((
Are there any kind of optimizations being done on this code: http://codeforces.net/contest/658/submission/16992448 ? I was gonna try to hack it as it seems like bruteforce (couldn't though, short by few seconds :| ). But it passes main tests too
Edit: nvm i didn't read k <= min(6, n) carefully...
1 ≤ k ≤ min(6, n)
Damn, i feel stupid now. I was somehow interpreting it like max and coded even considering that only :\
I didn't see that too, so i used priority_queue and got accepted, i was expecting a TLE :3
it's not brute force !
k <= min(6,n) so in worst case the set's size will be 6. so answering queries is O(1) .
he is using set and k <= 6 so it seems ok
I'm afraid there were some problems with the hacking system today. When I tried to open a solution of my roommate, it said "This solution has been hacked or resubmitted..." However, after I reloaded the room page for several times, the hacked verdict didn't appear on the standings. Also, according to the standings, at this time, there were only 2 successful hacks, but the above problem happened with 5-6 solutions.
Did anyone have the same problem? It wasted me a lot of time to hack :((
I did. I explained below what happened to me =/
Auto comment: topic has been updated by Radewoosh (previous revision, new revision, compare).
what is D 7th test?
100 1000
-62 57 -27 -67 49 -10 66 -64 -36 -78 62 -75 -39 75 -47 -36 41 -88 62 -43 22 29 -20 58 40 16 71 -2 -87 12 86 -90 -92 67 -12 -48 -10 -26 78 68 22 -3 66 -95 -81 34 14 -76 -27 76 -60 87 -84 3 35 -60 46 -65 29 -29 2 -44 -55 18 -75 91 36 34 -86 53 59 -54 -29 33 -95 66 9 72 67 -44 37 44 32 -52 -34 -4 -99 58 7 -22 -53 11 10 10 -25 -100 -95 -27 43 -46 25
According to the checker
I am Batman!
:O YES SIR YOU ARE!
Broken cat =(
Just one comment about C. It seems to be the type of problem where there are two very distinct solutions:
The intended one which iterates over the remainder of the value in O(n) or O(nlogn)
Mine (and some others) that iterates over the value itself in O(nlognlogmaxT)
The issue is that the first step of the solutions are not similar. I thought of the slower solution first, and after getting TLE 8, I did the usual of trying to optimize out one of the logarithms, which failed. I never really stepped back and redid all of my thinking.
How should I deal with this situation in the future? Anyone have any tips?
(also I had the same hacks problem everyone else was referring to — getting put in random rooms, and especially bad, sometimes the other room still had my score in it and I just thought CF was slow when the solutions didn't load)
One trick I use is to look at submission times of other contestants. If they submitted very fast, solution is probably pretty simple (easy implementation). I thought about solution 2 as well, but it seemed too messy and I doubted other contestants could implement it in such a short time.
Did anyone else got moved to another room during the challenge phase? While hacking I kept getting a message "the solution has been hacked or re-submitted" only to find out that after the refresh I'm in a room I'm not assigned to... This kept happening until the end of the contest, I had to refresh several times each time to get to my room and actually be able to open a solution. I suppose the new feature with after-registrations is somewhat buggy.
When will be the problems added to practice?
Хоть я никуда и не прошел, но мой код по Бэшке короче многих топов ****счастье**** http://codeforces.net/contest/639/submission/17004893
Ты слышал о code golf?
Не могу не вспомнить про acmp.ru, на котором топы формируются по краткости кода.
"Важна не длина, а умение пользоваться" (с)
Зато топы с первой попытки сдают, а не с 8 :)
Come on with the practice...I want to see if my almost in time finished source for C is correct.
An irrelevant question: What does VK stand for?
https://vk.com/
vkontakte.ru or vk.com
"v kontakte" if we translate it in english it means "in contact"
Когда будет открыто дорешивание?
Why do you keep upsolving closed for a while after contest? :(
Spent about an hour trying to get a Java BigInteger solution to Div 1 B to work, with no avail. I always TLE'd. I've been thinking about switching to Java, because of BigInteger among other things, but this has really dissuaded me. Is it possible to optimize this? Are there advantages to Java?
After I gave up and wrote a C++ solution, it ran in 200 ms :/
I think the complexity of a BigInteger solution is O(n2) since adding two BigIntegers takes O(n) and there are O(n) additions. BigInteger's can't exploit the fact that much of binary expansion of the numbers is 0.
That makes sense. Is there a workaround or is this method just bound to fail?
I don't think there is a workaround. BigInteger isn't designed for bit manipulations, it's just used for large numbers.
http://codeforces.net/contest/658/submission/17008837 Why is this answer accepted?? 4 4 4 gives wrong ans.
h < n
When are you going to update the rating?
its almost 2 am in my country. I can't sleep because of that. Have to catch a bus 5 hours later. I think Im gonna miss it -_-
Когда будет изменение в рейтинге? Стоит ли ждать сегодня или лучше поспать?
Спи, спи.
I wish that Wild-Card 1 will not be like the year before.
Auto comment: topic has been updated by Radewoosh (previous revision, new revision, compare).
tourist — 4126
The rich get richer...
But you ain't poor either! See me! I feel sad for my performance everyday ! :/
Until the final he probably would be 5000+ :P
WTF The rating change is ridiculous...
I know the new rating system is supposed to be better but what the hell is going on with tourist's rating? He used to get +40 for a first place and now he has +259, even though his rating is far beyond anyone else's. I don't really mind it, I'm just wondering what changed so drastically :D?
And his teammate is not a random weak guy but subscriber... +259 is not reasonable.
It's partly because of the team contest, but this is happening even for regular rounds, the rating system is being quite wacky around the top of the standings...
Before change about 50-60 was what he would get upon being first. After change it's +112, +124, +172 — while competing alone. Additionally, why does it matter if it's a team competition or solo when he is first?
Competing against teams is like competing against participants with higher rating. Beating them should reward you more.
But you are also competing in a team so aren't you also a participant with higher rating?
No. His team has exactly the same rating as tourist alone, lol.
Почему пишет, что мое решение игнорировано ?
у меня тоже
Почему у команды tourist + subscriber рейтинг
3867прямо как у одного tourist.http://codeforces.net/blog/entry/16986
Этот пост как раз говорит о том, что tourist + Workforces > tourist.
P.S. На скриншоте сортировка в порядке неубывания роста рейтинга. Это баг?
tourist getting 4k is like Leo getting Oscar.
I'll just leave this here.
why kicked in Vk cup round 1 (div 2) ?
Sorry if my questions is a little bit ridiculous,but I have to ask: are you really think that,same rating change for both team mate is correct? Was it the best way for distribution ratings?
I think the team rating should be independent from individual rating, just like tennis lol
A team contest is not that common though...
I think it's time to create a new color above "legendary grandmaster" for tourist
Nothing personal, but I'd rather say it's time to fix formulas
"Чемпионат преимущественно ориентирован на школьников старших классов и студентов РФ и стран бывшего СССР", "Рабочий язык чемпионата VK Cup 2016 — русский", а разбора задач на русском стоит ждать?
Спасибо за хорошие задачи.