Автор tourist, 22 месяца назад, По-русски

Привет!

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.

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

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

omg tourist round

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

Damn, 3 hours for only 8 problems. Scary

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

omg tourist round

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

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

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

Shortest announcement ever *_*

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

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

3 hours? How difficult the problems will be

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

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

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

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

Note the unusual timing

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

omg tourist round ...^,^

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

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

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

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

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

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

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

    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.

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

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

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

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

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

          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.

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

    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

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

omg 3hr round ><

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

Omg 3hr Round ><

»
22 месяца назад, # |
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...☝️

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

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

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

omg tourist round

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

omg tourist round

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

Omg clash with ABC.

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

.

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

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

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

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

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

It is rated ?(⊙﹏⊙)

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

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

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

.

  • »
    »
    22 месяца назад, # ^ |
    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.

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

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

Contest Clashing with atcoder Beginner Contest 285.

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

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

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

score distribution when?

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

omg tourist round

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

omg tourist round

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

ok

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

omg tourist round

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

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

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

Thanks to MikeMirzayanov for amazing platforms Codeforces and Polygon.

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

Contest Collision (CF & ABC):

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

omg tourist round

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

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

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

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

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

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

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

excited !!

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

tourist gang

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

The One Piece is real!!!

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

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

omg tourist

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

I wish the next round will be written by Benq

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

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

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

I will always be a fan of tourist!

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

omg tourist round

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

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

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

Where is score distribution?

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

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

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

glhf

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

scared!i hope i can solve A。。

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

OMG tourist round

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

»
22 месяца назад, # |
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?

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

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

Can somebody please tell the solution?

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

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

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

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

      My solution

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

Pretty hard contest.

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

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

    how's C done ....?

    • »
      »
      »
      22 месяца назад, # ^ |
      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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

          My testing code
        • »
          »
          »
          »
          »
          22 месяца назад, # ^ |
            Проголосовать: нравится 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.

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

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

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

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

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

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

    Definitely, not an easier one!!

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

      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

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

        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.

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

      Implementation is nightmarish.

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

    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?

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

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

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

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

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

Can't believe I clutched C like that.

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

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

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

Anyone know what pretest 11 was about in problem E ?

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

    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

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

any hint on D?

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

