By Errichto, 5 years ago,

Hi everybody.

The VK Cup Round 3 is coming (exact time).

The duration will be longer than usual, likely 3 hours.

As usually in VK Cup, there will be three contests — div1, div2, official one. All of them are rated. Div1 and div2 versions are for individual participants, not for teams.

Setters are Radewoosh, Errichto and qwerty787788. I think that (some) problems are extremely interesting and I really wish I could participate. Thanks to GlebsHP and MikeMirzayanov, we wouldn't have a round without them. Also, thanks to AlexFetisov and winger for testing.

We will later inform about the final duration. Maybe we will inform about the number of problems and scoring.

I wish you great fun and no frustrating bugs. And Limak wishes you good luck!

UPD

• The contest will last 3 hours.
• ADJUSTED POINTS DROP — Points will decrease with such a speed that submitting a problem at the end would give you the same number of points as in standard 2-hour rounds.
• I updated testers above.
• Top50 in the "Div1 Edition" contest will get t-shirts. Have I already said "I wish I could participate"?

UPD 2

There are 9 problems. Div2 gets problems 1 - 6, and Div1+R3 gets 3 - 9. It means that there are 4 shared problems.
Division 2: 500 750 1000 1500 2250 3000
R3 & Div1: 500 1000 1750 2250 2250 3000 3000

UPD 3

Enjoy the editorial

UPD 4

The system testing is over. Congratulations to winners. Later I will try to put winners here in some nice format.

 VK Round 3 Div. 1 Div. 2 1. subscriber, tourist 1. Endagorion 1. .o. 2. eduardische, Alex_2oo8 2. eatmore 2. Herzu 3. riadwaw, Kostroma 3. ikatanic 3. co_farmer 4. LHiC, V--o_o--V 4. JoeyWheeler 4. TDL9 5. KAN, vepifanov 5. rowdark 5. polingy
Announcement of VK Cup 2016 - Round 3

• +327

 » 5 years ago, # | ← Rev. 3 →   -24 Now my comment doesn't matter, just ignore it :3
 » 5 years ago, # | ← Rev. 3 →   -53 G
 » 5 years ago, # |   -20 Did you forget to mention AlexFetisov!?
 » 5 years ago, # |   +4 " Maybe we will inform about the number of problems and scoring. "Don't worry, that is not important :D
 » 5 years ago, # |   +25 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 .
 » 5 years ago, # |   +83 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
 » 5 years ago, # | ← Rev. 2 →   +45 What an original picture: http://codeforces.com/blog/entry/17690UPD: (oh, looks like it's also visible only in Russian version of the post)
 » 5 years ago, # |   +5 Can't wait to see the new points System hope this contest is even more fun than the last two :D
 » 5 years ago, # |   +76 you said "extremely interesting" That mean:
 » 5 years ago, # |   +26 It will be rated ?
•  » » 5 years ago, # ^ |   +11 Finally... There he is
•  » » » 5 years ago, # ^ |   +16 It's not nice to get out of tradition :3
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +4 traditions must take place every time Mr.ALi(New_Horizons)
 » 5 years ago, # |   +22 No more fogotten tree:)
•  » » 5 years ago, # ^ |   +16 And the tree had been forgotten
 » 5 years ago, # |   -38 "Top50 in the "Div1 Edition" contest will get t-shirts" .So div2's are not human?!
