Vladik and Memorable Trip Debugging

Debugging Help
#1

Problem Info

Vladic and Memorable Trip

My Work

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using std::cout;
using std::endl;
using std::vector;

/**
 * https://codeforces.com/contest/811/problem/C
 * 6
 * 4 4 2 5 2 3 should output 14
 */
int main() {
    int people_num;
    std::cin >> people_num;

    vector<int> people(people_num);
    vector<int> pref_xors{0};
    std::unordered_map<int, int> last_occ;
    for (int p = 0; p < people_num; p++) {
        std::cin >> people[p];
        if (last_occ.find(people[p]) == last_occ.end()) {
            pref_xors.push_back(pref_xors.back() ^ people[p]);
        } else {
            pref_xors.push_back(pref_xors.back());
        }
        last_occ[people[p]] = p;
    }

    // precalculate which segments are valid
    vector<std::unordered_set<int>> valid_starts(people_num);
    std::unordered_set<int> seen;
    for (int start = 0; start < people_num; start++) {
        // if we've already seen this, there's no way this can be a starting pt
        if (seen.find(people[start]) != seen.end()) {
            continue;
        }
        std::unordered_set<int> not_met;
        for (int end = start; end < people_num; end++) {
            if (end == last_occ[people[end]]) {
                not_met.erase(people[end]);
                if (not_met.empty()) {
                    valid_starts[end].insert(start);
                }
            } else {
                not_met.insert(people[end]);
            }
        }
        seen.insert(people[start]);
    }

    // this[i] = best if we only use segments that are within the first i people
    vector<int> max_comfort(people_num + 1);
    for (int p = 1; p <= people_num; p++) {
        max_comfort[p] = max_comfort[p - 1];
        for (int prev : valid_starts[p - 1]) {
            int total = pref_xors[p] ^ pref_xors[prev];
            max_comfort[p] = std::max(max_comfort[p], total + max_comfort[prev - 1]);
            // cout << prev << ' ' << max_comfort[prev - 1] << ' ' << total << endl;
        }
        // printf("%i %i --------------------------\n", p, max_comfort[p]);
    }
    cout << max_comfort[people_num] << endl;
}

I first precalculate all valid segments in O(n^2), and then I do a DP, where max_comfort[i] is the maximum comfort we can achieve using only segments that lie in the first i people.

Why does this WA on test 12?

#2

Bump!

#3

tldr; https://usaco.guide/general/debugging-lang?lang=cpp#stress-testing

Have you tried the following:

  • Write a very naive and simple solution to the problem (maybe exponential complexity) (if you can, you may also just copy someone else’s solution)
  • Write a program to generate thousands of small (!) test cases
  • Using those two, find a test case where your program gives the wrong answer
  • Use print statements or a debugger to see where exactly your program does the wrong thing.

98% of WAs and REs can be resolved this way. People here don’t have the time to delve into every code posted here, it’s much harder to debug somebody else’s code and being able to debug your own code is a valuable skill. It is also a very routine process that can be learned much faster than problem solving and algorithms.

1 Like
#4

How would I even go about writing an exponential time solution here?

#5

^