### djm03178's blog

By djm03178, history, 6 weeks ago,

Solutions

Solutions - C++ - Java - Python 3

Solutions - C++ - Java - Python 3

Solutions - C++ - Java

Solutions - C++ - Java

Solutions - C++ - Java - Python 3

• +178

 » 6 weeks ago, # |   +30 Nice Editorial by the looks of it... I mean the explanation seems thorough
 » 6 weeks ago, # |   +62 Well, B was harder than usual Div2 B.
 » 6 weeks ago, # |   0 Really the explanation is superb.
•  » » 6 weeks ago, # ^ |   0 In problem B=> Why it is optimal to equal two adjacent elements once? Cannot there be a case that we can get min operations by doing equal two elements but not adjacent? why not? what is the proof for that contradiction?
•  » » » 6 weeks ago, # ^ |   0 You might want to think of it like this : No matter what, you have to fix the adjacent differences using the operations. So what's the optimal strategy to achieve that by changing one element? It's to make a[i] anywhere between a[i-1] and a[i+1] because no matter what you do, abs(a[i+1]-a[i-1]) will remain. but as for the edges, this is not the case because they have only one adjacent element, and we can completely erase the difference by making them equal.
•  » » » 6 weeks ago, # ^ |   0 Mathematically, you can think of it like this. lets say you have three elements a b c. Initially total number of moves would be abs(c-b)+abs(b-a). Now without loss of generality lets assume that abs(c-b)
•  » » » » 6 weeks ago, # ^ |   0 thank you for the explanation
 » 6 weeks ago, # |   +7 Well, the working of D was googleable. You just need to connect and implement.Link to the site: https://www.codechef.com/wiki/tutorial-expectation (Q3).
•  » » 6 weeks ago, # ^ |   +3 Thanks for the article. It was very helpful.
 » 6 weeks ago, # |   +23 Thanks for your fast & detailed solution <3
 » 6 weeks ago, # |   +33 Thank you for the great solutions. (I love the problemset)
 » 6 weeks ago, # | ← Rev. 2 →   +3 Pls help. I did the problem C with almost exactly the same algorithm (which is O(n^2)), but got TL many times. Submission.Is this a std::vector slow or what?P.s. I even did an initialisation to vector before operating with digits
•  » » 6 weeks ago, # ^ |   0 Even my solution is giving TLE at test case 5, the time complexity is O(n^2) but I don't know why its showing TLE. Here is the link to the submission:Can someone please help me out?
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   +3 Your solution is actually O(N^4) . Consider a case where all the numbers in the grid are the same
•  » » » » 6 weeks ago, # ^ |   +4 Thank you very much! Now, I realize it :)
•  » » » 6 weeks ago, # ^ |   0 Yours solution is 666
•  » » 6 weeks ago, # ^ |   0 One optimization you can do to make this code run is that for each digit which is occuring >1 times in a row, just consider its leftmost and rightmost occurence for further calculations. This will not make the answer incorrect because we want the maximum area which will depend only on the extreme coordinates. For e.g. in this case below 1 5 00000 11111 00000 00000 00000 Instead of storing coordinates of 1 as (2,1),(2,2),(2,3),(2,4) & (2,5), store & consider 1 to be present only at (2,1) & at (2,5). This way that n^4 factor would be reduced to 2*n factor. I know its hard to understand as I have not explained it in that detail but try to think, you will get the feel. You can see my accepted submission (post contest) which is same as n^4 solution. Just this extra optimization.
•  » » » 6 weeks ago, # ^ |   0 That's a neat observation. Thanks! :)
•  » » » 6 weeks ago, # ^ |   0 Thanks a ton! It worked for me.
 » 6 weeks ago, # |   0 The observation for problem B was very critical relating to problem statement. But I think problem C was easier as it was greedy implementation problem.
 » 6 weeks ago, # |   +4 I really liked problem D. Thanks for the contest :)
•  » » 6 weeks ago, # ^ |   0 100401410 can u help me whats wrong in this...i just used binary search from 1-60 to find no. of zeroes.. nd giving WA on TEST3...
•  » » » 6 weeks ago, # ^ |   0 Hi, did you figure out the error? I see an accepted submission in your submissions.
•  » » » » 6 weeks ago, # ^ |   +5 hey, No.. i simply tried for loop from 1-60..in accepted submission.
•  » » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 https://codeforces.com/contest/1453/submission/100712318Anyone know why is this happening?The result changes when you declare "pow(2ll, lo+1ll)-2ll" with a separate variable
•  » » » » » » 3 weeks ago, # ^ |   0 magic
 » 6 weeks ago, # |   +11 I would admit B is an interesting problem, but it's way harder than a typical Div.2 B problem. Well, at least it's a good lesson about my mentality adjustment. I still can't overcome the frustration about can't solve easy(at least in my mind) problems during the contest (:」∠)_
 » 6 weeks ago, # |   +6 This contest was tough!!
 » 6 weeks ago, # |   +11 Nice ProblemSet, Editorial !
 » 6 weeks ago, # | ← Rev. 3 →   0 Everyone solved problem C assuming that it is always optimal for us to choose the right triangle. But how do we prove it? The statement said at least one side of the triangle should be parallel with one of the sides of the board. So we can have other types of triangles as well. djm03178
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +11 I don't think you can only choose right triangles. Consider digit 1 for 000 001 100 You need to put the last 1 in (1, 1), which does not form a right triangle. Do note that a triangle's area is 1/2 base times height regardless of whether it is right or not.
•  » » » 6 weeks ago, # ^ |   +1 Thanks a lot. It was my bad. I miscalculated a bit.
 » 6 weeks ago, # |   0 In problem E, I failed this problem in test 2, 14th testcase. System said I responded 3, but it expected 2. However, I debug the same code in code::blocks, it printed 2. I think the Testing system has error.E번 문제 두 번째 테스트 14번째 케이스에서 정답이 2이고, 코드블럭에서 똑같은 코드에 똑같은 테케를 넣어본 결과 2를 대답했는데, 3을 대답해서 틀렸다고 나옵니다. 시스템 오류가 있는 것 같습니다.
•  » » 6 weeks ago, # ^ |   +1 I checked my code is wrong. Sorry.아 잘못 봤네요 3이 나옵니다. 죄송합니다.
•  » » 6 weeks ago, # ^ |   +3 It seems, your code initializes $M$ only once, and in the loop the previous data is overriding. You need to initialize $M$ in each testcases.
•  » » » 6 weeks ago, # ^ |   0 Thank you... I initialized M and got AC. I could solve my first E.... Too bad.
 » 6 weeks ago, # |   +2 Problem B was not easy for us!
 » 6 weeks ago, # |   0 I did a very stupid mistake in B.For n = 2 answer will be 0 but I don't know what came to my mind, I printed their difference.Sadly that case wasn't in the pretests.
•  » » 6 weeks ago, # ^ |   0 Its best to keep code as genralized as possible.
 » 6 weeks ago, # |   +46 Here is an easier solution for E:Just binary search the answer $K$ and let $DFS(Node)$ return the minimum difference in height between this node and the last node you ate a snack from.If all the children return difference in height $\lt K - 1$ just return the minimum meaning the last child you will visit is the one with minimum difference in height.If one of them has difference in height equal to $\ge K - 1$ return it.If more than one of them has difference in height equal to $\ge K - 1$ then there is no answer.In the end just check that $DFS(1) \le K$.
 » 6 weeks ago, # |   0 in problem B's editorial -> "This value is minimized when ai is between ai−1 and ai+1" , should it not be maximized ?
 » 6 weeks ago, # |   +3 Can someone explain D with a bit more mathematical proof? For the sequence 1 0 1 what are the expected number of tries for each stage?
