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

Video Tutorial for C

Enjoy watching!

Thanks!!

Thanks stefdasca Please upload E also

you can use binary search : 80386041

Can you add subtitles. Unable to understand you.

possible you can use google translate

Why don't you make Tutorials of harder problems like F?

I'm not saying that C was easy.

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.

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.

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.

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:

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

For helping the coding community

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.

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

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 confident`

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

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.

`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 guranteeCredibility 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.

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

Editorial so fast

Yep,it's how I feel.

same

downvote this also

what about A

It's amazing

Problem C detailed video explanation: Link

So quick editorial! Thank you!

I should have checked editorial during contest

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

me https://codeforces.com/contest/1355/submission/80328002

can you explain this please?

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)

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

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!

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

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

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

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

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.

So fast Editorial!

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

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

frozen bro

yes you are right

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

C: "Non-degenerate triangles".

CF users:

CodeForces(×)

MathForces(√)

round was great execpt that D, found that too easy

DURING THE CONTEST WHEN YOU TRIED TO SOLVE TASK C VERY HARD BUT LATER SAW TASK D

it's not a problem it can be some joke, thats trains you to read all problems

PS: i solved C first

i'm not

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?

Yes.

Can you prove it?

proof by ac.

could you please elaborate...?

there can't be more than 2 minima, that will prove it I guess

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

can someone prove it?

lohit_97 could you?

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.

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.

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.Could I ask some stupid questions ^^ ?

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

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

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

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 caseThanks so much <3

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

How can we say this?

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.

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$$$AN−M(N−X_0) < 0 \Rightarrow MX_0 < MN - AN \Rightarrow -RN+MX_0 < N(M - (A + R)) \le 0$$$. (Because $$$M = min(M, A + R)$$$) $$$\Rightarrow -RN + MX_0 < 0$$$

With $$$H < H_0 \Rightarrow X < X_0 \Rightarrow -RN + MX < -RN + MX_0 < 0$$$. And we know that $$$H$$$ increases $$$\Rightarrow -RN + MX$$$ increases (but still $$$<0$$$) which will complete our remaining of an unimodal function.

We can simply say that it is unimodal graph because in start as mentioned in editorial is

P<=QandX is near 0So in starting-RN+MXis-RNso basically it is negative so graph will decrease and we know that thatAN−M(N−X)&-RN+MXare monotically increasing and at last x=N,ANso slope changed from negative in start to positive in last and slope increasing function giving the shape of concave function.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.

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

Uselessis 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 rectangleCould someone explain the mistake. thanks in advance

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

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

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

i know first was hard to strike the mind

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

Better to have strong test cases than get hacked afterwards

yeah ,that's right too.

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?

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 Queries19634730635520000, 67665248476907597, 877779077635511999, 15031861979012587, 239868713978954299, 8100049778130103, 32826117705688133, 96265407405451883, 260006624961107813, 707992818804600227, 3676594834162829, 6402204344683229, 9797084445859807, 15916020492768661, 27616086651273059, 41286304414422503, 229580147

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

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.

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

I searched and I think I found

$$$16$$$-query construction, that's it!Construction of 16 QueriesWe 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.

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

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?

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.

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

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.

So, fast editorial.

D was easier to think than c.

hmm

can anybody help in proving D second paragraph

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.

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

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

Thanks!

Thanks!

Brilliant Proof

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

i would say B and D.

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.

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

Spoilerit worked, awesome

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

Can you explain your approach?

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

Thanks for the super fast editorial

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

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

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

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

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

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)

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

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

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

I'm NOT

how to do c using prefix sum

Explanation of prefix sum approach

Alternative approach

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.

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.

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

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

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

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

i get it

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

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

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

yeahh... we all know that dude

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.

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

Sounds cool!

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.

could you explain proof ?

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.

Do you know what a proof means?

i should say it is just an observation.

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.

Good editorial. Delicate + sort. Thanks

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?

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.

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.

Thanks for detailed explanation! It helped.

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

Your explanation is awesome.Thanks for it.

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

Amazaing explanation friend, extremely grateful

i think i learn more from comments than tutorials

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

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

