DishonoredRighteous's blog

By DishonoredRighteous, history, 4 years ago, In English
Tutorial is loading...

Author's solution: 80407149

Tutorial is loading...

Author's solution: 80407200

Tutorial is loading...

Author's solution using formulas: 80407222

Author's solution using prefix sums: 80407239

Tutorial is loading...

Author's solution: 80407273

Tutorial is loading...

Author's solution: 80407303

Author's solution using ternary search: 80407326

Tutorial is loading...

Author's solution: 80407360

| Write comment?
»
4 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Video Tutorial for C

Enjoy watching!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks!!

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

    Can you add subtitles. Unable to understand you.

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

    Why don't you make Tutorials of harder problems like F?
    I'm not saying that C was easy.

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

      This is a question people keep asking me in both Youtube and Discord, and I feel the need to explain here the answer.

      The first reason why I can't do the video tutorials for literally every task I solved during the contest is because I don't have the time to do this as a full-time activity and I focus my effort on doing a video tutorial for the most interesting task in the contest which is not too easy or too hard.

      Another reason why I can't do some of the video tutorials is because some concepts used in tasks are not suitable for the video tutorial format, a good example would be today's F, because it involves several mathematical observations which are quite hard to explain properly, which would make the video boring and not enjoyable for most of the participants.

      Last but not least, I believe that doing a great video tutorial for something like F takes a lot of time, and at the same time it won't get as much audience as my usual content(Div2 CD/Div3 DE).

      In conclusion, such a discussion is always welcome(I have copypasted some of my arguments I have already mentioned in the discord server) and maybe I'll post something on Youtube to clarify this, because of the reasons I have mentioned above.

      You can always join my discord server for more in-depth discussion.

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

        Yeah audience matters. Quality of the content matters too. Youtube have too many coders. I hope you got my point. Waiting to see more vids in future.

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

        Yeah! this is my disscussion.

        I have answered your(stefdasca) doubts in the previous discussion here but i being green got wooed there and when an orange guy Bhj2001 said the same thing(in this post) audience supported him. I am going to be wooed here too but does that bothers me.

        I am said that such a biasing occurs on a plateform where people are literate and more importantly intelligent minds but this doesn't bothers me because i dont care about people's thinking until i my right in my views.

        Coming on stefdasca's doubts and replying to this comment:

        First of all u(stefdasca) need to be clear that why are you doing this:

        1. For sake of Your channels popularity, more views, more audience or

        2. For helping the coding community

        3. Both mixed

        If 1. or 3. is your answer then why dont you make videos for A and B too along with C as it would take very less time and would bring much audience,views and fame to you.

        If your answer is 1. u r doing great, don't read below this.

        Your actions show that you are 1. Otherwise

        You said that you dont have time, so instead of making Div1AB make Div1C(atleast) and D and i dont think so Div1C coudn't be explained with a video by an orange guy like you who has both calliber and talent.

        If you think harder problems would be boring to listen so i would tell you that people who gets bored from F would not come to see the F and who came are very eager to learn it. Also i am assumming that you are not in this for gathering more audience and popularity as stated in 1.

        Adding from previous disscussion, There are few blue coders who upload video editorials for Div1AandB(very well explained) like striver_79

        Dont reply by saying this nuisance "he is doing what he can contribute, atleast he is doing this what is your contribution" To reply this i would reply in your language only that why are you expecting from a green, moreover i upload solutions for ABandC.

        One of the personal reasons for this discussion is that few/many of the times i can't understand Div2DandE from text editorial but this new revelation of video editorials have helped me a lot in personal but i cant find good content for this.

        I know that you guys wouldn't understand but i have to say this.

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

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

          Basically you want me to do something else just because someone is already doing the same content?

          Sadly, this is not how arguments work, and I believe competition is always welcome in order to make our standards higher.

          As a matter of fact, I did video tutorials for F but they didn't get the same results as C from the same round.

          I don't feel confident enough to explain how every Div1C/D works, otherwise I would have done that, while having more than just 2116 rating.

          That being said, I invite you to respond to the poll I have done on my channel

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You got downvoted because when you asked this it sounds like you are asking just because you can and you don't need this whereas when bhj2001 asked it sounds like his current content is not useful for him, so he wants to ask if there will be something useful for him in his channel.

          That's the difference here agreed this difference is due to the rating. But blindly voting is not the case. Rather its difference of credibility. I'm also sure the people who downvote you there didn't vote here and those who voted here didn't downvote there.

          Here upvotes are by the people who need Div2F (rating similar to bhj2001) whereas downvotes there are by people with a rating similar to you.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Your videos are very helpful because they show to the point thinking.And they are really short time 5/6 min only.

        I saw your last Div 3 video E. I was very confused for this problem. But after watching your video I got to know the very basic first approach that was brute force then visualizing it as a DP wheras others just explained it as a DP never told why Dp.

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

          I will like to address the "other" keyword here. Since I was the only "other" one who made a video on E, I guess I did say, why DP, when I referred you to checkout min cost path problem during the problem. In min cost path problem video, a proper explanation was given on why DP.

          P.S: If this comment of "other" is for me, please checkout the content before saying this.

»
4 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Editorial so fast

»
4 years ago, # |
Rev. 2   Vote: I like it -14 Vote: I do not like it

So quick editorial! Thank you!

»
4 years ago, # |
  Vote: I like it -62 Vote: I do not like it

I should have checked editorial during contest

»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Did anyone use recursive DP on problem B, would that TLE?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -26 Vote: I do not like it
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you explain this please?

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

        1) sort array(a)
        2) for every dp[i][j] two cases i)j=0 ii)j=1 (when ith explorer go)
        3) go function will return max of i'th position
        4) if we have already calculated that stage return max(dp[i][0],dp[i][1]) else we need to calculate dp[i][0]&dp[i][1]
        I) calculating dp[i][1]
        if(i>a[i]) we can't add ith explorer and
        if (i<=a[i])we can add and the i-a[i] previous ones will have to be added
        II) calculating do[i][0]
        it is simply go(i-1)

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did it and I don't understand why my solution get TLE https://codeforces.com/contest/1355/submission/80314876

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -12 Vote: I do not like it

      I can understand that my solution get WA after the contest, but TLE? It is very easy to prove that a solution fit in time, the pretests really sucks!

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

        You reset the whole dp array $$$T$$$ times, so the complexity will be $$$O(TN)$$$

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think your problem is with your memset, you are assigning MAXN times -1 for every test case, that is O(n^2).

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's because of memset. You are reseting whole array of size 2 * 10^5 for every test case. So the complexity is O(MAXN * T) where T is the no. of test cases

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

      same happened with me https://codeforces.com/contest/1355/submission/80344928 and now when i implemented it in c++ it got accepted, quite amazing

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So fast Editorial!

PS: the round is too hard for me. A isn't friendly to newbies.

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

    Div2 isn't supposed to be friendly with newbies. That's why we have Div3's and now Div4.

»
4 years ago, # |
  Vote: I like it -11 Vote: I do not like it

The fastest editorial I've ever seen!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

round was great execpt that D, found that too easy

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

