Code-overflow 1.2

problem1 link-problem2 link-
Asked in recent contest by nit calicut how to approch this problem please help???

https://www.codechef.com/viewsolution/37170973 quite clear ig if not i m sorry i will explain just ping me :slight_smile:

1 Like

can u tell me like which concept u have used? thanks

at ith postion what is max length u can make?
cases - any one j from 0-9 can be odd so just brute force it
need - let say 2,5,6 are odd in no upto ith pos so we require a postion where 2,5,6 were odd before

1 Like

i got it thanks :grinning:

I did not understand. Can you please explain in a bit more depth?

What is output for the problem Subarray And Array for this test case:
5 2
-3 -1 -2 3 5
-2 1

If 15, then why not 16?
(-3 + 3 + 5) + (-3 * -2 + 5 * 1) = 16
Maybe I’m missing something, correct me please.

as i said we will find max length ending at i
tot[i] is the total no. of i’s from 0 to i

now any no. from 0-9 can be odd let say it is j
if j is odd then all other should be even but let say 2,4,5 are not even
so we need a position k<i where only 2,4,5 are odd we are storing this pos in array b
there is a catch j can also be odd so either 2,4,5,j or 2,4,5 both the cases should be taken into account

1 Like

You have chosen complete subarray so add -1, -2 also which would give 13. Please note that you still need to add the elements which you multiplied with b[i]

Sorry, why I’ve to add -1 and -2 ? It’s from array B[].

Got it, totally missed that I have to take contiguous subarray, my bad.

Can you still help me how to do it? I could only score 20 pts with O(n^3) algorithm.

You can go for 100 directly using n * (1<<m) * 3 dp.

submit button dissapered after the contest

With a few optimisations and using compiler flags, I was able to get my O(n^2) solution passed.
https://www.codechef.com/viewsolution/37171413

  • The if(answer > n-i) statement is very important to avoid TLE.
  • The basic idea behind my solution is to maintain a set and a counter to count the number of mismatches upto now and keep updating the answer when there is only one mismatch.

Yeah, but exactly how??

/* Binod & Subarray /
/
Code Overflow 1.2*/

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define eb emplace_back
#define precision(n) cout << fixed << setprecision(n);
#define fast {ios_base::sync_with_stdio(false);cin.tie(NULL);}
int main()
{
long long int n,k,s,sum1=0;
cin>>n>>k>>s;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
sum1+=a[i];
}
sort(a,a+n);
if(k>=n)
{
cout<<-1<<endl;
return 0;
}
if(sum1<=s)
{
cout<<-1<<endl;
return 0;
}
long long int sum=0;
long long int cnt=0;
for(int i=n-1;i>=0;i–)
{
sum+=a[i];
cnt++;
if(sum>s)
{
break;
}
}
cout<<max(cnt,k+1)<<endl;
return 0;

}
why this code is working…
what’s the logic behind this

Simpul Koshan V2 how to solve this one

how to solve simpul koshan?

a simple logic of placing the range queries according to their heights and then checking for every number in the given array to which range it belongs is enough to pass the given time limits for the given test cases(tbh i belive the test cases are a bit weak)

my code-https://www.codechef.com/viewsolution/37173602