Блог пользователя cry

Автор cry, 3 месяца назад, По-английски

Thanks for participating! Despite the round being unrated, we hope you've enjoyed the problemset. We put a lot of effort into this round :prayge:

I want to give huge thanks to Dominater069 and satyam343 for their heavy contributions to the subtasks of G. If you're participating out of competition, we hope you enjoyed attempting these bonus subtasks. Otherwise, we hope you will enjoy upsolving them!

2009A - Minimize!

Problem Credits: cry
Analysis: cry

Solution
Code (Python) (ntarsis30)

2009B - osu!mania

Problem Credits: cry
Analysis: cry

Solution
Code (Python) (chromate00)

2009C - The Legend of Freya the Frog

Problem Credits: vgoofficial
Analysis: cry

Solution
Code (Python) (ntarsis30)

2009D - Satyam and Counting

Problem Credits: vgoofficial
Analysis: cry

Solution
Code (Python) (ntarsis30)

2009E - Klee's SUPER DUPER LARGE Array!!!

Problem Credits: cry
Analysis: cry

Solution
Code (Python) (ntarsis30)

Bonus: Solve in $$$\mathcal{O}(1)$$$.

Code (Python) (Non-origination)

2009F - Firefly's Queries

Problem Credits: cry
Analysis: cry

Solution
Code (C++) (awesomeguy856)

2009G1 - Yunli's Subarray Queries (easy version)

Problem Credits: cry, vgoofficial
Analysis: vgoofficial

Solution
Code (C++) (yash_9a3b)

2009G2 - Yunli's Subarray Queries (hard version)

Analysis: Solution 1: vgoofficial, Solution 2: awesomeguy856

Prologue
Solution 1 (Lazy Segment Tree, Offline)
Code (C++) (vgoofficial)
Solution 2 (Binary Lifting, Online)
Code (C++) (awesomeguy856)

2009G3 - Yunli's Subarray Queries (extreme version)

Analysis: Dominater069

Solution
Code (C++) (awesomeguy856)
Разбор задач Codeforces Round 971 (Div. 4)
  • Проголосовать: нравится
  • +156
  • Проголосовать: не нравится

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

Auto comment: topic has been updated by cry (previous revision, new revision, compare).

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

The G2 problem can also be solved by the MO algorithm. My solution is:https://codeforces.me/contest/2009/submission/279633321

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

    Can you explain your solution in detail

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

      I've just solved it with mo+sqrt decomposition too. here my 279746467

      The idea is the following:

      1. get array ans from G1 problem. ans[i] means the min number of operations needed in range [i,i+k).

      2. Now, for a query (l,r), the problem reduces to find min({ans[l]}) + min({ans[l],ans[l+1]}) + min({ans[l],...ans[r-k+1]}). This is range queries and it can be solved with mo+sqrt by dividing ans in buckets and sorting the queries

      3. Your bucket size X = q/sqrt(n) // this is an optimal value, no need to explain here. You can also choose X = sqrt(n) as your bucket size.

      4. Sort queries. Say query1 = l1,r1 and query2 = l2,r2. if l1/X == l2/X, then they are on the same bucket and order by r1 < r2. If on different bucket, return l1/X<l2/X. Save original order of queries before sort it.

      5. Answer queries by getting answer from left sid (it just iterates over a bucket size, X) and for right sid I build on every query of the same bucket a vector to save min values of ans[i] and a suffix sum. Then with the min value from left side make a lowerbound to the vector of min values and find the position from which min value from left side is smaller in fector of min values of right position. Use the suffix sum to add the rest to your answer.

      Sorry for large explanation ^-^

      Check mo+sqrt here

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

        Thanks for Explanation. I understood your solution

        I have solved it using Range Min Query and Next Smallest Element in array

        My Submission : 279798999

        Time Complexity : O((N+Q)*logK)

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

    It can also be solved using merge-sort tree

    Solution using merge-sort tree: https://codeforces.me/contest/2009/submission/279748718

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

      Can you explain the idea, the code is too messy to read

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

        from G1 we precompute the answer for every window of k and store it in a new array (c). now answer for query (l,r) will be sum(j=l, r-k+1) min(i=l,j)ci. now we construc a merge-sort tree that stores values in (l,r). lets say sub-array c is like cl,cl+1,cl+2,cl+3,...,cr. this vector seg[400001] in (i,l,r) stores cl,min(cl,cl+1),min(cl,cl+1,cl+2),...min(cl,cl+1,...cr). now lets say query is (l,r), and we are in a segment (gl,gr), we also maintain an int pre_mn that calculates min in (l,gl-1). answer from this seg would be min(pre_mn,cgl),min(pre_mn,cgl,cgl+1),...min(pre_mn,cgl,...,cgr). now lets calculate sum of this values using binary search and prefix sum by finding the index until where cgl+i is greater than pre_mn, as it will become pre_mn.

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

          ur merge sort tree is storing

          cl,min(cl,cl+1),min(cl,cl+1,cl+2),...min(cl,cl+1,...cr).

          and we need to query

          min( cl , c(l+1) , c(l+2), c(l+2) ... )

          how u did that ?

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

binary search forces

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

Nice Div. 3 contest !

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

In problem E i used prefix sum and got MLE bruh...

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

Can we solve D faster than O(n^2) if xi's were real numbers instead of integers ?

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

    It appears I am wrong. Disregard this

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

      actually, no i think there are other cases,

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

    I'm interested in your n^2 solution, is it something to do with circles?

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

      Even easier (use the fact that left difference times right difference has to be equal to onesee prrof) : iterate over each point where y= 0 name it a , now for each point where y= 1 find its x difference from a say it is d now check if there is a point (1/d,1) and the rest is same as D.

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

