Невозможно понять алгоритм

Question

Вот ссылка проблемы https://www.hackerrank.com/challenges/equal

Я прочитал его редакционную и не в состоянии понять это. И если вы не делаете никаких учетных записей на hackerrank, то, несомненно, вы не увидите, что это редакционная статья, так что вот несколько строк редакционной статьи.

Это равносильно тому, Christy может забрать конфеты из один 1 сотрудника, 2 или 5, сохраняя при этой шоколаде чужого нетронутым.
Давайте рассмотрим, как можно уменьшить шоколад коллеги в качестве операции. Чтобы свести к минимуму количество операций, мы должны попытаться сделать количество шоколадных конфет каждого сотрудника равным минимальному количеству в группе (мин). Нам нужно уменьшить количество конфет i-го человека A [i] на (A [i] - min). Пусть это значение равно x.

This can be done in k operations. 

k = x/5 +(x%5)/2 + (x%5)%2 

и здесь я не мог понять

Пусть F (мин) быть сумма операций, выполняемых по всем коллегам, чтобы уменьшить каждого из своих конфет мин. Однако иногда f (min) может не всегда давать правильный ответ. Она также может быть случай, когда

f(min) > f(min-1) 

f(min) < f(min-5) 

, как F (мин-5) принимает N операций больше, чем F (мин), где N является числом из сослуживцев. Поэтому, если

A = {min,min-1,min-2,min-3,min-4} 
then f(A) <= f(min) < f(min-5) 

может кто-то помочь мне понять, почему это необходимо для проверки F (мин), F (мин-1), ..., F (мин-4)

Answer 1

Рассмотрите случай A = [1,5,5]

Как было сказано в редакционной статье, интуитивно понятно, что оптимально изменить A на [1,1,1] с помощью 4 (2 минус 2) операций, но лучше изменить его на [ 0,0,0] с 3 (1 минус 1, 2 минус 5) операций.

Следовательно, если min = minimum element in array, то изменить все элементы на min может быть не оптимальным.

Часть, которую вы не понимаете, должна удовлетворять этой ситуации, мы знаем, что min может быть не оптимальным, поскольку min-x может быть лучше, но насколько велика x? Ну это . Редакция говорит, что если мы знаем, что x не более 4, мы можем просто просто грубой силой min, min-1 ... min-4, чтобы узнать, какой из них является минимальным, не задумываясь слишком много.

Рассуждения (не доказательство!) Для й < = 4

Если х> = 5, то вы должны использовать операции по крайней мере дополнительного N типа 3 (5 минуса) на все элементы, которые, безусловно, не стоимость.

В принципе, это не относится к типу операции, потому что вам нужно использовать такую ​​же операцию на ВСЕХ элементах, после этого проблема не будет уменьшена, относительная разница между элементами по-прежнему остается то же самое, пока вы нацелены на то, чтобы сделать относительную разницу в 0, вы стоите N операций для ничего.

Другими словами, если x> = 5, то x-5 должен быть более оптимальным выбором цели, ведь x% 5 должна быть лучшей целью.

---

(Ниже TL; DR часть: Version 2) Перейти к последнему разделу Если вы не заинтересованы в доказательстве

В процессе написания оригинального решения, я подозреваю, х < = 2 действительно, и я попытался отправить код на HackerRank, который проверяет минимум только на f(min-x) where x <= 2, и он получил ACed.

Более формально, я требую

Если 5> (г-мин)% 5> = 3 и (г-мин ')% 5 == 0, то Р (мин') < Р (мин) , где мин = мин-х при х < = 2, Р (к) = мин # операции для элемента г, чтобы стать K

(Осторожно обозначения, я использую F(), она отличается значение от f() в вопросе)

Вот доказательство:

Если (z-min)%5 = 1 or 2, то необходимо, по крайней мере (z-min)/5 + 1 операций, в то время как (z-min')%5 == 0 needs (z-min')/5 = (z-min)/5 + 1 операции, средства F(min') = F(min)

Если (z-min)%5 == 3 or 4, то необходимо, по крайней мере (z-min)/5 + 2 операций, в то время как (z-min')%5 == 0 needs (z-min')/5 = (z-min)/5 + 1 операции, средства F(min') < F(min) (or F(min') = F(min)+1)

Таким образом, мы доказательство

