Автор tourist, 3 недели назад, По-русски

Привет!

VK Cup 2022 - Отборочный раунд (Engine) начнётся уже скоро: 15.01.2023 15:05 (Московское время). Это соревнование предназначено для тех, кто решил хотя бы 6 задач из 8 в квалификационном раунде VK Cup 2022. Раунд будет рейтинговым.

Остальных приглашаем на открытый для всех Codeforces Round #844 (Div. 1 + Div. 2, основан на Отборочном раунде VK Cup 2022), который начнётся в то же время и тоже будет рейтинговым.

Все задачи придуманы и подготовлены мной. Также этот раунд стал лучше благодаря KAN, errorgorn, lperovskaya, dario2994, Monogon, Arpa.

Участникам будет предложено 8 задач и 3 часа на их решение.

64 лучших участника закрытого отборочного раунда получат фирменные футболки VK Cup, а 16 лучших пройдут в финал и смогут побороться за призы 4-5 февраля очно в офисе VK или онлайн:

  • 1-е место — 300 000 рублей;
  • 2-е место — 250 000 рублей;
  • 3-е место — 150 000 рублей;
  • 4-е место — 100 000 рублей.

UPD: Разбор

Поздравляем победителей отборочного раунда:

  1. turmax
  2. Petr
  3. never_giveup
  4. isaf27
  5. 353cerega

и остальных участников, попавших в число сильнейших.

Также поздравляем победителей открытого для всех раунда:

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

и отдельно maroonrk как автора единственного принятого решения по задаче H2.

 
 
 
 
  • Проголосовать: нравится
  • +1305
  • Проголосовать: не нравится

»
3 недели назад, # |
  Проголосовать: нравится +144 Проголосовать: не нравится

omg tourist round

»
3 недели назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

Damn, 3 hours for only 8 problems. Scary

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

omg tourist round

»
3 недели назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

omg tourist round

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится -13 Проголосовать: не нравится

    omg tourist round

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится +29 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 недели назад, # ^ |
          Проголосовать: нравится +7 Проголосовать: не нравится

        وانتا مالك؟؟

        • »
          »
          »
          »
          »
          3 недели назад, # ^ |
          Rev. 2   Проголосовать: нравится -31 Проголосовать: не нравится

          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 недели назад, # ^ |
              Проголосовать: нравится +16 Проголосовать: не нравится

            Respect to newbie

            • »
              »
              »
              »
              »
              »
              »
              3 недели назад, # ^ |
              Rev. 2   Проголосовать: нравится +17 Проголосовать: не нравится

              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 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 недели назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится -13 Проголосовать: не нравится

    newbie detected.. opinion rejected xD

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Надеюсь, будет задача про All Cups

»
3 недели назад, # |
  Проголосовать: нравится +75 Проголосовать: не нравится

Shortest announcement ever *_*

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

its revenge

»
3 недели назад, # |
  Проголосовать: нравится +192 Проголосовать: не нравится

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 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

3 hours? How difficult the problems will be

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 недели назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

Note the unusual timing

»
3 недели назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

omg tourist round ...^,^

»
3 недели назад, # |
  Проголосовать: нравится +458 Проголосовать: не нравится

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 недели назад, # |
  Проголосовать: нравится -120 Проголосовать: не нравится

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 недели назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

omg 3hr round ><

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Omg 3hr Round ><

»
3 недели назад, # |
Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится

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

»
3 недели назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
3 недели назад, # |
  Проголосовать: нравится -44 Проголосовать: не нравится
tourist is a great person
»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

omg tourist round

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

omg tourist round

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

omg tourist round

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

omg tourist round

»
3 недели назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Omg clash with ABC.

»
3 недели назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

I am a pro memer.

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится -43 Проголосовать: не нравится

.

»
3 недели назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

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

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Who is tourist ?!!

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It is rated ?(⊙﹏⊙)

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 недели назад, # |
Rev. 3   Проголосовать: нравится -39 Проголосовать: не нравится

.

  • »
    »
    3 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится -16 Проголосовать: не нравится

    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 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Omg, tourist round!

»
3 недели назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

»
3 недели назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Contest Clashing with atcoder Beginner Contest 285.

»
3 недели назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

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

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

omg tourist round

»
3 недели назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится
»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 недели назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

Orz tourist round.

»
3 недели назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

score distribution when?

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

omg tourist round

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

omg tourist round

»
3 недели назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

while(1) { OMG Tourist Round }

»
3 недели назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

GOAT

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

omg tourist round

»
3 недели назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

omg tourist round

»
3 недели назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

ok

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится -24 Проголосовать: не нравится

omg tourist round

»
3 недели назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

ОМГ. Раунд туриста.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Should be Interesting.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

omg tourist round

»
3 недели назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Thanks to MikeMirzayanov for amazing platforms Codeforces and Polygon.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

omg tourist round

»
3 недели назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Contest Collision (CF & ABC):

Timings
»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

omg tourist round

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

omg tourist round

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

круто!

»
3 недели назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

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

»
3 недели назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Note the unusual timing.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

excited !!

»
3 недели назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

tourist gang

»
3 недели назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

The One Piece is real!!!

»
3 недели назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

omg tourist

»
3 недели назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

I wish the next round will be written by Benq

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 недели назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

I will always be a fan of tourist!

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

AtCoder-ABC 285 and Round#844 Clash, I'm sad now :(

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

omg tourist round

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

OMT Gods round

»
3 недели назад, # |
  Проголосовать: нравится -22 Проголосовать: не нравится

»
3 недели назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

All the best guys! Lets see how much can I change my ratings today

PS:- I wish the change to be positive :)

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

is this rated for everyone?

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

omg tourist round

»
3 недели назад, # |
  Проголосовать: нравится +79 Проголосовать: не нравится

Where is score distribution?

»
3 недели назад, # |
  Проголосовать: нравится -55 Проголосовать: не нравится

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

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

glhf

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

scared!i hope i can solve A。。

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

OMG tourist round

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

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А разбор будет сразу после раунда или чуть попозже?

»
3 недели назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

omg tourist round

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

Why does the selection round of VK Сup start at the same time as the third selection round of the Technocup starts?

»
3 недели назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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

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

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

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

Can somebody please tell the solution?

»
3 недели назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      My solution

»
3 недели назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Pretty hard contest.

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

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    how's C done ....?

    • »
      »
      »
      3 недели назад, # ^ |
      Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится

      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 недели назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 недели назад, # ^ |
      Проголосовать: нравится -7 Проголосовать: не нравится

    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 недели назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 недели назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          3 недели назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          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 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          3 недели назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          My testing code
        • »
          »
          »
          »
          »
          3 недели назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    have idea for D but got wa

»
3 недели назад, # |