For problem E, if we set F(h) = minimum cost to make all pillars height h, is this function monotonically nonincreasing up to a point and then monotonically nondecreasing?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes.

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

      Can you prove it?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I see passed solutions assume that. and uses the ternary search!

      can someone prove it?

      lohit_97 could you?

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

        No, I don't have a proof. More of an intuition.

        You can look at the editorial, and see the cost function for P < Q and P > Q and concavity of cost function changes at some point as mentioned by the editorialist.

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

          Also, just to strengthen my intuition I ran the cost function from H=1 to H=100 for multiple arrays, and I could that function is unimodal.

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

        I cannot prove it analyticaly. but i can prove it intuitively. let f(x) be the function for minimum cost to make all pillars of height x. hence F(x)=n1*a+n2*r-min(n1,n2)*(a+r-min(m,a+r)). n1 is number of bricks to add. n2 is number of bricks to remove. As x increases n1 increases and n2 decreases. let say c is the point where n1 attains its max value but less than n2. And then you can break the function about c. F(x)=n1*(min(a+r,m)-r)+n2*r, x<=c and F(x)=n2*(min(a+r,m)-a)+n1*a, x>c both of the function are of the form $$$ax+by$$$. Hence we can see it intuitively that given function is unimodal.

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

          Could I ask some stupid questions ^^ ?

          1. So do you mean your "$$$c$$$" is the local minima of the function?

          2. And the form of your function is $$$F(x) = ay + bz$$$, so how do you ensure that $$$F(x - 1) < F(x)$$$ or $$$F(x + 1) > F(x)$$$ or something like that? It actually wasn't intuitively understandable for me.

          Sorry for my poor logic ^^. Hope you will answer me <3 <3. Thank you

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

            To answer your question lets define some functions
            $$$g(x)$$$ = $$$Number$$$ $$$of$$$ $$$blocks$$$ $$$needed$$$ $$$if$$$ $$$common$$$ $$$height$$$ $$$=$$$ $$$x$$$.
            $$$h(x)$$$ = $$$Number$$$ $$$of$$$ $$$blocks$$$ $$$to$$$ $$$remove$$$ $$$if$$$ $$$common$$$ $$$height$$$ $$$=$$$ $$$x$$$.
            $$$F(x)$$$ = $$$a*g(x) + b*h(x).$$$
            In div2E g(x) and h(x) have some properties.
            1. g(x) is monotonic increasing function.
            2. h(x) is monotonic decreasing function.
            3. Rate of chnage in $$$g'(x)$$$ is greater than rate of change of $$$h'(x)$$$.
            4. From 3rd $$$g^″(x)$$$ $$$>$$$ $$$h^″(x).$$$
            Now for a unimodal function its derivative has to be monotonic.
            i am assuming a>0 and b>0. $$$F'(x)$$$ $$$=$$$ $$$a*g'(x) + b*h'(x)$$$. at some $$$x$$$ postive $$$g(x)$$$ cancels negative $$$h(x)$$$ , and that $$$x$$$ will be the required minima. You will see it more clearly by writing values of $$$g(x)$$$ and $$$h(x)$$$ for some test case

            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thanks so much <3

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

              Rate of change in g′(x) is greater than rate of change of h′(x)

              How can we say this?

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

        My proof goes like this:

        Let $$$H, X, P, Q, M, A, R$$$ is declared the same as in the editorial above.

        We prove (from the editorial), when we increase $$$H$$$ by $$$1$$$:

        • $$$P \ge Q$$$ : the cost will change $$$AN−M(N−X)$$$.

        • $$$P \le Q$$$ : the cost will change $$$-RN+MX$$$. $$$($$$Because $$$R(Q' - P') + MP' = R(Q - P) + MP - RN + MX$$$).

        Let $$$F(H)$$$ is the cost when ADD / REMOVE / MOVE so that the resulting height for all the pillars is $$$H$$$.

        Let $$$H_0$$$ is the minimum $$$H$$$ such that : $$$P \ge Q$$$ and $$$X$$$ is minimum as possible (call this $$$X$$$ : $$$X_0$$$).

        When $$$H \ge H_0$$$, because the rate of change when $$$H$$$ increases by $$$1$$$ in $$$F(H)$$$ is $$$AN−M(N−X) \Rightarrow $$$ when $$$H$$$ increases $$$\Rightarrow X$$$ increases $$$\Rightarrow AN−M(N−X)$$$ increases . The same thing implies with $$$H < H_0$$$, when $$$H$$$ increases $$$\Rightarrow X$$$ increases $$$\Rightarrow -RN + MX$$$ increases.

        • Case 1: Suppose $$$AN−M(N−X_0) < 0$$$, when $$$H$$$ increases the rate of change will go from negative to positive. And the function will go like this:

        So it's a part of a unimodal function. We need to prove that with $$$H < H_0$$$ the function $$$F(H)$$$ will be the remaining part of that unimodal function.

        Proof
        • Case 2 : Suppose $$$AN−M(N−X_0) >= 0$$$, no matter the sign of $$$-RN+MX$$$ it will always make an unimodal function because the monotonicity of $$$-RN+MX$$$ and $$$AN−M(N−X)$$$.
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Could someone help me figure out my mistake in Problem C. I iterate over z and try to find the valid x, y pairs. Here is my submission 80373780. Thanks in advance.

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

    You have ignored the restriction of $$$x$$$ and $$$y$$$ when calculating $$$useless$$$. $$$x$$$ should be in $$$[A,B]$$$ and $$$y$$$ should be in $$$[B,C]$$$.

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

      Useless is basically the number of points in the rectangle domain [A, B] X [B, C] which are not valid. So I'm interested in the triangle which is within the rectangle. tot is the total number of points which is in the rectangle

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could someone explain the mistake. thanks in advance

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I almost thought about how to solve problem D! Thank you for preparing this contest!

»
4 years ago, # |
  Vote: I like it +20 Vote: I do not like it

One minute silence for those who wasted time on C instead of D

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Didnt see the leading zero condition in A(sad)..wasted time there; however lucky to notice that D was easy.. At the end did B and D only;; Great Contest overall

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

felt like one of the toughest div 2 contest ,more like div 1 contest. Test cases were really strong

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

    Better to have strong test cases than get hacked afterwards

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

      What if someone doesn't hack my submission and my solution is wrong but it passed all pretests.So,during the main tests,the hacker's test cases will again judge my submission,Right?

»
4 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Maybe problem F is solvable for 16 queries. It's still a conjecture, though. Here's why:

We need to find the GCD of hidden number and $$$2^{11} \times 3^7 \times 5^4 \times 7^3 \times 11^2 \times \cdots \times 31^2 \times 37 \times \cdots \times 617$$$.

If my checking program is not wrong, it will go all correct through $$$X = 1$$$ through $$$10^9$$$. The multiplied number is large but $$$1.90354 \times 10^{274}$$$. Since it is less than $$$\left(10^{18}\right)^{16}$$$, we may be able to seek the GCD in $$$16$$$ queries.

Now, the problem is, pack the array $$$(2^{11}, 3^7, 5^4, \dots, 617)$$$ into $$$16$$$ groups, so that products of all groups will be less than $$$10^{18}$$$. When we pack them greedily, I was able to construct the division of $$$17$$$ groups. The $$$16$$$ is somewhat a combinatorial optimization task...

Remark: Construction of 17 Queries
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When $$$X = 2^{29}$$$, your code will return $$$12$$$ but the answer is $$$30$$$ which is not correct. right?

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

      I forgot to mention that, when the number of divisor is $$$d$$$, we will output $$$max(d + 7, 2d)$$$. So, the program will output $$$24$$$ and the correct answer is $$$30$$$, which is correct.

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

    Yes, we have solution that solves problem in 17 queries. But we make bound a bit bigger.

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

      I searched and I think I found $$$16$$$-query construction, that's it!

      Construction of 16 Queries

      We ask the 16 queries and let $$$P$$$ the product of number of divisors of return value. Then we output $$$max(P + 7, 2P)$$$.

      The implementation is 80386409. You can easily see that it's granted accepted for 16 queries! Maybe a world new record?

      The algorithm to find such partition is following.

      1. Choose elements so that product will not exceed $$$10^{18}$$$.
      2. Do 1. for $$$100 \ 000$$$ times and get the choosing combination nearest to $$$10^{18}$$$.
      3. Then, erase the chosen values from the list.
      4. Repeat 1. — 3. while the list is not empty.

      P.S. I have came up with another question. Is it impossible to do with 15 queries? I can barely prove that 14-query construction is impossible, because the product of primes up to $$$617$$$ is around $$$4.35916 \times 10^{255}$$$, which is slightly larger than $$$\left(10^{18}\right)^{14}$$$.
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        I wouldn't be certain that the product of these values is enough to claim impossibility. For example, maybe it would be better to ask lower powers of the numbers first?

        If you ask $$$2^6$$$ and the power of number $$$2$$$ is less than $$$7$$$ in the optimal solution then you didn't have to ask $$$2^11$$$ at all which gives you some improvement. And if not, then we know that the product of rest of the numbers can be at most $$$10^9/64$$$, so although we have to retry with powers of $$$2$$$, other numbers may be used in smaller powers.

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

    I have a randomised solution here. Can it be hacked or improved ??

    Here are the details of my solution:

    I ask for all the primes less than (10^9)^(1/4). Which can be packed into 4 queries. Then I ask for the primes found in another 5 queries. Now the remaning part has atmost 3 primes. Let's denote the remaning part as 'Y' and the no. of divisors found so far as "res".

    Case 1 : Y = p / p*p / p*p*p / p*q , answer = res*2

    Case 2 : Y = p*q*r / p*q*q ,

    Here If I manage to find atleast one prime's existence, I can safely answer res*4, otherwise I answer res*2.

    Atleast one prime among these will be less than X^(1/3). So for each remaning query, I shuffle the remaining primes from (10^9)^(1/4) to (10^9)^(1/3) and ask the query by taking maximum primes.

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

      I'm afraid that this solution can be hacked. There are 128 primes which lie in the range $$$[10^{\frac 94}, 10^{\frac 93}]$$$. You can check at most 4 such primes in each randomized query, so at most 52 of them in total. When $$$Y=p*q*q$$$, your probability of failure is more than $$$(\frac{126}{128})^{52} \approx 44\%$$$, which is actually very big. So it can be hacked by a test case like $$$824069460=2*2*3*5*179*181*181$$$.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well, Thanks for the hack.

        There are some mistakes in your calculation because I can check 6 primes (why not ?) and I stick to word "remaining" so I remove checked primes for next queries. Still proof by hack says it is significant.

        Here I changed limit from 1000 to 800. Because If all 3 primes are > 800, answer is atmost 8.

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

So, fast editorial.

»
4 years ago, # |
  Vote: I like it +33 Vote: I do not like it

D was easier to think than c.

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

can anybody help in proving D second paragraph

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

    If we assume S<2*N and assume K>0, then we calculate prefix sum array M{ M1, M2, M3,...,Mn}. Now, we are marking all the number that are of the form M1+T*S, M2+T*S, ... , Mn+T*S for all T>=0. An observation is made that if for any integer X, X and X+K is marked, then the array will contain a segment with sum K. This is because if X and X+K is marked then X = Mi + T*S and X+K = Mj + T*S, Mj>=Mi. "T" will not change because K<=S. Now, (X+K)-X = Mj-Mi=K which is the sum of the segment [j...i+1]. hence this segment will contain sum as K. Now we are considering the range [0,..,2*K*S-1]. This contains 2*K*N marked elements because marked elements are M1, M2,..., Mn, M1+S, M2+S,...,Mn+S,....., M1+(2K-1)*S, ...., Mn+(2K-1)*S (Next element M1+2*K*S>2*K*S hence out of range) ----> these are 2*K*N elements.Also all the numbers in the range[0,2KS-1] can be divided in pairs(x,y) such that y-x=K hence (0,K), (1,K+1), (2,K+2), ..., ,(2*K*S-K-1,2*K*S-1). Number of pairs are K*S. Since we are assuming that Petya will lose, so there is no segment whose sum is K, so there is no marked element X for which X+K is marked, So in each pair atmost 1 element will be marked since y-x=K. So number of marked element in the range [0,2KS-1] are less than or equal to KS (number of pairs). But number of marked elements in the range[0,2KS] are 2*K*N. Hence 2*K*N<K*S ---> 2N<S But initially we assumed that S<2*N which is a contradiction.

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +33 Vote: I do not like it

    Here's another way to look at the proof of D:

    Let's look at the prefix sums modulo $$$S$$$. There are $$$N$$$ different prefix sums: $$$M_1, M_2, \ldots,M_N=0(mod\;S)$$$. They are distinct because elements of the array are positive.

    Now, for a given $$$K >0$$$, look at the $$$N$$$ numbers $$$M_1+K, M_2+K,\ldots,M_N+K\,(mod\;S)$$$. These again are distinct among themselves.

    Now you have a total of $$$2N$$$ numbers in $$$[0,S-1]$$$, and since $$$2N > S$$$, two of them must be equal. So we have some $$$1\leq i\neq j \leq N$$$ such that $$$M_i + K = M_j\,(mod\;S)$$$. If $$$i \lt j$$$, then the segment $$$[i+1,j]$$$ sums to $$$K$$$, otherwise if $$$i \gt j$$$ then the segment $$$[i+1,j]$$$ (of the cyclic array) sums to $$$K$$$

»
4 years ago, # |
Rev. 2   Vote: I like it +75 Vote: I do not like it

I think these problems are much harder to prove than to solve. For A, and for D.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i would say B and D.

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

    I got the solution for A in 3 minutes, but spent 30 minutes trying to convince myself i was right, but i couldn't, then i tried to submit it anyway.

»
4 years ago, # |
  Vote: I like it -18 Vote: I do not like it

I am curious if binary search would work in problem E?

Spoiler
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    it worked, awesome

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

      This is like ternary search(or gradient descent) only. You're moving in the direction of decreasing slope, hence it works.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain your approach?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what about this #include <bits/stdc++.h> instead of that many?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the super fast editorial

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

Great problems(especially div2e) and nice editorial! Thanks!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody hack my C? Im not using dp or any pref sums. 80347181

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

    There is a similar one with nicer code formatting. Can somebody explain how it works? Thanks!

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it's just like mine. we can use two binary searches, one for z and one for x while iterating through values of y. My Submission

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

      logic is excluding all [x,y,z] tuples which will not form a triangle i have used an exact opposite approach can look at my solution https://codeforces.com/contest/1355/submission/80351154 (i can explain this if you want may be it will help yo understand that also)

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 3   Vote: I like it +1 Vote: I do not like it

      Mine very simple code. perhaps similar to editorial.

      For given $$$Z$$$ we have to find $$$X\,\, and \,\, Y$$$ such that $$$X+Y>Z$$$. which is same as $$$X>Z-Y.$$$ Let say difference $$$d=Z-Y$$$ for any possible value of $$$Z$$$ and $$$Y.$$$ Traverse through all the value of $$$Z$$$ then we can find what are the potential values for difference i.e. $$$ (Z-Y)$$$ can take value in range $$$[Z-c,Z-b]$$$. Now Increment this value of difference in this interval. Do this for all possible $$$Z$$$. Now for each difference you have it's frequency so check where this difference lie in the interval $$$[a,b]$$$ for poosible value of $$$X$$$ and updated the count for $$$X$$$ in the final result.

      Submission

»
4 years ago, # |
Rev. 2   Vote: I like it -56 Vote: I do not like it

Its easy to spot that a great percentage of top 100 participants are alternate accounts of DIV1 people. It will be really great to increase the frequency of Div1 contests to stop the rating theft of Div2 participants. (-_-)

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

    Yeah, it will be really great to increase the frequency of Div1 contests. I haven't participated any rated Div1 in about one month.

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

    I'm NOT

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

how to do c using prefix sum

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

For problem B using Pypy3 (Python), O(n log n) solutions TLE on test case 26. I saw other Python solutions with the same complexity which failed as well.

It seems to me you have not done a good job of balancing time constraint for the language.

My submission which TLE on test case 26

UPD: The cause seems to be input handling, people who used sys.stdin.readline() instead of input() passed.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    not really, c++ also TLE, though i think it is O(n) my submission

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

      You are getting TLE because of the memset function which is called for every testcase and size of your array is MAXN so total complexity is testcases*O(MAXN).

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

        oh! amazing details. thank you. so in some cases memset is not as good as a simple loop XD

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

          It works fine but you have to set the size of the array dynamically instead of a fixed size array.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

WAS A GOOD ROUND AND I THINK C , D SHOULD BE CHANGED

»
4 years ago, # |
  Vote: I like it -9 Vote: I do not like it

D was easier than c. Problem A ~ Problem B.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeahh... we all know that dude

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

To the guys who solved E in contest time. Do you really prove that it's a ternary search problem during the contest or because it's obvious that binary search won't work over here that you go for ternary search? Please it'd be helpful because I thought of it first but then I always stop when I can't prove something.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also didn't waste time in proving. Just run the cost function from 1 to 100 for various arrays.

»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Thanks for the amazing contest :)