•  » » 6 weeks ago, # ^ |   0 basically 1 is 2 1 0 is 6 (2*(1+2)) 1 0 0 is 14 (2*(1+2+4)) 1 0 0 0 is 30 (2*(1+2+4+8))so for 1 0 1 it is 6 + 2 = 8
•  » » 6 weeks ago, # ^ |   +6 Let $E(x)$ be the expected number of tries to complete a game with $x$ levels, i.e, if you lose you have start again from level $1$. Let us have $m$ checkpoints at $a_1=1$, $a_2$, $...$ $a_m$. Then answer required is $E(a_1)+E(a_2-a_1)+...E(a_n-a_{n-1})+E(n-a_n)$.For a game with a single level, game ends once you make a single win, and you can win either in $1^{st}$ try or ${2^{nd}}$ try and so on. If you win at $i^{th}$ try, you would have made $i$ moves. Since the probabilities of winning and losing are same,$E(1)=\sum_{i=1}^{\infty}1/2^i*i=2$.To calculate $E(n)$, we can use the same method we used for calculating $E(1)$. The difference here is that, every time you lose, you have to make $E(n-1)+1$ moves. The main idea is that, every time you win level $n$, you have to win level $n-1$ as well.So, $E(n)=\sum_{i=1}^{\infty}1/2^i*(i*(E(n-1)+1))=2*(E(n-1)+1)$.Solving this recurrence yields, $E(n)=2(2^n-1)$.The "constructing the checkpoints" part is nicely explained in the editorial.
•  » » » 6 weeks ago, # ^ |   +3 Thanks a lot for this clear explanation!
•  » » » » 6 weeks ago, # ^ | ← Rev. 2 →   +14 For me this is less hard to understand:Let $x_i$ be the expected number to finish i stages without any checkpoint.$x_1=\frac{1}{2} + \frac{1}{2} \cdot (1+x_1)=2$ (Because with half prob we finish the stage in first atempt, and other half prob we need that one atempt and again have the same expected value)$x_2=x_1 + \frac{1}{2} + \frac{1}{2} \cdot (1+x_2)=6$...$x_i=(x_{i-1}+1)\cdot 2$We see that this value gets bigger quickly, 1e18 is reached with less than 60 steps. Lets write those numbers into an array.Then for a given $k$, we can search that array for the biggest number smaller than $k$, let that be $x_j$. To construct stages so that the expected number is $x_j$ we need to put $j-1$ times 0 then a 1.Put that to ans and decrement $k$ by $x_j$, then repeat. Note that for some reason we are forced to place a 1 in first stage, so start with $k-2$. If $k$ is odd there seems to be no solution.
•  » » » » » 6 weeks ago, # ^ |   0 Wow, this seems pretty neat. I always tend to solve the summations that are formed in the questions involving expectations, but thanks to you, I learnt a neat way to avoid them!
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 How to prove this: $E(1) = \sum\limits_{i = 1}^\infty 1/2^i * i = 2$ ?
•  » » » » 4 weeks ago, # ^ |   0 UPD: Understood it. It's actually an A.G.P, Arithmetic Geometric Progression with numerator in AP and denominator in GP.This is a good article if anyone wants to understand AGP.
 » 6 weeks ago, # |   0 I tried E but I dont know where its wrong.can someone point out my error https://codeforces.com/contest/1453/submission/100387883
 » 6 weeks ago, # |   0 My O(n^2) C gives TLE -_-: C//Think simple yet elegant. #include using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define all(v) v.begin(),v.end() #define ff first #define ss second #define pb push_back #define mp make_pair #define pi pair #define REP(i,n) for(int i=0;i> t; while(t--){ cin >> n; int gr[n][n]; for(i=0;i> s; for(j=0;j av; for(d=0;d<10;++d){ vector v; ll ans=0; for(i=0;i
•  » » 6 weeks ago, # ^ |   0 Consider the case when all the numbers in grid are same then the size of vector v in your code becomes n*n and then looping around them for n*n time so overall it become pow(n,4);
•  » » » 6 weeks ago, # ^ |   0 Right
 » 6 weeks ago, # |   0 "we don't need to check the case where we change a cell that is not used as an end of a base separately, since we can always move it around so that they will eventually be horizontal / vertical to one of the other vertices without changing the area..." (Div2C)I don't really get this statement. Can someone explain?
 » 6 weeks ago, # |   +1 B was harder than usual...!
 » 6 weeks ago, # |   0 During the contest I had the same idea for E as the editorial, but I couldn't see why it is always optimal to choose the child that has the shortest 'moving back' distance. I'd like to know if there is an easy proof/intuition for this.
 » 6 weeks ago, # |   0 Thanks for fast editorial though! Now I can check what went wrong
 » 6 weeks ago, # |   +13 It should be forbidden to write an editorial for that C without drawing a picture.
