Question statement: A certain bug's home is on the x-axis at position x. Help them get there from position 0. The bug jumps according to the following rules:

It can jump exactly a positions forward (to the right). It can jump exactly b positions backward (to the left). It cannot jump backward twice in a row. It cannot jump to any forbidden positions. The bug may jump forward beyond its home, but it cannot jump to positions numbered with negative integers.

Given an array of integers forbidden, where forbidden[i] means that the bug cannot jump to the position forbidden[i], and integers a, b, and x, return the minimum number of jumps needed for the bug to reach its home. If there is no possible sequence of jumps that lands the bug on position x, return -1.

1 <= forbidden.length <= 1000

1 <= a, b, forbidden[i] <= 2000

0 <= x <= 2000

Solution: Tried making graph of size 4001 and then bfs to find the answer. I am getting wrong answer on test case: [14,4,18,1,15] //forbidden array

40 //a

12 //b

1300 //x

MY CODE:

class Solution {
unordered_map<int,bool>mp;

int ul=4001; /*no real proof on upperlimit( might be wrong. please provide insight), but going too many jumps forward and then backwards to reach home can be equivalent to jumping forward and backward alternately! SO do not need to have more than these many nodes.*/
public:  void populate(vectoradj[],vector&vis,int i,int &a,int &b)//,int &x,bool back)  {
for(i=0;i<ul;i++)
    {
        if(i+a<ul && mp.find(i+a)==mp.end())
            adj[i].push_back(i+a);
        if(i-b>=0 && mp.find(i-b)==mp.end())
            adj[i].push_back(i-b);
    }
}
int bfs(vector<int>adj[],vector<bool>&vis,int &a,int &b,int &x)
{
    queue<pair<int,bool>>q;
    int step=0,num_now=0,num_next=1;
    q.push({0,false});
    while(!q.empty())
    {
        step++;
        num_now=num_next;
        num_next=0;

        while(num_now--)
        {
            int temp=q.front().first; //temp=current node
            bool back=q.front().second;//back => did i reach temp using a backward jump?
            q.pop();
            // vis[temp]=true;
            if(temp==x)
                return step-1;
            for(int i=0;i<adj[temp].size();i++)
            {
                int neigh=adj[temp][i];
                if(!vis[neigh] && (neigh==temp+a or (neigh==temp-b && !back)))//if neighbour awaits forward jump,go for it , if backward jump? check if back false or not
                {  
                    vis[neigh]=true;
                    q.push({neigh,neigh==temp-b});
                    num_next++;
                }
            }
        }

    }
    return -1;
}
int minimumJumps(vector<int>& forbidden, int a, int b, int x) {//The main function

    vector<int>adj[ul];
    vector<bool>vis(ul,false); 
    int n=forbidden.size();
    for(int i=0;i<n;i++)//mapping forbidden nodes for quick access
        mp[forbidden[i]]=true;

    populate(adj,vis,0,a,b);        

    n=bfs(adj,vis,a,b,x);
    mp.clear();
    return n;
}
}; 

Question statement: A certain bug's home is on the x-axis at position x. Help them get there from position 0. The bug jumps according to the following rules:

It can jump exactly a positions forward (to the right). It can jump exactly b positions backward (to the left). It cannot jump backward twice in a row. It cannot jump to any forbidden positions. The bug may jump forward beyond its home, but it cannot jump to positions numbered with negative integers.

Given an array of integers forbidden, where forbidden[i] means that the bug cannot jump to the position forbidden[i], and integers a, b, and x, return the minimum number of jumps needed for the bug to reach its home. If there is no possible sequence of jumps that lands the bug on position x, return -1.

1 <= forbidden.length <= 1000

1 <= a, b, forbidden[i] <= 2000

0 <= x <= 2000

Solution: Tried making graph of size 4001 and then bfs to find the answer. I am getting wrong answer on test case: [14,4,18,1,15] //forbidden array

40 //a

12 //b

1300 //x

MY CODE:

class Solution {
unordered_map<int,bool>mp;

int ul=4001; /*no real proof on upperlimit( might be wrong. please provide insight), but going too many jumps forward and then backwards to reach home can be equivalent to jumping forward and backward alternately! SO do not need to have more than these many nodes.*/
public:  void populate(vectoradj[],vector&vis,int i,int &a,int &b)//,int &x,bool back)  {
for(i=0;i<ul;i++)
    {
        if(i+a<ul && mp.find(i+a)==mp.end())
            adj[i].push_back(i+a);
        if(i-b>=0 && mp.find(i-b)==mp.end())
            adj[i].push_back(i-b);
    }
}
int bfs(vector<int>adj[],vector<bool>&vis,int &a,int &b,int &x)
{
    queue<pair<int,bool>>q;
    int step=0,num_now=0,num_next=1;
    q.push({0,false});
    while(!q.empty())
    {
        step++;
        num_now=num_next;
        num_next=0;

        while(num_now--)
        {
            int temp=q.front().first; //temp=current node
            bool back=q.front().second;//back => did i reach temp using a backward jump?
            q.pop();
            // vis[temp]=true;
            if(temp==x)
                return step-1;
            for(int i=0;i<adj[temp].size();i++)
            {
                int neigh=adj[temp][i];
                if(!vis[neigh] && (neigh==temp+a or (neigh==temp-b && !back)))//if neighbour awaits forward jump,go for it , if backward jump? check if back false or not
                {  
                    vis[neigh]=true;
                    q.push({neigh,neigh==temp-b});
                    num_next++;
                }
            }
        }

    }
    return -1;
}
int minimumJumps(vector<int>& forbidden, int a, int b, int x) {//The main function

    vector<int>adj[ul];
    vector<bool>vis(ul,false); 
    int n=forbidden.size();
    for(int i=0;i<n;i++)//mapping forbidden nodes for quick access
        mp[forbidden[i]]=true;

    populate(adj,vis,0,a,b);        

    n=bfs(adj,vis,a,b,x);
    mp.clear();
    return n;
}
}; 

Now what i did was similar to editorial. The problem isnt with the approach but with the fact that if use operation ans+=(n*(n-1))/2 i get wrong answer due to integer overflow, now I AM using long long but still it gives -ve answer in 2nd test case which is ofcourse due to overflow. To solve this what i did was first divide n or (n-1) by 2 (depending upon parity) and then multiplying and got answer accepted. Can someone tell why this is happening?? I know i would probably be a very dumb mistake but plz dont judge harshly. :D

MY CODE:

#include<bits/stdc++.h>

using namespace std;

//void swap(int &a,int &b){

// int tmp=a;a=b;b=tmp;

//}

int size(long long a){

int n=0;

while(a!=0){

n++;

a/=2;

}

return n;

}

int main(){

ios_base::sync_with_stdio(false);

cin.tie(NULL);

int t,n;

cin>>t;

while(t--){

cin>>n;

long long A[n],ans=0;

for(int i=0;i<n;i++)cin>>A[i];

` `

vector<int>nums(32,0);

for(int i=0;i<n;i++){

nums[size(A[i])]++;

}

for(int i=0;i<32;i++){

// long long a=nums[i],b=nums[i]-1;

// if(nums[i]%2==0){

// a/=2;

// }

// else{

// b/=2;

// }

// ans+=(a*b);

ans+=((nums[i]*(nums[i]-1))/2);

}

cout<<ans<<"\n";

}

` `

return 0;

}

So after reading the approach in the tutorial, i understood for every x cheaper ones, we need x+1 expensive spheres. I understand why but i am still confused about how to handle duplicates since they will cause problems! I need help to understand this!! Any help would be appreciated!! Thanks :D

So i have almost similar approach to the editorial, where i chose the smallest feasible day for every exam and update my answer. Though i am getting RUNTIME_ERROR in test case 18.

Things i checked for: - proper data types used - dry ran my code on paper on many cases - searched for meaning of exit code -1073741819, but to no avail. still get the error.

The compiler does not show the full test case and stops in between so cannot give u the test case. But it is numbered 18 with very large values.

Here is my code:

#include<bits/stdc++.h>
using namespace std;
bool compare(pair<long long,long long> &a,pair<long long,long long> &b)
{
	if(a.first<=b.first)
		return true;
	return false;
}
int main()
{
	int n;
	cin>>n;
	pair<long long,long long> A[n];
	long long day=0;
	for(int i=0;i<n;i++)
	{
		long long a,b;
		cin>>a>>b;
		A[i]={a,b};
	}
	sort(A,A+n,compare);
	for(int i=0;i<n;i++)
	{
		long long temp=LLONG_MAX;
		if(day<=A[i].first)
			temp=A[i].first;
		if(day<=A[i].second && temp>A[i].second)
			temp=A[i].second;
		if(temp!=LLONG_MAX)	
			day=temp;	
	}
	cout<<day;				
	return 0;
}