In the C problem, there is a neat way to check whether there will be any other case or not.

Following the given explanation, one can see, that if any of the points on the side which contributes 2 points to the triangle are moved, the angle increases, and since we can't get them any closer without falling into Case 1, we can't have any more cases.

Another way that can be used is the fact that the slopes of the two perpendicular lines must give a product of -1.

So, if the points were $$$(x_{1}, 0), (x_{2}, 1), (x_{3}, 0)$$$, then we would have :

$$$(\frac{x_{2} - x_{1}}{1 - 0}) * (\frac{x_{3} - x_{2}}{0 - 1}) = -1$$$

which leads to :

$$$(x_{2} - x_{1})(x_{3} - x_{2}) = 1$$$

And since the differences will always be integers, we have :

$$$x_{1} + 1 = x_{2} = x_{3} - 1$$$

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

    It's a good explanation for showing there is no other cases. I came up with similar idea using geometric properties of the median in a right triangle. Other than triangles with sides in a vertical line $$$(x, 0), (x, 1)$$$, triangles must have sides on a horizontal line. Then the median of the right triangle separate out the two parts $$$(x - t, k) ,(x + t, k)$$$ with the last vertex is $$$(x, k'), k,k'\in \{0,1\}$$$. Then the median of length m calculated as $$$m^2 = 1^2 + t^2\ $$$, thus $$$(m - t)(m + t) = 1$$$, with similar argument $$$m$$$ must be 1. Sides on horizontal line is 2, then $$$t = 1$$$

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

~~~~~~

if(x > y){
    cout << 2* ceil(1.0 * x/k) - (ceil(1.0 * x/k) >= ceil( 1.0 * y/k)) << endl;
    continue;
}

else {
    cout << 2 *ceil(1.0*  y/k)<< endl;
    continue;
}

~~~~~

why this fails??

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

I'm really happy to unrate b/c I'm really mad because I don't submit my code. :)))))

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

