### Destopia's blog

By Destopia, 2 months ago, 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.

By Destopia, history, 10 months ago, 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

By Destopia, history, 12 months ago, 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$.

By Destopia, history, 12 months ago, 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.

By Destopia, history, 13 months ago, 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? By Destopia, history, 14 months ago, 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?

By Destopia, history, 16 months ago, 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.

By Destopia, history, 2 years ago, 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?

By Destopia, history, 3 years ago, 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? By Destopia, history, 5 years ago, 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?