DishonoredRighteous's blog

By DishonoredRighteous, history, 5 months 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

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

»
5 months ago, # |
  Vote: I like it +37 Vote: I do not like it

Video Tutorial for C

Enjoy watching!

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks!!

  • »
    »
    5 months ago, # ^ |
    Rev. 3   Vote: I like it -22 Vote: I do not like it

    Thanks stefdasca Please upload E also

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

    Can you add subtitles. Unable to understand you.

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it -6 Vote: I do not like it

        Please try once to make solution of harder problems like F if you will not get attention then next time leave it. Thanks for your other solutions.

      • »
        »
        »
        »
        5 months 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.

      • »
        »
        »
        »
        5 months 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.

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

        • »
          »
          »
          »
          »
          5 months 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

          • »
            »
            »
            »
            »
            »
            5 months ago, # ^ |
              Vote: I like it -8 Vote: I do not like it

            No, I want you to upload Div2C because it helps many people but you are only saying that you don't have time.

            I just wanted you to upload Div1C/D because 'YOU CAN' but as you say you are not confident I am waiting for you to become confidentbeacause there is no one else who is doing this.

            It is very much obvious that response would not be same for F as that of C but that helps a lot bro even though it is to a much smaller audience and also I assumed you are not following statement 1..

            Over and Out from my side.

        • »
          »
          »
          »
          »
          5 months 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.

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

            Maybe I should work on my tone If this reminds you something if not open it.

            You are wrong in saying that 'i dont need this' beacuse I wouldn't waste my so much time just replying if i didn't wanted but it may had sounded as you said. Also, i dont ask questions like "Why don't you make Tutorials of harder problems like F?" rather say it straight forward which many of the times piches the reader.

            Colour Biasing is the truth so comes the blind voting. Also, colour coundn't gurantee Credibility of thoughts.

            People who voted here also downvoted there because here I explained it, instead if I would have written only two lines here, I am damn sure of being negative.

            Though I agree with you(aryanc403) on few points.

            Lastly I know I am not good in writing especially creative writing,

            I know my tone, I like it and wouldn't change it either.

      • »
        »
        »
        »
        5 months 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.

        • »
          »
          »
          »
          »
          5 months 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.

»
5 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Editorial so fast

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

So quick editorial! Thank you!

»
5 months ago, # |
  Vote: I like it -62 Vote: I do not like it

I should have checked editorial during contest

»
5 months ago, # |
  Vote: I like it -8 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it -27 Vote: I do not like it

Damn it! I should've tried D. Spent a good one hour trying to come up with O(N) for C and failed in that too. Last 5 mins, I just tried sending in O(N^2) trying my luck (lol) after my O(N) failed on test 5 :( Have no clue about E and didn't read F.

Great problems and round! Looking forward to more contests by you guys. C was my favourite problem and editorial solution is simply great.

»
5 months 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.

»
5 months ago, # |
  Vote: I like it -11 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it -6 Vote: I do not like it

round was great execpt that D, found that too easy

»
5 months 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?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes.

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

      Can you prove it?

    • »
      »
      »
      5 months 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?

      • »
        »
        »
        »
        5 months 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.

        • »
          »
          »
          »
          »
          5 months 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.

      • »
        »
        »
        »
        5 months 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.

        • »
          »
          »
          »
          »
          5 months 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

          • »
            »
            »
            »
            »
            »
            5 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            i think this might work but not sure. for a height of x let g(x) be bricks to be removed f(x) bricks need to be added and a(x) the total cost is Af(x)+Rg(x) let T the total number of bricks first so we can relate f and g. T-g(x)+f(x)=nx where n is the number of pillars. then we get a(x)=A*n*x-A*T +g(x)*(A+R). intially when x increase by one the decrease in g(x) is n*1 but as x increase some pillars become shorter than x and no longer contribute to decrease in g(x). so we see that as x increases g'(x) decreases a'(x)=An- g'(x)(A+R).intially this is negative as g'(x) is n or n-1.as x increases the second term is lesser thus a'(x) turns around and starts increasing thus there is minimum somewhere in between

          • »
            »
            »
            »
            »
            »
            5 months ago, # ^ |
              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

      • »
        »
        »
        »
        5 months 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)$$$.
»
5 months 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.

  • »
    »
    5 months 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]$$$.

    • »
      »
      »
      5 months 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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could someone explain the mistake. thanks in advance

»
5 months 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!

»
5 months 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

»
5 months 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

»
5 months 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

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

    Better to have strong test cases than get hacked afterwards

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah ,that's right too.

    • »
      »
      »
      5 months 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?

