By tourist, 3 weeks ago, translation, In English

Hello!

Welcome to the Codeforces Round #844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round) that will start on Jan/15/2023 15:05 (Moscow time). It will be a combined rated round for both divisions and open to everyone.

This round is a mirror of VK Cup 2022 Elimination — annual programming championship for Russian-speaking competitors organized by VK. VK Cup started in 2012 and has grown to be a five-track competition in competitive programming, Mobile, ML, Go, and JavaScript.

All the problems are authored and prepared by me. Thanks to KAN, errorgorn, lperovskaya, dario2994, Monogon, Arpa for making this round better.

You will be given 8 problems and 3 hours to solve them.

UPD: Editorial

Congratulations to the winners:

  1. orzdevinwang
  2. noimi
  3. Radewoosh
  4. gamegame
  5. QAQAutoMaton

and to maroonrk for getting the only accepted solution to problem H2.

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

»
3 weeks ago, # |
  Vote: I like it +144 Vote: I do not like it

omg tourist round

»
3 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

Damn, 3 hours for only 8 problems. Scary

»
3 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

omg tourist round

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

    omg tourist round

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

      I am so interested in your graph, how did you maintain a slope of 45 degrees ?

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

        وانتا مالك؟؟

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
          Rev. 2   Vote: I like it -31 Vote: I do not like it

          What language is this, looks Arabic I don't know it. Speak in English. Also, I expressed my interest in speedy_boy graph NOT yours. Actually, your graph isn't interesting at all mr.newbie! The comment directed to you is below : Newbie detected, opinion rejected XD

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

            Respect to newbie

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
              Rev. 2   Vote: I like it +18 Vote: I do not like it

              yes sir. all due respect! but he seems talking in a rude manner to me by a foreign language tho I didnt talk to him and replied to ur comment only :-( However, your graph with slope 45 is so cool ✪ω✪ speedy_boy

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        For your first 6 contests, you actually start at 1400, and as you do contests your hidden rating is updated as normal and your shown rating rises rapidly-ish to reach it.

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

        He didn't maintain it after this contest though, if he did he should be orange by now.

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

    newbie detected.. opinion rejected xD

»
3 weeks ago, # |
  Vote: I like it +75 Vote: I do not like it

Shortest announcement ever *_*

»
3 weeks ago, # |
  Vote: I like it +192 Vote: I do not like it

Tourist can't compete against benq in this round, but he can make some crazy geometry problems to force benq to lose rating and get back to rank #1.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

3 hours? How difficult the problems will be

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe my "master experience card" will be expired in this contest.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't care about the difficulty lvl of the problems if it's Tourist Round. All i know that it is going to be fun.

»
3 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

Note the unusual timing

»
3 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

omg tourist round ...^,^

»
3 weeks ago, # |
  Vote: I like it +458 Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Guess will have to wait for tourist vs Benq :-(

»
3 weeks ago, # |
  Vote: I like it -120 Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

what you guys think is Benq gonna or not gonna participate this contest?

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

    Benq will not participate, because tourist has intentionally made problems with topics where Benq is weak. This is to make Benq fall to second place in top rating chart, so that tourist can become #1 again.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      xD

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh,man !! Is there any topic on earth in which these legendary guys are weak?

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

        I don't know, maybe some optimization of matrix multiplication algorithm from $$$O(n^{2.43})$$$ to $$$O(n^{2.42})$$$.

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

          To make benq lose rating you have to specifically make it hard for him. If it’s hard for everyone he won’t lose rating.

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

      But Benq is better...

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it -18 Vote: I do not like it

    I think Benq only wanna compete with tourist who is well-known as the No.1 in competitive programming. In my opinion, he will not participate contests without tourist such as this contest

  • »
    »
    3 weeks ago, # ^ |
    Rev. 6   Vote: I like it -35 Vote: I do not like it

    Benq only participate in the contest in which tourist participate.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Omg 3hr Round ><

»
3 weeks ago, # |
Rev. 3   Vote: I like it +4 Vote: I do not like it

I think, Benq will not perticipate in this contest. But I will participate and face to the world number one Programme's problems...☝️

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Score distribution.......???

»
3 weeks ago, # |
  Vote: I like it -44 Vote: I do not like it
tourist is a great person
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

omg tourist round

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

omg tourist round

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

omg tourist round

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

omg tourist round

»
3 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Omg clash with ABC.

»
3 weeks ago, # |
  Vote: I like it -28 Vote: I do not like it

I am a pro memer.

»
3 weeks ago, # |
Rev. 2   Vote: I like it -43 Vote: I do not like it

.

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

    My IQ has decreased by 20 points while trying to read this. Thanks.

»
3 weeks ago, # |
  Vote: I like it +38 Vote: I do not like it

This is the shortest announcement for a round that I have ever seen :))

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

    Legend don't need to say much. Their presence is enough alone sir!

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

