### DishonoredRighteous's blog

By DishonoredRighteous, history, 12 months ago,

Author's solution: 80407149

Author's solution: 80407200

Author's solution using formulas: 80407222

Author's solution using prefix sums: 80407239

Author's solution: 80407273

Author's solution: 80407303

Author's solution using ternary search: 80407326

Author's solution: 80407360

• +199

 » 12 months ago, # |   +37 Video Tutorial for CEnjoy watching!
•  » » 12 months ago, # ^ |   0 Thanks!!
•  » » 12 months ago, # ^ | ← Rev. 3 →   -22 Thanks stefdasca Please upload E also
•  » » » 12 months ago, # ^ |   0 you can use binary search : 80386041
•  » » 12 months ago, # ^ |   +16 Can you add subtitles. Unable to understand you.
•  » » » 12 months ago, # ^ |   0 possible you can use google translate
•  » » 12 months ago, # ^ |   +30 Why don't you make Tutorials of harder problems like F? I'm not saying that C was easy.
•  » » » 12 months ago, # ^ |   +31 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.
•  » » » » 12 months ago, # ^ |   -6 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.
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 12 months ago, # ^ |   +10 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. OtherwiseYou 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.
•  » » » » » 12 months ago, # ^ |   +2
•  » » » » » 12 months ago, # ^ |   +8 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
•  » » » » » » 12 months ago, # ^ |   -8 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.
•  » » » » » 12 months ago, # ^ |   0 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.
•  » » » » » » 12 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » » » 12 months ago, # ^ |   0 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.
•  » » » » » 12 months ago, # ^ | ← Rev. 2 →   0 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.
 » 12 months ago, # |   -12 Editorial so fast
•  » » 12 months ago, # ^ |   +112
•  » » » 12 months ago, # ^ |   0 Yep,it's how I feel.
•  » » » » 12 months ago, # ^ |   -49 same
•  » » » » 12 months ago, # ^ |   -27 downvote this also
•  » » » 12 months ago, # ^ |   0 what about A
•  » » » 9 months ago, # ^ |   0 It's amazing
•  » » 12 months ago, # ^ |   +8 Problem C detailed video explanation: Link
 » 12 months ago, # | ← Rev. 2 →   -14 So quick editorial! Thank you!
 » 12 months ago, # |   -62 I should have checked editorial during contest
•  » » 12 months ago, # ^ |   +64
 » 12 months ago, # |   -8 Did anyone use recursive DP on problem B, would that TLE?
•  » » 12 months ago, # ^ |   -26
•  » » » 12 months ago, # ^ |   0 can you explain this please?
•  » » » » 12 months ago, # ^ | ← Rev. 4 →   0 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 position4) 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)
•  » » 12 months ago, # ^ |   0 I did it and I don't understand why my solution get TLE https://codeforces.com/contest/1355/submission/80314876
•  » » » 12 months ago, # ^ |   -12 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!
•  » » » » 12 months ago, # ^ |   +3 You reset the whole dp array $T$ times, so the complexity will be $O(TN)$
•  » » » » 12 months ago, # ^ |   0 I think your problem is with your memset, you are assigning MAXN times -1 for every test case, that is O(n^2).
•  » » » 12 months ago, # ^ |   0 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
•  » » » 12 months ago, # ^ |   +1 same happened with me https://codeforces.com/contest/1355/submission/80344928 and now when i implemented it in c++ it got accepted, quite amazing
 » 12 months ago, # |   -27 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.
 » 12 months ago, # |   0 So fast Editorial!PS: the round is too hard for me. A isn't friendly to newbies.
•  » » 12 months ago, # ^ |   +53 Div2 isn't supposed to be friendly with newbies. That's why we have Div3's and now Div4.
•  » » » 12 months ago, # ^ |   0 frozen bro
•  » » 12 months ago, # ^ |   0 yes you are right
 » 12 months ago, # |   -11 The fastest editorial I've ever seen!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
•  » » 12 months ago, # ^ | ← Rev. 2 →   +102 C: "Non-degenerate triangles".CF users:
•  » » » 12 months ago, # ^ |   +8 CodeForces(×)MathForces(√)
 » 12 months ago, # |   -6 round was great execpt that D, found that too easy
