Negationist's blog

By Negationist, history, 7 weeks ago, In English

Problem: Array Game — https://mirror.codeforces.com/contest/1904/problem/C Idea of the code, consider all possible combinations of 2 elements to make diff, mn = min of, mn, diff, [first element greater than diff]-diff, [one element left of the first element greater than diff]-diff. Thanks so much.

My Code
  • 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

my man k==2 case will get you to a nice n^2 TLE you must use binary search for each difference

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

    The time complexity of n^2logn was correct if you look at the editorial

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

      Oops wow. I solved it in nlog(n) and never checked the constraints wow

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

        I dont even think thats possible

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

          Yes you can sort the array and check for each

          $$$x=a_{i+1}-a_{i}$$$

          what is the closest element to it from the right and left

          and consider them in the answer

          You answer is the minimum amoung these

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

at k==2 for(int i=0; i<n-1;i++) You put i<n-2, so you skipped one check

Try a=[5,98,99], ans is 1, but you get 4 because 98-(99-5)=4