djm03178's blog

By djm03178, history, 6 weeks 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

»
6 weeks 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

»
6 weeks ago, # |
  Vote: I like it +62 Vote: I do not like it

Well, B was harder than usual Div2 B.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Really the explanation is superb.

  • »
    »
    6 weeks 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?

    • »
      »
      »
      6 weeks 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.

    • »
      »
      »
      6 weeks 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.

»
6 weeks 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).

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thanks for the article. It was very helpful.

»
6 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

Thanks for your fast & detailed solution <3

»
6 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

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

»
6 weeks 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

  • »
    »
    6 weeks 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?

    • »
      »
      »
      6 weeks 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

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

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

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yours solution is 666

  • »
    »
    6 weeks 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.

»
6 weeks 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.

»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

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

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

»
6 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

This contest was tough!!

»
6 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Nice ProblemSet, Editorial !

»
6 weeks 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

  • »
    »
    6 weeks 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.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

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

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I checked my code is wrong. Sorry.

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

  • »
    »
    6 weeks 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.

    • »
      »
      »
      6 weeks 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.

»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Problem B was not easy for us!

»
6 weeks 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.

»
6 weeks 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$$$.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      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.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks a lot for this clear explanation!

      • »
        »
        »
        »
        6 weeks 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.

        • »
          »
          »
          »
          »
          6 weeks 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!

    • »
      »
      »
      4 weeks 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$$$ ?

      • »
        »
        »
        »
        4 weeks 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.

»
6 weeks 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.com/contest/1453/submission/100387883

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

C
  • »
    »
    6 weeks 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);

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

"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, # |
  Vote: I like it +1 Vote: I do not like it

B was harder than usual...!

»
6 weeks 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.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 weeks 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.

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Wow... all codes are short!

»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Thank you for B, I learnt something new.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What did you learn ?

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Well documented editorials

Thanks for providing answers for more than one language.

»
6 weeks 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???????

  • »
    »
    6 weeks 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

»
6 weeks 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.

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

»
6 weeks 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.com/contest/1453/submission/100385834

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

gildong did make my life tough today

»
6 weeks 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

»
6 weeks 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.

»
6 weeks 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** ...

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 weeks 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

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
6 weeks 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. :(

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
6 weeks 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

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      6 weeks 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

      • »
        »
        »
        »
        6 weeks 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.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            6 weeks 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.

»
6 weeks 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 :(

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      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.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks a lot got it now :)

»
6 weeks 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

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice tutorial and problem set. Thank you.

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
6 weeks 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 :)

»
6 weeks 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

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Solution for prob B I found this video really helpful.

»
6 weeks 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.

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

F is cool, thanks

»
6 weeks 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 ?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me with this problem

»
6 weeks 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.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, # |
  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

»
6 weeks 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

»
6 weeks 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.

»
4 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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.

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
10 days 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