Given a permutation of length $$$n \geq 2$$$, what is the maximum number of fixed points after reversing a subarray exactly once? Subarray should have length $$$\geq 2$$$. A fixed point is $$$a_i = i$$$.

Input:

7
6 2 3 4 5 1 7

Output:

4

$$$2, 3, 4, 5$$$ are already fixed points we can reverse last $$$2$$$ elements.

I can't solve it faster than $$$O(n^3)$$$, which will try every possible subarray. Any help to find an $$$O(n)$$$ solution? This problem came from random thoughts it's not from an ongoing contest.

Given an array of non-positive integers of length $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ i.e. $$$a_i \leq 0$$$. $$$(-10^9 \leq a_i \leq 0)$$$ We want to make all elements equal to $$$0$$$. We can do the following operation any number of times (possibly zero).

Choose any subarray and increase all its elements by $$$1$$$.

What is the minimum number of operations to make all elements equal to $$$0$$$?

Input

7

0 -1 -1 -1 0 -2 -1

Output

3

Given an array of $$$n \leq 10^5$$$ integers. $$$a_1, a_2, \dots a_n$$$. $$$f(i)$$$ is defined as follows:

• Take the first $$$i$$$ elements $$$a_1, a_2, a_3, \dots a_i$$$, sort them in nondecreasing order. Let's call resulting prefix after sort $$$s$$$

• Let $$$f(i) = 1 \times s_1 + 2 \times s_2 + 3 \times s_3 + \dots + i \times s_i$$$.

We're asked to calculate $$$f(1) + f(2) + \dots + f(n)$$$

Unable to parse markup [type=CF_MATHJAX]

Example $$$n = 4$$$ and array $$$[4, 3, 2, 1]$$$

$$$f(1) = 1 \times 4 = 4$$$

$$$f(2) = 1 \times 3 + 2 \times 4 = 11$$$,

$$$f(3) = 1 \times 2 + 2 \times 3 + 3 \times 4 = 20$$$

$$$f(4) = 1 \times 1 + 2 \times 2 + 3 \times 3 + 4 \times 4 = 30$$$

$$$f(1) + f(2) + f(3) + f(4) = 4 + 11 + 20 + 30 = 65$$$.

Consider following code:

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  int sum = 0;
  for (auto &it : a) {
    cin >> it;
    sum += it;
  }
  cout << sum << "\n";
  for (int i = 0; i < n; i++) {
    cout << a[i] << " ";
  }
  cout << endl;
}

Input like (or anything greater than INT_MAX into k)

5 1234567891564
1 2 3 4 5

makes the program print

0
0 0 0 0 0

What actually happens? We don't use the value of $$$k$$$ at all.

I've solved a lot of two pointers problems, I found that every problem I solved with two pointers is also solvable with binary search, is that true?

Let's say I want to check whether an integer is prime or not.

Implementation $$$1$$$:

bool is_prime1(long long n) {
    if (n < 2)
        return false;
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

Implementation $$$2$$$:

bool is_prime2(long long n) {
    if (n < 2)
        return false;
    for (long long i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

Which implementation is better?

Is there any way to submit past year problems? It seems there's only a practice problem which is duplicated every year and every one get almost a perfect score in it.

Given N strings N <= 1000. The task is to choose a subsequence such that the concatenation of the chosen elements gives the maximum lexicographical string. For example N = 3, ["ab", "ac", "b"] answer = "b", N = 2 ["z", "za"] answer is "zza". How to solve this problem?

int n = 1000;
int cnt = 0;
for (int i = 0; i < n; i++)
   cnt++;

Is the above code O(n) or O(1)? Could anyone verify this?

I am a manager of a group, and want to add some contest as training. Whenever I type the contest name and click add, I get a message "contest not found". What should I do?