Also for people saying D was easier than C, sure getting an AC was easier if you tried your luck.

The difficulty of problem D lies in proving that the answer is NO for the case N < 2*S.

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

    could you explain proof ?

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it -8 Vote: I do not like it

      Just an observation for suppose n = 4 m = 5 only option for array is all 1 and any one element is 2 like 1 1 1 2 we can get all k's

      for n = 4 m = 6 we have two option either make two elements as 2 or one element as 3 like 1 1 2 2 (or) 1 1 1 3 in both these cases we can get all k's as we have enough 1's and 2's in first option and in second option we have 3 so we can get higher numbers like 5 and 6.

      simillarly for n = 4 m = 7 but in case of n = 4 m = 8 we can make array as 1 1 1 5 (i.e last element is greater than 4 and there are no enough 1's to get 4) so answer is k = 4.

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

      My strategy to solve D during the contest : strategy

      PS: unable to come up with a convincing proof right now, will try to understand author solution.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good editorial. Delicate + sort. Thanks

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Why should we add 1 on $$$[x + B, x + C]$$$ segment? How can this give us the number of pairs such that they have a particular sum?

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

    The (intermediate) goal is to calculate the number of (x, y) pairs such that x + y = s for each possible sum s. (It is convenient to keep this counts in a frequency vector indexed by values of s.) For that we can iterate over valid values of x, i.e. from A to B and for each value of x iterate over valid values of y, i.e. from B to C. That enumerates all (x, y) pairs and for each such pair we can add 1 to the count of pairs with sum x+y, thus obtaining the total count of pairs per possible sum value in the end. This has a bad complexity and should be optimized.

    Note that for a given value of x, while iterating over y values, we add 1 to frequencies of all sums in the contiguous interval from x + B to x + C. Think of the desired frequency vector as a prefix array, which we will calculate later. And for now let us compute the vector whose prefix sums we are going to calculate to obtain it. To increase an interval in the prefix vector by 1, increase the element at the beginning of the same interval (index x + B), but in the original array, by 1 and decrease the element past the end of the interval (index x + C + 1), also in the original array, by 1. Iterate over values of x and do the same constant time operation just described (+1/-1) for each x. At the end compute the prefix sums vector to obtain the desired frequencies of the sums s.

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

    After calculating frequencies of x+y sums, the z variable comes into play. For the triangle to exist and not be degenerate, x + y > z must be satisfied. (x + z > y and y + z > x are already satisfied due to the increasing order restriction from the condition.)

    Now we can either iterate over values of s=x+y and calculate how many z values from the interval C to D are smaller than the given value of s and add the count to the answer. Or we can iterate over values of z from C to D like in the editorial and calculate the number of (x, y) pairs that satisfy x+y > z for the given z, again adding up all counts. To be able to get the number of (x, y) pairs with sum exceeding z in constant time, the second prefix sum calculation mentioned in the editorial is required.

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

      Thanks for detailed explanation! It helped.

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

      Amazing explanation thanks, editorial should write it as a difference array rather than a prefix sum , that's where i was getting confused , you also shared approach using difference array only.

      Maybe it would have been better if they included code.

      Thanks anyways :)

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Your explanation is awesome.Thanks for it.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Amazaing explanation friend, extremely grateful

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i think i learn more from comments than tutorials

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

