AM_I_Learning's blog

By AM_I_Learning, history, 4 years ago, In English
A

94665721

B

94680223

C

94711408

D

94748833

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

| Write comment?
»
4 years ago, # |
  Vote: I like it +34 Vote: I do not like it

I have tried writing editorial for A to D problems as official version is not out yet. Hope it helps someone.

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

    YEAH IT DOES HELP ME AND MANY OTHERS ...THANK YOU

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

    You wrote every teleport connected to two nearest 2 row wise teleport if some teleport is index i to which which it connected??

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

      You have to sort the teleports according to rows once and thus the original indices will be changed. if your i is in the newly sorted array then you have to add an edge of it with i-1th in the newly sorted teleports and with i+1 th in the newly sorted teleports.

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

        Why with i-1 is it necessary for adding i-1?? Why it will come forward after going to backward is it not optimal to add only I+1th edge??

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

          I mean that adjacent ones have to be added an edge. It may come backward when destination is in opposite direction, not always destination will be having greater row and greater col number to each telports and source, thus to consider all the possible cases I have simply made an edge between adjacent row numbers. and adjacent col ones. whatever be the location.

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

            So if I add for only for one position (I+1) then that will not work??

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

              YOur edge must be undirected then only it will work.

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

Auto comment: topic has been updated by AM_I_Learning (previous revision, new revision, compare).

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

Can you explain the ceil part for A again. How do you ensure that D doesn't connect beyond C?

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

    OK cool. in the diagram you may see that I have made the lines AD and BC at 90 degree to line AB . lets say the calculated length for CD comes not an integer. thus I can rotate any of AD and BC to such an extent to fit it into the next integer . Because still I have free space of 90 degree + 90 degree for rotation. like this . if CD comes non integer then take its ceil value to fit something like this.

    |         
       D\    
          \         |C
          A\________|B
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    A simpler solution to A:

    void solve()
    {
    	int a, b, c;
    	cin>>a>>b>>c;
    	cout<<a+b+c-1<<endl;
     
    }
    
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      any reason on why it works? (even i did the same , but i don't know why it works)

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

        For any non-degenerate quadrilateral sum of three sides should be greater than the fourth side.

        a+b+c>d
        a+b+d>c
        b+c+d>a
        a+c+d>b
        

        I simply did binary search to find the answer(94671381).

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

        well, proof is simple. Think all the given three sides in a line, but you know that these can't be straight line so you have to tilt two sides upwards and your answer will be (a+b+c-something positive).

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

          that was nice , thanks.

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

          could u tell me why do we have to subtract something from the sum ?

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

            If we don't subtract, then d = a+b+c and it won't be a quadrilateral either(you can find what is a quadrilateral on google)

            Btw, why your profile pic is so scary?

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

guys cant we simply do a+b+c-1.although i loved authors approach.it is an overkill for first problem.

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

    We can even just do "c", "c" being the longest between a,b,c.

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

      That would fail for 1 100 1

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

        I think his c is the maximum value between a, b and c

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

        I meant c when a,b,c are ordered from smallest too largest, sorry.

        Edited my comment to make that clear.

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

nice explanation

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

agp

I kept trying this formula for AGP to calculate S2, but got no luck. Was constantly getting wrong answer.

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

For Problem A I just printed the maximum element of input array as the quadrilateral inequality will always hold for this configuration 94661820

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

Someone please help me in problem B, I have tried the same approach that the author said for the problem i.e , I considered all the 4 values :- mat[i][j],mat[i][m-1-j],mat[n-1-i][j],mat[n-1-i][m-1-j] and tried to make them equal by taking their average and changing every value to the avg. value but somehow ans is not coming right.

How can you prove that given 4 values to make them all equal , we have to change them into one of the values among them and not into their avg ?

My code's link is :- https://codeforces.net/contest/1422/submission/94722871 please help me .

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

    Use the median, not the average.

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

      can you please explain me why should i use median and not the average ?

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

        Eg: 4 matrix values(to be equal for being palindrome) be = 2, 4, 6, 20 =>avg=8, cost = 24, median = 4/5/6, cost=20

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

          I got your point but can you suggest me when to use median and when avg?

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

            When changing some values into a same value , changing them into their median is always the smallest.

            It can be proven by maths.

            We consider $$$a_1$$$ and $$$a_n$$$. We know that changing them into some value between $$$a_1$$$ and $$$a_n$$$ is the best choice. Now consider $$$a_2$$$ and $$$a_{n-1}$$$ , it's the same as our previous step.

            Continue doing this,and we know changing them into their median is always the best choice.

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

    Every time I see your profile picture, it strikes me as someone's dead photo. The white background, the date under it, all strike together as someone's memorial.

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

You can try formatting the equations in your editorial

Thanks anyways.

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

Auto comment: topic has been updated by AM_I_Learning (previous revision, new revision, compare).

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

Do you mean O(mlogm) i guess in the editorial of Problem D , cause just seen you swap n & m in the code :)

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

    Ya you got correct.

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

      Great effort man ! You did a great job to make an unofficial editorial . I have read the whole and just i thought you missed explaining the important part of optimal thing to connect adjacent neighboring teleportation points in the Problem D . By the way i made a video editorial of the Problem D here : https://www.youtube.com/watch?v=X1nmTo_Gkww Have a great day ahead man , Jai Shri Ram :)

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

Please,Can someone please tell me where did I go wrong in this solution for C?? I am taking left and right contribution of every digit but it just isn't working.For right contribution I computed the sum of AGP.

UPD: Ignore this comment.

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

What does AGP mean?

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

Can someone explain how the final answer for C is S2+S1? Why isn't it S*S1?

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

in problem B,can't I do binary search to find the optimal value for the 4 values a[i][j],a[i][m-j-1],a[n-i-1][j],a[n-i-1][m-j-1]?

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    If I got you correctly then .. you are trying to
    1.do a binary search in range [0,10^9] .

    2.choose the number which gives minimum result.

    but how do you decide which element to choose. Let's say you fix an upper_limit =5*10^9 . in the next step you find the mid=(10^9+0)/2. for each set of 4 values in the range [0,10^9] you will always have an answer < upper_limit with this mid value. In this case how do you choose which half to choose in the next step [0,mid] or [mid+1,10^9].

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

"Teleport to Destination edges :- Similarly from each teleportation point (x,y) the edge weight to reach destination D(x2,y2) is abs(x-x2)+abs(y-y2)."

Here you are considering weight from destination to the teleportation point, why not to consider from teleportation point to the destination?, although intuitively it looks correct to add the edge in the way you added here but I am not able to get the proof why we are considering the former one!

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

    Because destination is not a teleportation point which can be accessed instantly if you reach its row. Hope it makes some sense?

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

I think in D we don't even need to connect edges from source to each and every teleport since according to analysis 4(edges between transport to transport) we can just connect edges from source to 2 nearest row-wise and 2 nearest column wise teleports and rest all will be handled by the sort function in the same way, won't it be working? AM_I_Learning, I haven't tried proving from the destination point of view, but I think it might be the same as well, if the former one is true!