I am practicing algorithms for the last couple of days and I came across this question, the gist of which is:
Given apples and oranges arranged in a circle indexed form 1 to n , where n is an odd number(we know which ones apple and which ones orange), divide these into k contiguous groups each havind odd number of fruits such that most of the groups have more apples than oranges. Also, the arrangement can be such that a group can contain fruits of indices (n-3, n-2, n-1, n, 1 , 2, 3).
This appears like the linear partition problem to me, but the circular arrangement confuses me. Also, I was thinking of masking Apples as 1 and Oranges as -1 so that it’s easy to calculate the which one is higher in the group( if sum is +ve, then apples are higher else oranges). Also, I observed that k must be an odd number as n is an odd and each of the k groups have odd fruits, so sum of odd number of odds is an odd number.
We have to maximize the sum of each of the groups in this case right?
It would be great if someone can help out.
Thanks a lot!!!