alaincr7's blog

Need help for this problem came in meesho online assessment 2025
By alaincr7, history, 7 months ago, In English

Given an array arr of N integers. Each array has some hardness

hardness = max abs(arr[i+1]-arr[i]) for all 1<=i<=N-1

And hardness = 0 if N<=1

You are given a number K you can change at most K elements of the array. You have to minimize the hardness of the array

Both N and K were less than 2000

where arr[i]>=-1e9 and arr[i]<=1e9

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

»
7 months ago, hide # |
 
Vote: I like it -10 Vote: I do not like it

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

→ Reply
»
7 months ago, hide # |
 
Vote: I like it -13 Vote: I do not like it

This should be easy one.

→ Reply
»
7 months ago, hide # |
← Rev. 3  
Vote: I like it -10 Vote: I do not like it

if the array is {a1,a2,a3, ... an}, the answer is always an-a1 because the rest of the elements get canceled out, so just decrease an, and increase a1 as much as possible

→ Reply
»
7 months ago, hide # |
← Rev. 2  
Vote: I like it -10 Vote: I do not like it

[REDACTED]

→ Reply
»
7 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

https://www.codechef.com/problems/KEVIN

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

Lets say you have fixed $$$x$$$, consider $$$dp_i,_j$$$ which means the minimum number changes needed to have this property: The hardness of prefix $$$i$$$ is smaller than $$$x$$$, and last $$$j$$$ elements were changed.

If all elements of some segment $$$[l, r]$$$ were changed, then u can make the hardness of the segment $$$[l-1, r+1]$$$ equal to $$$\lceil \frac{a_{r+1}-a_{l-1}}{r-l+3}\rceil$$$(I am not sure if this formula is correct)

Let segment $$$[l, r]$$$ be good if and only if $$$\lceil \frac{a_{r+1}-a_{l-1}}{r-l+3}\rceil \leq x$$$

You have these transitions:

$$$1.$$$ if $$$[i, i - j + 1]$$$ is good then: $$$dp_i,_j=min(dp_i,_j, dp_{i-1},_{j-1}+1)$$$

$$$2.$$$ $$$dp_i,_0=min(dp_i,_0, dp_{i-1},_{j-1})$$$

Now u can just binsearch the value $$$x$$$, and this should work in $$$O(n^2\log x)$$$

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

    Is there a n log(x) , binary search solution for this

    I was thinking for each X in binary search , we check greedily if its possible to make diff <= X by using at most K operations.

    // checker greedy if(abs(arr[i] — arr[i-1]) > X // then K has to be reduced .

    Now which leads to maximum distances without using another K-1 --> changing arr[i] or arr[i-1]

    Oh shit , will not work : changing arr[i-1] will make me recompute everything till here.

    → Reply
»
7 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply