We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Probability
  4. Colorful Polygon
  5. Discussions

Colorful Polygon

  • comp0zr
     + 0 comments

    As usual, I think the editorial code/approach is needlessly compex. There's no need for any fancy data structures like segment tree or Fenwick tree, just a few standard arrays:

    WARNING: Low-key spoilers ahead. No implementation code, just declarations.

    int A[200010]; // Input array

int next_index[200010]; // next_index[i] is the next index j such that A[i] = A[j], or -1 if no such index exists
int prev_index[200010]; // prev_index[i] is the previous index j such that A[i] = A[j], or -1 if no such index exists

bool start_index[200010]; 

// start_index[i] = true if DP algorithm should be run on a segment beginning at index i

long long DP[200010][2] = {0}; 

// DP[i][0] = count of binary subsets ending with a zero bit at index i
// DP[i][1] = count of binary subsets ending with a one bit at index i

long long sums[200010][2] = {0};

// Prefix sum array of values in DP

    Anyway, I still found this to be a very interesting and fun challenge. Sadly, I'm starting to run out of DP-related problems to solve on this site... :/