Online assessment Question --> How to apply dp to such large constraints

#	User	Rating
1	tourist	3857
2	jiangly	3747
3	orzdevinwang	3706
4	jqdai0815	3682
5	ksun48	3591
6	gamegame	3477
7	Benq	3468
8	Radewoosh	3463
9	ecnerwala	3451
10	heuristica	3431

#	User	Contrib.
1	cry	165
2	-is-this-fft-	161
3	Qingyu	160
4	Dominater069	158
5	atcoder_official	157
6	adamant	155
7	Um_nik	151
7	djm03178	151
9	luogu_official	149
10	awoo	148

This question was asked was in an OA. I was not able to sovle it fully i.e my soln got partially accepted.

Question

Code

ll getDistance(ll x1, ll y1, ll x2, ll y2)
{
    return (abs(x1 - x2) + abs(y1 - y2));
}


ll func(ll ax, ll ay, ll bx, ll by, ll idx, vvi &corr)
{
    if (idx == corr.size()) return 0;

    vector<ll>pos = corr[idx];

    ll x1 = pos[0], y1 = pos[1];

    ll alice = getDistance(ax, ay, x1, y1) + func(x1, y1, bx, by, idx + 1, corr);

    ll bob = getDistance(bx, by, x1, y1) + func(ax, ay, x1, y1, idx + 1, corr);

    return   min(alice, bob);

}


void  getAns(ll n, ll ax, ll ay, ll bx, ll by, vvi &corr)
{


    ll ans = func(ax, ay, bx, by, 0, corr);
    cout << ans << line;
}

void solve()
{
    ll n, ax, ay, bx, by;
    cin >> n >> ax >> ay >> bx >> by;

    vvi corr;

    f(i, 0, n)
    {
        ll x, y;
        cin >> x >> y;

        vi v;
        v.pb(x);
        v.pb(y);
        corr.pb(v);
    }


    getAns(n, ax, ay, bx, by, corr);
}

Constraints

I want to solve this problem via memorization as I am not so good at writing bottom-up approach directly.

I took 5 states-> X and Y coordinates of alice and bob and index of the corr(array of position of apples). How to optimize states?

Thanks in advance.

Comments (3)

Show archived | Write comment?

nikilrselvam

21 month(s) ago, # |

+12

Firstly, observe that there are only $$$n+2$$$ locations/coordinates you care about: the $$$n$$$ apples and starting locations of Alice and Bob. So a naive dp state might look like $$$dp[Current\;apple][Alice\;location][Bob\;location]$$$. However this is $$$n^3$$$ and is likely too slow for given constraints.

Hint #1

Hint #2

Solution

→ Reply

bin_2u

21 month(s) ago, # ^ |

Really inspiring reduction in dimension.

Vaid23

Which college are you from??

wronganswer.5's blog