I got a Wrong Answer on System Testing in D. Div3, here I come :).

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Can anyone explain the solution to Problem-C? Please. Thanks in advance

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem A,

I couldn't code for next 1:40 minutes

And I was like how can a problem A be so tough, because at first look it was saying that there is no way you can optimize K jumps. No log(K) or root(K) was coming to mind

then after I solved B and D. I read the lines of A again

It said calculate minDigit(a) and maxDigit(a) without leading zero, then it striked me that a zero can come in the middle digits.

And then assuming that it will happen definately and in time limit, I wrote the solution, without confirming that it will happen and it passed :)

If this problem would have been a C or something then confirming should have become mandatory (you can't wish magic happen at C) and confirming it would actually take a lot of thought in contest time!

But it took 1:40 min. What a game!

Nice Contest!!

PS: C was way tougher than D!!

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

    I think comparing C and D isn't logical. D is more about thinking and proving the case and it is easy to code. While C has completely different story!!

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

    When I read problem A, I looked at contest name if it was div1 contest!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone point out my mistake. My submission 80378908. I'm getting TLE

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Read about time complexity. Your code is O(K) and K can go upto 10^18. Hence this TLEs.

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

      But as given in tutorial it should not take more than some 60 moves right when we condition on 0

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

        You have to condition the smallest digit to 0, not N.

        I think you are misunderstanding the tutorial a bit.

        EDIT: My bad, I misread your code. Let me check it again.

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

        I think there is an issue with (int) and (long) in your code.

        In this line, int r = (int)n % 10; you're converting long to int. I think this is causing it to go into infinite loop. I haven't used JAVA but most likely issue is here.

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

          Lol thanks bro . The mistake was the int cast should be for the whole thing not for only n. Thanks again

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please explain C sulution with exactly one cycle.

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I solved problem Div2E in $$$O(10^9)$$$ time, because I check each possible height. It works in 421 ms.Submission

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How come it is working? About 3*10^7 runs in 1s, then shouldn't it be TLE?. Please correct me if I am wrong.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 3   Vote: I like it +10 Vote: I do not like it

      This example shows, that we can complete $$$10^9$$$ operations of addition and calculation maximum in time less than 1 second (0.88s). It is what I do in cycles for (int hh = s; hh <= low; hh++) and for (int hh = low+1; hh <= f; hh++) in my original solution. I sort all heights in not decreasing order and than process each segment $$$\left(h_i, ..., h_{i+1}\right)$$$ naively. It is not necessary, but I have no extra time to think during a contest (my strategy was a solve this problem in $$$O(10^9)$$$ and back to unsolved problem A next).

      In gereral words, all operations have their own cost. We have fast and simple operations like +, -, ^, |, and slow operations like % or /. For each CPU we known his clock speed (GHz). Modern Intel CPU has a $$$3.8$$$ GHz clock speed (in $$$1$$$ second). It is equal to $$$3.8 \cdot 10^9$$$ Hz. If we suppose, that one simple instruction can be executed in a few Hz, than we can complete $$$10^9$$$ such instructions, what we can see by example above.

      Why std::max also a fast instruction? Firstly, maximum of two integers can be calculated without comparison (there is a old problem on russian educational platforms to find maximum without comparison), if we will use binary representation of numbers. Even if GCC generates code with calculation of maximum with comparison, than in this for-cycles (specific behavior for this problem) branch predictor works well, because, actually, function is monotonic: we always update maximum or always keep old value, and CPU can predict a result of comparison.

      $$$3 \cdot 10^7$$$ abstract operations can spent different time and it depends on cost of operations.

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Problem E:
Can anyone please explain why the additional breaking point (i.e the point where P>Q changes to P<Q) occurs at the mean?

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +20 Vote: I do not like it

    Because, you can rewrite some sums.

    Let $$$H$$$ = $$$\dfrac{\sum\limits_{i=1}^N h_i}{N}$$$.

    So we know, that $$$\sum\limits_{i=1}^N h_i - H=\sum\limits_{i=1}^N h_i - N * \dfrac{\sum\limits_{i=1}^N h_i}{N} =0$$$. By the defenition, $$$P = \sum\limits_{i \in X}H - h_i,$$$ $$$Q = \sum\limits_{i \in Y}h_i - H$$$, where is $$$X$$$ is the set of indexes $$$i, h_i \leq H$$$, and set $$$Y$$$ is the set of indexes $$$i, h_i > H$$$.

    $$$\sum\limits_{i=1}^N h_i - H = Q - P = 0 \Rightarrow Q=P$$$

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any other more intuitive way for proving for the case S<2*N in D?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i did it as follows: if u need length n try to fill the array with ones except for the last position for example if n = 5 and sum = 10 the the array will be 1 1 1 1 6 at this case if k = 5 then u win then u need k to be more than the sum of ones and less than the last number. let the last number t, t = S — (n — 1) = S — n + 1 then t — (n — 1) >= 2 S — n + 1 — (n — 1) >= 2; S — 2n + 2 >= 2 S — 2n >= 0 then S >= 2n hope it helps

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

      it does not prove anything.

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

      It does proof for the general case. you have to show that for any combination of numbers it is not possible......Here you are proving for a particular combination.

»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Problem C can also be solved by finding valid solutions of the inequality x + y > z. Add a dummy variable d to get the equality x + y + d = z and remove the invalid solutions from the valid ones. Check this out.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did using presums but this method seem simpler. Can you explain the two lines in the for loop, I mean how you count for a particular value of $$$z$$$

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

    Let's start with the inequality x + y > z itself. If we find the number of solutions of the equation x + y <= z, then we can get the answer by subtracting it from total combinations of x and y i.e. (B - A + 1)*(C - B + 1).

    We know how to find the number of non-negative integral solutions of the equations of the kind a1 + a2 + ... + ar = n. So to reduce our inequality to get an equation like above, we need to get rid of the <= symbol by adding a dummy variable d. Now we have the equation x + y + d = z. But there is still a problem. Variables x and y can not be non-negative. To achieve this, we replace x with X + A and y with Y + B.

    Now our equation looks like this X + Y + d = z - A - B. So the number of solutions for this equation(without taking into account the upper limits of X and Y) is $$$\binom{z - A - B + 3 - 1}{3 - 1}$$$. Now to remove the solution where x >= B + 1 or X + A >= B + 1, we can replace X with (B — A + 1 + dx) to get the equality dx + Y + d = z - 2*B - 1. It has $$$\binom{z - 2*B - 1 + 3 - 1}{3 - 1}$$$ solutions. Do the same for Y. Thus total number of solutions for a given z becomes: (B — A + 1)*(C — B + 1) — ($$$\binom{z - A - B + 3 - 1}{3 - 1}$$$ — $$$\binom{z - 2*B - 1 + 3 - 1}{3 - 1}$$$ — $$$\binom{z - A - C - 1 + 3 - 1}{3 - 1})$$$. Hope it helps:)

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

      Your solution seems good, but isn't there double counting when you are taking dx + Y + d = z-2B-1 and X+dy+d = z-A-C-1 separately.
      Like it means in eqn(1), you may have cases like X>=B-A+1 with Y>=C-B+1 or Y<C-B+1
      likewise in eqn(2), you may have cases like Y>=C-B+1 with X>=B-A+1 or X<B-A+1.
      In both the cases, Y>=C-B+1 & X>=B-A+1, so aren't you double subtracting somehow.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Another solution for problem D:

Make the array consisting of (n-1) 1s and then the last element would therefore be (s-(n-1)). Now simply check if there exists a number which is greater than n-1 and is less than (s-(n-1)). That number, if it exists will never be achieved by summing any of the subrarrays.(Why? Give it a thought!). For the case of n=1, s must be more than 1 and then one valid value of K is 1. For the rest, the answer is NO :)

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

My python3 solution for young explorer div2 B gol tle ,it has passed pretest ,I didn't even sorted ,is this wrong ? Kindly look into this solution[submission:80341292]- https://codeforces.com/contest/1355/submission/80341292

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

    Just replace input() with sys.stdin.readline() (import sys before obviously). Input() is too slow, need to read number(s) faster.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same concept in C++ will be an AC

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

Another solution for E since the cost function has a local minima we can just use the simple binary search to find the local minima submission

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Although this isn't required as the editorial already explains everything about D. But here is an easy way to look at it. Let's just say you have N and S and you start off by putting 1 in each of the (N-1) places and the last place with (S-(N-1)).

1---1---1---1---1---(S-(N-1)). Let's prove that the answer is NO for the case when S<2*N. for simplicity let's take a case N=8 and S=15 1--1--1--1--1--1--1--8 now it's easy to see that the first (N-1) subarrays will fetch all the sums from 1 to (N-1). Now S-(N-1) is nothing but N(or greater than N). Include last element in the subarray and start constructing possible sum and you'll see that it will cover all the sum till S.