•  » » 12 months ago, # ^ |   +4 DURING THE CONTEST WHEN YOU TRIED TO SOLVE TASK C VERY HARD BUT LATER SAW TASK D
•  » » 12 months ago, # ^ |   0 it's not a problem it can be some joke, thats trains you to read all problems
•  » » » 12 months ago, # ^ |   0 PS: i solved C first
•  » » » » 12 months ago, # ^ |   0 i'm not
 » 12 months ago, # |   +2 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?
•  » » 12 months ago, # ^ |   0 Yes.
•  » » » 12 months ago, # ^ |   +4 Can you prove it?
•  » » » » 12 months ago, # ^ |   +62 proof by ac.
•  » » » » » 12 months ago, # ^ |   0 could you please elaborate...?
•  » » » » 12 months ago, # ^ |   0 there can't be more than 2 minima, that will prove it I guess
•  » » » 12 months ago, # ^ |   0 I see passed solutions assume that. and uses the ternary search!can someone prove it? lohit_97 could you?
•  » » » » 12 months ago, # ^ |   +1 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.
•  » » » » » 12 months ago, # ^ |   +1 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.
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   +12 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.
•  » » » » » 12 months ago, # ^ |   +20 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
•  » » » » » » 12 months ago, # ^ |   0 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
•  » » » » » » 12 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » » » » » 12 months ago, # ^ |   0 Thanks so much <3
•  » » » » » » » 5 months ago, # ^ |   0 Rate of change in g′(x) is greater than rate of change of h′(x)How can we say this?
•  » » » » 12 months ago, # ^ |   +14 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$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. Case 2 : Suppose $AN−M(N−X_0) >= 0$, no matter the sign of $-RN+MX$ it will always make an unimodal function because the monotonicity of $-RN+MX$ and $AN−M(N−X)$.
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   -29 We can simply say that it is unimodal graph because in start as mentioned in editorial is P<=Q and X is near 0 So in starting -RN+MX is -RN so basically it is negative so graph will decrease and we know that that AN−M(N−X) & -RN+MX are monotically increasing and at last x=N, AN so slope changed from negative in start to positive in last and slope increasing function giving the shape of concave function.
 » 12 months ago, # |   +2 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.
•  » » 12 months ago, # ^ |   +2 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]$.
•  » » » 12 months ago, # ^ |   +3 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
•  » » 12 months ago, # ^ |   0 Could someone explain the mistake. thanks in advance
 » 12 months ago, # |   0 I almost thought about how to solve problem D！ Thank you for preparing this contest！
 » 12 months ago, # |   +20 One minute silence for those who wasted time on C instead of D
 » 12 months ago, # |   0 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
•  » » 12 months ago, # ^ |   0 i know first was hard to strike the mind
 » 12 months ago, # | ← Rev. 3 →   0 felt like one of the toughest div 2 contest ,more like div 1 contest. Test cases were really strong
•  » » 12 months ago, # ^ |   +11 Better to have strong test cases than get hacked afterwards
•  » » » 12 months ago, # ^ |   0 yeah ,that's right too.
•  » » » 12 months ago, # ^ |   +3 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?
 » 12 months ago, # |   +30 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
•  » » 12 months ago, # ^ |   0 When $X = 2^{29}$, your code will return $12$ but the answer is $30$ which is not correct. right?
•  » » » 12 months ago, # ^ |   +23 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.
•  » » 12 months ago, # ^ |   +8 Yes, we have solution that solves problem in 17 queries. But we make bound a bit bigger.
•  » » » 12 months ago, # ^ | ← Rev. 3 →   +13 I searched and I think I found $16$-query construction, that's it! Construction of 16 Queries999917266738362368 = 2^11 * 11^2 * 101 * 293 * 383 * 577 * 617 999988220452765909 = 29^2 * 211 * 239 * 283 * 367 * 379 * 599 999908326373204009 = 41 * 43 * 151 * 223 * 257 * 311 * 359 * 587 999940111774602057 = 3^7 * 109 * 127 * 307 * 419 * 433 * 593 999965058848838029 = 37 * 59 * 73 * 179 * 313 * 331 * 563 * 601 999836608922529251 = 31^2 * 149 * 157 * 401 * 421 * 463 * 569 999988688533604771 = 67 * 89 * 97 * 163 * 199 * 269 * 347 * 571 999857663600302163 = 191 * 271 * 281 * 439 * 467 * 547 * 613 999989807092188397 = 167 * 353 * 373 * 409 * 443 * 499 * 503 999997550573275589 = 53 * 79 * 83 * 139 * 241 * 389 * 461 * 479 999861104955508549 = 13^2 * 19^2 * 47 * 103 * 107 * 233 * 251 * 541 999939187144038125 = 5^4 * 137 * 173 * 457 * 509 * 521 * 557 999811893518395379 = 227 * 263 * 337 * 431 * 449 * 491 * 523 998273209131921967 = 17^2 * 61 * 71 * 113 * 131 * 317 * 349 * 487 546399719195948513 = 7^3 * 23^2 * 197 * 229 * 277 * 397 * 607 34933 = 181 * 193 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. Choose elements so that product will not exceed $10^{18}$. Do 1. for $100 \ 000$ times and get the choosing combination nearest to $10^{18}$. Then, erase the chosen values from the list. 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}$.
•  » » » » 12 months ago, # ^ |   +18 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.
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   0 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?
•  » » 12 months ago, # ^ |   +8 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*2Case 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.
•  » » » 12 months ago, # ^ |   +16 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$.
•  » » » » 12 months ago, # ^ |   0 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.
 » 12 months ago, # |   +9 So, fast editorial.
 » 12 months ago, # |   +33 D was easier to think than c.
•  » » 12 months ago, # ^ |   -16 hmm
 » 12 months ago, # |   +8 can anybody help in proving D second paragraph
•  » » 12 months ago, # ^ | ← Rev. 2 →   +4 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 2N
•  » » » 12 months ago, # ^ |   0 "[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
•  » » 12 months ago, # ^ | ← Rev. 3 →   +33 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$
•  » » » 12 months ago, # ^ |   0 Thanks!
•  » » » 12 months ago, # ^ |   0 Thanks!
•  » » » 5 months ago, # ^ |   0 Brilliant Proof
 » 12 months ago, # | ← Rev. 2 →   +75 I think these problems are much harder to prove than to solve. For A, and for D.
•  » » 12 months ago, # ^ |   0 i would say B and D.
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 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.
 » 12 months ago, # |   -18 I am curious if binary search would work in problem E? Spoiler#ifndef _GLIBCXX_NO_ASSERT #include #endif #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #if __cplusplus >= 201103L #include #include #include #include #include #include #include #include #endif // C++ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #if __cplusplus >= 201103L #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #endif #define ll long long #define vi vector #define loop(i,n) for(int i=0;i=0;i--) #define revloop1(i,n) for(int i=n;i>=1;i--) #define pb push_back #define mp make_pair #define pii pair #define vpii vector< pair > #define ff first #define ss second #define print(x) printf("%.9Lf\n",x) #define MOD 1000000007 #define MAX 100005 #define MAX6 1000005 #define MAX3 1005 #define nw cout< hh, h; ll cost(ll val){ h= hh; /// moving always benificial ll moves =0; ll lowers=0, highers=0; for(int i=0;ival){ highers+=(h[i]-val); } else{ lowers+=(val-h[i]); } } moves = min(lowers,highers); ll append=lowers-moves, rem=highers-moves; /// now subtract and add respective values of moves if(m cost(mid+1)){ low =mid+1; ans = cost(mid+1); } else{ return cost(mid); } } // printf("cost of %lld is %lld \n", mid, cost(mid)); return ans; } int main() { // int t;cin>>t; int t=1; int x,y,z; while(t--){ cin>>n>>a>>r>>m; for(int i=0;i>x; hh.pb(x); } sort(h.begin(), h.end()); cout<
•  » » 12 months ago, # ^ |   -11 it worked, awesome
•  » » » 12 months ago, # ^ |   +3 This is like ternary search(or gradient descent) only. You're moving in the direction of decreasing slope, hence it works.
•  » » 12 months ago, # ^ |   0 Can you explain your approach?
 » 12 months ago, # |   0 Thanks for the super fast editorial
 » 12 months ago, # | ← Rev. 2 →   0 Great problems(especially div2e) and nice editorial! Thanks!
 » 12 months ago, # |   0 The contest had really good problems. Also, I appreciate that the editorial is written in a very constructive way, explaining every detail.
 » 12 months ago, # |   0 Can somebody hack my C? Im not using dp or any pref sums. 80347181