•  » » 6 weeks ago, # ^ |   0 yeah, explanation with a picture would be nice :(
 » 6 weeks ago, # |   +5 Wow... all codes are short!
•  » » 6 weeks ago, # ^ |   0 But logic is not.
 » 6 weeks ago, # |   +2 Thank you for B, I learnt something new.
•  » » 6 weeks ago, # ^ |   0 What did you learn ?
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Another thinking approach from editorial.I am too dumb so I was trying to find the optimal number to be changed at first by some pre-processing, but here the way, you find the lower bound of the moves and then you maximise the deleting operations was new to me.
 » 6 weeks ago, # |   +4 Irrespective of how much I f***ed up in the contest , I want to say that the problems are beautiful. I learnt a lot. I will practice harder. Thank you for such a nice contest.
•  » » 6 weeks ago, # ^ |   0 Yeah bro, even I had the same experience
 » 6 weeks ago, # |   0 Well documented editorialsThanks for providing answers for more than one language.
 » 6 weeks ago, # |   0 my this WA solution and this AC solution is almost same, just diff is i am using log2 operator instead of another loop, why its wrong then???????
•  » » 6 weeks ago, # ^ |   0 I had this problem too, and i think it's because of decimal error of log2(x). If x is over e15 this error appears
 » 6 weeks ago, # |   0 Okay this is probably silly, but help me out a bit.To my understanding, I derived the following,Assertion : In a sequence of length $k+1$, where the 1st and last characters are 1 and rest are zero. The expected number of tries to reach (not beat) $(k+1)^{th}$ stage from $1^{st}$ stage is $2^{k}$ ProofLet $w$ be the probability of reaching the last stage in 1 try. $\\E = w+2(1-w)(w)+3(1-w)^2(w)+\dots+\infty\\$ $E=w\times\sum_{r=1}^{r=\infty}r\times(1-w)^{r-1} = wS\\$Let $k = 1-w$, hence we get $S$ as, $S=1+2k+3k^2+4k^3+\dots=\dfrac{1}{(1-k)^2}=\dfrac{1}{w^2}$ $\therefore E=\dfrac{1}{w}$Now for $w$, you need to beat all the $k$ stages to reach the $(k+1)^{th}$ stage, so the probability $w=\dfrac{1}{2^k}$With this assertion, I did the following, for an input x, subtract 2 (Since we need this to exit the last stage) and now for $k^{th}$ set bit, append sequence $1(0)^{k-1}$. And finally append $1$.However for $8$, my algorithm prints $1011$, $2^2$ (beating 1,2) to reach $3^{rd}$, then $2$ beating $3$ to reach $4$, and finally beating $4^{th}$ with $2$ itself to win. A total of $4+2+2=8$. It would be very helpful if someone could point out where I am wrong.
 » 6 weeks ago, # | ← Rev. 2 →   0 .
 » 6 weeks ago, # |   0
•  » » 6 weeks ago, # ^ |   0 lol...
 » 6 weeks ago, # |   0 Thanks for the great problems. For E, I keep getting runtime error for a pure dfs solution.Looking at the submissions, it looks like only two solutions in PyPy3 were accepted, and each of these does dfs 'non-recursively' (by a bfs first), e.g. https://codeforces.com/contest/1453/submission/100385834Could someone explain why a pure dfs solution gives a runtime error? Many thanks.
 » 6 weeks ago, # |   0 gildong did make my life tough today
 » 6 weeks ago, # |   0 can someone please tell why this gives tle but this is Ac .only difference between them is that the Ac code does not have the line #define int long long
 » 6 weeks ago, # |   +2 Personally, I think that this is one of the most interesting contests in a long time. I enjoyed solving these problems a lot, especially problems B and E.
 » 6 weeks ago, # |   +5 For E: it's too **boring** to find the sub-maximum in linear time, so just sort the candidates and it will be O(nlogn) for each test case.More like: it's too **tedious** ...
 » 6 weeks ago, # |   0 Can anyone hack my O(n^3) solution for F? 100403925
 » 6 weeks ago, # |   0 In B how is it correct to say the answer is to find the difference between minimum no of operations on initial array and maximum no of ways of reducing such operations by changing one element?? I know this may sound ridiculous to many but this is something I couldnt understand :(
 » 6 weeks ago, # |   0 Can anyone provide me the explanation of third case in editorial of B. abs(ai-ai+1)+abs(ai-ai-1)+abs(ai+1-ai-1).I am not able to understand why we are doing this.
