Важный день!
Сегодня мы узнаем победителей трека Engine VK Cup 2019–2020. Лучшие участники сезона, прошедшие отбор в феврале, к сожалению, не соберутся вместе на Новой сцене Александринского театра в Санкт-Петербурге, но в 17:05 начнут бороться за звание чемпиона VK Cup и призовой фонд:
- 1 место — 524 288 рублей,
- 2 местo — 131 072 рубля,
- 3 местo — 32 768 рублей.
Болеть за финалистов можно по ссылке.
А уже в 02.11.2020 17:35 (Московское время) вас ждут Div1 и Div2 раунды по мотивам задач финала VK Cup.
Задачи для финального раунда VK Cup подготовлены сотрудниками ВКонтакте PavelKunyavskiy, izban, YakutovDmitriy и Kurpilyansky, .31, а также неповторимым 300iq. Дополнительные задачи для Codeforces раунда подготовлены Supermagzzz, Stepavly и MikeMirzayanov.
В подготовке и тестировании этого раунда помогали MikeMirzayanov, ecnerwala, Egor, hos.lyric, yosupo, lperovskaya, Stepavly, Supermagzzz, HIR180, qwerty787788.
Спасибо большое!
Удачи!
UPD И победителями VK Cup 2019-2020 становятся:
Поздравляем! Полная таблица результатов доступна по ссылке.
UPD:
Div.1 Scoring: 500 1000 1500 1750 1750 2500
Div.2 Scoring: 500 1000 1500 2000 2500 3000
UPD: Разбор
Auto comment: topic has been translated by PavelKunyavskiy (original revision, translated revision, compare)
is it rated??
I don't know why every time someone asks this question?
When it is mentioned that it is a div2 / div1 round its anyways rated. It would be specified if it is some external contest. :)
Best Wishes to the contest!
could you please mention the duration and the approximate number of problems in each div?
& Score distribution too
Hope that there will be interesting and pleasant problems)
Note that the start time is usual. :)
Its Usual Now :)
please tell me how to put a photo in the comments. plsss ＼(＾▽＾)／
1.Upload picture to: https://www.imageupload.co.uk/
2.Get "HTML Embed" link of picture
3.**Paste it!**
Thank you ＾ω＾
(*_*)
Was it rated?
I mean the actual finals, not upcoming rounds.
.
Дорешки не будет до окончания зеркала?
Wish it a big success!
This round is very successful! By the way,I've never seen a round like this-1A is 2D,but 1B is 2F...Is 2E 1(A+B)/2? :)
Hello! In today's contest (round # 680) I was promoted to candidate master, I had previously registered as div2 in round # 681. Due to the announcement that some features were not available for the VK cup final round. Are they meaning that the changes will affect after the round? , I want to know if I have to give the div1 or the div2 (to make a virtual participation of two past contests to train). Thank you for reading . (I didn't find an answer in other blogs) uwu
Wow tourist won before it even started!
It is for 2019/2020
Hold on, did I just traveled back in time?
And this contest is based on VK Cup 2019/20 finals...
Can someone explain me that based on means what? Will there be same questions which appeared in the VK Cup finals!!
Congrats tourist for another victory!!
According to the VK Cup scoreboard, C had a significant FST rate (six FSTs compared to 19 solves). Will the pretests be augmented prior to the round tomorrow in order to prevent the same issue from presenting itself again?
Why there's public scoreboard in the first place
This is honestly not clear to me either, but obviously that ship has sailed. At the very least, though, the authors should take advantage of the fact that they basically just had 36 extra testers in order to ensure that the round doesn't devolve into a massive FST-fest. (I'm likely to participate if and only if this gets fixed; I'm not willing to risk my rating on a round where about 25% of C solutions FST.)
How many common problems between div1, div2 and VK Cup Final?
)
Thanks for the birthday round :) Hopefully, I can inflate up back to div1 lol
wait, I didn't get it..Is the contest already conducted as VK cup final and we are gonna get the same problems today?? Please clarify I am a newbie
How are the rounds constructed from the actual finals? Because original only had 6 problems. And reds only solving A and B, really scares me.
Read that line also-:
Additional problems for codeforces rounds were authored and prepared by Supermagzzz, Stepavly and MikeMirzayanov.
So they prepared two extra problems for Div. 2 right? And rest will be from the VK cup?
That gives me hope.
(
)
Do you guys prepare for exams?
We don't
Can someone please explain something? It seems to me that the people in the scoreboard have already been through the problem set are playing the role of testers in a way, and are not going to participate in the contest today! Am I right about this?
how many new problems are added for div 2?
2 probably
can anyone tell me where i can find previous rounds based on VK cup on codeforces?
you can find any cf contest here in well organized manner.
I have seen the scoreboard of VK Cup Finals 2019/20. Even some red coders were able to solve just one problem!! Is it really for div2 users?
Keep company with your rating for the last few hours before farewell.
to make it div2 some div2ish problems will be added
Score distribution?
Edit 1: 25 minutes left and we don't even know yet how much problems are there
this is a serious issue, sorry for the tag MikeMirzayanov
Edit 2: 10 minutes, I think contest should be delayed. smh
How many Questions appears on the content???? and What there Score distribution?
Please mention the contest duration, the approximate number of problems and score distribution of the problems in each div?
isn't it ? :(
No it's not
Wait, full scoreboard? Isn't that a big spoiler?
May be they travelled future.
No, it's for the onsite but it gives out some nontrivial information.
May I become a Candidate Master after this contest
Best of Luck :)
Why such a bad ordering?
I have this strong nagging feeling that I saw div1D before. Idk why.
I think it's a variation of the problem 'termites' from the famous Looking For A Challenge book. I have read the problem after the contest but these ideas can probably be applied there
Why divide and conquer doesn't work? It seemed soo classical. Is it an alternation of d&c optimization?
My solution is kind of d&c. So we're doing basically knapsack DP for all "skip one array, all other arrays are either fully taken or ignored" cases. We can add $$$A$$$ arrays to a DP state in $$$O(AK)$$$. If we have a state where we processed all arrays except $$$[2^k \cdot i, 2^k \cdot (i+1)]$$$, we can use that to compute states for $$$[2^{k-1} \cdot 2i, 2^{k-1} \cdot (2i+1)]$$$ and so on. Okay, it's not really d&c but there's splitting ranges involved.
I was somewhat surprised to see $$$1A=2D$$$ and $$$1B=2F$$$, and other problems are not common between both division.
Though looking at solves it was practically $$$1A = 2D$$$ and $$$1B = 2E$$$.
problem D div 2
what test can be in test 2 ?
Same question!
Probably a lot of things. The whole problem has 5 pretests.
Its most likely just all permutation of some small numbers. If you want try some of the following, these were cases I came up with while I was stuck on the incorrect idea, it might help:
That helped indeed. Ty!
Thanks man
1
5
2 4 3 4 2
NO
indeedly NOOOOOOOOOOOOOOOOOOOOOOO ):
It was only for me that Codeforces was down from 12h30 UTC-3 to 13h15 UTC-3 or it was like that for others? Maybe an internet issue on my computer? I could acess other websites though.
I have no Idea of D. So I would like someone to give hints/spoilers so that I can go towards building a solution. Help Appreciated in advanced !
You need to find two sequences $$$b, c$$$, such that:
$$$min(b_i, c_i) \gt = 0$$$
$$$b_i + c_i = a_i$$$
$$$b_i \lt = b_{i-1}$$$
$$$c_i \gt = c_{i-1}$$$
You can create them greedily from the end, giving $$$b_i$$$ lowest value possible ($$$max(a_i - c_{i+1}, b_{i+1}$$$)).
I got this intuition pretty quick .. But sadly after this I have no idea what to do next :<, Thanks for help !
Notice that $$$a[i] - a[i - 1] = (c[i] - c[i - 1]) - (b[i - 1] - b[i])$$$. Notice how the the difference of consecutive elements can be written as difference of 2 positive terms, and all such positive terms are independent (as they are just elements of the difference array of $$$b$$$ and $$$c$$$) so it looks like there always exists a solution. However try to figure out why sometimes no solution exists.
Yea, I would try again, seems I have a interesting upsolve this time . Thanks for help :)
D1A is very similar to 1406D (which was in my contest)
3 of the first 4 problems greedy? :(
true :(
The sample tests have been extremely unhelpful for me this time.
Wrong answer on pretest 2
Couldn't figure out $$$C$$$, what was the solution?
I binary searched the answer
So did I. Didn't work for me however. Maybe I messed it up completely. Will have to debug more.
I am sure that its not the intended solution but you can binary search the answer
Sort by delivery time. Iterate in decreasing order of delivery time. If you decide to choose a restaurant with delivery time d, you don't need to go to all the restaurants whose delivery time is less than d. So just keep iterating till your pickup time is less than the current delivery time, and when it isn't, break.
I think this is a way simple and easy to understand than binary search O(nlogn) due to sorting solution 97471086
Approach for Div2 B??
Greedy. For each segment of 0s, you can either destroy the two 1s segments on its left and right separately or combine them using making all 0s 1 and then just destroy one segment.
Treat any chunk of 0's between two 1's as a bridge, greedily check if taking that bridge is optimal or not, i.e. (bridge_size * b) < a. This is because taking that bridge will save you 1 detonation (a coins)
shouldn't it be (bridge_size*b)<a i mean you swwapped a and b Edit: plz react
yeah whatever you get the point.
greedyforces
IN D is there any concept , find leftmin and rightmin and if current element is grater than sum of leftmin and right min then answer is no else yes. Is this approach is right ?
No, that did not work for me. Try 1 2 1 2 1
its like sum of all min ...?
Sum of all min?
No, for example try 1 2 1 2 1
Your answer is YES but it should be NO
97488984 Can anyone explain why this code give me WA on 681 DIV2 C but gave all correct on my compiler
I'm gonna die if my div1D gets correct. Stupid WAs on pretest 2 costed me.
You meant Div2E?
div1D. A clever dp, I got the idea very late and couldn't do anything
i got that we make dp[n][k], but didn't understand how to make transitions faster than O(n).
Nevermind, TLE on test 10
Is Div2 C solved with binary search?
I solved using binary search.
I tried to binary search the time taken for the couriers delivery. Is that correct?
You can check at particular time t. Let ans=0; All the items whose courier time is less than or equal to t ignore them. And add time petya takes to ans otherwise. return ans<=t
Yes, it should be correct!!
Binary search worked for me :)
Fun fact : I am the only one in my room who did a binary search solution on C, So its definetly not a intended solution
in previous 3 contest some problems pass pretest but fails in system test , i hope not to repeat my streak lol.
How to solve C?
For example, a binary search for the answer. Let's say we are given a number x. How to determine whether we can do this in no more than x? (Checker for the bs) Well let's go through the a array. If a[i] > x then we definitely need to go there on our own, since the company is not fast enough. Summarise all such a[i]. If sum > x then x is to small. If sum <= x, then this can be done in x.
(In the start l bound for bs is 0 and r bound can be the largest a[i]) 97454890
tbh Div2 A was very difficult for me to come up in < 10 minutes (in my real account) . Does any one else faced same issue ?
Whats your real color ?
How to solve D?
Consider an array $$$d$$$, where $$$d[0] = a[0]$$$, and for other positions, $$$d[i] = a[i] - a[i-1]$$$, which is the consecutive difference. The problem becomes like this, you have to make all the elements of the array $$$d$$$, 0. Now, decreasing all values of the segment $$$[0,r]$$$ of the input array $$$a$$$ by $$$1$$$ means to do $$$d[0]:=d[0]-1$$$ and $$$d[r+1]:=d[r+1]+1$$$. And decreasing all values of the segment $$$[l, n-1]$$$ by $$$1$$$ means to do $$$d[l] := d[l]- 1$$$. The reason for this is, if you increase or decrease the value of a segment by a constant, the difference of the consecutive elements of the boundary values of that segment are affected only. Try out some examples if you don't get it. So, you are allowed to decrease any element of the array $$$d$$$ by $$$1$$$ (operation 2), but if you want to increase any of the elements by $$$1$$$, you must also decrease $$$d[0]$$$ by $$$1$$$ (operation 1). So, summation of absolute value of all the negative values of the array $$$d$$$ must be less or equal to $$$d[0]$$$.
wow nice analysis brother
Thanks. Scaling the values of a range of an array using the difference array trick is quite common I guess. That comes to my mind first when I see this kinda range update problem.
Can someone tell me what's wrong with the logic in this code for Div2 D:
https://codeforces.me/contest/1443/submission/97488563
basically, going through the elements from left to right, and checking if the smallest number on the left is smaller than the current number => if it is we check if we can decrease this current number from the right(by checking the minimum on the right) to make it equal to the smallest number on the left, if we can't decrease it then the answer is no, otherwise we decrease the whole range on the right by that amount^.
https://codeforces.me/contest/1443/submission/97496228 Accepted... my dumb ass forgot to clear the lazy segment array when building.
I really multiple test cases in the same test.
I think A is harder than B.
I agree.
but div1 ranking says that div2F is easier than div2D
Has anyone solved B with DP?
I did
Can someone tell how to solve the 4th problem? My logic was to make the array first decreasing and then increasing, if I am able to do so then answer is "YES" else the answer will be "NO" and but I was getting WA on pretest 2!! Can someone point out the mistake?
I was also thinking the same!
You can set all decreasing prefix to 0. From that index try to decrease further elements the maximum you can and also do not decrease any element more than previous element. Check if array is sorted if yes ans is yes else no. Maximum you can decrease will depend on previous elements. 97452271
My correct solution I was thinking in the correct direction but I missed some trivial cases !!
Obviously your logic fails at
3
1 2 1
No, in this case I can make it like I told earlier!! Take 1st 2 elements and then decrease it by 1 .... Now 0 1 1 is the type of array which I have to make ..... So the answer is YES!!
Look at my solution. It is simple enough.
Please explain your approach with some small examples.
Hey everybody! Could you please comment why the following solution of div2 D is wrong (or maybe it's ok and I'm so freaking stupid that just have spent more than an hour to implement this correctly)
Looks like a strict proof, but where is my mistake?
UPD: seems like the proof is ok and I'm kind of an idiot :D
Can you check your code with this input:
6
1 5 4 5 4 4
The correct answer is NO.
Can someone tell me what's wrong with my solution? 97486806
Spent half the contest on A . Solved B + C + D for the remaining time
lol I spent 30 mins for ABC and bricked on D
D2/F is quite easy, solved it after contest, but don't have enough time. RIP. Hope I can solve previous problems quicker next time!
I solved A almost one hour!!!
What was B? Couldn't understand in the whole contest. I need to improve my English more.
:(
Can someone explain test case 1 of the Problem B so that I can understand, What was the Problem.
What about the sample in particular do you not understand? 2 In the first one, it is best to activate both mines, while placing none, giving a total cost of $$$2 \cdot 1 = 2$$$. In the second sample, it's optimal to place a mine at index $$$4$$$ ($$$1$$$-indexed), and then activating any of the mines, which in turn will activate all of the other mines, with a total cost of $$$1+5=6$$$.
Actually I had misunderstood the problem, I was thinking about to make all the characters 1 using mines.
I totally misunderstood the Problem :(
can somebody say what is wrong in this Probelm B solution SOLUTION B
It is horrible complecated.
edit: never mind, I misunderstood the problem.
How is it the same problem?
I can't even open the link. CF just randomly throws me somewhere.
My aproach to Problem $$$D$$$ Div2 was:
For every $$$0 \lt i \lt n-1$$$ take $$$x=min(a[0],...,a[i-1])$$$, $$$y=min(a[i+1],...,a[n-1]$$$ and $$$if(a[i] \gt x+y)$$$ for any $$$i$$$ then the answer was NO, otherwise, the answer was YES. I can't find a case in which it doesn't work, could anyone help me?
I also did the same thing for D. In this test case it will fail:
5 4 6 2 7 5.OneLastDance were using an $$$\mathcal O \!\left( k \sum\limits_{i=1}^n t_i \right)$$$ algorithm to pass Div. 1 problem D: submission 97477874.
My similar submissions:
You can compare these two submissions, and you will be as confused as me.
(P.S. They called about $$$1.5 \times {10}^9$$$
std::maxfunctions)Separate question, but do you know what the pragmas actually do? I've seen many people use pragams from
#pragma GCC target ("sse4")to#pragma GCC optimize ("O3")to#pragma GCC optimize("unroll-loops"). I just randomly include some subset of these pragmas and hope for the best, as I have no idea what they actually do and which pragmas are actually useful.They discuss in detail on this blog: https://codeforces.me/blog/entry/66279?#comment-502778
Seems like in the first code inner loop wasn't vectorized. Honestly, I wasn't sure if it would be so I used another variable to store maximum and turns out it was good decision xD
I've read something like https://www.archer.ac.uk/training/course-material/2017/10/KNL_Camb/Slides/L04-Vectorisation.pdf to learn about vectorization and pragmas. Maybe this will help you too
Thank you very much!
Just write your own inline assembly 420 lmao. Btw there's a function attribute to display what gets vectorised and another to only enable extra optimisation on a given function.
When will rating be updated?
UPD: Ratings changed!
Dreams come true ;)
congrats man.
Thanks <3
what does upd stand for?
update
thank you
You are not allowed to have two accounts competing in the same contest.
Please, guys, can you let me know if the Div2 C question nowadays easier than the previous times. The reason I want to know is that for the past few contests I am able to solve the DIV2C question so I thought I was improving but at the same time my rating is always in the range 1400-1500 which implies I am stuck at the same solving level. Can someone help me with this?? Thanks in advance!!
You can check the problems' difficulty in the problemset section.
Yet, regardless of the problem's rating, you're neither stuck or improving, you have only 11 contests and a few months in this business
Solving Div.1D with $$$O(nk^2)$$$ solution and lots of optimizes is soooooooooo cool
Nah, you don't need nearly that many. See a few comments above.
What is "soooooooooo cool" about it? The fact the Time Limit is set to 1500 ms and not 1000 ms?
The round VK Cup 2019-2020 - Final Round (Engine) has a problem 1441F - Matching not included in the Div1/Div2 versions, and it is not included in the problemset page. It seems the only way to submit it is by virtual participation, and many people have done this already. Can you make this problem available for normal practice?
300iq