How to solve D? :(

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

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

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

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

        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.

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

I swear F is easier than E...

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

any hint on d?

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

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

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

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

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

    So ... it is not simple, then?

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

D was very good

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

    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.

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

    How did u solve D ?

    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится
      Spoiler
      • »
        »
        »
        »
        22 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

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

          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.

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

            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 :(

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

              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

              Unable to parse markup [type=CF_MATHJAX]

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

    That's what she said

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

trash problem E, only boring implementation.

I will never think a strong competitor to be a certainly good author any longer.

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

    I thought it has to be obvious after first stage

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

    Implementation is an important aspect of problem solving too; in my opinion, there's nothing wrong with problem E. You need to find a way to systematically reduce the rectangles, and figuring out how to structure your code to do this as efficiently as possible is part of the challenge.

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

    I agree. Compaired with implementation, observation is much too easier in this problem. That makes me feel really bad.

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

    I can't implement it, too. But I think it's not all the author's fault. E is not very good but also not trash.

    We should consider to improve ourselves. I have already suffered a lot for my poor implementation ability.

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

    Problem E is a good problem. Please do not send such stupid comment only because you can't solve it. This will make you look like a loser.

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

      I don't solve FGH, but I don't criticize them. You never get to know why I am saying it's trash and others are upvoting me. So you are a fool.

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

        That's because you can solve E in usual, while you have never been solved problem FGH in the past. You just arrogantly make silly comment on problems you can't solve, and try to infect others with your trash emotion. You never get to know why I am saying your comment so brainless, you will just like a mouse hide in the hole and won't listen to others opinions.

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

          OK, next time at div4 A I will provide you with a math problem that has 10,000 corner cases and requires 100KB code and you cannot solve it and I say to you that you should improve your coding skills and not complain about the problem itself

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

            Actually, E was not that difficult to implement.

            For me, implementation is like an art: if you do it the right way, it feels godly.

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

            Yes, of Course he will not complain.

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

              I really hate a homeless dog barking at me when I'm walking in the street. It's really annoying. But I can't have too many requirements to a dog, right? They just want a bone.

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

          More often than not I cannot solve problem E even D in div1+2 but never have I criticized them if it's my fault that causes me to fail to solve it

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

        You are being offensive. You are not offering any explanation for your words. You are attacking when attacked. I really can't stand this behavior by entitled contestants. Many comments by you in the past have a similar attitude, that makes you a bad member of the community. Please be more respectful.

        Problem E was rather easy to mind-solve in quadratic time (and still interesting). Rather hard to implement properly in pseudo-linear time. That is one of the main points of the problem. The implementation itself (at least mine) is short, but I wasted more than one hour because of wrong assumptions, wrong ideas, not having the whole picture clear in mind, and blah blah. That does not make the problem trash, it makes me weak. I was very satisfied when I finally solved it.

        You are the fool if you assume that codeforces upvotes are a valid support for the content of your messages.

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

      pls shup up until you can solve E

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

        What make you mention that i can't solve E? Please shut up until you can prove it.

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

          so how can you know he can't solve E

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

            He agree it himself bro, please don't ask such stupid question next time.

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

            they ACed A-D 1:17 into the contest, then proceeded to WA on pretest 1 on E for two hours.

            Now, perhaps I'm too low rated, too unexperienced to judge a master, so take my word with a grain of salt all you like, but that doesn't sound like they can solve "only boring implementation". If they only had a hour or so sure it might have been a time issue, but two hours for ~150 lines of implementation that only involves greedy and sortings? Please.

            When I get stuck on implementation for two hours in a contest, I don't say the problem is trash. I say that I'm too bad at programming and that this problem exposes an issue in me. I should be grateful to this problem even though it gave me -delta because it shows me how to improve my ability.

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

    That's very offensive to say Sir. Either problem is Good or it is not meant for you. Tourist has put his hardWork and time into that problem, atleast he deserve a valid constructive criticism sir. Codeforces upvotes are merely a number to me. You are still wrong to me. Also Someone hardwork isn't trash at all.

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

thanks for this great round

»
22 месяца назад, # |
Rev. 5   Проголосовать: нравится -8 Проголосовать: не нравится

How to solve problem C?
My idea was to enumerate the number of occurrences of each character.
It took me about 2 hours. But I got TLE on pretest2.

(Forgive my poor English.)

Edit:
Why many people downvote this comment?

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

    My idea was to first, implement a function that optimally changes the string to be balanced with $$$x$$$ different characters ($$$O(n\log(n)$$$) in my implementation). And then go to all the divisors of $$$n$$$ less than 27, because the number of characters cannot be greater than 26. Then in total is something like $$$O(26 n\log(n))$$$.

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

How to solve F?

I turn the problem into this:

There's an array S indexed from -n to n, the number on index 0 is 1, rest is 0.

Do n operations, on each operation there's S[i]/sum(S) possibility to choose index i, add 1 to S[i], then P possibility to add S[i+1] 1, 1-P possibility to add S[i-1] 1.

Output the possibility to make S[-n...-1] both 0 after n operations.

But I have no idea how to solve this :(

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

If D doesn't use long long type to save $$$x$$$, will it be WA on #5? I got WA on #5 and I think it was because I didn't use long long type to save $$$x$$$, but I didn't have enough time to change. :(

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

F was a lovely problem, absolutely loved it !

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

How to solve Problem B

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

    More generally, how to approach these questions based on sorting?

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

    Check if you can take k people. You can take k people iff there are exactly k people for whom a<k and there is no person for whom a=k

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

when upsolving will be open?

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

In problem D, suppose any two consecutive square numbers are p^2 and (p+1)^2 . Then their difference will be (p+1)^2 — p^2 = 2p+1. Now given the maximum element is 1e9. so after choosing some x and changes a[i] to a[i]+x. The maximum number of all a[i]+x will be at most 2e9 or even less than 2e9. Isn't it? Or I am wrong somewhere? If this is the final solution we can brute force all the perfect squares of a[i]. But this solution gives me WA at test 5. Where is this solution wrong then? My solution . TIA :)

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

    Hint: 1e9*1e9=1e18

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

    no, difference is at most 5e8, but actual squares can be up to 3e17,and number of squares is still 1e9

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

    "so after choosing some x and changes a[i] to a[i]+x. The maximum number of all a[i]+x will be at most 2e9 or even less than 2e9"

    How you came to this fact?, like x can be upto 10^18.

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

    Got it. Found the mistake. Thanks a lot.

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

8

6 0 3 3 6 7 2 7

For the third testcase in problem B (reproduced above), why couldn't 2 people (persons 2 and 7) come? They'd both be happy (2 because at least 0 come and 7 because at least 2 come) and the rest because they're each happy if and only if 3 or more come; less than 3 come, so the rest should be happy as well. Why isn't this a valid result?

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

    a person is happy if at least ai persons OTHER THAN i are coming

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

    The problem statement says a[i] excludes the i-th person themselves. So 7 would not be happy, since there aren't two other people who went (just one).

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

    How can you participate in 234 contests consistently for 4 years and still be a newbie?

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

When will we be able to upsolve?

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

Wrote solution for 1782D - Many Perfect Squares few minutes after the contest and got WA on test 6. Can anybody tell me what's wrong? (189360636) It passed more than 50000 random tests with $$$n\leq{7}$$$.

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

    You shouldn't stop iterating over $$$k$$$ when you found an appropriate one. If you try out all valid $$$k$$$'s, your solution will pass the tests (check out this submission: link)

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

A pretty hard contest tbh especially C, so hefty implementation

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

    I liked C. Good problem where you think how to implement rationally.

    ...Cofeforcer codefofced coresorces!...

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

The tasks were more interesting than usual. Liked B and D!

But C was a bit difficult to implement.

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

The ratings are updated preliminarily. Tomorrow I will remove cheaters and update the ratings again!

»
22 месяца назад, # |
Rev. 5   Проголосовать: нравится +26 Проголосовать: не нравится

Now I've upsolved E. My submission:189365023

Basic idea:

First the maximum total area is the initial area. Proof: for any 2 overlapping rectangles, if they are same type (row1, row2 or row1+row2; we'll call them type1, type2 and type3 later), we can shrink one of them to remove the overlapped area and remain the same total area,like this:

[-------[+++++]||||||] -> [-------] [|||||||||||]

('-': left '|':right '+':overlap)

So we can remove all overlaps caused by same type of rectangles. If they are still 2 rectangles who are overlapping, then one of them is type3, the other is type1 or type2 (since type1 cannot overlap with type2, and we've removed all overlaps of same type in previous step). WLOG assume they are type 3 and 1. If type3 is "penetrated" by type1, which means type1.L<=type3.L && type1.R>=type3.R, we need to shrink type3 to row2 (and it becomes type2), like this:

[---[+++]---] --> [---------]

.....[| | |]...............[| | |]

('-': type1 '|':type3 '+':overlap)

Otherwise, we can shrink type1 to remain the area (since type1 can only get out of type3 from at most 1 side). Now we could solve the whole problem.

The naive approach is O(n^2), but by classifing rectangles by different types and sort them by the left borders, we can get an O(n*log(n)) solution. In the first step, for each type of rectangles, we keep prevR=the largest right border of rectangles we've checked, and for every rectangles with left border <= prevR, we move it’s left border to prevR+1 (and if it's left border is greater than the right border, we mark it as removed). In the second step, we maintain 3 pointers p1, p2, p3. For each type3 pointed by p3, we check for every type1 and type2 until there's no more that type of rectangles, or it's left border is greater than type3.R. If there's any type1 penetrates the type3, we mark flag1 as true, similar for flag2. After checked type1 and type2, if(flag1 && flag2) we mark type3 as removed, elif (flag1) we change it's type to 2, elif(flag2) we change it's type to 1. (However, the code implementation is very very very annoying)

Update: Now I've kicked back to div2. Maybe I need more practice to make sure that I can solve all solvable problems in contest.

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

Worst problem C ever

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

Cheating case Codeforces Round #844 (Div. 1 + Div. 2, based on VK Cup 2022 — Elimination Round) problem C

Zaoldyeck code :- 189324513

HAKUNAA_MATATA code :- 189349431

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

Thanks for the fast editorial

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

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

I suddenly know why 19000+ people registered but there were only 9000+ people submit.

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

    People either got scared of problem A, or they accidentally slept in. (I started the contest 30 minutes late bc I slept in XD)

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

      Unusual timing also didnt helped the cause. I couldnt participate due to contest getting started ealier than usual

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

This is the hardest race I've ever done

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

Can someone plz tell where this code goes TLE. Solution code for problem C 189395773

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

Hi guys! If you're having troubles with B and C problem you can check the video tutorial at this channel- www.youtube.com/@grindcoding

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

omg tourist round

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

Hi there!

If you have any doubts in problem B and C you can checkout the tutorials here- www.youtube.com/@grindcoding . Happy coding!

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

Anyone tried to solve the problem D using Binary sesrch?

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

H is a problem designed cleverly (although most haven't ever clicked the link of it). For case k=0 it's a trivial div2C problem (consider the smallest "bounding-box" of a pattern and use inclusive-exclusion principle to count for each bounding-box). For case k=1 it's a normal div2E problem (consider every possible position of the broken light relative to the bounding-box, they'll form a rectangle, if it's contained in the bounding-box, subtract the number of patterns where all lights in this rectangle are turned on). For case k=2 we get 2 rectangles, and we need to guarantee that there must be at least one pair of corresponding positions of rectangles where lights are both off. We consider how many patterns will violate this condition: If for every pair of corresponding positions, there must be some position with light on, we construct a graph whose vertexs are positions in the 2 rectangles, and add an edge between each pair of corresponding vertexs, we need to find the number of ways to color these vertexs where every edge has a vertex with a light on. Since the graph can be disposed to several chains, and the number of such coloring for a chain is Fibbonaci numbers, we need to find the length of each chain (if any chain has 2 adjacent vertexs out of the bounding-box, the answer is 0, because they can't be light on).

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

    I'd rather say it is too classical and easy (to come up with a solution, implementation not included) for most who did click the link of it, and totally not worth higher points than G. And I bet many solved G but could not solve H1 only because of a lack of time. (For me, an additional 5 minutes would suffice.)

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

      It's a waste that H is not a problem with case of k=0,1,2 as easy, medium, hard subtasks, where much more people would try to think about it instead of ignore it completely.

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

Can anybody teach me that how to solve F? many thanks.

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

tround

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

When editorial will be published?

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

when will we get editorial of this contest?

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

I feel like D was a lot more easier than C, I still am not sure how to do it. I guess D and C should have swapped places

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

Solution sketch for F:

Let us say that two characters are paired if they were inserted in the same operation. Note that there are always an even number of characters between any character and its pair. Let $$$g(n, k)$$$ be the probability that after $$$n$$$ operations, there are $$$2k$$$ characters between the leftmost character and its pair. Note that $$$g$$$ does not consider the type of pairs inserted (() vs )().

Compute $$$g$$$ by DP. $$$g(1, 0) = 1$$$ and $$$g(1, k>0) = 0$$$. From any state there are three possible transitions. A new pair may be inserted left of the leftmost character, producing state $$$(n+1, 0)$$$. A new pair may be inserted between the leftmost character and its pair, producing $$$(n+1, k+1)$$$. Finally, a new pair may be inserted entirely to the right of the leftmost character's pair, producing $$$(n+1, k)$$$. $$$g$$$ has a quadratic number of states each with a constant number of transitions.

Suppose that ( has value $$$1$$$ and ) has value $$$-1$$$. In a regular bracket sequence, all prefix sums must be non-negative. Let $$$f(n, s)$$$ be the probability that in a string produced from $$$n$$$ operations on an empty string, all prefix sums are $$$\geq s$$$.

Compute $$$f$$$ by DP. $$$f(0, s \leq 0) = 1$$$ and $$$f(0, s > 0) = 0$$$. To compute $$$f(n, s)$$$, suppose there are $$$2k$$$ characters between the leftmost character in the resulting string and its pair, and suppose that pair is of type )(. Inside the pair, we have a sub-problem $$$f(k, s+1)$$$. To the right of the pair, we have a sub-problem $$$f(n-1-k, s)$$$. Each $$$k$$$ contributes a term $$$(1 - \frac{q}{10^4}) \cdot g(n, k) \cdot f(k, s+1) \cdot f(n-1-k, s)$$$ to $$$f(n, s)$$$. Pairs of type () are handled similarly. $$$f$$$ has a quadratic number of states each with a linear number of transitions.

Finally, output $$$f(N, 0)$$$ for $$$N$$$ in the input.

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

    Thank you!! I've been waiting for someone to make an editorial on F the whole day.

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

    In computing of f, if all prefix sums at the left are not less than s, then at the right we should make all prefix sums not less than zero? Because if all prefix sums on the right are not less than x, then by adding to each of them s from the left we get that they are not less than x+s?

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

      The condition that prefix sums of the right part are not less than zero is sufficient but not necessary. Note that $$$s$$$ is non-positive.

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

      Because we always insert () or )( pairs, the prefix ending at the leftmost character's pair has sum 0.

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Some corner cases in the DP

    Also, this problem is quite tight on time, and $$$\text{mod}$$$ operation is quite costly, so try to minimize the use of it by using long long and only modding a state after the third loop has finished.

    AC submission with a few comments: 189490185

  • »
    »
    22 месяца назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    Compute f by DP. f(1,s<=0)=1 and f(1,s>0)=0...

    I think f(1,s<=0) is not 1.

    There is p possibility that f(1,0) is 1 and (1-p) posssibility that f(1,0) is 0.

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

      Thanks, it should be $$$f(0, s \leq 0) = 1$$$ and $$$f(0, s>0) = 0$$$.

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

First time seen that there is no thanks to MikeMirzayanov for Codeforces and Polygon platforms.

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

When will editorial be released

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

Can someone share a solution to C?

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

    Here is the code : 189565190

    Basically what i have done here, is start iterating from 1 to 26, and for every integer when n%i == 0, called a function solve which gives the most optimal string when the no of distinct characters present in the string are i.

    Now, In solve function, first I calculated the no of times a character should be present in the string, that is n/i, then replaced all the characters whose frequency in the string is greater than n/i to of those whose frequency is less than n/i, till all the i characters have n/i frequency.

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

So I have a solution for F which requires O(N^3) memory and time but the memory is way too much it is something like this : dp[i][j][k] = the probablity of it being a balanced string after i moves and having exactly j sub balanced strings (any balanced string is a number of balanced strings next to each other) having k positions in the whole string were if string )( is added the number of balanced substrings go up by one (in other words if you write the prefix sums of +1 and -1 the prefix sum is +1 at that point). now updating each cell of this dp is O(1) because all you have to consider is where the string () or )( is added. in case of string () if it is added between 2 balanced substrings it adds one to the number of them and also adds one to k value. if it is added in the k positions where the prefix sum is +1 it doesnt add the number of balanced substrings but adds one to k and in other positions it doesnt change k or j. for string )( , it cant be added between the balanced substrings, in the chosen k positions it adds one to the number of balanced substrings and also adds one to k and in other positions it doesnt change anything.

is this approach wrong ? and if it is not can i somehow iterate on something to change memory to O(n^2) ?

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

No editorial?

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

Please Publish Editorial.

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

where is the tutorial???

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

omg tourist round

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

Internet explorer tutorial

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

in C after fixing the number of distinct characters in the final string how to decide which characters i have to keep and which to delete so as to minimise operations ... mathematical proof is appreciated .

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

    Sort the frequency of the initial string and draw a histogram, then draw a rectangle represent the target frequency, see what's the difference between them.

    For example, if the frequency of the initial string is 6,4,4,1 ans you need to change all frequency to 5 (and there will be 3 different chars), the histogram will be like this:

    -----!

    ----*

    ----*

    !

    ('-':the character will remain the same '*':the character will be added '!':the character will be removed) in this case the number of chars will be changed is 2.

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

internet explorer tutorial

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

where is tutorial ? we want to upsolve..

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

Please give the editorial before the next contest starts !!

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

The slowest editorial ever. Oh, wait, there's no editorial yet!

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

Spent a day looking at B. Still can't solve. tourist Please make tutorial easy and if possible early.

Thanks.

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

It is the first announcement to have those triples of no:
1- No editorial
2- No score distribution
3- No thanks to mike mirzayanov

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

There are thousands of problems in Codeforces, you guys could solve them instead of waiting for editorial and you guys can upsolve the problems anytime later after getting the editorial, Mike won't delete any problems. So instead of worrying about it, solve some other problems:)

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

Can someone share a solution for problem H?

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

omg tourist round

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

lets go

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

Извините, будет ли, и если да, то когда примерно объяснения задач этого этапа? Или оно уже есть, но не в блоге Туриста? Подскажите, пожалуйста, кто-нибудь

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

TUTORIAL IS OUT!!!

TUTORIAL IS OUT!!!

TUTORIAL IS OUT!!!

TUTORIAL IS OUT!!!