### Destopia's blog

By Destopia, history, 2 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)$ $\bmod 10^9 + 7$.

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$.

Read more »

• +9

By Destopia, history, 3 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.

Read more »

• +3

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

Read more »

• +3

By Destopia, history, 4 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?

Read more »

• 0

By Destopia, history, 6 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.

Read more »

• +6

By Destopia, history, 15 months 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?

Read more »

• -17

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

Read more »

• -14

By Destopia, history, 4 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?

Read more »

• -7