djm03178's blog

Codeforces Round #688 (Div. 2) Editorial
By djm03178, history, 4 years ago, In English
Tutorial is loading...

Solutions

Tutorial is loading...

Solutions - C++ - Java - Python 3

Tutorial is loading...

Solutions - C++ - Java - Python 3

Tutorial is loading...

Solutions - C++ - Java

Tutorial is loading...

Solutions - C++ - Java

Tutorial is loading...

Solutions - C++ - Java - Python 3

  • Vote: I like it
  • +178
  • Vote: I do not like it

Comments Comments (100)
| Write comment?
»
4 years ago, # |
  Vote: I like it +30 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +62 Vote: I do not like it

Well, B was harder than usual Div2 B.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Really the explanation is superb.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thanks for the article. It was very helpful.

    → Reply
»
4 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Thanks for your fast & detailed solution <3

→ Reply
»
4 years ago, # |
  Vote: I like it +33 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

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

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yours solution is 666

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's a neat observation. Thanks! :)

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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 (:」∠)_

→ Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

This contest was tough!!

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Nice ProblemSet, Editorial !

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I checked my code is wrong. Sorry.

    아 잘못 봤네요 3이 나옵니다. 죄송합니다.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Problem B was not easy for us!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +46 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks a lot for this clear explanation!

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +14 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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!

          → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried E but I dont know where its wrong.

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

C
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

B was harder than usual...!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Wow... all codes are short!

→ Reply
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Thank you for B, I learnt something new.

→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Proof

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.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.net/contest/1453/submission/100385834

Could someone explain why a pure dfs solution gives a runtime error? Many thanks.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone hack my O(n^3) solution for F? 100403925

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

B was hard enough

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Input:
    1
    2000
    111.....111
    .
    .
    .
    .
    111.....111

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            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.

            → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

As a matter of fact, the problem C is a little boring.
But overall, the contest is pretty good.
Thanks for the contest

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice tutorial and problem set. Thank you.

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Solution for prob B I found this video really helpful.

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

F is cool, thanks

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Video Tutorial for E

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me with this problem

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

Video link

→ Reply
»
18 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply