C++

Forum

 
Absolute maximum difference

gokuluffy (9)
Write your question here.
Source:- https://www.codechef.com/JULY19B/problems/MMAX

I did solve this problem but it has been accepted only partially can any one help me to make it correct, so far I know my logic is correct and I am doing some silly mistake.


Chef has K chocolates and he wants to distribute them to N people (numbered 1 through N). These people are standing in a line in such a way that for each i (1≤i≤N−1), person i and person i+1 are adjacent.

First, consider some way to distribute chocolates such that for each valid i, the number of chocolates the i-th person would receive from Chef is Ai and the sum S1=∑N−1i=1|Ai−Ai+1| is minimum possible. Of course, each person must receive a non-negative integer number of chocolates.

Then, Chef wants to create a new sequence B1,B2,…,BN by rearranging (permuting) the elements of the sequence A1,A2,…,AN. For each valid i, the number of chocolates the i-th person actually receives from Chef is Bi. Chef wants to distribute the chocolates (choose B1,B2,…,BN by permuting the sequence A and give Bi chocolates to the i-th person for each valid i) in such a way that S2=∑N−1i=1|Bi–Bi+1| is maximum possible. You need to find the maximum value of S2.

It is guaranteed that S2 does not depend on the exact choice of the sequence A1,A2,…,AN, as long as it is a sequence that minimises S1.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
long long valueContainer[100000+2];

cin>>n;
cin>>k;

max1 = 0, max2 = 0;


for(iterator=0; iterator < n; iterator++)
{
    valueContainer[iterator] = k/n;
}
for(iterator = 0; iterator < k%n; iterator++)
{
    valueContainer[iterator]++;
}

sort(valueContainer, valueContainer+n); 

long long fs = 0, sc = n - 1;

vector <long long> ValueOne, ValueSec;

while ( fs <= sc ) {
    ValueOne.push_back(valueContainer[fs]);
    ValueSec.push_back(valueContainer[sc]);
    if ( fs != sc ) ValueOne.push_back(valueContainer[sc]), ValueSec.push_back(valueContainer[fs]);
    fs++, sc--;
}


for ( long long i = 0; i < n - 1; i++ ) {
    max1 += abs(ValueOne[i] - ValueOne[i + 1]), max2 += abs(ValueSec[i] - ValueSec[i + 1]);
}

if(max1 > max2) cout<<max1; else cout<<max2; cout<<"\n";
ne555 (10692)
> so far I know my logic is correct
explain your logic


¿what datatype is `k'?
2 ≤ K ≤ 10^100,000
salem c (3685)
> so far I know my logic is correct and I am doing some silly mistake.
Your logic may be correct, and be acceptable on an infinite machine.

But all codechef problems (at least the hard part of them) require you to think up a better approach than "try every possible combination".

Trying every combination is what every kid with a keyboard can manage.

What sets you apart from the crowd is being clever with your analysis and making a program which works smarter.

And no, we're not here to do your thinking for you just for you to earn brownie points on a competition website.
dutch (2548)
Chef has K chocolates to lure N children ....

Why are you performing his evil computations?
Topic archived. No new replies allowed.