»
4 years ago, # |
  Vote: I like it -22 Vote: I do not like it

This was my solution for problem B can any help me where I am making a mistake here

include<bits/stdc++.h>

define ll long long int

using namespace std; int main() { ll t; cin>>t; while(t--) { ll n; cin>>n; ll arr[n]={0};ll ans=0; for(ll i=0;i<n;i++) {cin>>arr[i];} sort(arr,arr+n); for(ll i=n-1;i>=0;i=i-arr[i]) { if((i+1)>=arr[i]) ans++;} cout<<ans<<"\n"; }

}

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

WEAK PRETEST for B. I got TLE in contest submission in system testing. When I used my Fast IO template accepted verdict. Now I can do nothing but weep.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me with the editorial of Div2 B ??

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what exactly you dont understand. look at someone's solution first maybe that will help

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me with an issue I have? For problem B if I run the test case 1 1, it shows the answer 1 as it is supposed to on my machine. But the output when I submitted it was 2 apparently and I ended up getting Wrong Answer. Here is a link to my code :

https://pastebin.com/XP6ZzDui

Thanks in advance

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

does anyone passed B with python? thanks!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    With pypy.80386366. Fast IO. Got TLE in contest submission on system tests but hen used Fast IO and AC.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone simplify the proof for solution D? The editorial is hard to understand :/

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Just Imagine an array consisting of all 1's except for the last element. 
    Now our last element must be (total_given_sum-1's_so_far) and our (k is size_of_array). Eg 4 7; 
    - 1 1 1 4 will be the array as per our algo. 
    - k=3 but total_1's will be equal to k so answer is "NO". 
    - So, we can conclude that if total_1's is + 1 >= last_element. We wil never get answer.
    
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the reply. I followed a similar method during the contest but I was looking for a simpler explanation for the formal proof in the editorial.

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

Please suggest more problems like D that involve a similar prefix sums approach(adding to a segment). There was a question in a recent Div 3 which involved something similar, but I am unable to find more of those questions.

»
4 years ago, # |
Rev. 5   Vote: I like it +7 Vote: I do not like it

Short and Simple Solution for Problem 1355 C. Count Triangles

The min possible value of x + y is equal to a + b.

The max possible value of x + y is equal to b + c.

For all k from (a + b) to (b + c), find the number of different (x, y) pairs, such that x + y = k. This can be easily found since numbers are continuous (refer code). Let us call this array e[]. (e[k] = number of (x, y) pair such that x + y = k).

Now, for a given value of z, we have to count all possible (x, y) pairs such that x + y = z + 1, x + y = z + 2 ....... x + y = b + c. This can be found in O(1) if we maintain a suffix array for the array e[], found previously.

Now simply add all the suff[] values from index c + 1 to d + 1.

typedef long long ll;
typedef vector<long long> vl;
#define fe(i,s,n) for(int i=s;i<=n;i++)
#define fre(i,s,n) for(int i=s;i>=n;i--)
ll solution()
{
	int a, b, c, d, g = 0;
	cin>>a>>b>>c>>d;
	vl e(1e6 + 10, 0), s(1e6 + 10, 0);
	fre(i, b + c, a + b)
	{
		g = min(g + 1, min(i - (a + b) + 1, min(b - a + 1, c - b + 1)));
		e[i] = g;
	}
	fre(i, b + c, c + 1)
	{
		s[i] = s[i + 1] + e[i];
	}
	ll ans = 0;
	fe(i, c, d)
	{
		ans += s[i + 1];
	}
	return ans;
}
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    In this whole calculation use of both the arrays can be removed also(refer code).

    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long
    int main() {
        ll a,b,c,d;
    	ll ans=0;
    	cin>>a>>b>>c>>d;
    	for(int x=a+b;x<=b+c;x++){
    		if(x<c) continue;
    		ans+=max(0LL,min(x-b,b)-max(x-c,a)+1)*(min(x-c,d-c+1));
    	}
    	cout<<ans<<'\n';
    }
    
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain me this expression: g = min(g + 1, min(i — (a + b) + 1, min(b — a + 1, c — b + 1)));

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

      Let's assume a = 5, b = 6, c = 9, d = 15

      The value of x + y will be in the range (5 + 6, 6 + 9), inclusive, i.e., (11, 15).

      Now write down all the (x, y) pair which satisfies x + y = 11. We can find only one such pair — (5, 6).

      (x, y) pairs for other cases are :-

      x + y = 12 -> (5, 7), (6, 6)

      x + y = 13 -> (5, 8), (6, 7)

      x + y = 14 -> (5, 9), (6, 8)

      x + y = 15 -> (6, 9)

      Observation 1

      It is clear that the maximum number of (x, y) pair for any fixed value of (x + y) is always less than or equal to (b — a + 1) and (c — b + 1), i.e., the count of numbers that x can take and the count of numbers that y can take, respectively.

      Observation 2

      The minimum possible value of x + y is m and maximum possible value of x + y is M. (where m = a + b, and M = b + c)

      Then, for x + y = m and x + y = M, there'll be at most 1 (x, y) pair each. For example :- for x + y = 11, and x + y = 15, we can have at most one pair i.e., (5, 6), (6, 9) respectively.

      For x + y = m + 1 and x + y = M — 1, we can have at most 2 pair.

      Similarly for x + y = m + k and x + y = M — k, we can have at most k + 1 pair.

      So, we've found 2 conditions that'll help us determine the number of (x, y) pairs such that x + y = m + k :-

      1) No of (x, y) pair such that x + y = m + k, will always be less than or equal to min(b — a + 1, c — b + 1).

      2) No of (x, y) pair such that x + y = m + k, will always be less than or equal to k + 1.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell why I'm getting memory limit exceeded in problem A.

https://code.sololearn.com/cK5Ie6MoP594/#cpp

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The value of k is so high. So a[k+1] is beyond of memory limit.

»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

E and F were like, at a different level compared to the first 4 problems!

(Luckily it's unrated cause I could not AC D during the contest :( )

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I did this solution for B using PyPy 3: https://codeforces.com/contest/1355/submission/80386227

it passed the protests but TLE'd test case #26 after system testing I did the same code in CPP , and it ran flawlessly: https://codeforces.com/contest/1355/submission/80387439

What is my mistake...

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Bro same with me. I used Fast IO after contest and then passed.

»
4 years ago, # |
  Vote: I like it +111 Vote: I do not like it

 )

»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

I didn't get the part where in the proof of D it says " and for prefix sum M let's mark all the numbers of the form M+TS for integer T≥0." I can't get a clear intuition on it. Please anyone help.

