# | User | Rating |
---|---|---|

1 | tourist | 3778 |

2 | Benq | 3592 |

3 | ecnerwala | 3521 |

4 | Um_nik | 3423 |

5 | jiangly | 3375 |

6 | Petr | 3342 |

7 | Radewoosh | 3337 |

8 | scott_wu | 3313 |

9 | maroonrk | 3265 |

10 | yosupo | 3259 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 202 |

2 | 1-gon | 200 |

3 | rng_58 | 194 |

4 | SecondThread | 193 |

5 | awoo | 187 |

6 | vovuh | 183 |

7 | Um_nik | 182 |

8 | antontrygubO_o | 177 |

9 | Ashishgup | 175 |

10 | -is-this-fft- | 171 |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/18/2021 04:01:00 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Nice Editorial by the looks of it... I mean the explanation seems thorough

Well, B was harder than usual Div2 B.

Really the explanation is superb.

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?

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.

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)<abs(b-a).

Lets make two non-adjacent elements a, c equal : c b c ans=2*abs(b-c).

Now, lets make two adjacent elements equal, b b c ans=abs(b-c)+0. As you can see, it is always optimal to make two adjacent elements equal.

Hope this was useful.

thank you for the explanation

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

Thanks for the article. It was very helpful.

Thanks for your fast & detailed solution <3

Thank you for the great solutions. (I love the problemset)

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

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?

Your solution is actually O(N^4) . Consider a case where all the numbers in the grid are the same

Thank you very much! Now, I realize it :)

Yours solution is 666

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

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.

That's a neat observation. Thanks! :)

Thanks a ton! It worked for me.

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.

I really liked problem D. Thanks for the contest :)

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

Hi, did you figure out the error? I see an accepted submission in your submissions.

hey, No.. i simply tried for loop from 1-60..in accepted submission.

https://codeforces.com/contest/1453/submission/100712318

Anyone know why is this happening?

The result changes when you declare "pow(2ll, lo+1ll)-2ll" with a separate variable

magic

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

(:」∠)_This contest was tough!!

Nice ProblemSet, Editorial !

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

I don't think you can only choose right triangles. Consider digit 1 for

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.

Thanks a lot. It was my bad. I miscalculated a bit.

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을 대답해서 틀렸다고 나옵니다. 시스템 오류가 있는 것 같습니다.

I checked my code is wrong. Sorry.

아 잘못 봤네요 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.

Thank you... I initialized M and got AC. I could solve my first E.... Too bad.

Problem B was not easy for us!

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.

Its best to keep code as genralized as possible.

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

in problem B's editorial -> "This value is minimized when ai is between ai−1 and ai+1" , should it not be maximized ?

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?

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

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.

Thanks a lot for this clear explanation!

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.

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!

How to prove this: $$$E(1) = \sum\limits_{i = 1}^\infty 1/2^i * i = 2$$$ ?

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.

I tried E but I dont know where its wrong.

can someone point out my error https://codeforces.com/contest/1453/submission/100387883

My O(n^2) C gives TLE -_-:

CConsider 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);

Right

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

B was harder than usual...!

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.

Thanks for fast editorial though! Now I can check what went wrong

It should be forbidden to write an editorial for that C without drawing a picture.

yeah, explanation with a picture would be nice :(

Wow... all codes are short!

But logic is not.

Thank you for B, I learnt something new.

What did you learn ?

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.

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.

Yeah bro, even I had the same experience

Well documented editorials

Thanks for providing answers for more than one language.

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

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

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

Let $k = 1-w$, hence we get $$$S$$$ as,

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.

.

lol...

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

gildong did make my life tough today

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

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.

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

Can anyone hack my

`O(n^3)`

solution for F? 100403925In 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 :(

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.

try to think if we have changed a2 with a1

so 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

why abs(ai+1-ai-1) is substracted from abs(ai-ai+1)+abs(ai-ai-1).

from above comment you can subtract originalans — finalans you can see the results.

Yeah thanks i got it

The problems were great. Thank you, djm03178. But I totally messed up this round. :(

if i am not hungry, i could solve F and become master

While I was trying to solve B, I thought I was solving any C or D problem. Tbh, it was too hard.

Deteailed hindi video tutorial from A to E and thought process here

B problem was fun to solve! Thanks for such questions :)

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 advance

100388093

Input:

1

2000

111.....111

.

.

.

.

111.....111

yes, but it will still be strictly 4X10^6. so why will it give tle? nagaraj41

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.

understood, thanks. any advice on how to make it work?

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.

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

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

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.

Can anybody explain why this solution(https://codeforces.com/contest/1453/submission/100422469) for C gives TLE

Thanks a lot got it now :)

As a matter of fact, the problem C is a little boring.

But overall, the contest is pretty good.

Thanks for the contest

Nice tutorial and problem set. Thank you.

This was by far the best editorial on codeforces according to me.

B was more tuff than usual but thanks for the explanation really helpful :)

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

Solution for prob B I found this video really helpful.

for the first time, I will say the tutorial is awesome. I am learning a lot.

F is cool, thanks

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 ?

I derived this knowledge during the contest, spend many time on paper =)

Video Tutorial for E

Fantastic explanation, very helpful for beginners to understand the logic.

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]));

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 :

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

Thanks

Can anyone help me with this problem

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.

Can anybody please explain the general equation derived in question D.I cannot get it please

can anybody please explain the main idea of solution used in problem E DOG'S SNACK

The problem D is very useful. I hope to conduct more value contests.

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.

My Submission for C

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

It took us one month to prepare a video solution for problem B :) If it is still interesting to anyone, please consider: