same
3 things need to be corrected:
1.Convert int to long
2. Formula is M(M+1)/2 you have written M(M-1)/2
3.Substract minsum from count as number of 1’s in minsum are already taken so we need to remove those from total 1’s.
Just curious, Can this problem be solved using DP?
1 Like
https://www.codechef.com/viewsolution/44033600
Can someone tell me why am i getting TLE in this solution
I think so, but time complexity wouldn’t remain same, I guess.
2 Likes
for i in range(N-K+1):
a.append(A[i:i+K])
For K = N/2 and N = 2\times10^5, the number of instructions you perform in this loop will be
(N - K + 1) \times (K), viz., (10^5 + 1) \times 10^5 or, simply, 10^{10}. Hence, TLE.
I wonder you should also get RE because you are appending the slices of the given list, which should exceed the memory limits for worst case input as discussed above.
3 Likes
Really Nice Mathematical Formulation of Problem
I have used the prefix sum method to find the minimum number of 1’s in subarray of length k .
You can check it here 
code
same
please tell me where i am wrong in this code defalut test cases running fine
import java.util.*;
import java.io.*;
class CodeChef {
public static void main(String[] args) throws java.lang.Exception {
// Scanner scn = new Scanner(System.in);
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int tc = Integer.parseInt(bf.readLine());
while(tc-- > 0 ){
String line[] = bf.readLine().split(" ");
int n= Integer.parseInt(line[0]);
int k= Integer.parseInt(line[1]);
int ssf[]= new int[n];
line = bf.readLine().split(" ");
ssf[0]=line[0].charAt(0)-'0';
for(int i =1 ; i < line.length;i++){
ssf[i]= ssf[i-1]+line[i].charAt(0)-'0';
}
int minWindow = k ;
for(int i= k-1; i< line.length;i++){
int prev = i-k>=0 ? ssf[i-k]: 0;
minWindow =Math.min(ssf[i]-prev, minWindow );
}
// System.out.println("min windows is : "+minWindow);
// System.out.println("number of one : "+ssf[line.length-1]);
int ans =( (minWindow *(minWindow+1)) / 2) + ssf[line.length-1]-minWindow;
System.out.println(ans);
}
}
}
One of the reason the code is getting W A might be the range of the cost. Please see to it.
Thanks
1 Like
check the range of cost. Hope it helps !
Yeah, time complexity wouldn’t remain same.
But can you tell you how we can solve using DP?
Actually I didn’t undertstand can you please elaborate . In my opinion my code is working fine under the given constraints . Can you project me any testcase where my code might be failing
What he says is, you are using int. But the solution requires the usage of long. So, it is causing WA.
1 Like
It would be great if anyone helps me out with my submission. It is giving WA. I’m not able to figure it out.
https://www.codechef.com/viewsolution/44062991
Here’s the submission link
I even tried without the long long, but still got WA
Your code fails in first test-case :
1
5 3
1 0 1 0 1
Expected O/P :
3
Your O/P :
4
Hey, i am able to pass all the sample cases but still, it showing me wrong and can anyone plz tell me is there any special case I’m missing or there is any mistake in my logic?
#include
using namespace std;
int main() {
long long int t;
cin>>t;
while(t>0){
long long int n;cin>>n;long long int k;cin>>k; long long int arr[n]; long long int count=0;long long int b=0;long long int sum=0;long long int minsum=1000000;
for(long long int i=0;i<n;i++){
cin>>arr[i];
if(i==0)b=arr[0];
if(i<k){sum=sum+arr[i];}
else{
if(sum<minsum)minsum=sum;
sum=sum-b;b=arr[i];sum=sum+arr[i];
}
if(arr[i]==1)count++;
}
if(count==0)cout<<0<<endl;
else if(count==1)cout<<1<<endl;
else if(k==n)cout<<count*(count+1)/2<<endl;
else{
cout<<(minsum*(minsum+1)/2)+(count-minsum)<<endl;
}
t--;}
return 0;
}