By tourist, 13 months ago, translation, In English

Hello again!

VK Cup 2021 - Final (Engine) starts very soon: on Aug/22/2021 15:05 (Moscow time). Today, 32 best contestants of the elimination round will be fighting for cash prizes and eternal glory.

You can follow the course of the contest and root for your favorite contestants via this link.

Everyone except for VK Cup 2021 finalists is invited to Codeforces Round #740 (Div. 1, based on VK Cup 2021 - Final (Engine)) and Codeforces Round #740 (Div. 2, based on VK Cup 2021 - Final (Engine)) that start a couple of days later: on Aug/24/2021 17:35 (Moscow time). The rounds will be rated for everyone.

All the problems were authored and prepared by me. Big thanks to everyone without whom this round would not be possible: KAN, PavelKunyavskiy, scott_wu, xiaowuc1, Monogon, Aleks5d, lperovskaya, MikeMirzayanov. Special thanks to s-quark (2nd place of the first ever VK Cup 2012!) for inspiring problem titles.

You will be given 6 problems and 2 hours 30 minutes to solve them in both divisions. It is recommended to read all the problems. Good luck!

UPD: Scoring distribution in the VK Cup finals: 500 — 1250 — 1500 — 2000 — 3000 — 3500

UPD2: Congratulations to the winners of the VK Cup 2021 Final Round!

  1. never_giveup
  2. Maksim1744
  3. Um_nik
  4. SpyCheese
  5. Nebuchadnezzar
  6. vepifanov
  7. Golovanov399

UPD3: Division 1 round will be held on the VK Cup 2021 Finals problem set without any changes.

Scoring distribution for Div. 1: 500 — 1250 — 1500 — 2000 — 3000 — 3500

In Division 2 problems BDEF will match problems ABCD of Div. 1. Problems A and C of Div. 2 will be similar to problems F and E of Div. 1 (albeit being much easier). Besides that, problem D of Div. 2 will have a subtask with lower constraints than the original problem.

Scoring distribution for Div. 2: 500 — 1250 — 1250 — (1500 + 1000) — 2500 — 3500

As a reminder, the standings of the VK Cup Finals are available via this link — feel free to try gaining an advantage using all the information available before the round :)

UPD4: Editorial is available.

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

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

another great round is coming :)

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

    It's tourist Round.

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

    Why are you getting downvoted?

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

      codeforces.

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

        Many people have the mindset of "me see rating below 1900, me go downvote"

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

          It would be nice to add the ability to see who exactly downvoted or upvoted you. This will keep those people off.

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

            or it just would be more of a reason to downvote

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

              At least it would make random downvoters fear the possible consequences if they are made known to the victim.

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

                there are no possible consequences

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

          me see comment not from 1-gon, me go downvote

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

Hope for a great round, good luck everyone.

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

Amazing round!

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

Good luck

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

Going

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

Hoping for a god contests

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

orz

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

best whishes.

»
13 months ago, # |
  Vote: I like it +41 Vote: I do not like it
What's Special
»
13 months ago, # |
Rev. 2   Vote: I like it -31 Vote: I do not like it

Problem C of last two rounds made by tourist can be solved using binary search so what are the odds that this time also it's gonna be binary search. As he is on hattrick.. Binary_Tourist

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

    you are right there.. hattrick done...

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

      Yes, but really i don't have an idea why CF community gave so many downvotes to my instinct..

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

tourist rounds are always great! Very excited to participate this round!

