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.
