first input will be number of test cases t then given two numbers a and b u have to perform 'i' operations such that, add 1 to a if i is odd add 2 to a if i is even now print YES if a can become equal to b and NO if it can't

when i tried to submit my solution i got error that time limit is exceeded.

enter code here
#include<bits/stdc  .h>
using namespace std;

int main() {
    int t,a,b;
    cin>>t;
    while(t){
        cin>>a>>b;
       int flag=1;
       while(a!=b && a<b)
       {
           if(flag%2==0)
           {
               a =2;
           }
           else
           {
               a =1;
           }
           flag  ;
       }
       if(a==b)
       cout<<"YES"<<endl;
       else
       cout<<"NO"<<endl;
        t--;
    }
    return 0;
}

CodePudding user response：

You don't need to actually iterate from a to b, just use the following observations to solve:

• After 2 operations, the value of a increases by 3. So after an even number of operations (let number be 2k), a increases by 3k.
• Similarly, for an odd number of operations (of form 2k 1), a increases by 3k 1.

As you can see, a can either be increased by 3k or 3k 1, which implies that b will be reachable from a if (b-a) mod 3 = (0 or 1) (and obviously, if b>a). You can check this in O(1) complexity.

CodePudding user response：

The inner loop can be simplified into a math expression. We can come up with the model using some examples.

For example, if a = 10, b = 20.

Loop 1 a  = 1 (11)
Loop 2 a  = 2 (13)
Loop 3 a  = 1 (14)
Loop 4 a  = 2 (16)
...

We can see that after two operations, a increases by 3. Which can be generalized, that after the 2n operation (which represents an even number), that a increases by 3n. On the other hand after the 2n 1 operation (odd numbers), a is equal to an increase of 3n 1. Thus, a can be increased either by 3n or 3n 1. Thus, 3n or 3n 1 has to be able to be equal to the difference of a and b, which in this case is 10.

Thus either

1. 3 has to divide b - a, (b-a)%3 = 0 
2. 3 has to divide b - a with a remainder of 1, (b-a)%3=1

Thus, instead of a loop, using a mathematical expression can simply the runtime to O(1) per input.