DIFFICULTY:
Easy
PREREQUISITES:
Adhoc , Implementation
PROBLEM:
Given two integers o1,o2 and an array A of size o1*o2 which contains 0s and 1s. Assuming the array to be circular , find out if it’s possible to partition the array into o1 blocks such that size of each block is o2 and more than half of these blocks have 1s as the winning(majority) element.
EXPLANATION:
Subtask 1:
Consider N=o1*o2 .
So the most straightforward way is to iterate over 1 to N and assuming that this is the starting of the first block, we partition the array into o1 blocks of size o2 each. After partitioning the array, for each block check which element is the winning one. And finally if the count of blocks in which 1 wins is greater than o1/2 then we have successfully found out one of the required configurations. As the time required to build those blocks and check the winning condition is O(N) and we assume each position as the starting position for the first block one by one, so the time complexity is O(N^2).
This solution gives us 10 pts.
Subtask 2:
The above solution can be optimised by the observation that it’s redundant to consider each position as the starting position for the first block because if the starting position of the first block becomes greater than o2 then this means that we are not talking about the first block anymore as there surely exist a block whose starting position is smaller than o2 and that block will be the first one. So even if we iterate only from 1 to o2 to consider them as the starting positions, even then we can find the solution by the same method as above. Time complexity is O(o2*N).
This solution gives us 30 pts .
Subtask 3:
Lets try to come up with a solution where there’s no need to build the partition configuration multiple times. Basically we will update our old configuration to build the next one in lesser time, lets see how. Let’s have a look at the first configuration that will be built : Starting of the first block will be 1, Starting of the second block will be 1+o2, Starting of the third block will be 1+2*o2 …. Starting of the o1 block will be 1+(o1-1)*o2. Good, now let’s store the Start indexes of each block in an array START and sum of elements of each block in an array SUM where START[i] and SUM[i] denotes starting index and sum of the ith block respectively. Both of these arrays can be built in O(N) time.
Updating previous data to build the 2nd configuration’s data :
Pseudo Code :
For i=1 ..o1-1
{
SUM[i]=SUM[i]-A[START[i]];
SUM[i]=SUM[i]+A[START[i+1]];
}
SUM[o1]=SUM[o1]-A[START[o1]];// handle the last block separately
SUM[o1]=SUM[o1]+A[START[1]];
For i=1 ..o1
{
START[i]++;
}
So updating configuration part is done O(o1) time. Now to check if the configuration is the good one iterate over the blocks and check if SUM[i]>o2-SUM[i] i.e. number of 1s are greater than 0s and if more than half of these blocks satisfy this then we have found out the solution else keep updating the configuration and keep checking if the config is good one or not. We will update the configuration at max o2 times as discussed in previous subtask and updation and checking is done in O(o2) time. Hence the time complexity is O(o1*o2). Good enough to give 100 pts. If you are unclear about the configuration thing then try to consider this as sliding of blocks one position at a time in the circular array.
Time Complexity :
O(O1*O2)