•  » » 5 years ago, # ^ | ← Rev. 2 →   +145 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).
•  » » » 5 years ago, # ^ |   +98 At least making a combined round makes more sense , bringing everyone to compete for t-shirts is a better choice.
•  » » » » 5 years ago, # ^ |   +54 become div.1
•  » » » » 5 years ago, # ^ |   +32 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.
•  » » 5 years ago, # ^ |   +78 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.
•  » » » 5 years ago, # ^ |   +33 You can have 1899 rating, after a failed contest, where you got -250
•  » » » » 5 years ago, # ^ |   +10 If you are good enough to get top 50 in div 1, it's extremely unlikely that you would ever drop to div 2.
•  » » » » » 5 years ago, # ^ |   +12 but a lot of strong div1 coders take part in official Round3:)
•  » » » » 5 years ago, # ^ |   +24 Unlucky man. But it is your fault.
 » 5 years ago, # | ← Rev. 2 →   +23 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?
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Thought about it, if only I were powerful enough :) :(
 » 5 years ago, # | ← Rev. 3 →   +19 bug or feature?there is 88 teams and 168 participants... UPD: for now 73 teams and 134 participants, looks real:)
•  » » 5 years ago, # ^ |   0 No, there are teams with a single participant.
•  » » » 5 years ago, # ^ | ← Rev. 3 →   +30 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
•  » » 5 years ago, # ^ |   0 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.
 » 5 years ago, # |   +3 i'm already registered in DIV2 round but my name doesn't appear in registrants list ?
 » 5 years ago, # | ← Rev. 2 →   +6 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?
 » 5 years ago, # | ← Rev. 2 →   +8 I was outvoted to post the scoring. So, check out a new update (in the blog).EDIT: someone is working on the registration issue.
 » 5 years ago, # |   +26 There is a bug with showing participants list, and may be it's something legated with teams
 » 5 years ago, # |   +35 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.
•  » » 5 years ago, # ^ |   +8 Yes E so hard :'(
•  » » 5 years ago, # ^ |   +6 Yea, same feelings.
•  » » 5 years ago, # ^ |   +10 I think every VK round has erratic jump of difficulty due to the fact they aren't originally meant for Div2.
 » 5 years ago, # |   +8 Complete problem D and thinking about sleep :)) :))
 » 5 years ago, # |   +30 I made someone angry and then...
•  » » 5 years ago, # ^ |   +1 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!
•  » » » 5 years ago, # ^ |   +7 Likely one of those guys like .o..
•  » » » 5 years ago, # ^ |   -15 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.
•  » » » » 5 years ago, # ^ |   +26 It's not true. I've checked it today? Effect? -120 :)
•  » » » » » 5 years ago, # ^ |   -15 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).
•  » » » » » » 5 years ago, # ^ |   +5 It never was like you describe. Even having an ultra-negative score always affected your rating.
•  » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » » » 5 years ago, # ^ |   +5 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
 » 5 years ago, # |   +1 What is the hack for Div2D?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 4 51 2 3 4
•  » » » 5 years ago, # ^ |   +1 Answer is -1?
•  » » » » 5 years ago, # ^ |   +1 Yep.
•  » » » » 5 years ago, # ^ |   +1 yes
•  » » 5 years ago, # ^ |   +1 My hack was n=4. The answer should be -1.
•  » » 5 years ago, # ^ |   0 n == 4 
 » 5 years ago, # |   0 What was the hacks for Div2A and Div2B?
•  » » 5 years ago, # ^ |   +14 Some guy in my room was outputting 2^(max — min — 1) and that passed pretests.
 » 5 years ago, # |   +8 I didn't even submit a single problem and there it was the lock button for problem B. Must be a bug.
 » 5 years ago, # |   +5 What's the idea for div1 C?How to calculate the expected value on a interval?
•  » » 5 years ago, # ^ | ← Rev. 3 →   +19 P.S. didn't get AC on C, but I think the cost function is correctcost(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
•  » » » 5 years ago, # ^ |   0 And then do a segment tree or something?
•  » » » » 5 years ago, # ^ |   0 The editorial is posted.
•  » » » 5 years ago, # ^ |   0 how to divide them in K regions??
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 let :S1[k] be sum of T[i] for i = 1:kS2[k] be sum of 1/T[i] for i = 1:kS3[k] be sum of S1[i]/T[i] for i = 1:kthen 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 :'(
 » 5 years ago, # |   0 How do you avoid floating point errors with 1C/2E?
•  » » 5 years ago, # ^ |   0 Don't use any epsilons. Use long doubles if you want to be more precise.
•  » » » 5 years ago, # ^ |   0 Why not epsilon? Is this a common problem (that you shouldn't use epsilon)?
•  » » » » 5 years ago, # ^ |   +15 Why would you use epsilon here? What would you try to avoid/achieve?
 » 5 years ago, # |   0 Please allow practice.
•  » » 5 years ago, # ^ |   +7 After the system testing.
•  » » » 5 years ago, # ^ |   +57 Please start system testing =)
•  » » » » 5 years ago, # ^ |   +5 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.
 » 5 years ago, # |   0 The B,div 2 is maximum bipartite matching?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 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.
•  » » » 5 years ago, # ^ |   0 thanks...
 » 5 years ago, # |   0 In div2 D, input : 7 11 2 4 7 3  output 2 7 1 3 5 6 4 7 1 2 4 6 5 3 Why is this output incorrect ?
•  » » 5 years ago, # ^ |   +1 There can't be road between a and b.
•  » » 5 years ago, # ^ |   0 Edge 2 — 4 is present in the second line.
•  » » 5 years ago, # ^ |   0 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.
•  » » 5 years ago, # ^ |   +5 You can't have roads between A and B or C and D.You have road between A and B in second route.
•  » » 5 years ago, # ^ |   0 There can't be direct edge from 2 to 4.
•  » » 5 years ago, # ^ |   0 There shouldn't be a road between towns a and b. In your second line of output you has got such road.
 » 5 years ago, # | ← Rev. 3 →   +5 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 :)
 » 5 years ago, # |   +10 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.
•  » » 5 years ago, # ^ |   +4 I think B problem shall be C and C shall be B in div 2 contest .. thx at all
•  » » 5 years ago, # ^ |   0 yeah , there was a big gap ... but I liked the div2 E problem :D
•  » » 5 years ago, # ^ |   0 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!
•  » » 5 years ago, # ^ | ← Rev. 2 →   +21 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 :)
•  » » 5 years ago, # ^ |   0 it would be great if you lower the accuracy of DIV2E/DIV1C and rejudge all submissions :'D
•  » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ |   0 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 >.<
•  » » 5 years ago, # ^ |   +76 [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 ;)
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +10 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. solutionBottom-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).
•  » » 5 years ago, # ^ |   +3 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.
•  » » » 5 years ago, # ^ |   0 Imo C is harder than B. Only problem with B was a bit overcomplicated statement :)
•  » » 5 years ago, # ^ |   +54 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
•  » » » 5 years ago, # ^ |   +5 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?
•  » » » » 5 years ago, # ^ |   +8 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 :(
•  » » » » » 5 years ago, # ^ |   +20 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.
•  » » 5 years ago, # ^ |   +6 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. :(
•  » » 5 years ago, # ^ |   +20 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...
•  » » » 5 years ago, # ^ |   +14 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).
•  » » 5 years ago, # ^ |   -10 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.
•  » » 5 years ago, # ^ |   -10 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%+, ...)
•  » » » 5 years ago, # ^ |   +15 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.
 » 5 years ago, # |   0 Please enable upsolving immediately after systests...
 » 5 years ago, # |   0 How to solve div 2, C ?