Sorry for disturbing tourist :(

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

Everytime tourist writes a blog, his contribution reaches to the moon.

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

i was planning not to enter this round but when i saw that tourist is the author im going to enter and i hope i do well and stop my decreasing rating streak.

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

Making rounds based on some contest that has been held 2-3 days before, carries the risk of problem leakage. We do have seen such instances in the past when people submitted the first three problems in such minimal time which wasn't even enough to read them.

If someone finds this wrong then feel free to comment. This is only my personal opinion and I think that fair competition is not possible in such cases because some people get an unfair advantage.

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

    If I am saying something wrong then feel free to rectify it.

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

    There is no obligation to participate.

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

    This round was the Vk cup final. And all the contestants of this round were GM or above, also they're very well known in CF.

    It's highly unlikely that they would leak problems or cheat.

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

      Rounds that were based on many other contests have witnessed the same thing I am talking about. Not particularly with this round but there have been contests(based on some Random Olympiad) in the past in which the same thing happened as stated above.

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

    First of all, most of the participants of the final round of this VK cup have written contests for CODEFORCES before. So I think they will respect other contests, if not then the same thing could happen to their contest(by testers or whatever else) and that, of course, is not what an author would want.

    What you mentioned is correct, but that round was not based on the final round of another contest, if I'm not wrong it was based on an elimination round.

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

    What you have seen are virtual participants, which are not rated(they joined the contests after it finished).

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

Hopeforces...

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

Hello again! = excitement again! :D

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

I see that viewing this list has revealed the level of problems in div1

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

    How do you propose to win using this information?

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

      First, you must analyze the level and skills of each participant in this list and find out the favorite and non-favorite topics of each of them.

      Then you put some questions and answer them:

      • Why couldn't eatmore and receed solve the problem C? Although eatmore managed to solve both problems D and E.
      • Why couldn't mhq and Egor and KostasKostil solve the problem D? Although they managed to solve problem E.
      • Why did Endagorion and Petr solve only 3 problems?
      • Why was no all "Legendary Grandmaster" racer able to solve the last problem? Only never_giveup and Maksim1744 managed to solve it.
      • There are a lot of questions too!

      After answering all these questions and looking at the old tourist Contests, you can guess the topics of the problems and prepare for them well and develop an appropriate plan for this Contest!

      good luck for everyone!

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

        Wow, that's a lot of notifications.

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

        (⊙.⊙(☉ₒ☉)⊙.⊙)

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

        You spend way too much effort on this for it to be a joking post. See you in top 5 then.

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

        It's simple: my cat walked on the keyboard and wrote a solution to problem E. I tried to persuade her to write D as well, but she was unshakable.

        P.S. Yes, as you can see from the score I have, solution was correct not on the first attempt. Even cats sometimes make mistakes.

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

          I need your cat tomorrow, don't worry about the food, it's on me.

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

          i need your cat as a personal coach for mine, as my cat skills can solve max C div2 and want to develop. edit: it will pay with tuna.

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

      Ormlis Congratulations for the Nutella, sounds like you managed to use the information :D

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

        Thanks! Yes, I changed my strategy a bit for this contest =)

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

2000+ upvotes easily

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

My screencast (will become available after the round 740)

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

The score distribution is for both Div1 and Div2?

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

    neither, it is for the offical contest.

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

Good luck to everyone ( ◜‿◝ )

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

Has anyone noticed that the winner never_giveup was the last qualified person (Rank 32) of the elimination round! Congratulations for never giving up :)

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

    I think its a lesson for us that we should never_giveup. :p

    Congrats never_giveup !!

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

      I also never_giveup even after being stuck at specialist for around 8 months now .

      • »
        »
        »
        »
        13 months ago, # ^ |
        Rev. 3   Vote: I like it -65 Vote: I do not like it

        Hey, I understand that you want to make a point, but don't you think tagging is unnecessary? I believe noone likes to be tagged just to see their handle being called just to see your struggle :p

        Edit : Why downvotes :( , It was just a sarcastic comment which is often used by Ari

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

          Yeah,actually i thought to write something else before but then i wrote this and forgot to remove the tag

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

          bro this is codeforces here you can get downvoted for no reasons. You dont believe me checkout my blogs

        • »
          »
          »
          »
          »
          13 months ago, # ^ |
          Rev. 2   Vote: I like it -20 Vote: I do not like it

          i think now it's a lesson for you and again never_giveup on commenting.

          So many downvotes ,still never gonna give up

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

          Says the one who tagged the same person twice in one comment?

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

FINGERS CROSSED (̶◉͛‿◉̶)

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

Good luck to everyone!

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

This round was the final of the Vk. And all the contestants on this round were GM or above, and they are also well known in CF.

They are highly unlikely to cause leaking issues or cheating.

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

I desperately want my contribution to be the lowest on this website,so please,do not give me any upvotes,I am begging you:)

  • »
    »
    13 months ago, # ^ |
    Rev. 4   Vote: I like it -16 Vote: I do not like it

    Amen

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

      Yep, my wish is coming true, my contribution has been 4 point lower, big thanks to you guys:)

      And also, my first flag is to let my contribution be lower than yours @ELlMlNaToR

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

        Well if you want to go below me then cfiians might need to upvote me as well along with downvoting you right ?

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

          Ironically, I have never got a contribution higher than 0:)

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

I just came back to pupil with a div3 of +147. Now, I'm afraid to be gray again. Anyway, Enjoying the contest is important. Good luck to everyone. I am waiting for a high-quality contest!

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

First place winner is never_giveup .. hmmm I feel this is a sign )':

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

I'll never give up <3

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

never_giveup's nick should have been 'never_gonna_give_you_up' to rickroll the standings!

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

Since this round is prepared by tourist, you might as well check out some of his tips on competitive programming. link

»
13 months ago, # |
Rev. 4   Vote: I like it -11 Vote: I do not like it
»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it

We love the earth :)

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

LOL .. I thought the fanart image of the VK Cup was loading wrong in my screen :')

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

fine

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

Won't be able to solve any problem! Still participating :)

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

    Me too :(

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

      dude, you are a blue coder yet you are saying this?? You are soooo much better than me, man! I wish I knew half of what you know right now! I feel jealous :3

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

        hehe, Blue is nothing to be proud of, good luck I hope you get to solve a few problems :)

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

          I am still learning.. Maybe one day, I will be able to solve at least a few problems.

          Best of luck to you!

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

Good luck to everyone!

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

i can be wrong but Problem A statement is some how confusing for me (:

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

The problem statements are terrible!

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

tourist be like: Teri kehh ke lunga

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

I feel so dumb.

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

How to solve Div1D?

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

    Notice that the insertions put the following restriction on the final sorted array: for some positions $$$k$$$ and $$$k+1$$$ the values strictly differ $$$a_{k} < a_{k+1}$$$. For all other positions, the values might be equal. You have to count the number of such positions because if several insertions happen in the same place, they all contribute to a single restriction. To do so, you can track the current "strict" positions with a treap (it will allow you to increment positions for a suffix).

    Given the number of restrictions, let's look at the differences between subsequent elements. Add a 1 to the very beginning of the array and $$$n$$$ at the very end for simplicity. It's easy to see that for positions with restrictions the differences have to be at least 1, for other positions -- at least 0. In total, they should sum up to $$$n-1$$$, as the final element is now $$$n$$$ and the first is $$$1$$$. So, you have to divide $$$n-1-N_{restrictions}$$$ 1-point-differences between $$$n+1$$$ positions. By subtracting $$$N_{restrictions}$$$ we account for the "strict" positions. It is just a binomial coefficient.

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

      Damn, I think I got the second part, but I could not figure out how to find the strict positions. I guess I gotta learn treaps now.

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

      Ohh, I got the part after the calculation of those special points, but I am surprised that it involved treaps.

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

        Can be solved with segment trees, but using a treap is more straightforward here (find X, insert X, add 1 on the range).

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

        If you go backwards, you can get away with a Fenwick tree. All you need is point updates (subtract 1), queries, and lower_bound.

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

how do you solve B?

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

    Find the minimum number of breaks (let this be $$$x$$$). Now, every swap between A winning and B winning in will increase the number of breaks by 2 (because in the min. number of breaks, either all of A's wins are B's serves or all of B's wins are A's serves). So, we can reach everything in the sequence $$$x, x + 2, ... x + 2k$$$ breaks, where $$$k$$$ is the number of swaps we can make. You need to repeat this for both serving sequences ($$$ABABA$$$ or $$$BABAB$$$).

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

      There's an easier way around (IMO at least). Fix number of breaks A scores, for every $$$0 < i \leq a$$$. Now we can uniquely determine the number of breaks B possibly scored, because we know the total number of games A served, B served, A kept the serve, A lost the serve and B lost the serve. So just check for every combination if it's possible (total number of wins matches and no player won/lost negative number of times either by keeping their serve or breaking) and insert it into a set. Just print the output afterwards.

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

    Fix a K = total number of breaks._ Let K1 = number of breaks for Alice and K2 = number of breaks for Bob. Naturally, we have K1 + K2 = K. Now consider two cases: 1) The total number of games (a.k.a, a + b) is even: we know that the number of games where Alice serves the ball (call it HomeA) should be equal to the number of games where Bob serves the ball (call it HomeB)

    HomeA = HomeB
    a - k1 + k2 = b - k2 + k1
    a - b = 2 x k1 - 2 x k2
    k1 - k2 = (a - b) / 2
    

    and you also have k1 + k2 = K, so you could solve these. If k1 or k2 is negative or greater than a and b respectively, then the fixed value of K is invalid. 2) When a + b is odd, you could do the same work but this time, HomeA + j = HomeB where j = {1, -1}

    That is how I solved it not sure if there is an easier way to be fair.

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

    Consider a table

                 A serve  B serve  Total win
    A win        aa       ab       a (given)
    B win        ba       bb       b (given)
    Total serve  count_a  count_b       
    
    if a+b is even:
       count_a = count_b = (a+b)/2
    
    if a+b is odd: consider two cases
       count_a = (a+b+1)/2, count_b = (a+b-1)/2 
       count_a = (a+b-1)/2, count_b = (a+b+1)/2
    
    
    • You consider all possible values of aa which is between 0 to count_a inclusive.
    • For each possible value of aa, you can fill out the rest of the matrix like how you fill up a Sudoku.
    • The assignment is valid if all four entries are non-negative.
    • For each valid assignment, add k = ab + ba to the result
    • If a+b is odd, you consider the two possible set of values count_a and count_b could have.