omg tourist round . Probme 1 will be 1200+ Rated now

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It is rated ?(⊙﹏⊙)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

TFW you expect tourist to claim back first place then see that tourist himself is the author

»
3 weeks ago, # |
Rev. 3   Vote: I like it -39 Vote: I do not like it

.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it -16 Vote: I do not like it

    It was good one . Don't know what's wrong ? Maybe too rude or offensive for some people ?? Atleast you should have blurred the authors above. It's disrespectful for them.

»
3 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

Contest Clashing with atcoder Beginner Contest 285.

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

    Tourist round >>> Any Other round on this planet. As Simple as that .

»
3 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

I might just end up top1 because problems are being designed by tourist.

»
3 weeks ago, # |
  Vote: I like it -24 Vote: I do not like it
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

when I saw by tourist, inner me: Don't worry, Better luck next time!

»
3 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

Orz tourist round.

»
3 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

score distribution when?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

omg tourist round

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

omg tourist round

»
3 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

while(1) { OMG Tourist Round }

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There will be very Interesting questions. Very Excited for the round!!

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

GOAT

»
3 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

omg tourist round

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

ok

»
3 weeks ago, # |
Rev. 2   Vote: I like it -24 Vote: I do not like it

omg tourist round

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Should be Interesting.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

omg tourist round

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Thanks to MikeMirzayanov for amazing platforms Codeforces and Polygon.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

omg tourist round

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

Contest Collision (CF & ABC):

Timings
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

omg tourist round

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i do bad in tourist rounds, hopefully this will change tomorrow

»
3 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

why problem in this year contests are didn't given any rating till now?

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

conflict with ABC285... what a pity that i can't participate in both contests...

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Note the unusual timing.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It's such a piece of cake for tourist to send out a splendid contest. & Just BY HIMSELF !!!!!!!!

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

tourist gang

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

The One Piece is real!!!

»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Originally I am not planned to participate this contest because I have a date then. But when I see the author, I just postponed the date and register for this contest. Wish I can turn cyan once again.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

omg tourist

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

I wish the next round will be written by Benq

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Obviously tourist round will be full of fantastic problems. Good luck, yeah! ^=^

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

I will always be a fan of tourist!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

OMT Gods round

»
3 weeks ago, # |
  Vote: I like it -22 Vote: I do not like it

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

It is briefly before the beginning of the round now, and score distribution hasnt been announced yet...

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

is this rated for everyone?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

omg tourist round

»
3 weeks ago, # |
  Vote: I like it +79 Vote: I do not like it

Where is score distribution?

»
3 weeks ago, # |
  Vote: I like it -55 Vote: I do not like it