My Explanation

It was really helpful. Thank you and keep helping others :)

Explanation of prefix sum approach

Alternative approach

It was really helpful. Great explanation. Thank you and keep helping others :)

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!!

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!!

pupil

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

Hahahaha!

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?

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

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

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

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.

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.Lol thanks bro . The mistake was the int cast should be for the whole thing not for only n. Thanks again

Please explain C sulution with exactly one cycle.

My Explanation

Not sure what specific kind of solution you mean, but the implementation of this approach can be done in one loop.

I find this one, and can't get math proof of this submission: 80328178

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

`421 ms`

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

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.

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?

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

Thank you a lot for reply. Was really helpful.

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

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

it does not prove anything.

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.

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

can you elaborate more it seem really interesting

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

a. So to reduce our inequality to get an equation like above, we need to get rid of the_{1}+ a_{2}+ ... + a_{r}= n`<=`

symbol by adding a dummy variable`d`

. Now we have the equation`x + y + d = z`

. But there is still a problem. Variablesxandycan not be non-negative. To achieve this, we replacexwithX + AandywithY + 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 ofXandY) 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 replaceXwith(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 forY. 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:)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.

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

How to solve B using dp?

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

I checked for n-1+1 and s-(n-1+1) in the array from back side.If it exists then answer is NO else yes my ac solution 80355528

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

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

Thnx

Same concept in C++ will be an AC

Wish we could get editorials so fast after every rounds :)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

actually it's kind of optimized ternary search.link

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.

A well explained editorial....

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"; }

}

the logic is wrong. let say for some i i+1>=arr[i] so you included that in answer but sometimes the optimal and doesn't have that you have to consider both cases and take optimal one so it is a DP question. (can look at my solution https://codeforces.com/contest/1355/submission/80328002)

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.

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

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

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

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

does anyone passed B with python? thanks!

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

Video editorial for A and B

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

Probably the b.sort()

Works now..

thankx bro

I am not able to understand the proof of D.

https://codeforces.com/blog/entry/77491?#comment-623783

https://codeforces.com/blog/entry/77491?#comment-624253

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

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.

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

`

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

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.

Yeah, I also want to solve such questions. Please someone suggest.

Short and Simple Solution for Problem 1355 C. Count TrianglesThe 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.

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

Nice

Nice! I knew C was gonna be a one liner. Just needed more time.

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

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 1It 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 2The 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.

thanks!

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

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

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

Okay Got it! Thankyou.

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

You might want to read this

I just have read it. It's fine 'cuz I wasn't demoted to Spec. :))

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

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

)

Thank you for lightening fast editorial :)

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.

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

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:

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.

Very clear explanation, thanks a lot.

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

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

plz share any submission by that method

80395925

Those who solved D during the contest, what was your thought process?

How did you guys arrive at conclusion stated in editorial?

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.

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

Thanks!

Can anyone please explain the problem C using offline range update

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

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

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.

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.

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.

I added links to authors' solutions to editorial.

Thank you very much, but on clicking it shows "you are not allowed to view the requested page". can you please fix it DishonoredRighteous ?

Looks like I fixed it

Auto comment: topic has been updated by DishonoredRighteous (previous revision, new revision, compare).am i the only one not able to see the authors solution for problems ?

Looks like I fixed it

Auto comment: topic has been updated by DishonoredRighteous (previous revision, new revision, compare).I get 'you are not allowed to view requested page' when clicking on authors solutions. How to fix this?

Looks like I fixed it

Nice problems dude , C was specially good.

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

Thanks for the explanation.

Thanks for the awesome explanation!

After seeing editorial for Problem A.

I think, I was better off with no editorial.Can anyone explain B more clearly ?

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

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

I got it! Thanks a lot.

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)

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

so positive integers mean no 0 ok got it

Hi DishonoredRighteous. Could you explain why you use

`X=1000(⌊a1/1000⌋+1)`

in Problem A demonstration ? ThanksIt'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.

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

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

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

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:

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.

thanks mate.

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

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

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

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.

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

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

Can C solve in O(1)?

C solution with fft: 80351725.

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