Today we will celebrate the winners of the VK Cup 2019-2020! Even though finalists will not get together on the New Stage of Alexandrinsky Theatre in St. Petersburg, as initially planned, they will battle for the bragging rights to be called VK Cup Champion and the grand prize of 524 288 rubles. Best of luck to all the finalists!

On Nov/02/2020 17:35 (Moscow time) we invite everyone to participate in Codeforces Round #681 (Div. 1, based on VK Cup 2019-2020 - Final) and Codeforces Round #681 (Div. 2, based on VK Cup 2019-2020 - Final).

VK Cup problems are created and prepared by 300iq together with the VK team PavelKunyavskiy, izban, YakutovDmitriy, Kurpilyansky and .tx. Additional problems for codeforces rounds were authored and prepared by Supermagzzz, Stepavly and MikeMirzayanov.

We’d like to thank for the huge help in preparing and testing the problems MikeMirzayanov, ecnerwala, Egor, hos.lyric, yosupo, lperovskaya, Stepavly, Supermagzzz, HIR180, qwerty787788.

Good luck and have fun!

**UPD:** And the winners are:

Congratulations! Full scoreboard is available here.

**UPD:**

**Div.1 Scoring: 500 1000 1500 1750 1750 2500**

**Div.2 Scoring: 500 1000 1500 2000 2500 3000**

**UPD:** Editorial

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?

spoilerI 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

Yep

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

Yes, not for C. Master,like u :(

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.

Congrats -is-this-fft- you just crossed 1000 friends

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) >= 0$$$

$$$b_i + c_i = a_i$$$

$$$b_i <= b_{i-1}$$$

$$$c_i >= 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.

Pseudocode for the check function in my binary searchI 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.

Redacted

I did it using DP.

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?

i'm talking with respect to my first comment ... but yeah you can help me with some good idea to solve D.

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

In C, you just needed to sort the timings of array 'a' in non-increasing order, and changing the corresponding timing of array according to the order of a. Now,while iterating from beginning to the end of array 'a', you will encounter 3 cases:- 1. the earlier chosen time will be greater or equal than the ith timing of array a, meaning u need not to do anything 2.if the sum of previously choosen time and ith element of array 'b' is greater of equal to ith element of array 'a', then u need to choose timing to be ith element of array 'a' 3.if the sum of previously choosen time and ith element of array 'b' is smaller than the ith element of array 'a', then you need to increament the present time by ith element of array 'b'

Here is my code for reference:- https://codeforces.com/contest/1443/submission/97478698

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.com/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.com/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

even harder than c imo.

Has anyone solved B with DP?

I think i did

I did

please explain

yes

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.

Today i did well :D so now i will say very nice contest!!!:v :v

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

Great Contest for me !! This was the first time i was able to solve 4 problems in DIV2 . Hope it pass the system tests as well . I was feeling low since past few weeks but now it gave me strength . Will try my best to keep it up!!

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<i<n-1$$$ take $$$x=min(a[0],...,a[i-1])$$$, $$$y=min(a[i+1],...,a[n-1]$$$ and $$$if(a[i]>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`

.97469524

97461864

I found 2 contestant with the same code in current and previous contest.

alechin28 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::max`

functions)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.com/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.

Very cool

.

When will rating be updated?

UPD: Ratings changed!

Can someone please suggest me a test case where this solution fails for div2 D) plzz https://codeforces.com/contest/1443/submission/97507027

Try out this coding contest: https://www.credit-suisse.com/pwp/hr/en/codingchallenge/#/howtoplay/?promocode=jain-shreyansh

Dreams come true ;)

congrats man.

Thanks <3

what does upd stand for?

update

thank you

thank you

You are not allowed to have two accounts competing in the same contest.

Two account?? This is cheating. So bad

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

optimizesNah, 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