Hello Guys

This is the part 2 of **three** posts of unofficial editorials for October Long Challenge.

For Solutions of problems PERFCONT, MEX and/or CHEFCOUN, click here.

For Solutions of problems CHEFCCYL and/or SHTARR, click here

This post has editorials for problems **CHEFGP and MARRAYS**

### Problem CHEFGP

### Problem Difficulty : Easy

#### Problem Explanation

Given a distribution of apple and banana among people and two integers a and b, we need to distribute apples and bananas such that no (a+1) consecutive people get apple and no (b+1) consecutive people get bananas.

If this is not possible with given apple and bananas, we can distribute additional kiwis (kiwis are costly, so try using as less as possible).

#### Solution

First thing, the given distribution is of no use to us except the number of apples and bananas to be distributed.

So, first count number of ‘a’ and ‘b’ in given distribution, say A and B.

The approach i used here is:

### Case 1: A>B

while(A>B)

Distribute a apples, followed by 1 banana (or kiwi in case all bananas are distributed)

(i.e. append ‘a’ a times to output string, followed by one ‘b’ (if B > 0) or ‘*’. decrement A by a, B by 1 if B>0)

Then distribute remaining Apples and bananas as ababab… till A==0 and B == 0;

(i.e. append “ab” A times to output string.)

### Case 2: A < B

while(A<B)

Distribute b bananas, followed by 1 apple (or kiwi in case all apples are distributed)

(i.e. append ‘b’ b times to output string, followed by one ‘a’ (if A > 0) or ‘*’. decrement B by b, A by 1 if A>0)

Then distribute remaining Apples and bananas as ababab… till A==0 and B == 0;

(i.e. append “ab” A times to output string.)

## Case 3: A==B

Simply distribute as abababab… till A==0 && B == 0

(append “ab” A times to output string)

print output string.

Case 3 approach works for a=1 and b = 1.

So this will work for every value a >= 1 and b >= 1

Case 1 works because we always try to distribute as much as possible of apple which is present in greater amount, while taking care not to place more than **a** by distributing one banana or one kiwi (if banana are finished), thus using minimum number of kiwis.

Same goes for Case 2.

Here’s a link to my

```
[4]
#
### Problem [MARRAYS][5]
#
### Problem difficulty:Medium
#
#### Problem Explanation
Given an array of arrays, Maximize the following value
Summation (for i = 0 to i = N-2) += abs(A[i][last] - A[i+1][first]) *(i)
Allowed operations: Cyclic rotation within inner arrays of given arrays.
#### Solution
In this problem, My brute force solution got 100 points.
Amazed!! ryt...
Well, not entirely a brute force :D, but similar to one.
Created a Mapping array (LinkedHashMap in java) to store answers in following way
map[i] contains Key x mapped to value L means that Maximum answer from array N-1 to array i+1, keeping ith array in such an order that x is the first element of ith array.
Mapping here serves the purpose of weeding out trouble of handling duplicate values in array, as well as efficiency.
//The beginning
Inserted into map[N-1] two mappings
minimum value in (N-1)th array mapped to 0
maximum value in (N-1)th array mapped to 0
//because only the maximum or minimum value can give a larger answer when using in absolute operations.
int[] removal = new int[1e6+1] //removal array used to remove useless entries from map
loop from i = N-2 to i = 0{outer loop
//A[i] denote length of ith array
int min = 1e6+1, max = 0; // these store minimum and maximum values of next_value variable
for int j = 0 to j = A[i]-1 { //inner loop
int currentValue = A[i].get(j);
if(j == A[i]-1)nextValue = A[i].get(0);
else nextValue = A[i].get(j+1)
min = Min(min, nextValue);
max = Max(max, nextValue);
for every entry e in map[i+1]{ //loop l1
put in map[i] mapping from key (nextValue) to value (Max( map[i].getOrDefault(nextValue), abs(e.key - currentValue)*(i+1) + e.value;
));
}//end of loop l
}//end of inner loop
// Now the most important part: removing useless entries from map[i], so as to improve time complexity to pass the time limit
long minAns = map[i].get(min), maxAns = map[i].get(max);
//getting best answers mapped to minimum key and maximum key in map[i]
int r = 0 // setting removable entries to 0
for Entry e in map[i]{
if(e.key != min && e.key != max && e.value <= minAns && e.value <= maxAns)removal[r++] = e.key;
//if any value in mapping has answer smaller than answers mapped to both minimum key and maximum key in map[i], there's no way that this entry can get greater answer. So discarding these values.
}
//Now removing entries
for(int k = 0; k< r; k++)map[i].removal(removal[k]);
}end of outer loop
The final answer is the maximum value stored in map[0];
There is a recursive solution too, which i leave as a quest today for my readers..
The reason above algorithm works because it considers every possible permutation, discarding useless entries immediately so as to ensure that time complexity doesn't shoot up.
Still, i feel the official editorial for this problem deserves a look...
Link to my
```

In case you still find this problem difficult, see this

Next problems are discussed in Unofficial Editorial Part 3.

Keep Coding. Feel free to ask anything.