Unofficial Editorials October Long Challenge (Part 2)

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 

6

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.

7 Likes

@taran_1407, Regarding your solution in CHEFGP, Am I right that you didn’t use the x and y? I would like to check if string “aaaaaaaaaaaaabbb” x=2 y=1 would fall in Case # 1.

Mate

I did use x and y, the solution is impossible without using x and y.

But i happened to use variable a and b to denote x and y respectively. ‘A’ and ‘B’ denote number of apples and bananas in given distribution. ‘a’ and ‘b’ is same as x and y given in problem…

Hope this clarifies… feel free to ask :slight_smile:

@taran_1407 , Oh. Okay. :slight_smile: Thanks for clarifying my doubt. :slight_smile:

No problem :slight_smile:

Can you please help me , I don’t know where I’m going wrong

I am maintaining variables lan and lbn which indicates the latest index which is not ‘a’ (lan) and similarly lbn. Then I’m just running a loop and trying to put an apple or banana or a kiwi. I’m running a loop until noa and no=0.

https://www.codechef.com/viewsolution/15857796

Basically

Your solution end up distributing more kiwis than exactly necessary because of incorrect case handling…

Read the above approach carefully…

Your code will work (i guess, not sure) only in 1st case as i described above, where noa > nob…

But on other cases, it is guaranteed to fail…

If u wanna see test cases your code fails at, see the sample input given

Just replace a and b with each other in every test case and swap x and y…

Hope that helps… :slight_smile:

Thanks for your time :slight_smile:

No problem at all :slight_smile:

For string aaaaaaabbbbbb : 7 'A’s and 6 'B’s

x = 4, y = 1

Your approach is to append x 'A’s and then 1 B

Result : aaaab

Now, we should fill the rest of the as AB :

Result : aaaabababab *b *b

But, the optimal answer should be ababababababa

1 Like

Mate, you may refer to my code. I append ‘a’ once every iteration while A> B, so after appending one ‘a’, A becomes equal to ‘b’.

I don’t append ‘a’ x times in one go. Rather i append one character at a time, just for the case u provided :slight_smile:

Thanks for pointing it out. I had already taken care of this.

Yes, you forgot to mention this point in the above editorial. Btw, editorials are nice.

@taran_1407 why this code is not working for marrays ?

https://www.codechef.com/viewsolution/15901305

&& u said that only max and the min value will give the ans.
but can’t we directly sort the arrays and calculate its min and max as i did?
As u have started from the n-1 th array and calculated its min and max
after that when u looped through n-2 to 0.
and find min and max for each ith array…then what u did to get the final answer i couldn’t understand…
can u please elaborate it.

1 Like

@worldunique

You cannot sort the array as you are under the constraint of “cyclic shift” . I believe the pair-relationship/compulsion (i.e. "If this element X is the first element of this, then element Y HAS to be the last element of the dish) will get lost. Had sorting been allowed then the question would have been tons simpler I believe.

1 Like

As @vijju said in comment below, you cannot sort the array, @worldunique

Take example Given array {4,2,3,5}

sorting will result in {2,3,4,5}

But cyclic shift means that you can transform array {4,2,3,5} to

{2,3,5,4} using one shift

{3,5,4,2} - two shifts

{5,4,2,3} - three shifts

Observe the difference between sorting and cyclic shifts

Feel free to ask anything…

Hey taran , can you give a more simplified , just the textual version of your approach for MARRAYS.

I have posted a separate editorial at this link, explaining my approach in detail

Mate, textual version will appear like greek, even to me!!!

A bit of line by line explanation is needed i believe

yes…now i get the error.

so you calculated min and max but keeping them in cyclic order and then checking max for each element one by one as per formula |x-y|*i and finally calculated the maximum result.

am i right?

Well, that’s the general idea. :slight_smile: