Help needed in optimising the memoized solution!!!
Difference between en2 and en3, changed 14 character(s)
why memoized solution fails in this problem:↵
[Source](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=653&page=show_problem&problem=1247)↵
//below is the given code↵


//can you help me spot some patterns to optimise it!!!↵



lli solve(lli x,lli y,lli e,lli w)↵
{↵
    

if(dp[x][y]!=100000)↵
    

{↵
        ↵
        return dp[x][y];↵
    

}↵
    if((x*x+y*y)==e*e)↵
    {↵
     return 0;   ↵
    }↵
    for(int i=1;i<=N;i++)↵
    {↵
        if(((x+coins[i].a)*(x+coins[i].a)+(y+coins[i].b)*(y+coins[i].b))<=e*e)↵
        {↵
            dp[x][y]=min(dp[x][y],(solve(x+coins[i].a,y+coins[i].b,e,i)+1));↵
        }↵
    }↵
    return dp[x][y];↵
}↵

int main()↵
{↵

cin>>n;↵

for(int i=1;i<=n;i++)↵
{↵
    ↵
f=0;↵
    ↵
for(int j=0;j<1001;j++)↵
    {↵
        for(int k=0;k<1001;k++)↵
        dp[j][k]=100000;↵
    }↵
    ↵
for(int i=0;i<100000;i++)↵
    dp1[i]=100000;↵
    cin>>N>>e;↵
    ↵
for(int j=1;j<=N;j++)↵
    {↵
        cin>>x>>y;↵
        coins[j].a=x;↵
        coins[j].b=y;↵
    }↵
    lli d=solve(0,0,e,0);↵
    if(d==100000)↵
    cout<<"not possible"<<endl;↵
    else↵
    cout<<d<<endl;↵
}↵
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English Vesper_Lynd 2018-08-18 18:10:37 860
en4 English Vesper_Lynd 2018-08-18 16:54:47 28
en3 English Vesper_Lynd 2018-08-18 16:54:04 14
en2 English Vesper_Lynd 2018-08-18 16:53:04 14
en1 English Vesper_Lynd 2018-08-18 16:51:48 1181 Initial revision (published)