WA in K Halves problem from Fall For Code 2.0

Problem Link: https://www.codechef.com/FFC22019/problems/FFC219G

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: https://www.codechef.com/viewsolution/26911594

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.

2 Likes

I am not sure if this is the case but in your solution, inside the solve function at line 17, the for loop should be for(int k=(i+1); k<=j ; k+=2), I think equality should be there with j since your parameters have the initial value of (0,n-1) as I can see in the main function.

For the case k == j, the recurrence will not be valid, \because (k + 1) will go out of bounds according to the recursive definition of my DP states. Also, this case is being handled at line 16 where I have written:

x = cost[i][j];

So, I don’t think it is making any problem.

The test data is incorrect, I just figured out.

Solution: https://www.codechef.com/viewsolution/26922250

This is the same solution that I have provided in the description above, and I have just added assertions on everything according to the constraints. And now the same is giving Runtime Error, means my assertions did fail on the constraints. Also, I had used static arrays for a and pre of sizes 300 and 301 respectively.

Then I submitted this code: https://www.codechef.com/viewsolution/26922373
It gave WA just because I used vector<int> a(n). Then I submitted the same solution with vector<long> a(n), which means even a is going out of an int limit.

Finally I submitted this code and got AC: https://www.codechef.com/viewsolution/26922478

All of them have the same logic and implementation, just the AC solution is not blindly trusting the constraints.

So, I request the organizers to please rectify this problem and re-judge all the solutions, both for practice section and the contest.

Just emailed them about this also, with a link to this reply.

3 Likes

We’ll just look into this and get back to you.

1 Like

We have rejudged the solution!! Check it!!

What about Contest Rank List and Contest Page updation?
And what about Practice Submissions updation?

Contest rank list has been updated accordingly. Top 3 are unaffected.

@saurabhshadow Can you please provide the editorials for Fall for code contest .

1 Like

They did get affected!