G2 and G3 are not div4 problems. They should only appear in div2 or div1.

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

    On the contrary, they cannot appear in div2 or div1

    They are far too standard for both of them.

    They were never meant to be solved by actual participants, A — G1 is the actual div4 round. They are meant to educate higher rated people.

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

      so why have div 4 :/

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

        wdym? why have these "bonus" tasks in div4? or why have div4 at all?

        why have these "bonus" tasks in div4?

        how does it hurt you? Ignore it if you want to. It is not fit for a div2 or div1 clearly, why not have it here incase someone finds it useful?

        why have div4 at all?

        Because we have an abundance of easy tasks and an abundance of low rated people? D

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

      clearly not div4, admit your mistake instead of making baseless points.

      Dominater069 orz thanks for admitting it

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

        They were never meant to be solved by actual participants

        i admitted it lol.

        Not every task exists has to exist for intended participants.

        Authors (and me) wanted to add bonus educational tasks for high rated participants. I really dont understand how the intended audience was affected

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

          I appreciate the extra tasks. G2 is fairly new to me, and G3 was totally new to me. These were good tasks for learning.

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

          Yesterday I was feeling extra confident for some reason so i started from G2 and got destroyed. Luckily it went unrated. So that's how I intended participant got emotional damage LOL. Anyway I'll try to understand editorial.

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

          honestly, based from previous div 4s, i think G3 (or maybe also G2 idk) should be a bonus question that appears in the editorial, as a challenge

          although it's probably gonna be dismissed by lots of people, it'll be consistent with other rounds where in the editorial, they mentioned that they thought of harder constraints of the problem but not actually inserting it inside the problemset to make the round somewhat consistent.

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

      Why Div.4 have to educate Master or Grandmaster? I cannot understand.

      I think that that an overwhelmingly difficult problem is standard so can't put it in Div.2 doesn't mean that it can plugged in Div.4. I want a good problem must to be placed where a more people can solve it.

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

        Why Div.4 have to educate Master or Grandmaster?

        It doesnt have to, but isnt it good if it does? Who did it harm smh? Experts who want to be able to AK every div4 round. welp sad for them

        Authors tried to do a nice thing by including extra tasks (something which they didnt have to do and still would be paid the same)

        I want a good problem must to be placed where a more people can solve it.

        except G3 or G2 aren't good problems. Educational? sure. But educational problems should not affect rating.

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

          I hate you so much

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

          I think it's more like "it could've benefited more people in a higher division" rather than "it harmed those people."

          While I see your argument, and it may be true that it won't be very good to be in a Div. 1 round, I honestly don't think there would be many solves even if it was in a Div. 2. I agree that standard problems shouldn't heavily affect ratings, but I think the benefits are far bigger to have this problem in a Div. 2 round instead of a Div. 4 round.

          See how many of the 'target' people for these problems have actually participated in this round. If you want to attract those 'target' people and educate them, it needs to be rated for them to be motivated. Candidate masters won't expect a Div. 4 round to actually educate them, so there is little reason for them to even register for the contest and read the problem. It's not like having a few official solves ruins the whole authority of the rating system. It's way more important to motivate the fitting people to read and try the problem.

          Also, G2 was actually an interesting problem for me. It may involve only a few standard techniques, but I don't think such standardness necessarily made the problem bad.

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

            i agree with you that it would be on the edge of being fine for div2 because its hard enough so affecting only small number of people

            But

            • you cant easily port a problem in between rounds, or decide the division based on one problem

            • even if it doesnt affect much, i dont see many div2 coordinators who would accept G3 as a d2F (even though it would be somewhat fine imo)

            • there was a high likelihood that G3 existed on the internet since it is a very natural problem, and indeed it's max variant existed on hackerrank. https://www.hackerrank.com/challenges/little-alexey-and-sum-of-maximums/problem (somebody solved it using this too)

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

          Oh, you think G2 and G3 aren't good problems... Then why they are in contest? Isn't it wierd? Is it OK that not good problems in Div.4?

          But educational problems should not affect rating.

          Then why Educational CodeForces (Div.2) exists? Just do plug all Educational CodeForces problem in Div.3 or Div.4. But there is reason that Educational CodeForces exists.

          And why you're saying like that? Nobody said "I want to solve all of them!"

          I'm just saying that problem must be its suitable position, so it can teach more people. If you do not think so, then I'm sorry. But I believe every problemsetter and coordinator, tester knows that Div.4 is not for Master or Grandmaster, but for Newbie or Pupil.

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

            you think G2 and G3 aren't good problems

            From problem solving perspective, it is mostly standard and implementation for me.

            From eudcational perspective, it is useful as a problem to teach you the power of sweepline algorithms. There can be educational value in a problem despite it not being a "good" problem.

            Then why Educational CodeForces (Div.2) exists?

            It's fake educational and has been for a long time.

            years before, it used to be unrated and containing actually standard tasks. Now, it's just slightly more standard than average div2, but the name stuck.

            This change happened almost solely because they became rated rounds.

            I'm just saying that problem must be its suitable position, so it can teach more people

            But it comes at the cost of affecting people's ratings. Who likes to lose rating to a standard problem? I certainly don't

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

              just to be clear, does "standard" mean a problem that's solvable using ONLY well-known algorithms and methods?

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

                like everything it is a spectrum

                A problem is more standard the more well known algorithms and methods as opposed to thinking about the problem.

                so something like ratio of well known stuff : thinking needed gives you an idea about how standard a problem is

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

      Without a doubt, this problem cannot appear on Div1, but it is actually fine as Div2F (we definitely had worse and more standard d2F).

      The following only applies to unofficial contestants:

      the mild complaint I had is that I participated in a div 4 round, expecting div 4 difficulties and “div 4 level resistances” only to find that this is not the case. Div 4 to me had been a “quick and easy AK and funny internet speed test with no verdicts for 10 minutes and so every penalty is worth 25 or more”. In fact, div2/3/4 (and obviously also div1) have distinct feels to it, so I am not so sure in general making it feels like div2, which is what happened when G2 and G3 we’re included.

      This only made sense under my belief that this problem can totally be used on D2F as is.

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

        G3 is probably not fine as 2F either, as there is a square root solution which is trivial to think of (no sweepline or monotonic stacks or rectangle queries) but annoying to implement (279798653).

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

          Can you explain it in more details? I fail to see anything sqrt that isn’t a reinterpretation of a rectangle queries, it doesn’t seem like your solution is MO’s based.

          it is also worth noting that G3 is also trivial if you have segment tree beats (range chmin, historic sum). Implementation is at least half of the problem.

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

            I have solved it by processing queries offline.

            I iterate over the leftbound $$$l$$$ of the query in decreasing order, while maintaining two arrays $$$p$$$ and $$$q$$$ through my square root structure.

            When at a certain $$$l$$$, $$$p$$$ and $$$q$$$ are defined in the following manner:

            • $$$p_i = f[a_l, \dots , a_i]$$$
            • $$$q_i = \sum_{j = l}^{j = i - k + 1} {f[a_j, \dots , a_i]}$$$

            So the answer for any query $$$[l, r]$$$ simply becomes $$$\sum_{i = l + k - 1} ^ {i = r} {q_i}$$$.

            To maintain this array, my square root structure needs to be able to perform the following kinds of queries:

            1. $$$p_i \leftarrow x, \; l \leq i \leq r$$$ for some $$$[x, l, r]$$$
            2. $$$q_i \leftarrow q_i + p_i, \; l \leq i \leq r$$$ for some $$$[l, r]$$$
            3. Compute $$$\sum_{i = l}^{i = r} {q_i}$$$ for some $$$[l, r]$$$.

            which can be done.

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

              Your solution is identical to the intended one (Edit; after a slight more read on the intended solution it may have some subtle differences, nonetheless, it is identical to mine). It is just that you happens to choose to implement it via sqrt structures.This task could be completed by (lazy) segment tree too (no beats). I would say this is just difference in preference and the fact that it is passable by sqrt does not make it easier.

              Perhaps, this task is more standard/widely known to be doable by sqrt. In this case, then the task would be more standard than what I initially thought.

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

      me, who on;ly solved A-G1 :(

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

      I agree but I think it would be a better fit for a Div.3. Div.3 contests still contains standard questions

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

      Ye G2 and G3 educate me, I don't know why the problem like this can't appear in div2 or div1, only observe problem can. It would be nice if Codeforces Div 2 mix observe problem and standard problem :)

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

    I can see G2 barely being on the edge of a Div. 3 but G3 is straightforward way too difficult. It's maybe a harder one even for a 2F.

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

      G3 is definitely below d2F level

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

        I think it's more like most of the other 2Fs are too difficult in general, but okay.

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

          if most 2F are more difficult then that’s the 2F difficulty level lmao

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

            You can say the same thing to this: if we keep having these kind of problems in 4G, then this becomes a 4G level problem. However, that would be far from what I'd expect from a 4G, and 2F is kind of such state already.

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

              I agree that G2/3 are beyond div 4 level but I think it’s clear that they’re not intended to be solved by div 4 participants

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

                But they are in a DIV4 contest

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

                  It's an extra problem to be upsolved for education value. What harm did putting these questions here do? Did it affect anyone? No. Only 1 trusted user solved G2 and G3.

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

                  Maybe my opinion is stupid but when you say a DIV4 contest, I expect a contest that contains problems that a DIV4 participant can solve or upsolve. Similar logic for other divisions. But it is fine. Feel free to put a Div1F in the next DIV4 contest.

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

                  How many people in division 2 can solve F you think? What about the old div 4 G about 2-sat? Do you think newbies and pupils have a chance of inventing that on the fly without seeing 2sat before? Almost every final question on each round is far too hard for its division. We only included G2 and G3 because they follow quite naturally from G1, and if is impossible to port questions between rounds.

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

                  I never said the past div4 rounds were perfect. Also, I said I expect the target participants to be able to SOLVE or UPSOLVE the problems. So, because every final question on each round is too hard for its division, every round should follow this pattern? Anyway, it is your round, do as you want.

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

                  "Also, I said I expect the target participants to be able to SOLVE or UPSOLVE the problems."

                  Ok? isn't that the purpose of G2 and G3? For div.4 participants to upsolve? Of course, you don't have to upsolve it right now. You can always come back when you're better. The problem doesn't disappear.

                  I don't see any harm in contests with a harder final problem than its intended division. It gives strong participants of the intended division something to think about for the rest of the contest (instead of doing nothing), and makes more of a competition for higher rated participants.

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

                  do you really think that average div 4 users are gonna be able to understand the editorial for G2 and G3 just so that they can upsolve it hours or days after the contest? the point of upsolving a round that is consistent with your division is so that you can get AC on all of the problems by understanding what the editorial said shortly after the round ended. this is why most difficult problem in div 4s is usually around 1700-1900ish (that 2-sat 2100 problem doesn't count), because although most div 4 users cannot come up with the idea during the contest, the authors knew that some (not very small group of) div 4 users will understand the editorial given for the problem so that they can upsolve it immediately (or after some short period of time)

                  also, "makes more of a competition for higher rated participants" ok but the intended target for this round are pupils lmao

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

                  If you can’t understand G2 or G3, you can pretend those problems never existed, and move on. Alternatively, you can note their existence down and return later. It’s up to you.

                  A-G1 already makes a complete div 4.

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

                  so basically G2 or G3 is equivalent as the Ex problem in abc, where sometimes it's so hard it's not even intended for users who partake in abc

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

      I don't know if G3 is really div2. F level. I just brute-forced my G2 solution with a random optimization and it got AC (after the contest). Here's my Submission.

      If anyone is interested, try to hack me!

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

        Hacked, brute forcing with a G2 solution would result in $$$O(n)$$$ per query in worst case. Hence, if there are many instances where $$$ind = i + 1$$$, you are not skipping much numbers and therefore TLE.

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

          I also knew that it would give TLE on a case where my array ans[] had consecutively increasing elements. But I was not able to think of such a case.

          Not sure how it managed to pass all the pretests.

          Btw, thanks for hacking.

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

Sharing my video of winning the round along with explanations of my solutions: https://www.youtube.com/watch?v=JhL-oPzptlI

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

    Thank you very much for an explanation for G3! Took a long time to implement solution on my own but this was worthy.

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

E was great !

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

I tried solving E by interpreting it as a function and using the quadratic equation, but it keeps giving the wrong answer for n = 1000000000, k = 1000000000

typedef int64_t ll;
ll n, k, sk;
cin >> n >> k;

sk = gauss(k - 1); // starting k : the gauss sum of the numbers before the start of the series

ll max = gauss(k + n - 1) - sk;

// quadratic equation

// pref = gauss(n) - sk
// pref = (n^2 + n)/2 - sk
// where does 2pref intersect max? (because we want pref = max-pref)
// n^2 + n - 2*sk = max
// n^2 + n - (2*sk + max) = 0

// a = 1, b = 1, c = -(2*sk+max)

// delta = 1 ^ 2 - 4 * -(sk+max)
// delta = 1 + 4 * (2*sk + max)

ll delta = 1 + 4 * (2*sk + max);

// x1,2 = (-b +- sqrt(delta))/2*a
//	= (-1 +- sqrt(1 + 4 * (2 * sk+max)))/2 

ll x1 = round((-1 + sqrt(delta)) / 2);
ll x2 = round((-1 - sqrt(delta)) / 2);

ll x = min(abs(x1), abs(x2));

ll ans = 2 * (gauss(x) - sk) - max;
cout << abs(ans) << '\n';
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I also used the same logic. You probably have to use unsigned long long. I was able to pass the cases using that.

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

      But wouldn't a <= sqrt(D). so, a — sqrt(D) will never be a solution since it is negative why are u checking it ??

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

    was stuck in that for some time, but then used unsigned long long and it worked.. But came to the comments to see that it can be done by using binary search, need to see how they are applying it to the V curve, i mean ternary can work but binary.. no intuition honestly

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

    In the end, I had to use Java, because the delta's value was 999,999,999,940,000,000,001 in the n = 1000000000, k = 1000000000 test case.

    Here's my accepted submission: 279807077

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

For G1: There's a mathematical logic behind "ai — i". Let's say we have a sequence "(C, C + 1, C + 2, C + 3 + ...)". Any 'ith' element ai will be equal to "C + i — L", where 'L' is the starting index of the window. So (ai = C + i — L) => (C — L = ai — i). This (C — L) is a static part, which means we have to find the maximum occuring "ai — i".

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

You can think of E as an inverted mountain array and look for the minimum point using binary search

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

I think G1 can be solved by finding the longest increasing subarray for each query in O(logN)

Ans will be (right — left + 1) — longest;

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

My solution 279640569 of F, is giving correct output as 13 on my local and online compilers but wrong answer as 12 on codeforce's judge for following test case:

1

5 1

4 8 3 2 4

7 10

Can someone explain it?

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
import java.util.*;
 
public class one {
    public static void main(String[] args) {
        java.util.Scanner sc = new java.util.Scanner(System.in);
 
        int t = sc.nextInt();
 
        for (int i = 0; i < t; i++) {
            long x = sc.nextLong();
            long y = sc.nextLong();
            long k = sc.nextLong();
            
            long jumpsX = (x + k - 1) / k; 
            long jumpsY = (y + k - 1) / k; 
 
            long moves = Math.max(jumpsX, jumpsY) * 2 ;
 
           
            if (x>y) {
                moves--;
            }
 
            System.out.println(moves);
        }
        sc.close();
    }
}

why wasnt this AC for the frog and freya question?

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

can somebody explain how they used binary search for E? i found the function to be unimodal and hence i applied ternary search to find the point of minima, i dont get the intuition for binary search (i dont see monotonicity)

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

    There is a V formation, check my solution. To find minima just use formula of summation n there are different cases where mid will lie

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

    Just look for the point where current_sum > (total_sum)/2. The correct answer is nearby there. .

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

The entire universe is against me for becoming pupil. Was doin super well today until that announcement appeared, L cry, L servers... MikeMirzayanov I think its time to add a new god damm server.

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

I miss SlavicG,mesanu,flamestorm ... (╥﹏╥)

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

Here is a clean(er than the edi) solution to C and a unique solution to D.

For C we can see that

Spoiler

As for D, which I found much more interesting, though do note I misread it and as such overcomplicated it.

Spoiler

Here are submissions for both, hope that puts these problems into a bit of a different perspective! C: 279561294 D: 279622363

This contest had quite a few issues with the queue and pages loading, however I still enjoyed the problems and I hope you did too! I would have gotten plus VE if this contest was rated however instead of complaining I had fun solving these problems even if I did overcomplicate D a bit, however it would give insight to a possible harder version of the problem if it was not only 0 and 1 on the Y.

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

    I think this one is simpler 280325230.

    #include <bits/stdc++.h>
    using namespace std;
    using ll = long long;
    
    int32_t main() {
      int tt = 1;
      cin >> tt;
      while (tt--) {
        ll n;
        cin >> n;
    
        set<ll> a, b;
        int x, y;
        for (ll i = 0; i < n; i++) {
          cin >> x >> y;
          if (y == 0) a.insert(x);
          else b.insert(x);
        }
    
        if (a.size() < b.size()) swap(a, b);
    
        ll ans = 0;
        for (auto &it : b) {
          if (a.count(it)) ans += (a.size() + b.size()) - 2;
        }
    
        for (auto &it : b) {
          if (a.count(it - 1) && a.count(it + 1)) ans++;
        }
    
        for (auto &it : a) {
          if (b.count(it - 1) && b.count(it + 1)) ans++;
        }
    
        cout << ans << "\n";
      }
    
      return 0;
    }
    
    
»
3 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

This was a good round, sad that it got unrated.

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

thanks for writing, issues not your fault!

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

I have a different solution for G2. Use a set and a map to get the minimum moves for the window of size k starting from every index. Then use a stack to build a vector to store the index of next smaller number. Then use jumps to next smaller number to compute answer for every range.

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

    Hacked, your solution runs in O(n) per test case. Since in worst case, next_min[i] is just i+1, and you would be just jumping a number at a time.

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

Nice Div3 Contest !!!

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

My code is failing in case of- 1000000 100000 10 givng me answer- 200000 !! Can someone point the mistake ?? Thanks

#include<bits/stdc++.h> 
using namespace std;
int main(){ 
   long t; cin>>t; 
   for(long i=0;i<t;i++){ 
      long long x,y,k; 
      long count=0; 
      cin>>x>>y>>k; 
      while(x>0 || y>0){ 
         int result_x=min(x,k);
         x-=result_x; 
         int result_y=min(y,k); 
         y-=result_y; 
          count+=2;
        } 
        cout<<count<<endl; 
    } 
    return 0;
}
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Because for this case in last iteration the count should be += 1 instead of += 2, because we reached (x, y) by doing the x operation only so why count y operation too.

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

    the count after your process is always an even number.

    Note that at a moment when (x == 0 && y == 0), you should break the loop immediately.

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

      Tried that it is giving one less the actual output!! but nvm this solution is only good in smaller testcases + it is a bruteforce solution !!

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

    Moreover I tried this solution earlier , This will give you TLE

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

      Yes i know, it is only good if testcase are small !! Before this contest, I don't know ceil formula of ceil function !!

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

I loved the HSR and Genshin references. Please do continue naming problems on our favourite characters. Thank you!

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

I have implemented the same logic as the solution above for 2009D - Satyam and Counting, but keep getting

Wrong answer on test 2: wrong answer 7th numbers differ - expected: '100', found: '99'

I cannot see the corresponding input.

Can anyone please tell me what I am missing? https://codeforces.me/contest/2009/submission/279654100

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

    I spotted one mistake but that does not fix the Wrong Answer above. The mistake is that each array should have size n+1 instead of n because each 0 <= x <= n. I also fixed the ranges accordingly. But, as mentioned, the Wrong Answer stays the same.

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

    I figured it out. Because of my confusion with the range of x, the code decrements x. That maps x=0 to x=-1, which does not result in an error but in undesired behavior when used as a list index.

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

We can use binary search to search for the greatest i such that a1+⋯+ai≥ai+1+⋯+an

Isn't the solution for E wrong? If the above statement is the correct solution, the greatest i is just len-1 no?

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

In problem E's editorial ...

We can use binary search to search for the greatest i such that a1 + ⋯ + ai ≥ ai+1 + ⋯ + an . Note that here, the positive difference is minimized. If we move to i+1 , then the negative difference is minimized (since the sum of prefix will now be less than the sum of suffix). The answer is the minimum absolute value of both cases.

It should be a1 + ⋯ + ai ≤ ai+1 + ⋯ + an because we want to minimize the difference.

cry
(ignore the formatting)

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

Can't understood editorial solution for G2

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

G2 can also be solved using sqrt decomposition in $$$O(Q*N/B*log(B))$$$ where $$$B=\sqrt{N}$$$.

For each query, maintain the answer from left to right. If the current minimum is greater than the current block's minimum, we can use a binary search to find where the current block's first minimum is.

Submission: 279662760

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

Can we use ternary search at the problem E, though we need to find the minimum here?

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

anyone mind to explain solutions of G3?

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

    i wrote a really long solution as you can see above in the editorial :(

    Any specific queries in it?

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

Can someone suggest a testcase where this will fail for C? It fails on testcase 2.

wrong answer 862nd numbers differ — expected: '2', found: '1'

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

    Cannot compare x and y. You should compare ceil(x/k) and ceil(y/k) instead.

    Countercase: x=9, y=8, k=3. Your solution prints 5 but correct answer is 6

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

279728269

can someone pls tell me why is this failing

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

The solution to A talks about choosing c and then talks about "distance".

The solution to Problem D doesn't even mention (let alone prove/sketch) that the mentioned right-angled triangles are the only ones.

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

    Thats because people who read the editorial for A and people who read editorial to D are different audiences. Obviously more experienced people need less intermediate steps to understand a solution. Look at any div 1 F solution and see how fast paced they are.

    I remember the general guidelines is to keep solution to every problem approximately equal lemgth.

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

      What? My objection to A was not that it had too much fluff, but that it makes absolutely no sense.

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

You can just say that G3 is range sum of history sum(

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

last 3 problems G123 were actually suitable Div2DEF I think since many red & orange people couldn't solve G23.

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

Why my C wrong? 279562541

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

this is code of frog jumping problem c of 971 what is wrong with this code ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

include

using namespace std; int main() { int t=0; cin>>t; while(t--){ int x,y,k,ans,d=0; cin>>x>>y>>k; if(x<=y){

d=y/k;

if(y%k!=0){ d=d+1;} ans=2*d; } else if(x>y){ d=x/k; if(x%k!=0){d=d+1;} if((d-1)*k>y){ans=2*d-1;} else{ans=2*d;}

} cout<<ans<<endl;

} return 0; ~~~~~~~~~~~~~~~~~~~~~~~~~

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

Nice div3 so im sad for urt

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

My submission to problem E was exactly the bonus solution mentioned in the editorial. I spent around 1 hour debugging during the contest but the last sample case was failing. After the contest I submitted the same solution and it passed. I believe there is some precision bug in Apple clang. Can anyone else try this on the last sample test?

** Please ignore the excessive use of long double. I was getting panicked :) **

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

In D, how do we prove that there will be no other cases? Also, can someone share how did they arrive at those 3 points (last case)?

I eventually realized that those 3 points made a right triangle during contest, but it took me a long time.

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

Hi guys I'm new here. When a solution is provided in C++ does that imply that the time constraint for the problem is not achievable using a language like python?

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

firefly queries(f)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define pb push_back
#define pll pair<ll,ll>
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define endl "\n"
#define vpll vector<pair<ll,ll>>
#define vvll vector<vector<ll>>
#define vll vector<ll> 
#define sec second
#define fi first
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define geta(c,n) vector<ll> c(n); for(ll i=0;i<n;i++)cin>>c[i];
//-------Seive of Eratosthenes---------------------------------------
const ll MOD = 1e9 + 7;
const ll N = 200100; 
vector<ll> factorials(N + 1), inv_factorials(N + 1);
vector<int> is_prime(N, 1);
void seive(){
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i * i <= N; i++){
        if (is_prime[i]){
            for (int j = i * i; j <= N; j += i)
                is_prime[j] = 0;
        }
    }
}
ll lcm(ll x,ll y){
    return x*y/__gcd(x,y) ;
}
ll bin(ll x, ll n, ll mod) {
    ll ans = 1;
    x = x % mod;
    while (n > 0) {
        if (n % 2 == 1) {
            ans = (ans * x) % mod;
        }
        n = n / 2;
        x = (x * x) % mod;
    }
    return ans;
}
void precompute_factorials(ll n, ll mod) {
    factorials[0] = 1;
    for (ll i = 1; i <= n; ++i) {
        factorials[i] = factorials[i - 1] * i % mod;
    }
    inv_factorials[n] = bin(factorials[n], mod - 2, mod);
    for (ll i = n - 1; i >= 0; --i) {
        inv_factorials[i] = inv_factorials[i + 1] * (i + 1) % mod;
    }
}

ll ncr(ll n, ll r, ll mod) {
    if (r > n || r < 0) {
        return 0;
    }
    return factorials[n] * inv_factorials[r] % mod * inv_factorials[n - r] % mod;
}

vector<ll>  getfactors(ll n){ 
    vector<ll> ans ;
    for (int i=1; i<=sqrt(n); i++) { 
        if (n%i == 0){ 
              ans.pb(i);
              if (n/i != i) 
              ans.pb(n/i);
        } 
    }
     return ans ; 
}

void solve() {
ll n,q ;
 cin>>n>>q;
 geta(a,n);
 vector<ll> pre(n);
 pre[0]=a[0];
  for(int i=1;i<n;i++)
    pre[i]=pre[i-1]+a[i];
  ll sum=pre.back();
 while(q--){
    ll l,r;
    cin>>l>>r;
    l--,r--;
    ll q1=l/n,r1=l%n;
    ll q2=r/n,r2=r%n;
// q1+r1-1 -->n && 0-->q1-1
//q2 --> q2+ r2-1
ll ans=0;
  if(q1==q2){
    ll st=q1+r1;
    ll len=r-l+1;
    if(st+len-1<n){
      ans += pre[st+len-1];
       if(st>0)
       ans-= pre[st-1];
    }
    else{
        ans += sum-(st>0?pre[st-1]:0);
        ans += pre[(st+len-1)%n];
    }
  }
  else{

        ll st1=(q1+r1);
    if(st1<n){
         ans += sum-(st1>0?pre[st1-1]:0);
         if(q1>0)
        ans += pre[q1-1];
    }
    else{
        if(q1>0){
            st1%=n;
            ans += pre[q1-1]-(st1>0?pre[st1-1]:0);
        }
    }
    ll ed2=q2+r2;
    if(ed2<n){
        ans += pre[ed2]-(q2>0?pre[q2-1]:0);
    }
    else{
        ans += sum-(q2>0?pre[q2-1]:0);
        ed2%=n;
        ans += pre[ed2];
    }
     if(q2-q1-1>0)
     ans += (q2-q1-1)*1ll*sum;
  }
       cout<<ans<<endl ;
 }
}




int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

   ll t1=1;
    cin >> t1; 

    while(t1--) 
        solve();
    return 0;
}

can anyone check the error in my code

getting output: wrong answer 247th numbers differ — expected: '4', found: '-165885590936472'

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
from math import ceil
for i in range(int(input())):
    x,y,k = list(map(int, input().split()))
    if y>=x:
        print(ceil(y/k)*2)
    else:
        print(2*ceil(x/k)-1)

why does this not work for C

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

Great problems G1,G2,G3! It's nice to have bonus educational problems like these, although I feel like these problems could've also been placed in a div 3 round, since more higher rated participants take part in div 3 rounds than div 4.

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

kindly explain quadratic eq approach to E

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

    The function that we're minimizing is abs(quadratic). Imagine the graph of a quadratic — on taking absolute value, the part below x-axis goes above x-axis. Now, the minima occurs at one of the roots, because everything else is positive. Graph is symmetric around both roots, so we need to check one of them only.

    However, the root may not be an integer. Say, the root of our quadratic is equal to 1.22. You need to check at both 1 and 2 for minima because your range, in this question, is integers only. That is why he takes min(f(i), f(i+1)). At least, this is my understanding of the solution.

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

      I am also trying the quadratic formula method but can't find what I am missing. Can anyone point out what I am doing wrong 279810011

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

an anyone explain why from here ∑rj=l+k−1f([al,al+1,…,aj]). we can associate to here Let ci=f([ai,...,ai+k−1]). ∑r−k+1j=l(minji=lci)

I mean supposed we caculate the answer for interval [l, l+k] then if we take min(c[l], c[l+1]), it could be smaller than the answer. For example: [l, l+k] is already consecutive, so the answer for it would be k+1, but if we take min(c[l], c[l+1]), it will be only k.

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

Nevermind. Understood

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

1 2 2 1 3 2 1 2

Is this a valid test for G1?

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

Can someone help me with problem E

how is val1 in the solution equal to (mid+k-1+k)*mid//2 ?

from what I understand val1 is the sum of integers from k->k+mid, and for that I did this,

sumof k->k+mid = sumof 0->k+mid - sumof 0->k-1
               = ((k+mid)*(k+mid+1) - k*(k-1)) / 2
               = (k^2 + mid^2 + 2*mid*k + k + mid - k^2 + k) / 2
               = (mid^2 + 2*mid*k + 2*k + mid) / 2
               = (mid*(mid+2*k) + 2*k+mid) / 2
               = (mid+1)*(2*k+mid) / 2

this is where I arrive at and cant relate this with how the equation from the solution came

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

I think I found a mistake on problem D. My intuition is that there exists a Pythagorean Triplet (a, b, c) such that a belongs to triplet (m, n, a), and b also belongs to triplet (x, y, b). It is proven that such triplet exists. For example, (15, 20, 25), where 15 is also a hypotenuse of (9, 12, 15), and 20 is also a hypotenuse of (12, 16, 20). Then I drew these three triangles and got five points: (0,0), (0,12), (25,12), (25,0), and (9,0). It can be shown that there exists 7 right triangles among these 5 points, however, the answer given by the solution is 6. This is because the solution did not count the triangle (15, 20, 25).

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

Dominater069 Test cases of Problem G3 are too weak.

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

In problem G2 binary lifting solution, what does w(h, i) mean?

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

why my solution in G1 wrong :<. my solution did i forgot to reset something?

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

Hi folks,

I'm trying to solve 971, task D.

for this example

9 1 0 2 0 3 0 4 0 5 0 2 1 7 1 8 1 9 1

I get answer 9, but the task output says it should be 8. Can you confirm if the answer is really 8?

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

G3 binary lifting almost the same as G2.

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

Why one code is giving TLE other not can anyone explain advance thanks

**Problem G1**
void ram() {
    int n, k, q;
    cin >> n >> k >> q;
    vector<long long> a(n);
    vector<int> ans(n - k + 1);
    
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    int j = 0;
    multiset<int> st;
    map<int, int> mp;

    for (int i = 0; i + k <= n; i++) {
        int end = i + k - 1;
        while (j <= end) {
           if (mp[a[j] - j] > 0) {
              st.erase(st.find(mp[a[j] - j]));
           }
            mp[a[j] - j]++;
            st.insert(mp[a[j] - j]);
            j++;
        }
        ans[i] = k - *prev(st.end());
        if (mp[a[i] - i] > 0) {
            st.erase(st.find(mp[a[i] - i]));
        }
        mp[a[i] - i]--;
        if (mp[a[i] - i] > 0) {
            st.insert(mp[a[i] - i]);
        }
    }
    
    while (q--) {
        int l, r;
        cin >> l >> r;
        l--; 
        cout << ans[l] << endl;
    }
}


**Other Code Problem G1**
void ram() {
    int n, k, q;
    cin >> n >> k >> q;
    vector<long long> a(n);
    vector<int> ans(n - k + 1);
    
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    int j = 0;
    multiset<int> st;
    map<int, int> mp;
    for (int i = 0; i + k <= n; i++) {
        int end = i + k - 1;
        while (j <= end) {
            if (mp.find(a[j]-j)!= mp.end()&&st.count(mp[a[j]-j]) != 0) {
                st.erase(st.find(mp[a[j]-j]));
            }
            mp[a[j] - j]++;
            st.insert(mp[a[j] - j]);
            j++;
        }
        ans[i] = k-*prev(st.end());
       if (mp.find(a[i]-i)!= mp.end()&&st.count(mp[a[i]-i]) != 0) {
                st.erase(st.find(mp[a[i]-i]));
            }
        mp[a[i] - i]--;
        if (mp[a[i] - i] != 0) {
            st.insert(mp[a[i] - i]);
        }
    }
    
    while (q--) {
        int l, r;
        cin >> l >> r;
        l--;
        cout << ans[l] <<endl;
    }
   
}
 
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Both code are same only changes in if codition if (mp.find(a[j]-j)!= mp.end()&&st.count(mp[a[j]-j]) != 0) { st.erase(st.find(mp[a[j]-j])); } other: if (mp[a[j] — j] > 0) { st.erase(st.find(mp[a[j] — j])); }

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

Can someone please explain problem F? I can't understand the editorial.

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

Anyone facing issues viewing their submissions? Whenever I click on my submission to check test results I get 403 Forbidden error.

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

I have an easier way to solve D with an array and 2 for. Here is my submission 279941542

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

Can anyone kindly tell why this approach is wrong towards E- KLee's super duper large array submission

I am starting from k and ending at n+k-1 as my high. Then for each mid value, i am finding the prefix sum till that and suffix sum and finding absolute difference. Whichever gives us minimum is the answer.

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

The Solution of E written by the mathematical method is so beautiful. Thoroughly calculate the sum function of |a1+a2+...-an| , then find the zero position for this sum function, awesome math!

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

In fact, I built a tree to solve G2.

First, just like G1, I worked out the $$$f([a_i,a_{i+1},\cdots,a_{i+k-1}])$$$ for all $$$i$$$ such that $$$1\leqslant i\leqslant n-k+1$$$, then let $$$w_i = f([a_i,a_{i+1},\cdot,a_{i+k-1}])$$$.

Link an edge $$$i \xrightarrow{w_i\times(j-i)} j$$$, such that $$$j$$$ is the minimum that satisfies $$$j > i$$$, $$$w_j < w_i$$$ (if such $$$j$$$ doesn't exist, then let $$$j\leftarrow n-k+2$$$).

It can simply prove that these edges consitute a tree, and the root of tree is $$$n-k+2$$$.

Let $$$dis_i$$$ denote the distance from $$$i$$$ to the root.

When querying $$$[l, r]$$$, we need to do a binary search to find the shallowest $$$p$$$, such that $$$p$$$ is an ancestor of $$$l$$$ and $$$p \leq r-k+1$$$. Therefore, the answer is $$$dis_l - dis_p + w_p \times (r - k + 1 - p + 1)$$$.

This algorithm runs within $$$O(\log^2 n)$$$ time for each query. (if you use the "longest chain separation" to calculate the k-th ancestor within $$$O(1)$$$ time, it can be optimized to $$$O(\log n)$$$)

You can find my code here: https://codeforces.me/contest/2009/submission/279915573.

But now I have difficulties in using the same thought to solve G3.

Please help me. Thanks a lot.

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

Can someone explain why my submission is giving wrong answer?

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

Can someone explain the bonus solution of problem E

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

https://codeforces.me/contest/2009/submission/280117676 can anyone help me with this java code.. why it is wrong?? this is G1

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

Can anyone state the approach for O(1) solution for E?

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

can someone explain the lazy segtree solution for G2 in more detail please?

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

Gif in D singlehandedly lowered the rating by 200pts

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

Help! with problem C. why if x=8, y=0, k=2 there should be 7 steps and not 8 steps it would take to get from 0,0 to 8,0. please explain....

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

G2 can also be solved offline without lazy segment tree using prefix sum and binary search
281048790

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

Can someone please look what might be the issue in my implementation for G1.

https://codeforces.me/contest/2009/submission/281136208

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

problem C, test 1 : ans = 7 is min

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

how to do 2009E in C++ please

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

How do you solve F using bitmask?