By PavelKunyavskiy, 8 months ago, translation, In English

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:

  1. tourist
  2. Endagorion
  3. Merkurev

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

 
 
 
 
  • Vote: I like it
  • +293
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Auto comment: topic has been translated by PavelKunyavskiy (original revision, translated revision, compare)

»
8 months ago, # |
  Vote: I like it -114 Vote: I do not like it

is it rated??

  • »
    »
    8 months ago, # ^ |
      Vote: I like it -25 Vote: I do not like it

    I don't know why every time someone asks this question?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    When it is mentioned that it is a div2 / div1 round its anyways rated. It would be specified if it is some external contest. :)

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Best Wishes to the contest!

»
8 months ago, # |
  Vote: I like it +2 Vote: I do not like it

could you please mention the duration and the approximate number of problems in each div?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope that there will be interesting and pleasant problems)

»
8 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Note that the start time is usual. :)

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

please tell me how to put a photo in the comments. plsss \(^▽^)/

»
8 months ago, # |
  Vote: I like it +50 Vote: I do not like it

Was it rated?

spoiler
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wish it a big success!

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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? :)

»
8 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +259 Vote: I do not like it

Wow tourist won before it even started!

»
8 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Congrats tourist for another victory!!

»
8 months ago, # |
  Vote: I like it +36 Vote: I do not like it

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?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    Why there's public scoreboard in the first place

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it -21 Vote: I do not like it

      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.)

»
8 months ago, # |
  Vote: I like it +32 Vote: I do not like it

How many common problems between div1, div2 and VK Cup Final?

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

![ ](IMG_20200929_110612.jpg)

»
8 months ago, # |
  Vote: I like it +36 Vote: I do not like it

Thanks for the birthday round :) Hopefully, I can inflate up back to div1 lol

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +7 Vote: I do not like it

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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Read that line also-:

    Additional problems for codeforces rounds were authored and prepared by Supermagzzz, Stepavly and MikeMirzayanov.

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      So they prepared two extra problems for Div. 2 right? And rest will be from the VK cup?

      That gives me hope.

»
8 months ago, # |
  Vote: I like it +49 Vote: I do not like it

(IZOBRAZENIE_2020-11-02_150541.png)

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

how many new problems are added for div 2?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell me where i can find previous rounds based on VK cup on codeforces?

»
8 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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?

»
8 months ago, # |
Rev. 3   Vote: I like it +43 Vote: I do not like it

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

»
8 months ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

How many Questions appears on the content???? and What there Score distribution?

question-mark.jpg

»
8 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Please mention the contest duration, the approximate number of problems and score distribution of the problems in each div?

»
8 months ago, # |
  Vote: I like it -46 Vote: I do not like it

isn't it ? :( 44wfcm.png

»
8 months ago, # |
  Vote: I like it +22 Vote: I do not like it

Wait, full scoreboard? Isn't that a big spoiler?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

May I become a Candidate Master after this contest

»
8 months ago, # |
  Vote: I like it -13 Vote: I do not like it

Why such a bad ordering?

»
8 months ago, # |
  Vote: I like it +26 Vote: I do not like it

I have this strong nagging feeling that I saw div1D before. Idk why.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why divide and conquer doesn't work? It seemed soo classical. Is it an alternation of d&c optimization?

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
8 months ago, # |
  Vote: I like it +15 Vote: I do not like it

I was somewhat surprised to see $$$1A=2D$$$ and $$$1B=2F$$$, and other problems are not common between both division.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Though looking at solves it was practically $$$1A = 2D$$$ and $$$1B = 2E$$$.

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

problem D div 2

what test can be in test 2 ?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same question!

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it +25 Vote: I do not like it

    Probably a lot of things. The whole problem has 5 pretests.

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it

    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:


    5 1 2 3 2 1 NO

    5 3 2 4 2 3 YES (L1, L3, L3, R3, R3, R1)

    6 3 2 4 2 5 3 NO
    7
    5 7 6 7 6 7 5
    
    YES (L2, L4, L6, L6, L7, R2, R4, R6, R6)
    
    
    7
    5 7 2 4 2 7 5
    
    NO
    
    
  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    1

    5

    2 4 3 4 2

    NO

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
8 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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 !

  • »
    »
    8 months ago, # ^ |
    Rev. 5   Vote: I like it +4 Vote: I do not like it

    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}$$$)).

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I got this intuition pretty quick .. But sadly after this I have no idea what to do next :<, Thanks for help !

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yea, I would try again, seems I have a interesting upsolve this time . Thanks for help :)

»
8 months ago, # |
  Vote: I like it +29 Vote: I do not like it

D1A is very similar to 1406D (which was in my contest)

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

3 of the first 4 problems greedy? :(

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I binary searched the answer

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So did I. Didn't work for me however. Maybe I messed it up completely. Will have to debug more.

      • »
        »
        »
        »
        8 months ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it
        Pseudocode for the check function in my binary search
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am sure that its not the intended solution but you can binary search the answer

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think this is a way simple and easy to understand than binary search O(nlogn) due to sorting solution 97471086

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Approach for Div2 B??

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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)

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      shouldn't it be (bridge_size*b)<a i mean you swwapped a and b Edit: plz react

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Redacted

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did it using DP.

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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 ?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

97488984 Can anyone explain why this code give me WA on 681 DIV2 C but gave all correct on my compiler

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm gonna die if my div1D gets correct. Stupid WAs on pretest 2 costed me.

»
8 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Is Div2 C solved with binary search?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I solved using binary search.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I tried to binary search the time taken for the couriers delivery. Is that correct?

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, it should be correct!!

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

in previous 3 contest some problems pass pretest but fails in system test , i hope not to repeat my streak lol.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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

»
8 months ago, # |
Rev. 3   Vote: I like it -28 Vote: I do not like it

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 ?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

  • »
    »
    8 months ago, # ^ |
    Rev. 5   Vote: I like it +3 Vote: I do not like it

    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]$$$.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      wow nice analysis brother

      • »
        »
        »
        »
        8 months ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        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.

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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^.

»
8 months ago, # |
  Vote: I like it -9 Vote: I do not like it

I think A is harder than B.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Has anyone solved B with DP?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was also thinking the same!

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Obviously your logic fails at

    3

    1 2 1

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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!!

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Look at my solution. It is simple enough.

»
8 months ago, # |
  Vote: I like it -37 Vote: I do not like it

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

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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)

  1. We can make operations in any order we want.
  2. The amount of left-sided-operations for the element $$$i$$$ is more or equal to the same amount for the element $$$i+1$$$. The same for right-sided-operations. Let these amounts be $$$a_1, \dots, a_n$$$ and $$$b_1, \dots, b_n$$$ respectively.
  3. Let's go through the the sequence $$$v$$$ taking $$$a_1 = v_1, b_1 = 0$$$. Say we are looking at $$$i$$$-th element now. If $$$v_i > b_{i-1} + a_{i-1}$$$ than we need to increase $$$b_i$$$, thus $$$b_i = b_{i-1}, a_i = a_{i-1}$$$. Otherwise we need to decrease $$$a_i$$$ to $$$v_i - b_{i-1}$$$. If we can't do it — anser NO, otherwise we reach the end of the sequence and say YES.

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

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Can you check your code with this input:

    6

    1 5 4 5 4 4

    The correct answer is NO.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me what's wrong with my solution? 97486806

»
8 months ago, # |
  Vote: I like it -9 Vote: I do not like it

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!!

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Spent half the contest on A . Solved B + C + D for the remaining time

»
8 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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!

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I solved A almost one hour!!!

»
8 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

What was B? Couldn't understand in the whole contest. I need to improve my English more.

:(

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can someone explain test case 1 of the Problem B so that I can understand, What was the Problem.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Actually I had misunderstood the problem, I was thinking about to make all the characters 1 using mines.

        I totally misunderstood the Problem :(

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can somebody say what is wrong in this Probelm B solution SOLUTION B

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

edit: never mind, I misunderstood the problem.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    How is it the same problem?

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I can't even open the link. CF just randomly throws me somewhere.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I also did the same thing for D. In this test case it will fail: 5 4 6 2 7 5.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

97469524

97461864

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

»
8 months ago, # |
  Vote: I like it +31 Vote: I do not like it

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)

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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.

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it +36 Vote: I do not like it

    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

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Thank you very much!

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      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.

»
8 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Very cool

»
8 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

.

»
8 months ago, # |
Rev. 2   Vote: I like it -7 Vote: I do not like it

When will rating be updated?

UPD: Ratings changed!

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +87 Vote: I do not like it

Dreams come true ;)

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what does upd stand for?

»
8 months ago, # |
Rev. 3   Vote: I like it -31 Vote: I do not like it

thank you

»
8 months ago, # |
Rev. 3   Vote: I like it -32 Vote: I do not like it

thank you

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Two account?? This is cheating. So bad

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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!!

  • »
    »
    8 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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

»
8 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Solving Div.1D with $$$O(nk^2)$$$ solution and lots of optimizes is soooooooooo cool

optimizes
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Nah, you don't need nearly that many. See a few comments above.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    What is "soooooooooo cool" about it? The fact the Time Limit is set to 1500 ms and not 1000 ms?

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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