»
5 months 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
  • »
    »
    5 months 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?

    • »
      »
      »
      5 months 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.

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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}$$$.
      • »
        »
        »
        »
        5 months 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.

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

        Hey square1001 Can you elaborate more on your algorithm for finding partition. Your code for problem F was concise and clean, just please write comments there and please share code for finding the partition also?

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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$$$.

      • »
        »
        »
        »
        5 months 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.

»
5 months ago, # |
  Vote: I like it +9 Vote: I do not like it

So, fast editorial.

»
5 months ago, # |
  Vote: I like it +33 Vote: I do not like it

D was easier to think than c.

»
5 months ago, # |
  Vote: I like it +8 Vote: I do not like it

can anybody help in proving D second paragraph

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      "[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"

      here if I'm not wrong Mn is equal to S. Right ? So Mn+(2k-1)S=2kS which is out of range ([0,..,2*K*S-1]), so no of elements should be 2*K*N-1

  • »
    »
    5 months 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$$$

»
5 months 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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i would say B and D.

  • »
    »
    5 months 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.

»
5 months ago, # |
  Vote: I like it -18 Vote: I do not like it

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

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

    it worked, awesome

    • »
      »
      »
      5 months 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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain your approach?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the super fast editorial

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

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The contest had really good problems. Also, I appreciate that the editorial is written in a very constructive way, explaining every detail.

»
5 months 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

  • »
    »
    5 months 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!

    • »
      »
      »
      5 months 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

    • »
      »
      »
      5 months 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)

    • »
      »
      »
      5 months 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

»
5 months 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. (-_-)

  • »
    »
    5 months 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.

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

    I'm NOT

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

how to do c using prefix sum

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

For Problem B: I divided the groups on the basis of the group member exp level

Like for exp = 1, if I have 12 members

Then I made 12 new groups

then for exp = 2, if I have 7 members

Then I made 3 new groups (all having people of exp=2) and kept the count of person left i.e. 1 stored in rem (remainder), as he/she can be part of any group that has size greater that 2.

then for exp = 3, if I have 8 members then

then actually I have now 8+ 1(remainder from previous exp = 2)

So I can make 9/3 = 3 new groups

Like this I had 12 + 3 + 3 = 18 groups

Actually a member of exp = e can also go with more than e members. Thats what I have tried to accumulate the remainder member in group size greater than his e.

input (n);
int count[n+1]; // initally set to 0
for(int i =0; i < n; i ++){
        int temp;
        cin >> temp;
        count[temp]++;
}
		
ll int ans = 0;
ll int rem = 0;
for(int i = 1; i < n+1; i++){
	rem += count[i]%i;
	ans += count[i]/i;
	if(rem >= i){
	        ans += rem/i;
		rem = rem%i;
	}
}
		
out(ans);
»
5 months 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.

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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).

      • »
        »
        »
        »
        5 months 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

        • »
          »
          »
          »
          »
          5 months 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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am using stdin and stdout but still getting TLE Here. Can you pls help?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it -9 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeahh... we all know that dude

»
5 months 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.

  • »
    »
    5 months 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.

»
5 months 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.

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

    could you explain proof ?

    • »
      »
      »
      5 months 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.

    • »
      »
      »
      5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good editorial. Delicate + sort. Thanks

»
5 months 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?

  • »
    »
    5 months 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.

  • »
    »
    5 months 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.

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

      Thanks for detailed explanation! It helped.

    • »
      »
      »
      5 months 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 :)

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Your explanation is awesome.Thanks for it.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This was a great help! Shouldn't explanations like these be in the editorial in the first place?

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Amazaing explanation friend, extremely grateful

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i think i learn more from comments than tutorials

»
5 months 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 :).

»
5 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
5 months 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!!

  • »
    »
    5 months 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!!

  • »
    »
    5 months 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!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1355/submission/80344928
My solution for problem B got accepted in running contest but showing TLE after system testing I solved it in O(n) Can anyone help?

»
5 months 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

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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

      • »
        »
        »
        »
        5 months 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.

      • »
        »
        »
        »
        5 months 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.

        • »
          »
          »
          »
          »
          5 months 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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please explain C sulution with exactly one cycle.

»
5 months 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

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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.

»
5 months 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?

  • »
    »
    5 months 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$$$

»
5 months 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?

  • »
    »
    5 months 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

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

      it does not prove anything.

    • »
      »
      »
      5 months 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.

»
5 months 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.

  • »
    »
    5 months 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$$$

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you elaborate more it seem really interesting

  • »
    »
    5 months 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:)

    • »
      »
      »
      5 months 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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah thanks. Can you please explain a bit more how you applied P&C here to get the solutions? It'd be really grateful!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B using dp?

»
5 months 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 :)

»
5 months 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

  • »
    »
    5 months 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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same concept in C++ will be an AC

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wish we could get editorials so fast after every rounds :)

»
5 months 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

»
5 months 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.

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A well explained editorial....

»
5 months 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"; }

}

»
5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months 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

»
5 months 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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Dynamic Programming approach for div2 B, Easy to understand https://codeforces.com/contest/1355/submission/80387357

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

does anyone passed B with python? thanks!

  • »
    »
    5 months 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.

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

in problem A I don't know why I am getting TLE .can someone help please. https://codeforces.com/contest/1355/submission/80388504

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Probably the b.sort()

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    import sys
    
    for _ in range(int(sys.stdin.readline())): 
        a,k=map(int,sys.stdin.readline().split()) 
        p=a 
        b=list(str(a)) 
        i=0 
        while i<k-1 : 
            if (min(b))=="0": 
                break 
            else: 
                p+= int(min(b))*int(max(b)) 
                a=p 
                b=list(str(p)) 
            
            i+=1 
        
        print(p)
    
    

    Works now..

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not able to understand the proof of D.

»
5 months 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 :/

  • »
    »
    5 months 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.
    
    • »
      »
      »
      5 months 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.

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

      that's not how problem should be proved . what if i chose 1 2 1 2 1 2 ... or 1 3 1 2 1 ...

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I think this will make all possible sums from different Subarrays. Like,
        - 3 4
        - 1 2 1 will be our array as per your algo. 
        - so index 1 will make 1, 2 will make 2 , 1 and 2 will make 3 and 1 to 3 will make 4.
        - So this algorithm could be used to make all possible sums Subarray, not for our question. 
        

        `

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is not a different proof but I have just expanded the explanation of editorial: https://codeforces.com/blog/entry/77491?#comment-624253

»
5 months 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.

»
5 months 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;
}
  • »
    »
    5 months 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';
    }
    
  • »
    »
    5 months 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)));

    • »
      »
      »
      5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks!

»
5 months 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

»
5 months 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 :( )

»
5 months 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...

  • »
    »
    5 months 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.

»
5 months ago, # |
  Vote: I like it +111 Vote: I do not like it

 )

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for lightening fast editorial :)

»
5 months 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.

»
5 months 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

»
5 months 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.
  • »
    »
    5 months 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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Very clear explanation, thanks a lot.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

spent 1 hour on C question, during contest(although failed during contest because of a very silly mistake) I came up with the approach, I thought i should share it. https://hatebin.com/obojhmbwps

»
5 months 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.

»
5 months 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?

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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!

»
5 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Can anyone please explain the problem C using offline range update

»
5 months 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.

»
5 months 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??

  • »
    »
    5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

check out this solution for problem B. I think this is very easy to understand. solution code sort the array , loop through the elements — for every element ele check if a group can be made with previous ele elements. add groups before this element + 1.

»
5 months 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.

»
5 months 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).

»
5 months 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 ?

»
5 months 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).

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

»
5 months 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?

»
5 months 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) ).

»
5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain B more clearly ?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    simple- 1.> just sort the array and create groups

    2.> consider 3 3 4 7 7 7 7

    3.> you got 3, then record number of elements in a particular group by adding 1 to it if the current number don't match the number you are on(for eg you are on 3 currently but the number of elements are 1, if they were 3 we would make a group and reset number of elements to 1)

    4.> Then goto next position again 3 and you add 1 to current number(which is now 2) and you goto 4 and as this is still not equal to current number, you increment current number by 1(say curr) and then 7, and so on

    5.> when you arrive at last 7, you got curr=7 and number you are on is also 7 so you increase the number of groups(say num) by 1 and reset curr to 1 and go to next position

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I tried to use binary search looking for the smallest team possible for each explorer. Any idea why I would get a WA?

      My submission: 80421110

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I got it! Thanks a lot.

»
5 months 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)

  • »
    »
    5 months 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".

»
5 months 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

  • »
    »
    5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please help me proving 80418234's intuition of B? It feels too difficult to me..

»
5 months 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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 months 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.

»
5 months 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?

»
5 months 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

»
5 months 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.

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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?

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can C solve in O(1)?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C solution with fft: 80351725.

»
5 months 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)

  • »
    »
    5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I request you to present tutorials in points and step by step approach to solve the problem. It would help a lot to noobs like me. Sometimes it happens that i don't get the tutorials properly. Thank You for your efforts.......

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I got TLE on test 26 in question b then submitted similar approach solution in c++ .it passed all the tests in 93 ms..blown away

»
5 months ago, # |