Если 5> (г-мин)% 5> = 3 и (z- мин ')% 5 == 0, то F (мин') < F (мин) где мин = мин-х

Теперь давайте доказательства диапазон x

Как мы предполагаем, (z-min)%5 >= 3 and (z-min')%5 == 0,

так (z-min')%5 = (z-min+x)%5 = ((z-min)%5 + x%5)%5 == 0

Теперь, если x >= 3, то (z-min)%5 никогда не может быть> = 3 для того, чтобы сделать ((z-min)%5 + x%5)%5 == 0

Если x = 2, то (z-min)% 5 может быть 3; если х = 1, то (г-мин)% 5 может быть 4, чтобы удовлетворить обоим условиям: 5> (z-min)%5 >= 3 and (z-min')%5==0

Таким образом, мы вместе показывают

Если 5> (г-мин)% 5> = 3 и (г-мин ')% 5 == 0, то Р (мин') < F (мин), где мин = мин-х при х = 2 <

---

Примечание один всегда может генерировать массив P, такой, что f (min ') < f (min), так как вы всегда можете повторить целое число, которое можно улучшить с помощью такой метод до тех пор, пока его число не будет целым числом. Это связано с тем, что для элементов, которые не могут быть улучшены, им всегда потребуется ровно еще 1 операция

например: Пусть P = [2,2,2,10] f (min) = 0 + 3 = 3, f (min -2) = 3 + 2 = 5

Здесь 10 - это элемент, который можно улучшить, а 2 не может, поэтому мы можем просто добавить больше 10 в массив. Каждые 2 будут использовать еще 1 операцию, чтобы добраться до min' = min-2, в то время как каждый 10 сэкономит 1 операцию, чтобы получить min'.Поэтому нам нужно добавить еще 10 до тех пор, пока оно не выберет количество (компенсирует) «отходы» 2:

P = [2,2,2,10,10,10,10,10], затем f (min) = 0 + 15 = 15, F (мин-2) = 3 + 10 = 13

или просто

Р = [2,10,10], F (мин) = 6, F (мин-2) = 5

(Конец TL;! Д.Р. часть)

---

EDITED

OMG ИСПЫТАТЕЛЬНЫЙ ДЕЛО НА HACKERRANK СЛАБОЙ!

история, когда я приезжаю в мой офис сегодня утром, я продолжаю думать эту проблему немного, и думаю, что может быть проблема в моем коде (который получил Aced!)

#include <cmath> 
 
#include <cstdio> 
 
#include <vector> 
 
#include <iostream> 
 
#include <algorithm> 
 
using namespace std; 
 

 
int T, n, a[10005], m = 1<<28; 
 

 
int f(int m){ 
 
    m = max(0, m); 
 
    int cnt = 0; 
 
    for(int i=0; i<n;i++){ 
 
     cnt += (a[i]-m)/5 + (a[i]-m)%5/2 + (a[i]-m)%5%2; 
 
    } 
 
    return cnt; 
 
} 
 

 
int main() { 
 
    cin >> T; 
 
    while(T--){ 
 
     m = 1<<28; 
 
     cin >> n; 
 
     for(int i=0; i<n;i++) cin >> a[i], m = min(m,a[i]); 
 

 
     cout << min(min(f(m), f(m-1)),f(m-2)) << endl; 
 
    } 
 
    return 0; 
 
}

У вас проблема?

Проблема m = max(0, m);!

Это гарантирует, что min-x должно быть не менее 0, но подождите, мое доказательство выше ничего не говорит о диапазоне min-x! Это может быть отрицательно!

Помните, что исходный вопрос касается «добавления», поэтому нет максимального значения цели; в то время как мы моделируем вопрос «вычитая», не существует минимальное значение цели, а также (но я поставил его на 0!)

Попробуйте этот тест, с вышеуказанным кодом:

1 
 
3 
 
0 3 3

это заставляет min-x = 0, так что это дает 4 в качестве выходного сигнала, но ответ должен быть 3

(Если мы используем «добавление» модель, цель должна быть 10, с +5 к [0 ], a [2], +5 на a [0], a [1], +2 на [1 ], a [2])

Так что все, наконец, получило право (я думаю ...), когда я удаляю строку m = max(0, m);, она позволяет min-x получить отрицательный результат и дать 3 как правильный результат, и, конечно, новый код get ACed также ...