Thanks in advance.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain where i am wrong in ques c? solution: https://codeforces.com/contest/1355/submission/80358781

»
4 years ago, # |
  Vote: I like it +24 Vote: I do not like it

C can be solved without prefix arrays. Perhaps the following approach is more intuitive for some, at least for me it was.

Iterate over potential values of the sum s = x + y, which are larger than at least one possible value of z, i.e. from max(C + 1, A + B) to B + C. For each such value s:

  • Find the lowest allowable value of x: lowest = min(B, max(A, s - C)),
  • and the highest one: highest = max(A, min(B, s - B)).
  • For given values of s and x, y is fixed too. Hence the number of (x, y) pairs with sum x+y is equal to the number of x values between the found bounds: xyPairs = highest - lowest + 1.
  • Find the number of values of z lower than s: nrZ = min(s - C, D - C + 1).
  • Finally, add the obtained number of triangles equal to xyPairs * nrZ to the total answer.
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for sharing this approach. I was having a bit trouble in understanding the approach using prefix sums, but this approach is really easy to understand.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

After seeing the prefix sums solution of problem C, I feel, it wasn't that difficult.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Those who solved D during the contest, what was your thought process?
How did you guys arrive at conclusion stated in editorial?

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

    I had a slightly different approach. First I experimented with arrays of length 4, to see for which S it is possible to win. It was clear that things like 123x are not a good idea, as 123 immediately forms sums from 1 to 6. Instead, I thought it is better to have 111x — then first three numbers form only sums from 1 to 3, moreover, the only other two sums would be x and x+1. This led me to a conclusion that if I make array 111(S-3), then if S-3 >= 5, I can set K = 4. This generalizes to any N and S >= 2N: array 11...1(S-N-1) and K = N leads to a win.

    I did not attempt to prove that for S < 2N it is impossible to win. Intuitively, N numbers with sum < 2N will consist of a bunch of 1s and 2s, and maybe a few big numbers. But with a large number of 1s and 2s it is clearly possible to get any sum from 1 to their total sum, so it is very likely that any sum up to S will be achievable.

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

      Wow, this brings so much clarity to me on how to think.
      Thanks!

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Can anyone please explain the problem C using offline range update

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

nice problem and ideas but i think div.2 A must be easier.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain me why in problem A author has taken this X=1000(⌊a1/1000⌋+1) and whats its use??

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

    X is used to prove that given any a1, ai will have a 0 in one of its digits.

    If we assume that ai goes to infinity as it will never have a 0, then we can use X as just an arbitrary number between some ai and ai+1 (X cannot be in the sequence because 1000([a1/1000]+1) always has a 0 in the hundredths place).

    Because ai+1 cannot have a 0 (in the hundredths place), then ai+1 is at least X + 100. However, ai < X. Therefore, ai and ai+1 have a difference of more than 100, which is impossible as the max difference between any two elements is 81.

»
4 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Why aren't setter's and tester's solution link provided in editorial ? DishonoredRighteous

I need the implementation of problem C's editorial to understand it better.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

am i the only one not able to see the authors solution for problems ?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I get 'you are not allowed to view requested page' when clicking on authors solutions. How to fix this?

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

For C we need all x + y > z. x,y,z are the three sides of triangle.

Go over each x (a <= x <= b) and make a pref[] array to store the total values that make exactly sum value i. for each x you can make values from x + b to x + c. Don't add them using a for loop instead use difference array. so pref[x + b]++,pref[x + c + 1]--.

Now sum up the values pref[i] += pref[i — 1]. This will give you an array consisting all values u can make sum i using x and y where (a <= x <= b) and (b <= y <= c).

But we don't need the values that make this sum exactly, instead we need the toatal values greater than or equal to this value that can be made using some x and y. so make suffix sum of it. pref[i] += pref[i + 1].

Now all set. We go through each z and get the total numbers greater than or equal to z that can be formed using x and y. which is pref[z + 1]. do this for (c <= z <= d).

add them in a for loop.

Overall Complexity( O(a) + O(b + c) + O(d) ).

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

After seeing editorial for Problem A. I think, I was better off with no editorial.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In D problem the test case 3 4 answer is NO but if we write array as 0 0 4 and k as 3,then Petya wins, are we allowed 0 in the array, because that would make this problem really easy and this is not written anywhere(i think, sorry if i missed somethin)

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    2nd line of the question: "At the beginning of the game Petya has to come up with an array of N positive integers".

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi DishonoredRighteous. Could you explain why you use X=1000(⌊a1/1000⌋+1) in Problem A demonstration ? Thanks

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's just the next number to X where last three digits are equal to zero. It's easy to use such number for proof. Of course we can take some other number which has last three digits zero.

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

