Question link : https://atcoder.jp/contests/abc175/tasks/abc175_f and My Solution link : https://atcoder.jp/contests/abc175/submissions/15984070

Solution reference of int65536 (rank 1 in contest): https://atcoder.jp/contests/abc175/submissions/15936454

I did some sort of similar approach but instead of applying Dijkstra's algorithm to find the shortest path where state is defined using (prefix & suffix), I tried to use recursive dp approach with memoization (seemed intuitive to me).

I manage to pass almost all the cases but getting RE in 4 test cases. Can someone please help me where I might be going wrong with my solution?

Also can someone share an insight why every high rated coder intuitively thought of applying Dijkstra and not a recursive dp? Is there some property that I am missing? Can someone please help?

For reference : - tribute_to_Ukraine_2022 https://codeforces.me/blog/entry/81458?#comment-681148 and - galen_colin https://www.youtube.com/watch?v=HmbZiI0rAk4

Solution :

#include<bits/stdc++.h>
using namespace std;

#define LL long long

const int MOD = 1e9 + 7;
const LL INF = 1e18 + 9;
const int MX = 1e5 + 5;

int n;
vector<string> inp;
vector<LL> cost;

bool isPalindrome(string s) {
	int l = s.size();
	for(int i=0;i<l;i++) {
		if(s[i] != s[l-1-i])
			return false;
	}
	return true;
}

vector<string> getNextState(string s1, string s2) {
	vector<string> ret;

	int l1 = s1.size();
	int l2 = s2.size();
	int l = min(l1,l2);
	for(int i=0;i<l;i++) {
		if(s1[i] != s2[l2-1-i]) {
			return ret;
		}
	}
	if(l1 == l2) {
		ret.push_back("");
		ret.push_back("");
	}	
	else if(l1 > l2) {
		string tmp = s1.substr(l2);
		ret.push_back(tmp);
		ret.push_back("");
	}
	 else {
		string tmp = s2.substr(0, l2-l1);
		ret.push_back("");
		ret.push_back(tmp);
	}
	return ret;
} 

map<pair<string, string>, LL > cache;

LL solve(string pre, string suff) {
	if(isPalindrome(pre + suff)) {
		return 0;
	}

	if(cache.find({pre,suff}) != cache.end()) {
		return cache[{pre,suff}];
	}

	LL ret = INF;

	for(int i=0;i<n;i++) {
		vector<string> cand;
		if(pre.size() > 0) {
			cand = getNextState(pre, inp[i]);
		} else {
			cand = getNextState(inp[i], suff);
		}

		if(cand.size() == 0) {
			continue;
		}

		ret = min(ret, cost[i] + solve(cand[0], cand[1]));
	}

	cache[{pre, suff}] = ret;
	return ret;
}

int main() {
	cin >> n;
	inp.resize(n);
	cost.resize(n);
	for(int i=0;i<n;i++) {
		cin >> inp[i] >> cost[i];
	}

	LL ans = INF;
	for(int i=0;i<n;i++) {
		ans = min(ans, cost[i] + solve(inp[i], ""));
	}
	if(ans == INF) {
		cout << -1 << endl;
		return 0;
	}
	cout << ans << endl;

	return 0;
}