GUESSNUM from LTIME79B

1

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

2

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.

3

Please provide me the optimized code.

4

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

1 Like
5

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

please let me know
what is wrong in this code

6

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

But your code returns 0.

2 Likes
7

okkk
thank you @ankur314

1 Like
8

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?

9

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.

My code: CodeChef: Practical coding for everyone

It’s purely a combinatorics problem.

3 Likes
10

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-ia)!=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();

}

}

}

11

thanx a lot bro :slight_smile:

1 Like