I’ve got partially correct answer but don’t know why because test case inputs are not opened
I’ve just got following messages:
-
Wrong Answer. Your program’s output doesn’t match the expected output. You can try testing your code with custom input and try putting debug statements in your code.
-
Your code might be failing for larger test-cases
How can I find what’s the problem and debug it?
typedef unordered_map<string, pair<int, int>> memoType;
pair<int, int> cut(int start, int end, vector<int>& points, memoType& M) {
string key = to_string(start) + "_" + to_string(end);
auto pos1 = M.find(key);
if (pos1 != M.end()) {
return pos1->second;
}
pair<int, int> min(INT_MAX, 0);
int size = end - start;
for (int i = 0; i < (int)points.size(); i++) {
if (points[i] <= start) continue;
if (points[i] >= end) break;
auto rc1 = cut(start, points[i], points, M);
auto rc2 = cut(points[i], end, points, M);
if (min.first > size + rc1.first + rc2.first) {
min.first = size + rc1.first + rc2.first;
min.second = points[i];
}
}
if (min.first == INT_MAX) return make_pair(0, 0);
M[key] = min;
return min;
}
vector<int> buildSeq(memoType& M, int start, int end) {
vector<int> res;
string key = to_string(start) + "_" + to_string(end);
auto pos1 = M.find(key);
if (pos1 != M.end()) {
int P = pos1->second.second;
res.push_back(P);
vector<int> rc1 = buildSeq(M, start, P);
vector<int> rc2 = buildSeq(M, P, end);
res.insert(res.end(), rc1.begin(), rc1.end());
res.insert(res.end(), rc2.begin(), rc2.end());
return res;
}
return vector<int>();
}
vector<int> Solution::rodCut(int A, vector<int> &B) {
if (B.empty()) return vector<int>();
memoType M;
auto res = cut(0, A, B, M);
return buildSeq(M, 0, A);
}