I am trying to get better in CP. I came across this problem - Link. While I had a naive BFS solution in mind O(2^N) it obviously gave me a TLE.
string bfs(int t1,int t2)
{
queue<pair<VII,string>> st;
st.push({{0,1,1,2,1,1},"L"});
st.push({{1,1,2,1,1,0},"R"});
while(!st.empty())
{
VII u=st.front().first;
string v=st.front().second;
st.pop();
//cout<<u[2]<<' '<<u[3]<<endl;
if(u[2]==t1 && u[3]==t2)
return v;
st.push({{u[0],u[1],u[0]+u[2],u[1]+u[3],u[2],u[3]},v+"L"});
st.push({{u[2],u[3],u[2]+u[4],u[3]+u[5],u[4],u[5]},v+"R"});
}
return "";
}
The above is the code I was able to come up with. I am aware that there is binary search solution, But I could not understand how to divide the search space. It would be great if anybody could explain me the intuition behind this. Thank you!
You're trying to find the target number in the infinite interval lo=(0,1) hi=(1,0).
As the PDF says, you can find the mid-point of the interval by doing mid = (lo[0]+hi[0])/(lo[1]+hi[1]).
The decision to go left or right depends on the comparison of mid and your target number.
If you go left, you emit a L and start searching in the interval lo=lo hi=mid.
If you go right, you emit a R and start searching in the interval lo=mid hi=hi.
Repeat until mid == target.
Here's a quick solution in Python:
from fractions import Fraction
def walk(lo, hi, tgt):
mid = (lo[0] + hi[0], lo[1] + hi[1])
fmid = Fraction(mid[0], mid[1])
if tgt == fmid:
return
if tgt < fmid:
yield 'L'
yield from walk(lo, mid, tgt)
else:
yield 'R'
yield from walk(mid, hi, tgt)
print(list(walk((0,1), (1,0), Fraction(878, 323))))