1519D - Maximum Sum of Products

SXWisON molingspance

Idea

Assuming the old range is l~r, and expanded it by one unit, we get l-1~r+1,

It's interesting that, we only need calculate the changed portion, that is:

add: a[r+1]*b[l-1] + a[l-1]*b[r+1]

sub: a[l-1]*b[l-1] + a[r+1]*b[r+1]

Implementation

To implement this traversal, consider two scenarios:

when the swapped sequence has an even length, and when the swapped sequence has an odd length.

The indices for these scenarios are as follows:

• Odd length: l-i~r+i
• Even length: l-i+1~r+i

Code

#include <iostream>

typedef long long int LL;

LL a[5010];
LL b[5010];

int main() {
  int n;
  std::cin >> n;
  for (int i = 0;i < n;i++) {
    std::cin >> a[i];
  }
  for (int i = 0;i < n;i++) {
    std::cin >> b[i];
  }
  // Record the maximum value of change
  LL max = 0;
  // case of odd number exchange
  // Traverse Center
  // Note: It is meaningless to exchange only one, so at least three should be exchanged
  for (int i = 1; i < n - 1; i++) {
    LL delta = 0;
    // Exchange radius
    for (int r = 1; i - r >= 0 && i + r < n; r++) {
      delta -= a[i - r] * b[i - r] + a[i + r] * b[i + r];
      delta += a[i - r] * b[i + r] + a[i + r] * b[i - r];
      if (delta > max)
        max = delta;
    }
  }
  // The case of even number exchange
  // The definition is that the index is on the left side
  for (int i = 0; i < n - 1;i++) {
    LL delta = 0;
    // Exchange radius
    for (int r = 1; (i - r + 1) >= 0 && (i + r) < n;r++) {
      delta -= a[i - r + 1] * b[i - r + 1] + a[i + r] * b[i + r];
      delta += a[i - r + 1] * b[i + r] + b[i - r + 1] * a[i + r];
      if (delta > max)
        max = delta;
    }
  }
  // Calculate Total Sum
  LL sum = 0;
  for (int i = 0;i < n;i++) {
    sum += a[i] * b[i];
  }
  std::cout << sum + max;
  return 0;
}

1359D - Yet Another Yet Another Task

SXWisON molingspance

In this problem, we can use Kadane’s algorithm in dynamic programming to solve it.

Prototype

Question: Given a sequence a[i], find the optimal indices l and r such that the sum of a[l] + ... + a[r] is maximized.

Kadane’s algorithm:

localMax = Math.max(nums[i], localMax + nums[i])

max = Math.max(max, localMax)

Idea

Suppose we have a maximum value mx and we iterate through the range 1 to 30.

For any number greater than mx, we set it to negative infinity so that the optimization process only considers values where x <= mx.

localMax = Math.max(nums[i], localMax + nums[i]);

max = Math.max(max, localMax-mx);

Code

#include <iostream>
#include <algorithm>

int a[100010];

typedef long long int LL;
constexpr int INF = 10e9;

int main() {
  // load data
  int n;
  std::cin >> n;
  for (int i = 0;i < n;i++) {
    std::cin >> a[i];
  }
  // iteration
  LL Gmax = 0;
  for (int mx = 1; mx <= 30; mx++) {
    LL Lmax = 0;  // Local max for signle mx
    LL cur = 0;    // Current max
    for (int i = 0; i < n; i++) {
      LL val = (a[i] > mx) ? -INF : a[i];
      cur = std::max(val, cur + val);
      Lmax = std::max(cur, Lmax);
    }
    Gmax = std::max(Lmax - mx, Gmax);
  }
  std::cout << Gmax;
  return 0;
}

698A - Vacations

SXWisON molingspance

Idea

A variable p can be used to represent the available actions, with the following rules:

• If no action can be performed on that day, let p=0.
• If the input is x=1,2 and can be executed, then the possible action for p is x, that is p=x.
• If the input is x=3, there are two possibilities. Either both states can be performed, or only one of them can be executed.

If the previous value of p is 0, than the current value is 3, that means all actions can be executed.

If the previous value of p is 1, the current value must be 2.

Similarly, if the previous value of p is 2, the current value must be 1.

It’s interesting that all the calculations can be expressed as p=3-p.

It's easy to determine that a specific day cannot excute any actions is equivalent to:

Either x=0 (indicating that no venues are open) or x=p and x is not 3. If x is not 3, it means that the only action that can be taken is exactly the same as the only action that could be taken the previous day, violating the rest principle. Therefore, on that day, no actions can be performed.

Code

#include <iostream>
 
int main(int argc, char* argv[]) {
  int n, x, p = 3, ans = 0;
  std::cin >> n;
  for (int i = 1; i <= n; i++) {
    std::cin >> x;
    if (x == 0 || (x == p && x != 3))
      ans++, p = 0;
    else
      p = (x == 3) ? 3 - p : x;
  }
  std::cout << ans;
  return 0;
}