I think I may not be able to participate because I feel like going to the toilet right now. What a wrong timing. :(

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

glhf

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

OMG tourist round

I regret I couldnt participate in it as I got stuck with some personal work

»
3 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

omg tourist round

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

why the rating of H2 is higher than the rating of H1

it said that H2 is the hard version,doesn't it?

»
3 weeks ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

F is an amazing problem! couldn't code it in time though, but mindsolved it

Can somebody please tell the solution?

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

    $$$dp[i][j]$$$ = $$$P$$$(Minimum Prefix $$$\geq$$$ $$$ -j $$$ )

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

In E, finding maximum total area is not that hard but finding the exact subrectangles seems quite difficult. Stuck on it's implementation. Any approach regarding the same?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maintain a stack for the rightmost intervals for u, d, ud rectangles. It was very painful implementing this, especially when the contest started at 4am for my local time.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey, thanks. I just implemented the logic using your stack idea. Yeah, felt like handling a lot of cases!

      My solution

»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Pretty hard contest.

No idea for D. Have idea for E but got WA. Now I'll return to CM.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how's C done ....?

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 3   Vote: I like it +9 Vote: I do not like it

      It's pretty annoying. You need to consider all j that n is multiple of j, calculate how many char will be changed if you make the string to j kinds of different chars. You need consider 2 cases: j<j0 , j>=j0, where j0=the number of different chars in the initial string. If j<j0 you need change some chars with low frequency.

      After you decided the optimal j, you need to add all chars you'll put to the final string into a "char pool" (implemented as int pool[26]), first try to make every chars remain the same(if(pool[s[i]]>0) pool[s[i]]--; flag[i]=true;) the assign i where flag[i]=false any char in the pool.

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

    Well consider two indices i and j. now calculate all such x that make both a[i] + x and a[j] + x a perfect square. the rest should be easy

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    In E we can first shrink rectangles with same type (row1, row2, row1+row2) and then consider for each 2-height rectangle, shrink it if it's penetrated by any 1-height rectangle, and shrink every 1-height rectangles who doesn't penetrate it but cross with it.

    However I got WA at pretest 15. Also C was very annoying. I spent about an hour for it.

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

    What I did is calculate the answer firstly for two numbers, let's say a and b. We want to transform a into x^2 and b into (x+k)^2 (because b > a), and that means that $$$b-a = (x+k)^2 - x^2$$$, so $$$x = {(b-a-k^2)}/{(2k)}$$$. You can just try every k from 1 to sqrt(10^9) to see whether that k satisfy this condition, then, for each valid k, calculate the number of perfect squares you'd also obtain from the other numbers in the array.

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

    Let's choose some x. If ai & aj becomes perfect square after adding x, then: $$$a_{i}$$$+x = $$$u^{2}$$$ & $$$a_{j}$$$+x = $$$v^{2}$$$ Substracting , we get $$$a_{i}$$$ — $$$a_{j}$$$ = $$$u^{2}$$$ — $$$v^{2}$$$

    => $$$a_{i}$$$ — $$$a_{j}$$$ = (u-v)*(u+v)

    Now split ($$$a_{i}$$$ — $$$a_{j}$$$) into 2 factors f1 & f2 such that f1*f2 = $$$a_{i}$$$ — $$$a_{j}$$$.

    So, f1 = u-v & f2=u+v.

    Find, u from here. Substitute in $$$a_{i}$$$+x = $$$u^{2}$$$ & you will get x.

    Find the count over all possible x in this way & take the minimum one.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I thought trying for every factor of a 10^9 number for 50*(50*49/2) times would cause TLE…

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        my thinking was similar to you though instead of tle i got wa

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

          Now I upsolved D. My submission:189361440

          The proof of that the submission is available:

          In the algorithm we consider for all divisor k of (aj-ai) where j>i. The maximun number of divisors we check in one case is:

          sum(1<=i<j<=n, sqrt(aj-ai)/2)

          The "/2" is because if (aj-ai)%4==0 k must be even, if (aj-ai)%4==1 or 3 then k must be odd.

          Notice that sum(a[i+1]-a[i])<=A (A=max(a[i])=10^9). We can see for each d, sum(1<=i<=i+d<=n, sqrt(a[i+d]-a[i])/2) is maximized when all a[i+d]-a[i] are same (can be proved by the mean value inequality) and the maximun value is about (n-d)*sqrt(A*d/n)/2=n*(1-t)*sqrt(A*t), where t=d/n. We sum up it for d=1...n-1 and the sum is about O(n^2*sqrt(A)), which fits the time limit.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It doesn't TLE, because you're factoring the differences of $$$a_i$$$ and $$$a_j$$$, all of which can't be around $$$10^9$$$ simultaneously.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        it's around 4e7 operations (which should be doable even with 1s time limit), plus the time limit is 4s.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          But for case a[i]=1+20408160*(i-1), it runs for 10622587 operations.

          My testing code
        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          OHHHHH I forgoted there's this line in the statement:

          It is guaranteed that the sum of n over all test cases does not exceed 50.
          

          I missed in the contest.... I've thought sum(n) could be 2500 and missed the intended solution.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I just upsolved D with a similar solution. I iterated over all n^2 pairs of numbers. For each number, i iterated over all values of f1 (so sqrt(max(a)) time) and did some math to see if it worked. Then I took all the possible values of x I got, and I simulated the process for each value of x.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    have idea for D but got wa

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Problem A was kind of ugly. C also required (at least in my case) a quite hefty implementation.

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

problem C is tough :((( Can anybody show me some hint? :((

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

    Definitely, not an easier one!!

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I spend almost 3 hours but still couldn't solve it :((( But i see so many people could solve it :((( Pardon me for my bad english

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Just brute every i from 1 to 26(i is how many letters will be left in string -> n % i == 0) and then you should calculate how many ops(call it cnti) you needed to make string balance(i used greedy in this part). So your first answer is min among cnti.

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

      Implementation is nightmarish.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Suppose you want to modify the string to have exactly $$$x$$$ distinct characters. How many times will each character appear? Which $$$x$$$ characters should you pick? Can you calculate the minimum number of changes to reach $$$x$$$ distinct characters?

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

ofc the first question immediately got hit by annoying geometry question lol(don't worry imo it's also interesting)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how's problem C solved ...... nothing struck my brain for like 1.5 hrs i took multiple examples but i couldn't generalize it .

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

    You can keep only 1 <= i <= 26 characters with n/i frequency for each one

    Try them all and minimize the answer

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can't believe I clutched C like that.

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Seeing the drawing for problem A before reading the problem statement was intimidating lol

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

omg tourist round

»
3 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

Anyone know what pretest 11 was about in problem E ?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got WA11 and 2 1 3 2 3 2 3 2 4 helped me find the mistake. When I was using only 1 row out of 2-row rectangle I forgot to clear the other row in the segment tree

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D? :(

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    The answer can always be 1. Now let's see what will happen if the answer is $$$>1$$$.
    So suppose the answer is 2. This means that there are any two indexes(let's assume i and j) such $$$a[i]+x=c*c$$$ and $$$a[j]+x=d*d$$$. Here c and d can be any valid integer. So now $$$d^2-c^2=(d-c)*(d+c) $$$.This is equal to $$$(a[j]-a[i])=(d-c)*(d+c).$$$
    Now if we factorize $$$a[j]-a[i]$$$. We can find the value of $$$d. and .c$$$. Using those values we can find the value of $$$x$$$. Now we will store all the eligible values of x and use the best possible option.

    Spoiler
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I didn't get how you solved to get, d=(A+B)/2 and c=B−d

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        since $$$d+c=B$$$ and $$$d-c=A$$$. If we add both the equations we get $$$2*d=A+B$$$ which is equal to $$$d=(A+B)/2$$$. For the value of $$$c$$$ it comes from equation 1 by shifting $$$d$$$ from left side to right side.

»
3 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

I swear F is easier than E...

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

any hint on d?

»
3 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

D is simple but the constraints are way to big. Any idea how to solve it ?

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

    Suppose that $$$b_i^2 = a_i + x, b_j^2 = a_j + x$$$, then we have $$$(b_j - b_i)(b_j + b_i) = a_j - a_i$$$. By enumerating $$$b_j - b_i$$$ we know what $$$b_i$$$ and $$$b_j$$$ are, and also the $$$x$$$.

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

    So ... it is not simple, then?

»
3 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

D was very good

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, it was nice. I initially thought it was some sort of meet-in-the-middle trick, but was pleasantly surprised to see it was a much nicer brute-force.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How did u solve D ?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +10 Vote: I do not like it
      Spoiler
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks a lot!

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        As x can be of the order 1e18 wouldn't O(√n) will be of the order 1e9? which should TLE?

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          We only need to find the factors of a[j]-a[i] to deduce all the x's and a[j]-a[i] can at max be 1e9.

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

            Can you please Explain About How to Find X using (a[j]-a[i]) what two factors represents of difference and how this term come (factor1 + factor2)/2
            i am not getting it :(

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

              see for $$$n_{i}$$$ and $$$n_{j}$$$ to exist $$$n_{j}-n_{i}$$$ should exist and be a factor $$$a[j]-a[i]$$$ because this equation $$$a[j]-a[i] = (n_{j}-n_{i})*(n_{j}+n_{i})$$$ holds.

              therefore if we iterate on all the factors of $$$a[j]-a[i]$$$ , (p,q) such that p*q = $$$a[j]-a[i]$$$ then we can treat smaller of p,q & p<q as $$$n_{j}-n_{i}$$$ and the bigger one as $$$n_{j}+n_{i}$$$ and solve these two equations

              $$$n_{j}-n_{i}=p$$$

              $$$n_{j}+n_{i}=q$$$

              find a feasible $$$n_{i}$$$ , $$$n_{j}$$$ if it exists we can get the respective x from equation

              $$$x=n_{i}^{2}-a[i]$$$
              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                OMG this is so simple How did i not notice that :( Thanks For the Detail Explanation got it :) .

  • »