 # GUESSNUM from LTIME79B

This was the Question from lunchtime. I tried to optimize the code but still, I got 50 pts for this problem. Please, anyone, optimize my code.

https://www.codechef.com/viewsolution/28548241

The problem is in your for loop. In the worst case, you are moving from sqrt(m) + 1 to m, which is not fast (correct though). You should instead loop from 1 to sqrt(m). For example, if m = 25, then looping from sqrt(m) + 1 to m takes 25 - 5 - 1= 19 steps, while looping from 1 to sqrt(m) just takes 5 steps.

Also, you need not clear the vector every time as you are redeclaring it every time.

Please provide me the optimized code.

Have a look at my code. Does the same thing.
https://www.codechef.com/viewsolution/28532492

1 Like

https://www.codechef.com/viewsolution/28548489

what is wrong in this code

When a = 1, your code will always output 0, but it is not the case with the answer.

Eg.
Input
1
1 432874

Output
7
216437 399576 416225 432848 432861 432872 432873

2 Likes

okkk
thank you @ankur314

1 Like

bro…can you explain me the approach to the problem EVIPRO…I have seen many submissions…in awivh they are adding n(n-1)/2 to the answer if s[i] and s[i+1] are same…and adding n if not…I want to ask…how this…formula…came?

Basic idea is:

1. If s[i] and s[i+1] are same, they must be in the same chosen substring, or both must not be in the chosen substring.
2. Otherwise, one must be in chosen substring while other must not be in that.

We just need to count the number of ways to make that happen.

the term n * (n+1) / 2 comes from the number of sequences to left of s[i] or to right of s[i+1] for ensuring case-1, where none of s[i] and s[i+1] is in chosen substring.

It’s purely a combinatorics problem.

3 Likes

please see what is wrong with this code:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
ll t,m,n,a,i,s;
cin>>t;
while(t–){
cin>>a>>m;
vector v;
s=m/a;
//i=s;
if((m-sa)==0 && a!=1){
cout<<0<<endl;
cout<<endl;
}
else{
for(i=sqrt(m)+1; i<=(m/a); i++)
{
if( ((m-i
a)!=0) && (i%(m - i*a))==0 )
v.push_back(i);

``````}
//sort(v.begin(), v.end(), greater<int>());
ll size=v.size();

//ll* arr=new ll[size];
//ll c=0;
//for(auto i=v.begin();i!=v.end();++i)
//  arr[c++]=*i;

//sort(arr, arr+size);
cout<<size<<endl;

for(i=0;i<size;i++)
cout<<v[i]<<" ";
cout<<endl;

v.clear();

}

}
``````

}

thanx a lot bro 1 Like