Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

alaincr7's blog

Need help for this problem came in meesho online assessment 2025
By alaincr7, history, 12 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

Comments Comments (9)
| Write comment?
»
12 months ago, hide # |
 
Vote: I like it -13 Vote: I do not like it

This should be easy one.

→ Reply
»
12 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
  • »
    »
    12 months ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    Not really. Consider the array [1, 3, 2], answer here is abs(1 — 3) + abs(3 — 2) = 3. Whereas an-a1 = (2 — 1) = 1.

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

[REDACTED]

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

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

→ Reply
»
12 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