•  » » 12 months ago, # ^ |   +3 There is a similar one with nicer code formatting. Can somebody explain how it works? Thanks!
•  » » » 12 months ago, # ^ |   0 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
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 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)
•  » » » 12 months ago, # ^ | ← Rev. 3 →   +1 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
 » 12 months ago, # | ← Rev. 2 →   -56 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. (-_-)
•  » » 12 months ago, # ^ |   +14 Yeah, it will be really great to increase the frequency of Div1 contests. I haven't participated any rated Div1 in about one month.
•  » » 12 months ago, # ^ |   +53 I'm NOT
 » 12 months ago, # |   +3 how to do c using prefix sum
•  » » 12 months ago, # ^ |   +1
 » 12 months ago, # | ← Rev. 2 →   0 For Problem B: I divided the groups on the basis of the group member exp levelLike for exp = 1, if I have 12 membersThen I made 12 new groupsthen for exp = 2, if I have 7 membersThen 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 thenthen actually I have now 8+ 1(remainder from previous exp = 2)So I can make 9/3 = 3 new groupsLike this I had 12 + 3 + 3 = 18 groupsActually 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); 
 » 12 months ago, # | ← Rev. 2 →   +3 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 26UPD: The cause seems to be input handling, people who used sys.stdin.readline() instead of input() passed.
•  » » 12 months ago, # ^ |   0 not really, c++ also TLE, though i think it is O(n) my submission
•  » » » 12 months ago, # ^ | ← Rev. 2 →   +4 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).
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   0 oh! amazing details. thank you. so in some cases memset is not as good as a simple loop XD
•  » » » » » 12 months ago, # ^ |   +3 It works fine but you have to set the size of the array dynamically instead of a fixed size array.
•  » » » » » » 12 months ago, # ^ |   0 i get it
•  » » 11 months ago, # ^ |   0 I am using stdin and stdout but still getting TLE Here. Can you pls help?
 » 12 months ago, # |   0 WAS A GOOD ROUND AND I THINK C , D SHOULD BE CHANGED
 » 12 months ago, # |   -9 D was easier than c. Problem A ~ Problem B.
•  » » 12 months ago, # ^ |   0 yeahh... we all know that dude
 » 12 months ago, # |   +14 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.
•  » » 12 months ago, # ^ |   0 I also didn't waste time in proving. Just run the cost function from 1 to 100 for various arrays.
•  » » » 12 months ago, # ^ |   0 Sounds cool!
 » 12 months ago, # |   +18 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.
•  » » 12 months ago, # ^ |   +4 could you explain proof ?
•  » » » 12 months ago, # ^ | ← Rev. 2 →   -8 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.
•  » » » » 12 months ago, # ^ |   +11 Do you know what a proof means?
•  » » » » » 12 months ago, # ^ |   0 i should say it is just an observation.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   +1 My strategy to solve D during the contest : strategyPS: unable to come up with a convincing proof right now, will try to understand author solution.
 » 12 months ago, # |   0 Good editorial. Delicate + sort. Thanks
 » 12 months ago, # |   +6 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?
•  » » 12 months ago, # ^ |   +34 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.
•  » » 12 months ago, # ^ |   +33 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.
•  » » » 12 months ago, # ^ |   +3 Thanks for detailed explanation! It helped.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   +5 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 :)
•  » » » 12 months ago, # ^ |   0 Your explanation is awesome.Thanks for it.
•  » » » 12 months ago, # ^ |   0 This was a great help! Shouldn't explanations like these be in the editorial in the first place?
•  » » » 12 months ago, # ^ |   0 Amazaing explanation friend, extremely grateful
•  » » » 12 months ago, # ^ |   0 i think i learn more from comments than tutorials
 » 12 months ago, # |   +4 I got a Wrong Answer on System Testing in D. Div3, here I come :).
 » 12 months ago, # |   +2 Can anyone explain the solution to Problem-C? Please. Thanks in advance
•  » » 12 months ago, # ^ |   0
•  » » » 12 months ago, # ^ |   0 It was really helpful. Thank you and keep helping others :)
•  » » 12 months ago, # ^ |   0
•  » » » 12 months ago, # ^ |   0 It was really helpful. Great explanation. Thank you and keep helping others :)
 » 12 months ago, # |   0 For Problem A,I couldn't code for next 1:40 minutesAnd 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 mindthen after I solved B and D. I read the lines of A againIt 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!!
•  » » 12 months ago, # ^ |   +3 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!!
•  » » » 12 months ago, # ^ |   -10 pupil
•  » » 12 months ago, # ^ |   +20 When I read problem A, I looked at contest name if it was div1 contest!
•  » » » 12 months ago, # ^ |   0 Hahahaha!
 » 12 months ago, # |   0 https://codeforces.com/contest/1355/submission/80344928My solution for problem B got accepted in running contest but showing TLE after system testing I solved it in O(n) Can anyone help?
 » 12 months ago, # |   0 Could anyone point out my mistake. My submission 80378908. I'm getting TLE
•  » » 12 months ago, # ^ |   0 Read about time complexity. Your code is O(K) and K can go upto 10^18. Hence this TLEs.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 But as given in tutorial it should not take more than some 60 moves right when we condition on 0
•  » » » » 12 months ago, # ^ | ← Rev. 3 →   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.
•  » » » » 12 months ago, # ^ |   +1 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.
•  » » » » » 12 months ago, # ^ |   +3 Lol thanks bro . The mistake was the int cast should be for the whole thing not for only n. Thanks again
 » 12 months ago, # |   0 Please explain C sulution with exactly one cycle.
•  » » 12 months ago, # ^ |   0
•  » » 12 months ago, # ^ |   0 Not sure what specific kind of solution you mean, but the implementation of this approach can be done in one loop.
•  » » » 12 months ago, # ^ |   0 I find this one, and can't get math proof of this submission: 80328178
 » 12 months ago, # |   +16 I solved problem Div2E in $O(10^9)$ time, because I check each possible height. It works in 421 ms.Submission
•  » » 12 months ago, # ^ |   0 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.
•  » » » 12 months ago, # ^ | ← Rev. 3 →   +10 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.
 » 12 months ago, # |   +9 Problem E: Can anyone please explain why the additional breaking point (i.e the point where P>Q changes to P
•  » » 12 months ago, # ^ | ← Rev. 3 →   +20 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$
•  » » » 12 months ago, # ^ |   0 Thank you a lot for reply. Was really helpful.
 » 12 months ago, # |   0 Is there any other more intuitive way for proving for the case S<2*N in D?
•  » » 12 months ago, # ^ |   0 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
•  » » » 12 months ago, # ^ |   +8 it does not prove anything.
•  » » » 12 months ago, # ^ |   +1 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.
 » 12 months ago, # |   +7 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.
•  » » 12 months ago, # ^ |   0 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$
•  » » 12 months ago, # ^ |   0 can you elaborate more it seem really interesting
•  » » 12 months ago, # ^ |   +13 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:)
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 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 with X>=B-A+1 or X=C-B+1 & X>=B-A+1, so aren't you double subtracting somehow.
•  » » 12 months ago, # ^ |   0 Yeah thanks. Can you please explain a bit more how you applied P&C here to get the solutions? It'd be really grateful!
 » 12 months ago, # |   0 How to solve B using dp?
 » 12 months ago, # |   +1 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 :)
•  » » 12 months ago, # ^ | ← Rev. 3 →   0 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
 » 12 months ago, # | ← Rev. 2 →   0 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
•  » » 12 months ago, # ^ |   +1 Just replace input() with sys.stdin.readline() (import sys before obviously). Input() is too slow, need to read number(s) faster.
•  » » » 12 months ago, # ^ |   0 Thnx
•  » » 12 months ago, # ^ |   0 Same concept in C++ will be an AC
 » 12 months ago, # |   0 Wish we could get editorials so fast after every rounds :)
 » 12 months ago, # | ← Rev. 3 →   +6 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
•  » » 12 months ago, # ^ |   0 actually it's kind of optimized ternary search.link
 » 12 months ago, # |   +6 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.
 » 12 months ago, # | ← Rev. 3 →   0
 » 12 months ago, # |   0 A well explained editorial....
»
12 months ago, # |
-22

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

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

}

•  » » 12 months ago, # ^ |   +1 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)
 » 12 months ago, # |   0 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.
 » 12 months ago, # |   0 Can anyone help me with the editorial of Div2 B ??
•  » » 12 months ago, # ^ |   0 what exactly you dont understand. look at someone's solution first maybe that will help
 » 12 months ago, # |   0 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/XP6ZzDuiThanks in advance
 » 12 months ago, # |   0 Dynamic Programming approach for div2 B, Easy to understand https://codeforces.com/contest/1355/submission/80387357
 » 12 months ago, # |   0 does anyone passed B with python? thanks!
•  » » 12 months ago, # ^ |   0 With pypy.80386366. Fast IO. Got TLE in contest submission on system tests but hen used Fast IO and AC.
 » 12 months ago, # |   +1
 » 12 months ago, # | ← Rev. 2 →   0 in problem A I don't know why I am getting TLE .can someone help please. https://codeforces.com/contest/1355/submission/80388504
•  » » 12 months ago, # ^ |   0 Probably the b.sort()
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » 12 months ago, # ^ |   0 thankx bro
 » 12 months ago, # |   0 I am not able to understand the proof of D.
•  » » 12 months ago, # ^ |   -8
•  » » 12 months ago, # ^ |   0
 » 12 months ago, # |   0 Can someone simplify the proof for solution D? The editorial is hard to understand :/
•  » » 12 months ago, # ^ |   0 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. 
•  » » » 12 months ago, # ^ |   0 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.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 that's not how problem should be proved . what if i chose 1 2 1 2 1 2 ... or 1 3 1 2 1 ...
•  » » » » 12 months ago, # ^ |   0 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. 
•  » » 12 months ago, # ^ |   0 It is not a different proof but I have just expanded the explanation of editorial: https://codeforces.com/blog/entry/77491?#comment-624253
 » 12 months ago, # |   +4 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.
•  » » 12 months ago, # ^ |   0 Yeah, I also want to solve such questions. Please someone suggest.
 » 12 months ago, # | ← Rev. 5 →   +7 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. typedef long long ll; typedef vector 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; } 
•  » » 12 months ago, # ^ |   +6 In this whole calculation use of both the arrays can be removed also(refer code). #include 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
•  » » » 12 months ago, # ^ |   0 Nice
•  » » » 12 months ago, # ^ |   0 Nice! I knew C was gonna be a one liner. Just needed more time.
•  » » 12 months ago, # ^ |   0 Can you explain me this expression: g = min(g + 1, min(i — (a + b) + 1, min(b — a + 1, c — b + 1)));
•  » » » 12 months ago, # ^ | ← Rev. 3 →   0 Let's assume a = 5, b = 6, c = 9, d = 15The 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.
 » 12 months ago, # |   0 thanks!
 » 12 months ago, # |   0 Can anyone tell why I'm getting memory limit exceeded in problem A.https://code.sololearn.com/cK5Ie6MoP594/#cpp
•  » » 12 months ago, # ^ |   0 The value of k is so high. So a[k+1] is beyond of memory limit.
•  » » » 12 months ago, # ^ |   0 Okay Got it! Thankyou.
 » 12 months ago, # |   -13 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 :( )
•  » » 12 months ago, # ^ |   0 You might want to read this
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 I just have read it. It's fine 'cuz I wasn't demoted to Spec. :))
 » 12 months ago, # |   0 I did this solution for B using PyPy 3: https://codeforces.com/contest/1355/submission/80386227it 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/80387439What is my mistake...
•  » » 12 months ago, # ^ |   0 Bro same with me. I used Fast IO after contest and then passed.
 » 12 months ago, # |   +111 )
 » 12 months ago, # |   0 Thank you for lightening fast editorial :)
 » 12 months ago, # |   +12 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.
 » 12 months ago, # |   0 can someone explain where i am wrong in ques c? solution: https://codeforces.com/contest/1355/submission/80358781
 » 12 months ago, # |   +24 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.
•  » » 12 months ago, # ^ |   0 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.
•  » » 11 months ago, # ^ |   0 Very clear explanation, thanks a lot.
 » 12 months ago, # |   0 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
 » 12 months ago, # |   0 After seeing the prefix sums solution of problem C, I feel, it wasn't that difficult.
•  » » 12 months ago, # ^ |   +3 plz share any submission by that method
•  » » » 12 months ago, # ^ |   0
 » 12 months ago, # |   0 Those who solved D during the contest, what was your thought process? How did you guys arrive at conclusion stated in editorial?
•  » » 12 months ago, # ^ |   +12 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.
•  » » » 12 months ago, # ^ |   +8 Wow, this brings so much clarity to me on how to think. Thanks!
 » 12 months ago, # |   +2 Can anyone please explain the problem C using offline range update
 » 12 months ago, # |   +1 nice problem and ideas but i think div.2 A must be easier.
 » 12 months ago, # |   0 can someone explain me why in problem A author has taken this X=1000(⌊a1/1000⌋+1) and whats its use??
•  » » 12 months ago, # ^ |   +3 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.
 » 12 months ago, # |   0 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.
 » 12 months ago, # | ← Rev. 4 →   0 Why aren't setter's and tester's solution link provided in editorial ? DishonoredRighteousI need the implementation of problem C's editorial to understand it better.
•  » » 12 months ago, # ^ |   0 I added links to authors' solutions to editorial.
•  » » » 12 months ago, # ^ | ← Rev. 3 →   0 Thank you very much, but on clicking it shows "you are not allowed to view the requested page". can you please fix it DishonoredRighteous ?
•  » » » » 12 months ago, # ^ |   0 Looks like I fixed it
 » 12 months ago, # |   0 Auto comment: topic has been updated by DishonoredRighteous (previous revision, new revision, compare).
 » 12 months ago, # |   0 am i the only one not able to see the authors solution for problems ?
•  » » 12 months ago, # ^ |   0 Looks like I fixed it
 » 12 months ago, # |   0 Auto comment: topic has been updated by DishonoredRighteous (previous revision, new revision, compare).
 » 12 months ago, # |   0
 » 12 months ago, # |   0 I get 'you are not allowed to view requested page' when clicking on authors solutions. How to fix this?
•  » » 12 months ago, # ^ |   0 Looks like I fixed it
•  » » » 12 months ago, # ^ |   0 Nice problems dude , C was specially good.
 » 12 months ago, # |   +11 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) ).
•  » » 12 months ago, # ^ |   0 Thanks for the explanation.
•  » » 12 months ago, # ^ |   0 Thanks for the awesome explanation!
 » 12 months ago, # |   +4 After seeing editorial for Problem A. I think, I was better off with no editorial.
 » 12 months ago, # |   0 Can anyone explain B more clearly ?
•  » » 12 months ago, # ^ |   0 simple- 1.> just sort the array and create groups2.> consider 3 3 4 7 7 7 73.> 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 on5.> 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
•  » » » 12 months ago, # ^ |   0 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
•  » » » 12 months ago, # ^ |   0 I got it! Thanks a lot.
 » 12 months ago, # |   0 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)
•  » » 12 months ago, # ^ |   0 2nd line of the question: "At the beginning of the game Petya has to come up with an array of N positive integers".
•  » » » 12 months ago, # ^ |   0 so positive integers mean no 0 ok got it
 » 12 months ago, # |   0 Hi DishonoredRighteous. Could you explain why you use X=1000(⌊a1/1000⌋+1) in Problem A demonstration ? Thanks
•  » » 12 months ago, # ^ |   0 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.
 » 12 months ago, # |   0 Can anyone please help me proving 80418234's intuition of B? It feels too difficult to me..
 » 12 months ago, # |   +13 The prefix-sum approach for solving div2c is amongst the most beautiful and elegant things ive even seen
•  » » 12 months ago, # ^ |   0 Hi, I am not able to understand the approach, can you help ?
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 12 months ago, # ^ |   0 thanks mate.
 » 12 months ago, # |   +1 I can't understand the proof of s < 2n in the second paragraph？Can someone explain it？
 » 12 months ago, # |   0 can anyone please explain the proof in more details of why if S<2N petya will lose
 » 12 months ago, # |   0 Anyone got the output for First Question using java, for some reason I am getting timeout.
•  » » 12 months ago, # ^ |   0 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.
•  » » » 12 months ago, # ^ |   0 how can we do that? did u found a way to do that?
•  » » » » 12 months ago, # ^ |   0 If you cant solve it you are expected to read the editorial.
 » 12 months ago, # |   +1 Can C solve in O(1)?
 » 12 months ago, # |   0 C solution with fft: 80351725.
 » 12 months ago, # |   0 In A question this constrain is too large 10^16 & 10^ 18 how it able to pass in 0(n)
•  » » 12 months ago, <