无法理解算法 [英] Unable to understand algorithm
问题描述
这是问题
的链接 https://www.hackerrank.com/challenges/等于
我阅读了这篇社论，却听不懂。而且，如果您没有在hackerrank上建立任何帐户，那么您肯定不会看到它的社论，所以这里有一些社论。
相当于说，克里斯蒂可以将一个同事的
的巧克力拿走1、2或5，而其他人的巧克力则保持原样。
让我们考虑减少同事的巧克力作为一项操作。为了最大程度地减少操作次数，我们应尝试使每个同事的巧克力数量等于组中的最小巧克力数量（最小值）。我们必须将第i个人A [i]的巧克力数量减少（A [i]-分钟）。令此值为x。
这可以在k个操作中完成。
k = x / 5 +（x％5）/ 2 +（x％5）％2
并且从这里我无法理解
让f（min）求和对所有同事执行的操作，以将他们的每块巧克力减少到最少
。但是，有时f（min）可能不会总是给出正确的答案。
f（min）> f（min-1）
f（min）< f（min-5）
f（min-5）需要N个操作大于f（min），其中N是同事的数量
。因此，如果
A = {min，min-1，min-2，min- 3，min-4}
然后f（A）< = f（min）< f（min-5）
有人可以帮助我了解为什么要检查f（min ），f（min-1），...，f（min-4）
考虑案例 A = [1,5,5]
正如社论所说，直观地认为更改为最佳选择 A 到[1,1,1]有4（2减2）个运算，但最好将它更改为[0,0,0]并有3（1减1，2减去5）运算。
因此，如果 min =数组中的最小元素，则将所有元素更改为 min 可能不是最佳选择。
您不了解的部分是为了满足这种情况，我们知道 min 可能不是最佳的，因为 min-x 可能更好，但是 x 有多大？是 4 。社论说如果我们知道 x 最多为4，我们可以简单地用蛮力 min ， min-1 ... min-4 可以看到哪一个是最小值而不必考虑太多。
为x< = 4进行推理（不证明！）
如果x> = 5，则您必须在所有元素上至少使用额外的N型3（负5）运算，这绝对不值得。
基本上，这与运算类型无关，这是因为您需要对所有元素使用相同的操作，这样做之后，问题并没有减少，当您想要使相对差异达到目标时，元素之间的相对差异仍然相同。 0，您只需花费 N 操作即可。
换句话说，如果x> = 5，则x-5必须更好选择目标，实际上x％5一定是最佳目标。
（以下为TL； DR部分：版本2）跳到La st部分如果您对证明不感兴趣
在编写原始解决方案的过程中，我怀疑 x< = 2 确实如此，并且我尝试在HackerRank上提交代码，该代码仅检查 f（min-x）的最小值，其中x< = 2 ，并且它被接受。
我正式声明
如果5>（z分钟） ％5> = 3并且（z-min'）％5 == 0，则F（min'）< F（min）
其中，对于x <= 2，min'= min-x，F（k）=元素z变为k的最小运算次数
（请注意，我使用 F（），它与 f（）的含义不同）
以下是证据：
如果（z-min）％5 = 1或2 ，则至少需要（z-min）/ 5 + 1 操作，而（z-min'）％5 == 0需要（z-min'）/ 5 =（z-min）/ 5 +1 操作，表示 F（min'）= F（min）
If （z- min）％5 == 3或4 ，则它至少需要（z-min）/ 5 + 2 运算，而（z-min'）％5 == 0需要（z-min'）/ 5 =（z-min）/ 5 + 1 运算，表示 F （分钟）< F（min）（或F（min'）= F（min）+1）
所以我们证明
如果5>（z-min）％5> = 3并且（z-min'）％5 == 0，则F（min'）< F（min）
其中min'= min-x
现在让我们证明的范围x
我们假设（z-min）％5> = 3和（z-min'） ％5 == 0 ，
so （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；如果x = 1，则（z-min）％5可以为4，以满足两个条件： 5> （z-min）％5> = 3和（z-min'）％5 == 0
因此我们一起显示
如果5>（z-min）％5> = 3且（z-min'）％5 == 0，则F（分钟'）< F（min）
，其中min'= min-x for x <= 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（min-2）= 3 + 10 = 13
/ p>
P = [2,10,10]，f（min）= 6，f（min-2）= 5
（TL的结尾； DR部分！）
已编辑
OMG黑客攻击的测试案例很弱！
故事是当我今天早上到达办公室时，我一直在思考这个问题，并认为我的代码中可能存在问题（已被接受！）
#include< cmath> #include< cstdio> #include< vector> #include< iostream> #include< algorithm>使用命名空间std; ，a [10005]，m ＝ 1 ＜＜ 28； int f（int m）{m ＝ max（0，m）； int cnt = 0; for（int i = 0; i
您看到问题了吗？
问题是 m = max（0，m）; ！
它确保 min-x 必须至少为0，但是，等等，我的上面的证明没有提及
请记住最初的问题是关于加法的，因此目标没有最大价值。虽然我们将问题建模为减，但目标也没有最小值（但我将其设置为0！）
尝试使用上面的代码：
130 3 3
它强制 min-x = 0，因此输出为4，但是答案应该是3
（如果我们使用添加模型，则目标应该是10，a [0]，a [2]上为+ 5，+在a [0]，a [1]上为5，在a [1]，a [2]上为+2）
所以一切都终于正确了（我认为。 。）当我删除行 m = max（0，m）; 时，它允许 min-x 获得否定并给出3作为正确的输出，当然新代码也将被启用...
Here is the link of problem https://www.hackerrank.com/challenges/equal
I read its editorial and unable to understand it. And if you are not make any account on hackerrank then surely you will not see it's editorial so here is some lines of editorial.
This is equivalent to saying, christy can take away the chocolates of one coworker by 1, 2 or 5 while keeping others' chocolate untouched.
Let's consider decreasing a coworker's chocolate as an operation. To minimize the number of operations, we should try to make the number of chocolates of every coworker equal to the minimum one in the group(min). We have to decrease the number of chocolates the ith person A[i] by (A[i] - min). Let this value be x.
This can be done in k operations.
k = x/5 +(x%5)/2 + (x%5)%2
and from here i unable to understand
Let f(min) be sum of operations performed over all coworkers to reduce each of their chocolates to min. However, sometimes f(min) might not always give the correct answer. It can also be a case when
f(min) > f(min-1)
f(min) < f(min-5)
as f(min-5) takes N operations more than f(min) where N is the number of coworkers. Therefore, if
A = {min,min-1,min-2,min-3,min-4}
then f(A) <= f(min) < f(min-5)
can someone help me to understand why this is necessary to check f(min),f(min-1),...,f(min-4)
Consider the case A = [1,5,5]
As the editorial said, it is intuitive to think it is optimal to change A to [1,1,1] with 4 (2 minus 2) operations, but it is better to change it to [0,0,0] with 3 (1 minus 1, 2 minus 5) operations.
Hence if min = minimum element in array, then change all elements to min may not be optimal.
The part you do not understand is to cater this situation, we know min may not be optimal as min-x maybe better, but how large is x? Well it is 4. The editorial is saying if we know x is at most 4, we can just simply brute force min, min-1...min-4 to see which one is the minimum without thinking too much.
Reasoning (Not proof!) for x <= 4
If x >= 5, then you have to use at least extra N type 3 (minus 5) operations on all elements which is definitely not worth.
Basically it is not a matter of the type of operation, it is because you need to use same operation on ALL elements, after you do that, the problem is not reduced, the relative difference between elements is still the same while you aim to make the relative difference to 0, you cost N operations for nothing.
In other words, if x >= 5, then x-5 must be a more optimal choice of goal, indeed x%5 must be the best goal.
(Below is TL;DR part: Version 2) Jump to the Last Section If You are Not Interested in the proof
In the process of writing the original solution, I suspect x <= 2 indeed, and I have tried to submit a code on HackerRank which only check minimum for f(min-x) where x <= 2, and it got ACed.
More formally, I claim
If 5> (z-min)%5 >= 3 and (z-min')%5==0, then F(min')< F(min) where min'=min-x for x<=2, F(k) = min # of operation for element z to become k
(Beware the notation, I use F(), it is different meaning from f() in the question)
Here is the proof:
If (z-min)%5 = 1 or 2, then it needs at least (z-min)/5 + 1 operations, while (z-min')%5 == 0 needs (z-min')/5 = (z-min)/5 + 1 operation, means F(min') = F(min)
If(z-min)%5 == 3 or 4, then it needs at least (z-min)/5 + 2 operations, while (z-min')%5 == 0 needs (z-min')/5 = (z-min)/5 + 1 operation, means F(min') < F(min) (or F(min') = F(min)+1)
So we proof
If 5> (z-min)%5 >= 3 and (z-min')%5==0, then F(min')< F(min) where min'=min-x
Now let's proof the range of x
As we assume (z-min)%5 >= 3 and (z-min')%5 == 0,
so (z-min')%5 = (z-min+x)%5 = ((z-min)%5 + x%5)%5 == 0
Now, if x >= 3, then (z-min)%5 can never be >= 3 in order to make ((z-min)%5 + x%5)%5 == 0
If x = 2, then (z-min)%5 can be 3; if x = 1 then (z-min)%5 can be 4, to meet both conditions: 5> (z-min)%5 >= 3 and (z-min')%5==0
Thus together we show
If 5> (z-min)%5 >= 3 and (z-min')%5==0, then F(min')< F(min) where min'=min-x for x<=2
Note one can always generate array P, such that f(min') < f(min), as you can always repeat integer which can be improved by such method until it out number those integers cannot. This is because for elements that cannot be improved, they will always need exactly 1 more operations
eg: Let P = [2,2,2,10] f(min) = 0+3 = 3, f(min-2) = 3+2 = 5
Here 10 is the element which can be improved, while 2 cannot, so we can just add more 10 in the array. Each 2 will use 1 more operation to get to min' = min-2, while each 10 will save 1 operation to get min'. So we only have to add more 10 until it out number (compensate) the "waste" of 2:
P = [2,2,2,10,10,10,10,10], then f(min) = 0+15 = 15, f(min-2) = 3+10=13
or simply just
P = [2,10,10], f(min) = 6, f(min-2) = 5
(End of TL;DR part!)
EDITED
OMG THE TEST CASE ON HACKERRANK IS WEAK!
Story is when I arrive my office this morning, I keep thinking this problem a bit, and think that there maybe a problem in my code (which got 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;
}
Can you see the problem?
The problem is m = max(0, m); !
It ensure that min-x must be at least 0, but wait, my proof above did not say anything about the range of min-x! It can be negative indeed!
Remember the original question is about "adding", so there is no maximum value of the goal; while we model the question to "subtracting", there is no minimum value of the goal as well (but I set it to 0!)
Try this test case with the code above:
1
3
0 3 3
It forces min-x = 0, so it gives 4 as output, but the answer should be 3
(If we use "adding" model, the goal should be 10, with +5 on a[0],a[2], +5 on a[0],a[1], +2 on a[1], a[2])
So everything finally got right (I think...) when I remove the line m = max(0, m);, it allows min-x to get negative and give 3 as a correct output, and of course the new code get ACed as well...
这篇关于无法理解算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