•  » » 5 years ago, # ^ |   +5 Editorial : http://codeforces.com/blog/entry/44754
 » 5 years ago, # |   0 Can anyone explain the idea of recalculating all of the probabilities in Div1 E? Thanks
 » 5 years ago, # |   +17 Impressive performance of .o. in Div2! My NBHEXT expects +401 for him >_<
•  » » 5 years ago, # ^ |   -12 Wow! So accurated! He did +411! O.O
 » 5 years ago, # |   -16 round was rated or unrated ??
•  » » 5 years ago, # ^ |   +4 It is mentioned in the blog post. "All of them are rated"
 » 5 years ago, # | ← Rev. 3 →   0 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
•  » » 5 years ago, # ^ |   +2 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.
•  » » » 5 years ago, # ^ |   0 Thanks, I've got it.
•  » » 5 years ago, # ^ |   0 For your CHT you need to put lines in increasing by angle of line order.
 » 5 years ago, # |   0 My Div1-C timed out since I was using cin for input. Changed it to scanf and passed. :(
 » 5 years ago, # |   +5 Its happened first time with me this is my Div2 D soln which was hacked — > http://codeforces.com/contest/673/submission/17796235 after contest i submitted this code again — > http://codeforces.com/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
•  » » 5 years ago, # ^ |   +5 You've sent 2 solutions, and the second one (last one) was hacked
 » 5 years ago, # |   0 Waiting for Rating Changes.....
•  » » 5 years ago, # ^ |   +8 wait is over!
 » 5 years ago, # |   0
 » 5 years ago, # | ← Rev. 2 →   +58 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.
•  » » 5 years ago, # ^ |   +16 Do you imply that you didn't yet learn CHT? sorry if I'm acting stupid
 » 5 years ago, # |   -79 its too easy i white this when i have sex
 » 5 years ago, # |   0 Lol