My solution is failing 3 tasks
Solution: 57987419 | CodeChef
can anybody please help? i am unable to find the failing testcases.
My solution passes all test cases (even the ones in the discussion above). But unable to understand why it would fail only the first subtask. Any help is appreciated
// use prfix sum and factorisation
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
// your code goes here
ll int t;
cin >> t ;
while(t--){
ll int n ;
cin >> n;
vector<ll int> pref(n) , a(n) ;
for(auto &x : a) cin >> x ;
// prefix sum
pref[0] = a[0] ;
for(ll int i=1;i<n ;i++){
pref[i] = a[i] +pref[i-1] ;
}
// sum of all elements ;
int sum = pref.back() ;
if(sum==0){
ll int ans = n ;
for(auto x: pref){
ans -= (x==0) ;
cout << ans <<"\n" ;
}
}else{
ll int sign = (sum > 0 ? 1: -1) , ans = n-1 ;
sum = llabs(sum) ;
for (ll int i= 1; i*i <= sum ;i++){
if(sum %i) continue ;
ll int len1 = i , elem1 = (sum /i )*sign ;
ll int len2 = sum/i , elem2 = i*sign ;
auto possible = [&](ll int elem ,ll int len){
ll int cnt = 0 ;
for(auto x : pref) {
if(x== (elem*(cnt+1))) cnt++ ;
}
return cnt >= len ;
};
if(possible(elem1,len1)) ans = min(ans,n-len1) ;
if(possible(elem2,len2)) ans = min(ans, n- len2) ;
}
cout << ans <<"\n" ;
}
}
return 0;
}
this is failing for1subcase any help is appreciated
This testcase
1
3
0 -1 1
According to the editorial answer is 2, actual answer is 1.
EDIT: Implementations seem to handle it, might want to update the language in the editorial
Can anyone provide the proof for “maximum number of factors of a number X = O(X^1/3)”?
Can anyone help me how to correct the code so that it passes the test case 1.
As told in the editorial , I have included the condition >= but still not able to pass subtask one.
Please help.
Hey @rehankhan123
Thanks for asking your doubt.
for (int j = 0; j < n; j++)
{
if (pre[j] == (count + 1) * eachsum)
{
count++;
}
}
In this section of your code you have to write
for (int j = 0; j < n; j++)
{
if (pre[j] == (count + 1) * eachsum)
{
count++;
}
if(count==nsubarray)
break;
}
As count cannot be greater than y.