В субботу, 7-го мая, в 18:05 начнётся Раунд 3 чемпионата по программированию VK Cup 2016! Не забудьте зарегистрировать вашу команду на раунд, регистрация закроется за пять минут до его старта.
В этом раунде могут принять участие все те команды, которые отобрались в Раунде 2 или в Уайлд-кард раунде 2. Участников ждет соревнование по правилам классических раундов Codeforces. Раунд 3 пройдёт в таком же формате, как и Раунд 2 — с онлайн-трансляциями (рейтинговыми, раздельно для див-1 и див-2 участников).
Раунд подготовлен силами гроссмейстерского коллектива: Radewoosh, Errichto и qwerty787788.
Напомним, что в Финал VK Cup пройдут все те команды, которые наберут положительный балл, не меньший, чем у команды на 20-м месте. Также обращаем ваше внимание, что участники всех команд, прошедших в Раунд 3 (независимо от их участия или неучастия в Раунде 3 или в его трансляции), получат фирменную футболку Чемпионата. Помимо этого, фирменной футболкой будут награждены топ-50 участников интернет-трансляции для первого дивизиона.
Желаем удачи и интересной борьбы!
Now my comment doesn't matter, just ignore it :3
G
Did you forget to mention AlexFetisov!?
" Maybe we will inform about the number of problems and scoring. "
Don't worry, that is not important :D
Hope to have some Small & Precise & Easy to Understand Problem Statements . And I like the Contest hosted by Errichto most . And I love Errichto as a person.
Hopefully this will be an interesting Contest .
Last time (on vk cup round 1) only "Bear and Chemistry" was mine and nobody was able to solve it. I hope that this time you will perform better. :P Good luck from Radewoosh!!! :D
What an original picture: http://codeforces.me/blog/entry/17690
UPD: (oh, looks like it's also visible only in Russian version of the post)
На всякий случай напишу еще и тут — не проходит регистрация команды на основной контест. Получаю оповещение, что я уже зарегистрирован на трансляцию для Див1 (это не соответствует действительности)
UPD. Не актуально
Can't wait to see the new points System hope this contest is even more fun than the last two :D
you said "extremely interesting"
That mean:
It will be rated ?
Finally... There he is
It's not nice to get out of tradition :3
traditions must take place every time Mr.ALi(New_Horizons)
No more fogotten tree:)
And the tree had been forgotten
"Top50 in the "Div1 Edition" contest will get t-shirts" .
So div2's are not human?!
Why should strong div2 participants have better chances for a t-shirt than medium div1 participants? Also, t-shirts for div2 may cause cheating (div1 guys participating with other accounts).
At least making a combined round makes more sense , bringing everyone to compete for t-shirts is a better choice.
become div.1
I agree that combined rounds are good when it comes to prizes. Though, there are other factors then. Two important ones are that (1) problems may not fit such a round at all, and (2) hacking is more random.
Maybe div2 participants should treat usual rounds as a fight for t-shirts — good results will allow them to compete in div1 contests with prizes.
Ehm, yes. The idea is the 50 best guys gaining T-shirts. If you are in div.2, you cannot be the best by definition.
You can have 1899 rating, after a failed contest, where you got -250
If you are good enough to get top 50 in div 1, it's extremely unlikely that you would ever drop to div 2.
but a lot of strong div1 coders take part in official Round3:)
Unlucky man. But it is your fault.
Just curious — if someone qualified for round 3, but decided to participate in div1 mirror instead of main round, in case of making into top50 there he'll get two VK Cup t-shirts?
Thought about it, if only I were powerful enough :) :(
bug or feature?
there is 88 teams and 168 participants...
UPD: for now 73 teams and 134 participants, looks real:)
No, there are teams with a single participant.
Or some participants are in many teams.
EDIT. Maybe as an organizer I shouldn't make fun in comments. To make things clear: my comment isn't serious. #politicalcorrectness
I already reported that "bug" (also seeable in unofficial contests). I once thought that the number in the "Contests" page also involves people that unregistered later, but I may be wrong.
i'm already registered in DIV2 round but my name doesn't appear in registrants list ?
Is there a problem with the registrants page? Cause on the contest page it says:
But on the actual page it says:
Hoping the 2500 number is accurate but would there be a problem with contestants that aren't on the registered page? Would they be able to submit in the contest?
I was outvoted to post the scoring. So, check out a new update (in the blog).
EDIT: someone is working on the registration issue.
Только у меня так ?
Нет. Точно помню, что регистрировался с утра. Но пришлось зарегистрироваться заново сейчас.
+
There is a bug with showing participants list, and may be it's something legated with teams
Я понимаю, что участники не читают соглашение об участии, но почему его не читают те, кто его пишут?
Во-первых, адреса всё ещё ведут на codeforces.ru, с которым мы попрощались уже почти год назад. Во-вторых, какое отношение ко мне имеет первый пункт, если я регистрируюсь на интернет-трансляцию? И вообще, когда это "соглашение" наконец сделают нормальным шрифтом и с кликабельными ссылками?
Там ещё две ссылки одинаковые =)
http://codeforces.me/blog/entry/4088
The difficulty jump from Div2 D to E and F seems huge... Kinda sad that speed and hacking is going to determine most of the Div2 results, even if it seems like I'll be at the top of the 4-task-solvers.
Yes E so hard :'(
Yea, same feelings.
I think every VK round has erratic jump of difficulty due to the fact they aren't originally meant for Div2.
Complete problem D and thinking about sleep :)) :))
I made someone angry and then...
Yup we were in the same room.... I don't know what was on his mind....he tried to hack mine too a lot of times!
Likely one of those guys like .o..
I think it's clear he wasn't happy with his perfomance and he "hacked himselft out of the contest". If you have negative score, the contest is unrated for you, or at least it used to be that way.
It's not true. I've checked it today? Effect? -120 :)
Yes, it seems they changed that. I think this a much more reasonable policy. But there should have been a notification about this (I searched and didn't find it anywhere).
It never was like you describe. Even having an ultra-negative score always affected your rating.
Okay. Sorry for mixing things up. I was definitely mistaken. Don't know how I came up with that, I was sure I had read it somewhere.
I've also heard about it. Maybe there was such a bug (feature :D) a long time ago. We should probably ask Mike whether it's just a social myth
Прикольно, когда пытаешься взломать чувака, получаешь "Неудачная попытка взлома"
Time: 1981
Memory: 2465792
Переписываешь его решение, запускаешь в "запуске", а там стабильно 2100 мс =(((((
What is the hack for Div2D?
4 5
1 2 3 4
Answer is -1?
Yep.
yes
My hack was n=4. The answer should be
-1.What was the hacks for Div2A and Div2B?
Some guy in my room was outputting 2^(max — min — 1) and that passed pretests.
I didn't even submit a single problem and there it was the lock button for problem B. Must be a bug.
"Простые задачи? Зачем!"
What's the idea for div1 C?How to calculate the expected value on a interval?
P.S. didn't get AC on C, but I think the cost function is correct
cost(L, R) = cost(1, R) — cost(1, L — 1) — sum_of_1/a(L, R) * sum_of_a(1, L — 1)
idea: cost(L, R) = t_L / t_L + (t_L + t_(L+1)) / (t_(L+1))... =t_L * (1 / t_L + 1 / t_(L+1) + ..) + t_(L+1) + ...
which then becomes much easier to see
And then do a segment tree or something?
The editorial is posted.
how to divide them in K regions??
let :
S1[k] be sum of T[i] for i = 1:k
S2[k] be sum of 1/T[i] for i = 1:k
S3[k] be sum of S1[i]/T[i] for i = 1:k
then the expected time to finish the interval s->e is S3[e] — S3[s — 1] — S1[s — 1]*(S2[e] — S2[s — 1])
from that we can turn it to a dp + convex hull optimization problem ...
PS : my code fails test 14 — I should practice convex hull optimization more :'(
How do you avoid floating point errors with 1C/2E?
Don't use any epsilons. Use long doubles if you want to be more precise.
Why not epsilon? Is this a common problem (that you shouldn't use epsilon)?
Why would you use epsilon here? What would you try to avoid/achieve?
На мой взгляд, очень не хватало подзадачи DIV1 C, в которой бы проходил k*n*n.
Please allow practice.
After the system testing.
Please start system testing =)
Mike and/or Gleb must work a bit after each round, to manage hacks and any issues. I'm sure they don't try to be slow to annoy all participants. You must wait a bit. In the meantime, you can check the editorial.
The B,div 2 is maximum bipartite matching?
Nope, it's much simpler! The lower problem in each pair must be the div 2 problem. You just need to find the maximum div 2 problem and the minimum div 1 problem, then take the difference.
In div2 D, input :
Why is this output incorrect ?
There can't be road between a and b.
Edge 2 — 4 is present in the second line.
In the second line, the 2 and 4 are directly connected by a road (right next to each other). The problem statement said that was not permitted.
You can't have roads between A and B or C and D.
You have road between A and B in second route.
There can't be direct edge from 2 to 4.
There shouldn't be a road between towns a and b. In your second line of output you has got such road.
After one hour and solving the first four tasks, next two hours were like a fishing. I was trying to catch some wrong submission and I didn't manage in it :)
I'm sure you are all wait for the system testing. So maybe you have time to give the feedback. Which problems were good/bad and what could be better? Something too easy or hard? Too mathy? Too not-mathy?
Someone already said that there was a big gap between div2D and div2E. It may be true. Do you agree? Other opinions?
Seriously, your feedback will make future contests better.
I think B problem shall be C and C shall be B in div 2 contest .. thx at all
yeah , there was a big gap ... but I liked the div2 E problem :D
Yeah, it seems as though there was a ginormous gap between the two. I didn't really think much about the E problem though because I've never been able to solve an E problem during a contest. I went straight to try hacking :P (although I wasn't very successful).
In general, I liked all the other problems though!
Duplicating my russian comment in english: it would be nice to have a DIV1 C subproblem, which could be solved in O(nnk).
There were a huge difficulty jump between AB and the others.
UPD: so, if you are not red, then after solving AB problems in 30-60 min, there is nothing to do in remaining 2 hours, except reading other problem statements and trying to hack someone :)
it would be great if you lower the accuracy of DIV2E/DIV1C and rejudge all submissions :'D
I was stuck at Div1 C so I didn't read Div1 D, however it seems that Div1 D was seriously underestimated. Before system test, judging by successful submissions amount — it seems to be the hardest problem.
I was also thinking that Div1 D is simpler that C, and started it, but only 10 persons solved it so far in all 3 contests >.<
[TL;DR] => too many queries / expected value ;)
[Div 1] Two first problems were like a warmup, almost everyone solved them.
But then? [A, B, . . . . . . . . . . . . . E, C, F, G, D(wtf) ]
Looking at the problems :
*easy problems *
-Shieet, expected value.
-Oh god, queries.
-Expected value!!!11
-Hidden queries.
-Even more queries!!!
My opinion: Too many queries and expected value :) And almost every one of the C — G problems required DP (maybe with maths) , it is always nice to see a varying problemset with flows / graphs / strings (or even geometry ^^).
This is only my opinion, please don't dovnvote just because you don't agree with it ;)
The number of upvotes you got means that many agree with your comment. I see that there was too much DP, and maybe too much expected value. But I don't understand one thing — what is wrong with queries? Is it that they make a problem less elegant and nice? Because not all problems with queries are about the same topic.
Would the following version of 643E - Bear and Destroying Subtrees be better? It has no queries (does it make the problem nicer?). The tree is given and there are no queries at all. We consider removing each edge with prob. 1/2. What is the expected value of the height after the process, modulo 109 + 7.
Bottom-up dynamic programming on a tree. For each subtree we need a vector/list with probabilities, and one additional multiplier. When merging two subtrees, add smaller one to the bigger one. The complexity may look like O(n*log(n)) but it's O(n).
Yeah,there was huge gap between these problems.In addition C was too easy , I think it would be better if it was problem B.
Imo C is harder than B. Only problem with B was a bit overcomplicated statement :)
In my opinion, the pretests for problems which greatly affect standings (for today's contest, it's all problems after div1B) should be nearly identical to final tests, that is to say all corner cases should be present. It's definitely a frustrating bug to drop 70+ places because
for(int j=1; j<i; j++)should be
for(int j=i-1; j<i; j++)Before you say "but what about hacks", I'd like to point out pretty much nobody is going to hack a problem with more than a few lines of code. Indeed, there were no hacks on C, D, E, F, or G of div1 contest.
I think that we tried to make pretests strong in hard problems. I think that the only exception was a problem about the expected height of partly-destroyed subtree. (There, I thought there would be hacks requiring big value of MAX_H.) About which problem are you talking?
I failed Div1 C because my DP formulation considered splitting n levels into more than n parts, which obviously causes bad things to happen. Any test where n = k and n >= 3 will cause my program to output a value smaller than n. Adding two characters would fix this :(
It's hard to be so careful about pretests. Still, I see your point and I'll try to consider it in the future. Thank you.
In division 2 C, why was index written in brackets. All the while I thought only about index of the lowest tied color :| Rank dropped by at least 200. :(
This isn't that important, but I would prefer if the problem statements seemed more "natural" in some sense, maybe something that I would naturally be interested in, not too contrived statements, etc.
I thought A was OK in this respect. B was ehh, the condition that ab, cd aren't edges is slightly unnatural. C was pretty unnatural, in the statement of the game, etc. I didn't try D, E, G so no comments here.
F is a decently natural statement I thought, if you think about the problem mathematically.
Tell me if I confused you...
It's a very important thing in my opinion. Statements are a huge part of the contest. Initially, in B there was something like "Limak wanted to get from a to b. Unfortunately, there was no direct connection. So, he will be late anyway for some event and at least he will take a long nice walk. He then went to b, visiting all cities during his walk. On the other day, ...". It's easier to understand the story but the cost is that the statement is (much) longer. The current version is much shorter than the previous one, with some background. I was advised not to write long statements for this contest and I think it's better. For example because some people aren't fluent in English. So, maybe shorter precise statement is better than longer natural one. But still, I left some story. I will gladly hear more opinions about it.
But generally, it's hard to invent only natural problems. I can do nothing about the fact that C was unnatural for you. I thought it's still better that only definitions ("split sequence to maximize the score defined as ..."). But some problems are just artificial. I know I will never be able to produce only non-artificial stories and problems (enough of them to make contests).
I was expecting to solve more of the problems and it just feels bad to solve 2 and one of them didn't pass system tests, so I got a beautiful 1 problem accepted. I think that is because the difficulty gap between first 2 and all others was too high, if there are going to be 7 problems, I would expect the average to solve 3-4, if there are going to be 5, then 2 or 3 is nice, I just think that a minor mistake shouldn't move you more than 100 places, or 170 in my case, around half of the people that participated in div1.
It would be interesting to know: is "34 accepted solutions for D-G problems" near with expected estimation of AC ratio for this problems before contest?
What is ideal AC ratio in your opinion? (e.g. A 50%+, B 25%+, C 12%+, ...)
It's hard to estimate these numbers before the contest. I'm only sure that we considered div1C (CHT) and div1D (Fanpages) to be easier than they turned out to be. I think that the number of AC's in other problems is fine.
Please enable upsolving immediately after systests...
How to solve div 2, C ?
Editorial : http://codeforces.me/blog/entry/44754
Can anyone explain the idea of recalculating all of the probabilities in Div1 E? Thanks
Impressive performance of .o. in Div2! My NBHEXT expects +401 for him >_<
Wow! So accurated! He did +411! O.O
round was rated or unrated ??
It is mentioned in the blog post. "All of them are rated"
My solution in Div1C adds each of n lines in CHT after calculating DP for some k.
How to prove that the best line for i (when I calculate dp[i][k + 1]) will not have some index j > i?
It is not obviously for me but it passed systests. I even tried to change the order of addings but it didn't pass pretests :D. Or maybe weak testcases are the reason of my Accepted :D? 17793170
We have dp[i][k + 1] < dp[i][k], and
. I'm not sure this is sufficient to show more rigorously that adding further indices will not affect the answer, but it seems to make it intuitively clear.
Thanks, I've got it.
For your CHT you need to put lines in increasing by angle of line order.
А знает ли кто-нибудь, почему так долго пересчитывается рейтинг?(уже после компиляции)
My Div1-C timed out since I was using cin for input. Changed it to scanf and passed. :(
cin : http://codeforces.me/contest/674/submission/17792111
scanf: http://codeforces.me/contest/674/submission/17797745
Its happened first time with me this is my Div2 D soln which was hacked — > http://codeforces.me/contest/673/submission/17796235 after contest i submitted this code again — > http://codeforces.me/contest/673/submission/17798097 ( which got accepted ! and the test case on which my code was hacked seems to give correct result ) Am i missing some thing or is it just my hard — luck ??? → Reply
You've sent 2 solutions, and the second one (last one) was hacked
Waiting for Rating Changes.....
wait is over!
Доброго времени суток. Сравните посылки 17798554 и 17797966. Прошу перетестить все решения на задачу 673C - Медвежонок и цвета, так как при отправке идентичного кода каждый раз сервер дает разный вердикт
Меняй vi a(n); на vi a(n+1); у тебя не существует a[n] и поэтому должно выдать ошибку но выдаёт не знаю почему TLE.
C
Та это не важно, само поведение сервера доставляет: то на 4 ТЛ, то на 10, то на 26...
Засылаем программу с undefined behaviour, его же и получаем на сервере. Чему удивляться?
Важно. У тебя undefined behavior.
Кф такой тролль(
My todo list before todays contest.
Facepalm the point "Convex hull trick" is in my todo list for a several months and I failed today to solve C although I come up with a right DP.
Do you imply that you didn't yet learn CHT? sorry if I'm acting stupid
Доброго времени суток. Сравните решения 17787696 и 17803831 разница лишь в комментарии. Прошу перетестировать все решения по задаче 673C - Медвежонок и цвета, так как при меньшей загруженности сервера или просто другом сервере решение отлично успевает в 2 секунды, undefined behaviour вроде нету.
решение отлично успевает в 2 секунды.
1794 ms.
P.S. Самое быстрое решение по этой задаче : 46 ms.
Я знаю, что моё не идеальное и впритык, но всё же успело потом так почему на контестик её не засчитать?
Мне кажется, здесь просто не совсем точные органичения: по-хорошему лишний логарифм должен давать ТЛ.
Так что там с футболками ? Нашей команде так никто и не написал, это у всех так или конкретно у нас так?
UPD: Ребят, кому — то пришла? Потому что нам ничего так и не пришло.
Lol
А футболки ещё не всем разослали? Просто нам до сих пор ничего не пришло :(
мне кажется принтануть и разослать 250 футболок это не пол года. поправьте меня если я ошибаюсь плиз)
Мне тоже до сих пор не пришла футболка. Яндекс — молодцы в этом плане, прислали примерно через месяц после конца Яндекс.Алгоритма.