| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
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
Auto comment: topic has been updated by alaincr7 (previous revision, new revision, compare).
This should be easy one.
Bro, you just said a 2000 rated problem is easy. here, :skull :skull
It was sarcasm
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
Not really. Consider the array [1, 3, 2], answer here is abs(1 — 3) + abs(3 — 2) = 3. Whereas an-a1 = (2 — 1) = 1.
i thought it was ans = abs(a2-a1+a3-a2+...+an-an-1), but we're actually not adding all the values we're finding the max of all abs(a[i+1]-a[i])
[REDACTED]
https://www.codechef.com/problems/KEVIN
https://mirror.codeforces.com/problemset/problem/360/B
oh wow ... how did you find these problems ??
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)$$$
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.
Auto comment: topic has been updated by alaincr7 (previous revision, new revision, compare).