Codeforces Round #681 [Div1 and Div2]
By PavelKunyavskiy, 4 years 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

Comments Comments (171)
| Write comment?
»
4 years 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)

→ Reply
»
4 years ago, # |
  Vote: I like it -114 Vote: I do not like it

is it rated??

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -25 Vote: I do not like it

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

    → Reply
  • »
    »
    4 years 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. :)

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Best Wishes to the contest!

→ Reply
»
4 years 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?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope that there will be interesting and pleasant problems)

→ Reply
»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Note that the start time is usual. :)

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

please tell me how to put a photo in the comments. plsss ＼(＾▽＾)／

→ Reply
»
4 years ago, # |
  Vote: I like it +50 Vote: I do not like it

Was it rated?

spoiler
→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wish it a big success!

→ Reply
  • »
    »
    4 years 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? :)

    → Reply
»
4 years 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

→ Reply
»
4 years ago, # |
  Vote: I like it +259 Vote: I do not like it

Wow tourist won before it even started!

→ Reply
»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Congrats tourist for another victory!!

→ Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    Why there's public scoreboard in the first place

    → Reply
    • »
      »
      »
      4 years 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.)

      → Reply
»
4 years ago, # |
  Vote: I like it +32 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

![ ](IMG_20200929_110612.jpg)

→ Reply
»
4 years 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

→ Reply
»
4 years 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

→ Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
»
4 years ago, # |
  Vote: I like it +49 Vote: I do not like it

(IZOBRAZENIE_2020-11-02_150541.png)

→ Reply
»
4 years 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?

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

how many new problems are added for div 2?

→ Reply
»
4 years 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?

→ Reply
»
4 years 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?

→ Reply
»
4 years 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

→ Reply
»
4 years 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

→ Reply
»
4 years 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?

→ Reply
»
4 years ago, # |
  Vote: I like it -46 Vote: I do not like it

isn't it ? :( 44wfcm.png

→ Reply
»
4 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

May I become a Candidate Master after this contest

→ Reply
»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Why such a bad ordering?

→ Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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

    → Reply
  • »
    »
    4 years 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?

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

problem D div 2

what test can be in test 2 ?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same question!

    → Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years 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
    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    1

    5

    2 4 3 4 2

    NO

    → Reply
»
4 years 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.

→ Reply
»
4 years 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 !

→ Reply
  • »
    »
    4 years 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}$$$)).

    → Reply
    • »
      »
      »
      4 years 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 !

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
        • »
          »
          »
          »
          »
          4 years 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 :)

          → Reply
»
4 years ago, # |
  Vote: I like it +29 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

3 of the first 4 problems greedy? :(

→ Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I binary searched the answer

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it
        Pseudocode for the check function in my binary search
        → Reply
  • »
    »
    4 years 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

    → Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years 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

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Approach for Div2 B??

→ Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years 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)

    → Reply
»
4 years 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 ?

→ Reply
»
4 years 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

→ Reply
»
4 years 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.

→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Is Div2 C solved with binary search?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I solved using binary search.

    → Reply
    • »
      »
      »
      4 years 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?

      → Reply
      • »
        »
        »
        »
        4 years 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

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, it should be correct!!

        → Reply
  • »
    »
    4 years 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

    → Reply
»
4 years 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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

→ Reply
  • »
    »
    4 years 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

    → Reply
»
4 years 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 ?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

→ Reply
  • »
    »
    4 years 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]$$$.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      wow nice analysis brother

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
»
4 years 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.net/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^.

→ Reply
»
4 years ago, # |
  Vote: I like it -9 Vote: I do not like it

I think A is harder than B.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Has anyone solved B with DP?

→ Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was also thinking the same!

    → Reply
  • »
    »
    4 years 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

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Obviously your logic fails at

    3

    1 2 1

    → Reply
    • »
      »
      »
      4 years 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!!

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Look at my solution. It is simple enough.

    → Reply
»
4 years 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

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years 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

→ Reply
»
4 years 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!

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I solved A almost one hour!!!

→ Reply
»
4 years 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.

:(

→ Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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$$$.

      → Reply
      • »
        »
        »
        »
        4 years 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 :(

        → Reply
»
4 years 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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

edit: never mind, I misunderstood the problem.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    How is it the same problem?

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years 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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Thank you very much!

      → Reply
    • »
      »
      »
      4 years 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.

      → Reply
»
4 years ago, # |
  Vote: I like it +87 Vote: I do not like it

Dreams come true ;)

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what does upd stand for?

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it -32 Vote: I do not like it

thank you

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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!!

→ Reply
  • »
    »
    4 years 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

    → Reply
»
4 years 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
→ Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years 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?

    → Reply
»
4 years 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

→ Reply