| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 161 |
| 2 | adamant | 150 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
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! :)
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://mirror.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
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$$$.
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?
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://mirror.codeforces.com/contest/1453/submission/100387883
My O(n^2) C gives TLE -_-:
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);
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.
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!
Thank you for B, I learnt something new.
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.
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 to reach (not beat) $$$(k+1)^{th}$$$ stage from $$$1^{st}$$$ stage is $$$2^{k}$$$
Let $$$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.
.
...
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://mirror.codeforces.com/contest/1453/submission/100385834
Could someone explain why a pure dfs solution gives a runtime error? Many thanks.
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? 100403925Can 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
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
B was hard enough
Deteailed hindi video tutorial from A to E and thought process here
THANKS
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 :(
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.
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
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://mirror.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.
It took us one month to prepare a video solution for problem B :) If it is still interesting to anyone, please consider:
Alternate $$$O(N^2.\log{N})$$$ dp solution for problem F using a segment tree: link
The basic idea is to maintain n segment trees, and ith segment tree stores that if point i is the second point chosen, then all j > i, store the total answer if point i is chosen as the second point and j is chosen as the third point. This works because we only need to maintain information for the first two points, and rest of the chosen points will inductively be valid.
Note to self: Write explanation later.