By KAN, 5 years ago, translation,

Hi!

Tomorrow, on March 24-th, 2018 at 15:35 UTC we will host the second round of VK Cup 2018 — a programming tournament for Russian-speaking youth. 450 teams that were the best in the first round and the first wild-card round will compete tomorrow. The top 100 teams will advance to the third round directly and get a tournament t-shirt, while the others will have one more chance in the second wild-card round.

For English-speaking community as well as for those who haven't advanced to the second round or haven't participated in VK Cup 2018, we will host parallel Codeforces round for both divisions, as usual. Feel free to take part!

Please note that the tournament is for Russian-speaking people. If you don't speak Russian, you must not compete in the VK Cup round, register for the parallel round instead. Otherwise it is considered as a flagrant violation of rules and might be subject to disqualification and Codeforces ban. Please respect the organizers.

VK Cup 2018 Round 2 and the round for the first division will have six problems each, the second division round will have five of them.

The authors of the problems are cyand1317, skywalkert, Claris and me. Also many thanks to fcspartakm, Tommyr7 for their help in preparation and PavelKunyavskiy, winger, AlexFetisov, Errichto, vepifanov, immortalCO and qwerty787788 for testing the problems! Last but not least, huge thanks to vintage_Vlad_Makeev for his great help in coordinating and testing the round!

Good luck!

The editorial is published!

Congratulations to the winners!

VK Cup Round 2:

1. LHiC, V--o_o--V — solved all problems!
2. egor_bb, Nikitosh
3. -imc-, Golovanov399
4. AllCatsAreBeautiful, arsijo
5. aid

Div. 1:

Div. 2:

Announcement of VK Cup 2018 - Round 2

• +209

| Write comment?
 » 5 years ago, # |   +14 Is it rated for div2?
•  » » 5 years ago, # ^ |   -6 Yes
 » 5 years ago, # |   +24 I would suggest closing registrations for now and resuming it after system testing for Round 471 has been done. As otherwise, people currently in Div 2 (who are going to Div 1 after rating update) will register in Div 2 creating a messed up list.
•  » » 5 years ago, # ^ |   +5 They did that. I think you would be one of those people (who are going to Div 1 after rating update) :D .
•  » » » 5 years ago, # ^ |   +6 Haha yeah! In fact, I realized I just answered my own question from yesterday! xD
•  » » » » 5 years ago, # ^ |   +5 Haha It's funny actually.
 » 5 years ago, # |   +1 Wow ,i had miss this , 3 contests in 3 days
 » 5 years ago, # | ← Rev. 3 →   -15 I love Codeforces beacause of many contests these days! :)I wish you successful submissions, many hacks and high rating.
 » 5 years ago, # |   +55 Hopefully you'll enjoy these problems. Wish you a high rating!
•  » » 5 years ago, # ^ |   +7 Hope it will be not mathforces round
•  » » » 5 years ago, # ^ |   +19 And not Englishforces round. :)
•  » » » » 5 years ago, # ^ |   +46 No, no unnecessary stories this time ;)
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   +9 Thanks. That sounds great. NO Alice and Bob this time!
 » 5 years ago, # |   0 Three in a row
 » 5 years ago, # |   +1 Is it rated for VK Cup Round 2 participants?
•  » » 5 years ago, # ^ |   +8 yes
 » 5 years ago, # |   0 another contest storm , almost everyday , i think it's gonna be contest overflow :D
 » 5 years ago, # |   0 It is raining contests...!!!
 » 5 years ago, # |   0 Can we expect 6000 participation today??
 » 5 years ago, # |   0 Is it just like the last contest, only has three problems in reality? Just be faster.
•  » » 5 years ago, # ^ |   0 Well, last time it was at least four.
 » 5 years ago, # |   +13 I was just wondering when the score distribution would come out...
 » 5 years ago, # |   +51 For God's Sake , DO NOT UNRATE THIS CONTEST , I HAVE DONATED YOU CODEFORECES COMMUNITY
•  » » 5 years ago, # ^ |   +18 It's EarthDay, man
•  » » » 5 years ago, # ^ |   +18 It was on 22nd April , Are you using Internet Explorer ?
•  » » » » 5 years ago, # ^ |   +61 Nahh man I'm just using CodeForces' servers right now
 » 5 years ago, # | ← Rev. 2 →   0 A lot of "in queue" submissions, yet no submissions are being judged. Something is going really wrong this time.UPD: Just seen the announcement. Well, this is unexpected.
 » 5 years ago, # |   0 The Problem States:- "Two ways are considered different if and only if a segment is painted in different colours in them.""Only if" and "a" ? Then how are CYCMY and CYMCY different? There aren't "Only 1" difference there? If what they are meaning is "Two ways are considered different if any segment is painted in different colours in them." then the problem statement is wrong.
•  » » 5 years ago, # ^ |   0 IMO "a segment" phrase has meaning close to "some segment", which is technically any segment
•  » » » 5 years ago, # ^ |   0 How "only if a segment" and "only if any segment" are same?
•  » » » » 5 years ago, # ^ |   +17 I think, when we use indefinite article a/an, we mean "someone", in contrast to "exactly that one".So when I was solving it, I assumed "if and only if" there means (ways are different -> some segment is different) && (some segment is different -> ways are different)Have you asked jury to clarify that?
•  » » 5 years ago, # ^ |   0 "Two ways are considered different if and only if a segment is painted in different colours in them." means "Two ways are considered different if and only if (at least)a segment is painted in different colours in them."
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 The phrase "if and only if" is used to declare a coimplicative relationship. That is, ways are considered different if (condition), and only if (condition) they are considered diferent (if (condition) is not satisfied, they aren't different). Its meaning is not related to "only one segment".
 » 5 years ago, # |   +6 Anyone knows the test case 5 for Problem C of Div2 / Problem B of Div1 ?
•  » » 5 years ago, # ^ |   +8 I think you need to print output with enough precision.
•  » » 5 years ago, # ^ |   +1 printf("%.8f",ans) >> WA printf("%.12f",ans)>> ACCosted me one WA.
•  » » » 5 years ago, # ^ |   0 But please may i know the reason of the above?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +4 It is considered correct when error is less than 10^-9. (Check the input part) When you don't print 9+ digits it can cause precision errors.
•  » » » » » 5 years ago, # ^ |   0 ...... 5 WA & can't get accept at the end & wasting time do problem D
 » 5 years ago, # |   +5 My hacks for B: 4 10000 1 10 11 100 Answer: 89/90, Wrong answer: 90/99 4 1 1 2 3 100 Answer: -1, Wrong answer: 0
•  » » 5 years ago, # ^ |   -7 B?
•  » » » 5 years ago, # ^ |   0 B — VK cup / div1C — div2
•  » » » 5 years ago, # ^ |   0 Div 1 B
•  » » 5 years ago, # ^ |   +5 My hacks for Div2A. I managed to make 8 hacks in total. That includes hacking 3 people twice... Here my tests with correct answers. 6 Y?C??C Yes 3 Y?C No 2 YC No 3 Y?Y Yes 100 ???????????????????????????????????????????????????????????????????????????????????????????????????? Yes (Forces TLE) 1 ? Yes 2 ?C Yes 
•  » » 5 years ago, # ^ |   0 Lo_R_D why Wrong answer : 0 ?
•  » » » 5 years ago, # ^ |   +1 E[i] = 2, E[j] = 3, E[k] = 3answer = (3 - 3) / (3 - 2) = 0j == k — wrong.
•  » » » 5 years ago, # ^ |   +1 All E_i are different, so in order to be able to pick three of them, E_k — E_i should be at least 2 (since E_j is between E_k and E_i). So all tests where U = 1 have answer -1.
 » 5 years ago, # |   +3 me during the contest ...
•  » » 5 years ago, # ^ |   +13 How to paste image?
 » 5 years ago, # | ← Rev. 2 →   +11 one of my hacks is still showing "In queue" . Will it be counted?
•  » » 5 years ago, # ^ |   +1 Mine too.. I'm confused..
•  » » 5 years ago, # ^ |   0 Yes, this happened with me too in some previous contest but it got counted.
•  » » » 5 years ago, # ^ |   +1 But now it is showing "Ignored". What does it refer to?
•  » » » » 5 years ago, # ^ |   0 No idea
 » 5 years ago, # | ← Rev. 2 →   +18 How would I check for which planes could arrive at the same time if they came from the same direction?Edit: This is for Div 1 D
•  » » 5 years ago, # ^ | ← Rev. 4 →   0 (X[i] * V[j] — X[j] * V[i]) / (X[j] — V[i]) <=WYou can divide each speed by W, thus getting X[i] * V[j] — X[j] * V[i] <= X[j] — X[i]X[i]/(V[i]+1) <= X[j] /(V[j]+1)and the same for >= -w :)
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 my idea was to find what will be the time taken if wind speed is -w and w and then if 2 planes can meet than time taken by one plane will be more than second for +w wind speed and less for -w wind speed.
•  » » 5 years ago, # ^ | ← Rev. 3 →   +1 Let t(i, vair) arrival time for vair airspeed. If direction is same, it holds when xi < xj AND (t(j,  - w) ≤ t(i,  - w) OR t(j, w) ≤ t(i, w)).This reduces to finding a pair i < j such that xi < xj, yi < yj, zi < zj.Sort by x-coord, and do divide and conquer. Let L a set with Xi ≤ M, and R a set with Xi > M, then we should find a pair such that . This can be done with binary indexed tree. Thus, T(N) = 2T(N / 2) + O(NlgN) = O(Nlg2N)
•  » » 5 years ago, # ^ |   +8 You can get minimum and maximum arrival time for each plane.Then they can arrive at the same time (if they go in the same direction) iff one [mintime,maxtime] is included in the other.I didn't manage to count inclusions in an acceptable time during the contest though.
•  » » 5 years ago, # ^ |   0 For each plane create a point (xi, vi). Sort all points by angle around point (0, w) and point (0,  - w). You get 2 permutations of points a and b. You need to find number of pairs of points such that in a the first point comes before the second and in b the first point comes after the second. It's the number of inversions in a - 1b, which is a classical problem. You also need to handle the cases when 2 points have the same angle accurately in the comparator.
 » 5 years ago, # | ← Rev. 2 →   0 Can anyone please see why my nlog^2n solution for D is giving TLE? https://ideone.com/WGUMhc sorry for bad indexing of part where 2d Fenwick tree is declared though u may skip it as i had directly copied an implementation
•  » » 5 years ago, # ^ |   0 Unable to see submission.
•  » » » 5 years ago, # ^ |   0 Thanks, i have shared new link
 » 5 years ago, # |   +11 RIP T-shirt :(
 » 5 years ago, # |   +23 will the round be semi rated or unrated because of the long queue?
•  » » 5 years ago, # ^ |   +29 It really impacted some participants including me. I checked my solution of Problem C during the long queue.And finally I didn't have time to code Problem D which I think I can solve it during the contest.
 » 5 years ago, # | ← Rev. 2 →   -11 I have solved problem B for Round #471 in a video , the link : https://youtu.be/IG88Al6fWecand i will solve problems A and B of this contest in a videoschannel link : https://www.youtube.com/channel/UCmWvb73kIq_oRThWd05Mtfg
 » 5 years ago, # |   0 How to solve div1D. I think we can reduce the problem to count the number of lines that have abs(slope) <= w if each plane is converted to a point (1/xi,vi/xi). How to solve the reduced problem?
•  » » 5 years ago, # ^ |   0 if the wind power is -w and two plane meet at p1<=0 && if the wind power is w and they meet at p2>=0 then they are counted
 » 5 years ago, # |   0 Hello, I want to ask how to solve Div 2 C? My solution is: http://codeforces.com/contest/957/submission/36598579Basically I fixed for all index k, I want to find the first index i where Ei >= Ek — U, then to maximize the answer obviously j is equals to i + 1. Does the greedy solution above not work?Please kindly give me corner test case and explanation if you don't mind. Thank you!
•  » » 5 years ago, # ^ |   0 Cant See your solution now but I did the same thing. Hope i pass the sys tests. Did you handle the case of -1?
•  » » 5 years ago, # ^ |   +1 Noticed my mistake. I think in this case I should fix all index i, not k.Corner case:4 10000 1 10 11 15My solution answers: (15-10)/(15-1) = 0.357142857Expected: (15-11)/(15-10) = 4/5 = 0.8
 » 5 years ago, # | ← Rev. 5 →   0 del
 » 5 years ago, # |   0 Does anyone know pretest #7 for Div. 2 D? Thanks
•  » » 5 years ago, # ^ |   +1 use long long instead of int
•  » » 5 years ago, # ^ |   0 For me it was int overflow.
 » 5 years ago, # |   +5 i think GreenGrape can learn how to make a round from you :V Good round guys
•  » » 5 years ago, # ^ |   +8 Problems were nice, but this doesn't seem good. Almost same amount of people solved ABC.
•  » » » 5 years ago, # ^ |   +14 you should consider that these problems are used in Div 2 round too
•  » » » » 5 years ago, # ^ |   0 You are right, but I think organizers should give more attention to problems and scoring of the official round.
•  » » » 5 years ago, # ^ |   +5 It seems wonderful, what’s the problem?
•  » » 5 years ago, # ^ | ← Rev. 2 →   -27 Go to hell GreenGrape is the best problem setter ever, everyone makes mistakes sometimes your mother for example
 » 5 years ago, # |   +31 how to solve div2d/div1c?
•  » » 5 years ago, # ^ | ← Rev. 4 →   -6 hint : you can draw a line between 2 already drawn lines.
•  » » 5 years ago, # ^ | ← Rev. 3 →   +6 Don't add any new marks until you need to. Keep track of the records where you didn't create a new mark.Take this case: 0 0 0 1 0 4Before we see record of 4, ans should be 1. We only created a mark for the first 0 and the 1. Then we know we didn't create any new marks for the second, third, and fourth 0. Now when we see record of 4, we know we need to add 2 new marks on the previous records (not including the current 4). Now insight is that we should greedily add marks to the most recent records where we didn't create any new marks. This is because if we add a mark for some record, all records after it no matter what will have to contribute +1 to the answer. So we should add marks to the third and fourth 0. Adding mark to third 0 increases ans by 3 and adding mark to fourth 0 increases ans by 1. Now we can create new mark for the record 4 below all other marks, and will satisfy the condition of 4 marks above it. Thus ans is 5. Note that now we should get rid of third and fourth 0 from our list of where we didn't create any new marks. Since each record creates a mark at most once, complexity is linear.Maybe a little confusing, I can elaborate more. Also disclaimer I haven't passed sys test.Edit: passed
•  » » 5 years ago, # ^ |   +3 you can keep track of the minimum number v of marks that appear after day i.You know that they are non decreasing, so you can build them from left to right as you read the vector.Then you need to go from right to left and make sure the increments of your list are at most 1 per day.With v and m, you can get the minimum number of underwater marks for each day.
 » 5 years ago, # | ← Rev. 2 →   0 In Problem A it states "You are to determine whether there are at least two ways of colouring all the UNPAINTED SEGMENTS so that no two adjacent segments are of the same colour". In case of NO unpainted segments, if the painted segments have no adjacent same colours, it should be yes according to this. Very incorrect and unclear wordings!!!
•  » » 5 years ago, # ^ |   +28 How to color 0 unpainted segments in two different ways?
•  » » » 5 years ago, # ^ |   +8 I was hacked because of this :(
•  » » » 5 years ago, # ^ |   +30 Semenar is very incorrect and unclear!!!!!!!!
 » 5 years ago, # |   +28 Why there is no penalty for WA on first test, but there is penalty for WA on other samples? :/
•  » » 5 years ago, # ^ |   -10 i think the concept behind this is the problems that have multiple solution, so if one can't trace his solution he can submit it and see if it's right or not in the first case
•  » » 5 years ago, # ^ |   +44 In order to give some mercy for people which submit wrong files, for example from different directory.
 » 5 years ago, # | ← Rev. 3 →   0 (I didn't calculate correct complexity, this code runs in O(n))I think that the C test cases is weak.Check this solution: 36587731This get ACC, but is a O(n^2) solution.I think that this test break:100000 1000000000 1 2 3 4 ... 100000
•  » » 5 years ago, # ^ |   +3 It's O(n)
•  » » » 5 years ago, # ^ |   0 You are correct. Sorry xD
 » 5 years ago, # |   +73 It seems like we are going to get new top rated user after rating update :)Congratulations, Um_nik!
•  » » 5 years ago, # ^ |   -10 Um_nik is great.
»
5 years ago, # |
-14

Mystical Mosaic test cases are not appropriate. My wrong code has passed all the test cases. My code gives Yes for this input:- 2 5

## ...

.#...

 » 5 years ago, # |   +1 Why is this running on pretest 1 ? http://codeforces.com/contest/957/submission/36588552
 » 5 years ago, # | ← Rev. 2 →   +21 Hi, can some author pls check this my same solution got tle in contest and passes outside. TLE(during system test):- http://codeforces.com/contest/956/submission/36596404 AC(same code after contest):- http://codeforces.com/contest/956/submission/36601475
•  » » 5 years ago, # ^ |   +1 MikeMirzayanov or KAN if possible can you please look into the matter and make necessary changes thank you:)
•  » » » 5 years ago, # ^ | ← Rev. 4 →   0 Kind of same problem here. http://codeforces.com/contest/956/submission/36599452 It failed in system testing on a test case it passed during the contest. It passes if i change long double to double? http://codeforces.com/contest/956/submission/36608848
 » 5 years ago, # | ← Rev. 5 →   +4 What a code written by xepher52447 ! It takes 30 minutes to test it ! :p
 » 5 years ago, # | ← Rev. 4 →   -6 Why is there such a large difference in runtime?http://codeforces.com/contest/956/submission/36601805http://codeforces.com/contest/956/submission/36601828The only thing I changed was reading in integer instead of double. This cost me 30+ minutes and 5 resubmissions ...P.S. My submission which got TLE on test 7 now passes ...
•  » » 5 years ago, # ^ |   +22 'P.S. My submission which got TLE on test 7 now passes ...'You submitted it with different version of compiler
•  » » » 5 years ago, # ^ |   0 Guess I'm never using C++11 again :|
 » 5 years ago, # |   0 in problem c in div 2 how the answer of test 22 is 0 ?
•  » » 5 years ago, # ^ |   0 I'm sorry, but in test 22 answer is -1. It's impossible that the answer is zero in this problem, because all the energies are distinct
 » 5 years ago, # | ← Rev. 2 →   +32 WOW, first time I have full AC due to time extend. Want to say "Thank you" to your electricity supply. :-)
•  » » 5 years ago, # ^ |   0 Wow your submission passed in 998 ms :)
•  » » » 5 years ago, # ^ |   0 Yeah, I'm very lucky at this contest. Instead of reading to an int and typecast to long double, I read directly to long double variables using cin. This process is very time-consuming and many submissions do like this had been TLE. :-)
 » 5 years ago, # |   0 cool contest... :)
 » 5 years ago, # |   +6 Great... the contest made me need 8 point to 3 point...
 » 4 years ago, # |   0 .
 » 4 years ago, # |   0 Has somebody received a t-shirt? Or email about it?-
•  » » 4 years ago, # ^ |   +20 They said that t-shirts will be sent after vk cup final
•  » » » 4 years ago, # ^ |   0 Thank you!