The prefix-sum approach for solving div2c is amongst the most beautiful and elegant things ive even seen

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, I am not able to understand the approach, can you help ?

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

      suppose you keep an array number[ ] that keeps track of how many times s=x+y can be calculated. no say x goes from 1 to 2 and y goes from 2 to 4. so x+y can range from 2+1=3 to 2+4=6. now, one way to calculate can be iterate through the possible values of x and for each x add 1 to all elements ranging from number[x+2] to number[x+4]. but this approach is to slow and almost O((B-A).(C-B)).

      Now one thing you could do is, iterate through all values of x and for each x, add one to number[x+2] and subtract one from number[x+4 +1]; so:

      x=2----> number[] = 0 0 0 1 0 0 -1 0 0 0....
         x=3----> number[] = 0 0 0 1 1 0 -1 -1 0 0....
         x=4 ---->number[] = 0 0 0 1 1 1 -1 -1 -1 0...

      you could do this in O(B-A) steps.

      then calculate a prefix sum of the number array. that is iterate over the entire array and define number[i] = number[i-1]+number[i];

      now number[] = 0 0 0 1 2 3 2 1 0 0 ........

      which is the same result we would get if we had calculated the number array by iterating all possible values of y for each possible value of x.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I can't understand the proof of s < 2n in the second paragraph?Can someone explain it?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please explain the proof in more details of why if S<2N petya will lose

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone got the output for First Question using java, for some reason I am getting timeout.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The input $$$k$$$ can be a huge value. Your loop while(k-->1) {... will loop $$$k$$$ times, which simply takes to much time.

    The expected solution to this problem is finding a way to make this loop run less than $$$k$$$ times.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how can we do that? did u found a way to do that?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If you cant solve it you are expected to read the editorial.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can C solve in O(1)?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

C solution with fft: 80351725.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In A question this constrain is too large 10^16 & 10^ 18 how it able to pass in 0(n)

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$O(n)$$$ solutions fail on this problem since $$$n$$$ might be huge. Aside of that you are expected to read the editorial.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think problem E can be easily solved by binary search like this https://codeforces.com/contest/1355/submission/80432019

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me how to solve 1355C using prefix sums??

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in question E, can anyone tell why the additional breakpoint is to be considered separately, and how to think of that case while solving the question during the contest ? thanks in advance.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E, can someone help me prove that only one global minima point for the cost function will exist over the whole range of height? Can't there be many local minimas instead?

Thanks in advance

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain the proof of D? I don't understand why there's a segment with sum $$$K$$$ in the cyclic array if $$$X$$$ and $$$X + K$$$ have been marked. Isn't it possible that the two prefix sums used to mark $$$X$$$ and $$$X + K$$$ had $$$S$$$ added to them a different number of times? If so, how does it imply the segment formed by the end points of these two prefixes has sum equal to $$$K$$$?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't understand the formal proof of problem-A ,Any help??

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Problem C could be solved in $$$O(1)$$$.

Let us suppose that $$$x=B-a,y=C-b,z=C+c$$$, where $$$0 \leq a \leq B-A, 0 \leq b \leq C-B,0 \leq c \leq D-C$$$.

Since $$$B-a+C-b>C-c$$$,we have $$$a+b+c<B$$$.

Then we can use Inclusion-Exclusion Principle(just a classic application).Specifically, just enumerate all subset of these three elements, suppose they are much too large (eg. a>B-A).

see code for more details 80326731

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

In problem F, we need no more than 20 queries to find the answer for X1, but how about X2?

Shouldn't the queries for X2 be caculated?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't understand why solution for D is correct. Why always pick k = 1(considering Vasya plays optimally)? For example if you pick K = 2 and you chose one element that is = 2 the solution is not correct.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I really hate that problem c -_-

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

Here's an explanation for D, if you haven't understood it from the editorial.
Let the prefix sum array be $$$M = { M_1, M_2, .., M_n}$$$.
All the elements in this array are unique and $$$\leq$$$ S as we are adding a positive number at each step.

Let $$$M' = (M_1+k)\%S, (M_2+k)\%S, .., (M_n+k)\%S$$$.
Elements in this array are unique as well and all are < S due to modulo.

If k=0, it is trivial. Suppose k>0.
If $$$M'_i = M_j$$$, then either $$$M_j = M_i+k$$$ or $$$M_i+k = M_j+S$$$.
If $$$M_j = M_i+k$$$, then j > i, segment from i to j has a sum = k.
If $$$M_i+k = M_j+S$$$, then j < i, segment from j to i has sum = S-k.

So there is no solution if $$$S \lt 2n$$$ as there should $$$2n$$$ unique elements($$$\neq k$$$ and $$$\neq S-k$$$) $$$\leq$$$ S and this is not possible. We don't know whether $$$S \geq 2n$$$ has a solution or not, but the construction in the editorial shows that it is always possible.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

If anyone need detail explanation for div2 C Here

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Used a lot of time writing 17 queries solution for Problem F.

https://codeforces.com/problemset/submission/1355/80821530

I think 22 is a good bound for contest.

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Problem E is same as https://www.spoj.com/problems/KOPC12A/


It already has more than 1000 accepted on SPOJ. It's expected in educational rounds not in normal rounds.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem D,suppose n=3 and s=5...the answer according to the editorial is "NO" but if we take the array [2,1,2] and K=4 the answer shall be "YES".

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can take a sum of subarray S — K = 1. The 2nd element of your array is 1, so Petya loses.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For C, we may simply do this:

Iterate over all possible values s of x + y. We need z <= min(D,s-1) and z >= C. Thus there are exactly n1 = C — min(D,s-1) + 1 possible values of z.

Now it remains to count how many x, y satisfy x + y = s. We need a <= x <= b, and b <= s- x <= c. The size n2 of the intersection of these intervals is precisely the number we need. We then add n1*n2 to the answer.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I really loved the explanation for problem E. I hope codeforces editorial are like these most of the time.

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

For Div2C, a blog.

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

Let's now assume that P≥Q, we have exactly X pillars with no more than H bricks and exactly N−X pillars with strictly more than H bricks. Let's try to increase H by 1 and see how the total cost will change. P′=P+X,

Can someone please explain this with example?

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

1355C has on solution of O(1) and O(1).
Split [B,C] to three: [B,b_0], [b_0+1, b_1], [b_1+1, C].
Here, B,b_0,D can, B,b_0-1,D cannot; A,b_1,D can, A,b_1-1,D cannot.
seg0

private static long Segment0(int A, int B, int C, int D, int b_0, int b_1)
        {
            if (b_0 < B)
            {
                return 0;
            }
            var b_min = C - B + 1;
            if (b_min < B)
            {
                b_min = B;
            }
            if (b_min > C)
            {
                return 0;
            }
            var b_tmp = C - A +1;
            if (b_tmp > b_0)
            {
                b_tmp = b_0;
            }
            if (b_tmp < b_min)
            {
                b_tmp = b_min-1;
            }
            var res = 0L;
            if (b_min <= b_tmp)
            {
                var cnt = b_tmp - b_min + 1;
                var val1 = B + b_min - C;
                // (1 + val1 + i)(val1 + i)/2
                // = (1 + val1)val1/2 + i* val1 + i(i+1)/2
                res += (long)(1 + val1)*val1 / 2 * cnt;
                res += (long)val1 * (cnt - 1) * cnt/2;
                res += (long)(cnt - 1)*cnt*(cnt+1)/6; 
            }
            if (b_tmp < b_0)
            {
                var cnt = b_0 - b_tmp;
                var val1 = B + b_tmp + 1 - C;
                var tmp = B-A +1;
                // (val1*2 - tmp + 1 + i * 2)*tmp/2
                res += (long)tmp * ((val1*2 - tmp + 1) + cnt - 1) * cnt /2;
            }
            return res;
        }

seg1

private static long Segment1(int A, int B, int C, int D, int b_0, int b_1)
        {
            if (b_1 - b_0 <= 0)
            {
                return 0;
            }
            var b_tmp = C - A +1;
            if (b_tmp < b_0)
            {
                b_tmp = b_0;
            }
            var res = 0L;
            var val1 = D - C + 1;
            if (b_tmp > b_0)
            {
                var cnt = b_tmp - b_0;
                // (val1 + 1)val1 / 2
                res += (long)(val1 + 1) * val1 / 2 * cnt;
                var tmp = B - (D - b_0);
                // val1 * (tmp+i)
                res += (long)val1 * (tmp * 2 + cnt -1) * cnt /2;
            }
            if (b_1 > b_tmp)
            {
                var cnt = b_1 - b_tmp;
                var tmp = (D - b_tmp) - A + 1;
                // (val1*2 - tmp + 1 + i) * (tmp - i)/2
                // (val1*2 - tmp + 1) * tmp + (tmp -val1)i - i(i+1)/2
                res += (long)(val1*2 - tmp + 1) * tmp/2 * cnt;
                res += (long)(tmp - val1) * (cnt -1) * cnt /2;
                res -= (long)(cnt - 1)*cnt*(cnt+1)/6;
                // val1 * (B - A + 1 - tmp + i)
                res += (long)val1 * ((B - A + 1 - tmp) * 2 + cnt -1) * cnt/2;
            }
            return res;
        }

seg2

private static long Segment2(int A, int B, int C, int D, int b_0, int b_1)
        {
            if (b_1 >= C)
            {
                return 0;
            }
            return (long)(B-A+1)*(D-C+1)*(C-b_1);
        }
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain me the editorial of A. Let's take X=1000(⌊a11000⌋+1).... I didn't understand from this line. Where did it come from??