»
13 months ago, # |
  Vote: I like it +4 Vote: I do not like it

B is harder than D for me and I waste a lot of time on it :(

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

terrible question b.

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

how to solve C?

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

    i did binary search

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

      i also did but it wrong on pretest 2.

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

      how do you sort the input array(caves)?

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

        They can be sorted by the max value of $$$a[i][j] - j$$$.

        UPD:

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

          tried this and also got wa on test 2

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

            same

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

            realized the mistake. Use Vector/array instead of map. There are some cases (subtest case 39 in test case 2) where map removes duplicates and it will lead to WA.

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

        I created a structure

        struct Cave{ int cnt ; int maxA ; };

        bool myCompare(Cave a, Cave b){ return a.maxA < b.maxA ; } void solve(int t){ int n; cin>>n ; Cave cave[n] ;

        FOR(i,0,n){
            int m ; cin>>m ;
            cave[i].cnt = m ;
            int maxA = INT_MIN ;
            FOR(j,0,m){
                int a; cin>>a ;
                if(a-j>maxA){
                    maxA = a-j ;
                }
            }
            cave[i].maxA = maxA ;
        }
        
        sort(cave, cave+n, myCompare) ;
        long long power = cave[0].maxA + 1 ;
        long long morePower = 0 ;
        FOR(i,0,n){
            if(!(power>cave[i].maxA)){
                long long diff = cave[i].maxA - power ;
                morePower += diff+1 ;
                power = cave[i].maxA + 1 ;
            }
            power += cave[i].cnt ;
        }
        cout<<morePower + cave[0].maxA + 1 <<endl ;

        }

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

    First of all, you have to find maximum one for every group. While finding maximum our heroes power should be at least:

    armor of monster — index of monster.

    after this, you should sort values of maximums and start from minimum one. if maximum in this group is bigger than answer increase answer

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

C was easier than B for me

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

    same.. the problem statement of B was quite confusing to me :(

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

How to solve the bigger constraint for D? I feel blank :(

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

    Mark multiples instead of checking factors. At a position $$$x$$$ for a given multiple $$$k$$$, we want to add $$$ans_{x}$$$ to all possible $$$y$$$ where $$$x = \lfloor \frac{y}{k} \rfloor$$$. This is just the range $$$[x \times k, (x + 1) \times k - 1]$$$. We can mark this range using a difference array by adding $$$ans_{x}$$$ to $$$diff_{x \times k}$$$ and subtracting it from $$$diff_{(x + 1) \times k}$$$.

    Now when we arrive at a pos $$$y$$$ we add $$$diff_{y - 1}$$$ to $$$diff_{y}$$$ to get the corresponding value added using multiples. Now we just add this to $$$ans_{y}$$$.

    Total complexity is $$$O(1)$$$ per multiple, so $$$O(n logn)$$$ total.

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

      I did the same thing but used a Fenwick Tree. Unfortunately, it TLEs. Maybe $$$O(nlognlogn)$$$ is not intended to pass.

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

        I suspect that is the case. Fenwick Trees are fast, but almost 2e8 operations on it feels like far too much. And anyway, it can be implemented using a simple array since we only update $$$y > x$$$ for a given x.

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

        I feel you :( I was convinced it's right approach just to see TLE test 7.

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

I get that the constraints for Div1B were probably in an attempt to exclude $$$O(n^{3/2})$$$ solutions, but... seriously?

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

    $$$n=4*10^6$$$ was too large for $$$O(n^{3/2})$$$. Soln I wrote gets tle for $$$4*10^5$$$.
    Regarding memory constraint, to me, it seems it was to stop precomputations of all factors of numbers using $$$O(nlogn)$$$ sieve.
    But still, it was imo a bad attempt since one can just compute all factors on the go using prime factorization.

    I ended up doing this.
»
13 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Total shot in the dark, but is Div1D somewhere along these lines? Consider an initial array $$$a_i = i$$$. Perform the $$$m$$$ specified swaps. Let there be $$$x$$$ positions, where $$$a_i > a_{i + 1}$$$, the answer is something like $$$2n - x - 1 \choose n - x - 1$$$.

Ik its probs wrong, I have no proof for this at all, just intuition + guesswork, and no way to calculate this independently of $$$n$$$ (something related to at most $$$2m$$$ possible segments to check maybe?)

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

    Yes, that's what I did.

    To calculate x, you can go backwards through the swaps, keeping track of the remaining indices with a BIT.

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

      Oof, I thought of using a BIT somehow but didn't think of going backwards, though it seems obviously easier now that you mentioned it. Thanks!

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

I don't know if it's me but the problems seemed pretty difficult compared to other Div 2s. Seems I have a lot to work on.

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

    B was a slightly more difficult than normal, but D was miles easier than usual. You get something — you lose something. :P

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

Can anybody plz mention any edge case for C for which my program is giving WA?

My Program:

#include <bits/stdc++.h>
using namespace std;

#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define fori(from, to) for(i=from; i<to; ++i)
#define forj(from, to) for(j=from; j<to; ++j)
typedef long long int ll;

int main()
{
	fastio; ll T; cin >> T;
	
	while(T--)
	{
		ll caves, i, j; cin>>caves;
		
		vector<pair<ll, ll>> vres; 
		
		fori(0, caves)
		{
			
		    ll monsters; cin>>monsters; vector<ll> vmon(monsters);
		    forj(0, monsters) cin>>vmon[j];
		    
		    ll maxval=INT_MIN;
		    forj(0, monsters)
		        maxval=max(maxval, vmon[j]-(j+1-2)); //finding the starting strength for every cave

		    vres.push_back(make_pair(maxval, monsters)); //maintaining a vector of pairs : starting stength for a cave || no.of monsters in that cave
		}
		
		sort(vres.begin(), vres.end());
		
		fori(0, caves)
		{
		    ll temp=vres[i].first+vres[i].second;
		    bool flag=true;
		    forj(0, caves)
		    {
		        if(i==j) continue;
		        if(temp<vres[j].first) {flag=false; break;}
		        temp+=vres[j].second;
		    }
		    if(flag) break;
		}
		
		cout<<vres[i].first<<"\n";
	}
	return 0;
}
  • »
    »
    13 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    the distance between the max value and the entrance of the cave matters, you can't just sort by max value

    add spoilers to your code as well

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

      Yes, based on that only I had calculated the initial strength at the starting of every cave. Can u plz pin point the line/section, where it is wrong, and how to correct that, or provide any test cases?

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

how to solve problem A ?

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

Div2 B was a nightmare for me.

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

its perfect time for cf to evolve since a lot of people are now solving c, this round was awesome

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

    C was easier than B

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

      Yess, for today but on an avg many people are doing a,b,c , maybe due to covid and being at home

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

I accidentally submitted Div1B two times: 126856468, 126857306. The first submission was from the main site, but the page did not respond for quite a long time and I thought that CF is down. The second one was from m1.codeforces.com. The code is completely identical, so is it possible to return back -50 points for the "ignored" submission as it shouldn't have happened if not for some lags? CC MikeMirzayanov

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

    I see a few submissions like that, they will be fixed after system testing is done.

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

Is there a stream to explain the solution to the problems?I'm waiting for it.

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

Really great problems! I liked div 1 C and D (even though I wasn't able to solve D during the contest).

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

So were there no hacks today? And that's so good about today.

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

C was way easier than B... I feel so dumb. This was my best chance to become specialist for the first time and I lost it.. T_T

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

Wow, it seems like 4 out of the top 5 of div 2 are alt accounts :v

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

I was getting MLE on test 7 in Div2 D2, I wonder if I should have have locked my D1 and looked into the submissions of D1 which were failing on D2 due to TLE but not MLE, I might have solved D2 then lol, but time remaining was very less.

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

    You can't lock simplified version until u solved not simplified, can you?

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

      Ohh, I am sorry, I think you are correct, we can't do that.

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

Any ideas on how to solve Div1 E?

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

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

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

    Hey,it so happened that my solution to problem C matches quite a lot with the one by another user. However, the code I submitted and the solution idea were completely mine and I hadn't taken help of even any online source (let alone copying someone's solution.) Also, regarding the ide part,I use codechef ide to code my solutions and those can only be viewed by signing in to my codechef account,so there was no leakage of code from my side atleast. Also,my solution was pretty basic and short ,so there is a high chance that it matches with someone else's code. The message I received said that if I have a conclusive evidence that the coincidence could have occured due to using some code published online before the contest,I can post those details as a comment to this post...but since, I hadn't used any online source to write my code, I have no idea how to prove my honesty except for the fact that the solution was too basic. I can also completely explain my solution if required. Also,due to this my rating was rolled back and this hurts even more since this was my best contest till now and I had crossed 1800 for the first time but now,I feel that I have been deprived of those rating points despite no fault of mine. So, I humbly request you to consider my participation in this contest valid and grant me the delta I deserved.

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

    It seems that you've removed some of the cheaters.But why haven't the ratings updated again yet?

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

+1 upvote for this wonderful round !

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

Can anyone explain how to do D1? I am not able to understand

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

solved my first problem

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

Can div2 D be solved using segment trees? if yes. please can anyone help me with the approach!

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

    Yes, I upsolved Div2 D1 problem using lazy segment tree implementation from the atcoder library:

    Spoiler

    The lazysegtree header file can be copy/pasted into the source code. It's fast enough for D1 126922899, but fails with TLE on D2 126922883. I need to check the editorial to see if anything can be improved or it's a dead end.

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

Can anyone help me with a weird issue that I faced after the div2C main tests.

This was my submission which passed the pretests during contest : 126871707. However, It got runtime error on test 13 which I was not able to figure out why.

I randomly removed the custom comparator function used in sorting and it got accepted : 126911540. Can anyone help me understand what went wrong in that comparator function? According to given input data, every vector should have at least one element.

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

Last tourist round, I lost pupil, this time I gained it back :D

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

is this round unrated for div1 participants? because ratings hasn't rolled back yet!

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

Hello , I am pretty sure that there is a mistake in engine check , please check those 2 solutions for problem C — Deep Down Below: this is my last submission in the contest : http://codeforces.com/contest/1561/submission/126904661

and this is the exact code except that i removed the compare function passed to sort , which actually does exactly the same as sort except when pair.first == pair.second , i choose the cave with more monsters , and this should not affect the solution : http://codeforces.com/contest/1561/submission/126961415

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

    Actually it can influence.

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

    A C++ comparator should return false when elements are equal, otherwise you can get a number of different verdicts (RE, TLE, WA and sometimes even MLE). (should be a.second > b.second, not a.second >= b.second)

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

MikeMirzayanov Today,I got a message from system whose first few words were- "Your solution 126867937 for the problem 1561C significantly coincides with solutions ultizet/126864317, dumb_boi/126867937." I would like to clarify that I use codechef ide to code my solutions and that code can only be viewed by signing in to my codechef account. Also,my code was pretty basic and I hadn't taken help of any online resource to come up with the solution idea or code or anything. The message said that I must post my clarifications as a comment to this post. Also,since the code was solely mine,I don't have any evidence of any online resource which i 'might have' used(simply because i didn't use any) ,so I don't know how to prove my honesty except for the fact that the problem was pretty basic and there as a high chance that 2 solutions match coincidentally. Also,my ratings were rolled back. This hurts as this contest was my best contest till now and I had crossed 1800 for the first time :( . Now, it hurts knowing that I might not get those rating points despite no fault of mine.

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

    I haven't recieved any reply from codeforces yet...maybe i didn't post my clarification where I was supposed to...can someone help? Do I have to post it as a seperate blog post or something?

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

When will the points for div 1 be restored?

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

Is it unrated? /fn/fn

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

Yay the points for Div 1 are rebalanced and back!

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

After I entered this div,I become purple.But for the roll back,the next div2 I get unrated? Can it be solved?

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

In the first problem of div 2 category. editorial code gives output 5 but its real ans is 4. 5 4 5 2 3 1 can anyone tell me why its output is 5?

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

tourist Why only 3 problems (A, C and D1) from the contest are put in practice section? When will remaining problems be posted? I mean in problemset section.

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

    All the problems are available in the problemset section, the problems from Div. 1 are just a bit further down the list.

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

nice round