Problem Link: CodeChef: Practical coding for everyone
I tried to solve this problem using a memoized DP solution. The recurrence for my DP is as follows:
DP(i, j) = \max\limits_{k \in odd, \space i \lt k \lt j}(DP(i, j), \space cost(i, k) + DP(k + 1, j))
Initially DP(i, j) is cost(i, j) which is the half sum value of the segment (even lengthed) [i, j]. And the final answer is stored in DP(0, n - 1).
This is a link to my solution during the contest: CodeChef: Practical coding for everyone
I am still unable to understand where it went wrong and why it gave a WA verdict. After the contest, I downloaded an AC solution and tested it against my solution using this tester code:
gen.cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
char buf[16];
random_device rng;
while (true) {
ofstream fout("in.txt", ios_base::out);
fout << "1\n";
int n = (1 + rng() % 25) << 1;
fout << n << '\n';
auto choose = rng();
for (int i = 0; i < n; i++) {
int x = rng() % 1000;
if (rng() < choose) {
x = -x;
}
fout << x << ' ';
}
fout << '\n';
fout.close();
string a = "", b = "";
FILE *fp = popen("./A < in.txt", "r");
if (fp == nullptr) {
cout << "File Problem at line " << __LINE__ << '\n';
exit(0);
}
while (fgets(buf, sizeof(buf), fp) != nullptr) {
a += buf;
}
pclose(fp);
fp = popen("./B < in.txt", "r");
if (fp == nullptr) {
cout << "File Problem at line " << __LINE__ << '\n';
exit(0);
}
while (fgets(buf, sizeof(buf), fp) != nullptr) {
b += buf;
}
pclose(fp);
long aa = stol(a), bb = stol(b);
if (aa != bb) {
cout << " Me: " << aa << '\n';
cout << "Them: " << bb << '\n';
break;
}
}
return 0;
}
And this tester code is still running (since the past 3 hours, though my system’s specifications are pretty decent).
Please help me figure this out.