•  » » 6 weeks ago, # ^ |   0 try to think if we have changed a2 with a1so now it will be a1,a1,a3,a4.... so final answer will look like this- final ans=abs(a1-a1)+abs(a3-a1)+abs(a4-a3)+......original answer with a1,a2,a3,a4.... orig ans=abs(a2-a1)+abs(a3-a2)+abs(a4-a3)+........subract final ans from orig ans so it will become abs(a2-a1)+abs(a3-a2)-abs(a3-a1) and that is exactly written in 3rd case
•  » » » 6 weeks ago, # ^ |   0 why abs(ai+1-ai-1) is substracted from abs(ai-ai+1)+abs(ai-ai-1).
•  » » » » 6 weeks ago, # ^ |   0 from above comment you can subtract originalans — finalans you can see the results.
•  » » » » » 6 weeks ago, # ^ |   0 Yeah thanks i got it
 » 6 weeks ago, # |   0 The problems were great. Thank you, djm03178. But I totally messed up this round. :(
 » 6 weeks ago, # |   0 if i am not hungry, i could solve F and become master
 » 6 weeks ago, # |   +1 While I was trying to solve B, I thought I was solving any C or D problem. Tbh, it was too hard.
 » 6 weeks ago, # |   0 Deteailed hindi video tutorial from A to E and thought process here
 » 6 weeks ago, # |   +1 B problem was fun to solve! Thanks for such questions :)
 » 6 weeks ago, # | ← Rev. 2 →   0 For the triangles problem, I had the same approach and as n=2000 it should have worked for n^2. But it gave me TLE on the 5th pretest. Someone please tell me where I went wrong. Thanks in advance100388093
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Input: 1 2000 111.....111 . . . . 111.....111
•  » » » 6 weeks ago, # ^ |   0 yes, but it will still be strictly 4X10^6. so why will it give tle? nagaraj41
•  » » » » 6 weeks ago, # ^ |   0 You are saving all points of a particular d. That means for my above case, you are storing n^2 points in your v[1]. Now run through your code.
•  » » » » » 6 weeks ago, # ^ |   0 understood, thanks. any advice on how to make it work?
•  » » » » » » 6 weeks ago, # ^ |   +3 You can keep the right most, left most, top most and bottom most for each d. then you can do it efficiently. Editorial explains in detail.
 » 6 weeks ago, # |   0 Can someone explain how the max area*2 is 42 for digit-9 in this testcase 42987101 98289412 38949562 87599023 92834718 83917348 19823743 38947912 Any help is kindly required :(
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 To be precise I am talking about the last testcase of the problem. Howmuch ever I search, I am getting 36 as answer and not 42 :(
•  » » 6 weeks ago, # ^ |   0 Take the first 9 in the second row and the nine in the last row. The third one will be put on second row, last element.
 » 6 weeks ago, # |   0 Can anybody explain why this solution(https://codeforces.com/contest/1453/submission/100422469) for C gives TLE
 » 6 weeks ago, # |   0 Thanks a lot got it now :)
 » 6 weeks ago, # |   +8 As a matter of fact, the problem C is a little boring.But overall, the contest is pretty good.Thanks for the contest
 » 6 weeks ago, # |   +1 Nice tutorial and problem set. Thank you.
 » 6 weeks ago, # |   +1 This was by far the best editorial on codeforces according to me.
 » 6 weeks ago, # |   +1 B was more tuff than usual but thanks for the explanation really helpful :)
 » 6 weeks ago, # |   +1 can someone help me, i keep getting wrong ans on test case23 on test no 5. i have done something similiar to the first strategy in the editorial .I find the sum of the gp of 2,4,8... which is just smaller than n and take those many zeroes and then subtract that sum from n and then the dif becomes the new n and i do this recursively till the dif is zero.I even took the test case and found that the expected value was same as the number given .Any help is much appreciated 100441237
 » 6 weeks ago, # |   +1 Solution for prob B I found this video really helpful.
 » 6 weeks ago, # |   +1 for the first time, I will say the tutorial is awesome. I am learning a lot.
 » 6 weeks ago, # |   +1 F is cool, thanks
 » 6 weeks ago, # |   +5 For problem B, if you know before the contest that the basic solution (in case of no replacement) is : $\sum_{i=2}^n abs(a_i - a_{i-1})$. Then it's probably easier to solve it as you can reason about this equation.Is it part of a common knowledge that experienced competitive programmer have ?
•  » » 6 weeks ago, # ^ |   0 I derived this knowledge during the contest, spend many time on paper =)
 » 6 weeks ago, # |   +1
 » 6 weeks ago, # |   0 Fantastic explanation, very helpful for beginners to understand the logic.
 » 6 weeks ago, # |   0 I am trying to figure out below operation from yesterday still not getting. What is the intuition of this operation.Math.max(mx, Math.abs(a[i] — a[i — 1]) + Math.abs(a[i + 1] — a[i]) — Math.abs(a[i + 1] — a[i — 1]));
•  » » 6 weeks ago, # ^ |   0 The basic solution (no replacement) is $sum_0 = \sum_{i=2}^n |a_i - a_{i-1}|$.When you choose $a_i$ between $a_{i-1}$ and $a_{i+1}$, you obtain : $sum = |a_2 - a_1| + \ldots + |a_{i-1} - a_{i-2}| + |a_{i+1} - a_{i-1}| + |a_{i+2} - a_{i+1}| + \ldots + |a_{n} - a_{n-1}|$It's independent of the value chosen for $a_i$.So $sum = sum_0 - |a_i - a_{i-1}| - |a_{i+1} - a_i| + |a_{i+1} - a_{i-1}|$, i.e you remove the contribution of $a_i$ from $sum_0$ and add the contribution of the newly chosen value of $a_i$ (between $a_{i-1}$ and $a_{i+1}$).You do this for all i, and obtain (not taking into account edge cases i=1 and i=n) : $ans = min(ans, sum_0 - |a_i - a_{i-1}| - |a_{i+1} - a_i| + |a_{i+1} - a_{i-1}|)$
•  » » » 6 weeks ago, # ^ |   0 Thanks
 » 6 weeks ago, # |   0 Can anyone help me with this problem
 » 6 weeks ago, # |   0 For Problem F, 1453F — Even Harder, my O(n**3) DP solution passed. I didn't try to optimize the code, just wrote the simplest version for my DP expectig it will TLE and I will have to optimize my code to O(n**2). http://codeforces.com/contest/1453/submission/100570074 Although the solution is O(n**3), I am having difficulty in coming up with a test case which will trigger TLE on my solution.
 » 6 weeks ago, # |   0 Can anybody please explain the general equation derived in question D.I cannot get it please
 » 5 weeks ago, # | ← Rev. 2 →   0 can anybody please explain the main idea of solution used in problem E DOG'S SNACK
 » 5 weeks ago, # |   0 The problem D is very useful. I hope to conduct more value contests.
 » 4 weeks ago, # | ← Rev. 4 →   0 Can somebody explain why, in E, for the root node, we choose the sub-maximum of the candidates to find the maximum child-to-child distances instead of the minimum of the candidates.
 » 13 days ago, # | ← Rev. 2 →   0 My Submission for CI implemented following the editorial of C. Is there any corner case? I am getting WA in test 6. Can't really understand why. Can anyone pls help me?row_max -> vector which stores best area of triangle whose base is horizontal. col_max -> vector which stores best area of triangle whose base is vertical. I output the max(row_max,col_max) for all d.max_row & min_row -> to store max row no. and min row no. of every d. max_col & min_col -> to store max column no. and min column no. of every d.initially "base" variable contains length of base. In next line, I store area value in variable "base" by multiplying it with height.Hope this helps to understand my messy implementation.
 » 8 days ago, # |   +8 It took us one month to prepare a video solution for problem B :) If it is still interesting to anyone, please consider: