Chef and subarrays help

1

can somebody help me solve the chef and subarrays problem ? I tired this approach
https://www.codechef.com/viewsolution/46828687
my idea has been find maximum frequency of sums and finally total number of subarrays of size k - maximum frequency

2

just try to make all k length subarray equal and thats all

3

Sorry I think i implemented what you saying but where i am going wrong i dont know

4

if anyone could provide some edge test cases, it would be really helpful.

5

consider array with elements a,b,c,d,e,f,g,h,i,j.
let k =3; n=10
since , sum of subarray should be constant.
now according to question, a +b +c = b +c +d
that implies , a=d
similarly , d +e +f = e +f +g
that implies, d=g.

conclusion: a[i] should be equal to a[i-k] ,i.e , a[i]=a[i-k].

Hope, it helps.

Code:

6

Consider this case:

9 3
1 5 5 1 2 3 1 2 3

Your approach gives 3, the right answer is 2 (change both the 5’s to 2 and 3).

7

https://www.codechef.com/viewsolution/46822510
@darshancool25 @taran_1407
Please see my solution and tell me where is the mistake that failed the test cases.
Brief of what I have done,
Basically I run a loop k times and in every iteration I add element to the arrayList and then sort it. I sort it so that I can find the maximum frequency in the array and that I added the size of the arraylist and subtracted the highest frequency.

Please please please someone tell me where the mistake is.

8

Not sure where your code is going wrong. I am not familiar with JAVA, though I can suggest use HashMap (better way to store frequency of elements).

9

can anyone please help me why i am getting WA or this is wrong approach
@darshancool25

#include<bits/stdc++.h>
using namespace std;
    int arr[1000000];
     int arrsum[1000000];
    int main(){
int t;
cin>>t;
while(t--)
{
    int n,k;
    cin>>n>>k;

    for(int i=0;i<n;i++)
    cin>>arr[i];
   
    int kk=0;
    
    for(int i=0;i<n;i++)
    {   if((n-i)<k)
        break;
        for(int j=i;j<i+k;j++)
        {
        arrsum[i]+=arr[j];
            
        }
        kk++;
    }
 
    sort(arrsum,arrsum+kk);
 
    int diff=-1;
    for(int i=0;i<kk;i++)
    {
        if(arrsum[i]!=arrsum[i+1])
        diff++;
    }
    cout<<diff<<endl;
}
    
}
10

Can you tell what you are trying to do in your code ? Like whats your approach ?

11

I wrote same code in c++ and it got accepted.
c++ code CodeChef: Practical coding for everyone
java code CodeChef: Practical coding for everyone
pls tell me what is wrong. Both of the above code is exacty same.
Can anyone pls help me

12

@darshancool25
i am storing the array element upto next kth index into new array (arrsum) and then i sort the array and i am counting the no of different element (sum of kth element) in arrsum and count that that is the output it passes the given test case also

13

Maybe its an indication for you to switch to JAVA :sweat_smile:. Also on serious note someone whos used to coding in JAVA should be able to help. I am not !

14

Looks like you have complicated things, here’s my simple explanation that should help you. Our target is to modify the array such that every k length subarray has same sum, hence same set of elements, which implies elements must repeat themselves in cyclic fashion (i.e every kth element must be same, eg- for k=4, A = [a,b,c,d,a,b,c,d,.....]). Done ! Problem solved. Just use a map to keep a track of frequency of elements and use it to calculate the least number of modifications.