minimum and maximum
https://www.codechef.com/JULY19B/problems/MMAX
a little bit hint will be great. what is wrong with my I am getting WA
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.
a little bit hint will be great. what is wrong with my I am getting WA
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.
Topic archived. No new replies allowed.