# | User | Rating |
---|---|---|
1 | ecnerwala | 3649 |
2 | Benq | 3581 |
3 | jiangly | 3578 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | tourist | 3565 |
8 | maroonrk | 3531 |
9 | Radewoosh | 3521 |
10 | Um_nik | 3482 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 165 |
3 | adamant | 161 |
4 | TheScrasse | 160 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | orz | 146 |
8 | SecondThread | 146 |
10 | pajenegod | 145 |
This year's Asia-Pacific Informatics Olympiad (APIO) is approaching, it will be open on the 20-th of May for official participants.
It is an IOI-Style contest with 3 problems and 5 hours. You can find more information on the official APIO 2023 site apio2023.cn.
Let's discuss problems/cutoffs/results here in the comments after the contest (and the mirror, if there's any) ends.
I wish everyone participating good luck!
UPD: The contest has ended, you can now discuss the problems in the comments.
This year's Asia-Pacific Informatics Olympiad (APIO) is approaching, it will be open on 28 May for official participants for a 48-hours window, and the mirror will be open for everyone on May 30 for 24 hours.
It is an IOI-Style contest with 3 problems and 5 hours. You can find more information on the official APIO 2022 site apio2022.org.
Let's discuss problems/cutoffs/results here in the comments after the contest (and the mirror) ends.
I wish everyone participating good luck!
UPD: You can find more information about the mirror here.
UPD2: Both the contest and the mirror are now over.
UPD3: The final ranking has been announced, you can find it here.
Hello, I have a problem and some variations on it that I would like to share. At the moment, I don't know solutions to all the problems, so any ideas/solutions are welcomed in the comments.
Problem 0: You are given an array $$$A$$$ of $$$n$$$ integers, and $$$q$$$ queries of the form "$$$l$$$ $$$r$$$ $$$x$$$" and each number in $$$A[l...r]$$$ appear either once or twice. For each query you have to print the number of elements $$$A_j$$$ $$$(l \le j \le r)$$$ such that $$$A_j \lt x$$$, and the number $$$A_j$$$ appears exactly once in $$$A[l...r]$$$.
Problem 1: The same as Problem 0, but without the restriction that each number in $$$A[l...r]$$$ appear either once or twice.
Problem 2: The same as Problem 1, but with the following change in the queries: "an odd number of times" instead of "exactly once".
Problem 3: The same as Problem 0, but we have updates of the form "$$$i$$$": swap $$$A_i$$$ and $$$A_{i + 1}$$$.
Problem 3.5: The same as Problem 0, but we have updates of the form "$$$i$$$ $$$j$$$": swap $$$A_i$$$ and $$$A_j$$$.
Problem 4: The same as Problem 1, but we have updates that change single elements (e.g. $$$A_i := x$$$, $$$A_i := A_i + x$$$, or some combination of updates like these).
Problem 5: The same as Problem 2, but we have updates that change single elements.
Problem 6: The same as Problem 1, but we have updates that change the elements of ranges (e.g. $$$A_i := A_i + x$$$ for $$$(l \le i \le r)$$$, $$$A_i := min(A_i, x)$$$ for $$$(l \le i \le r)$$$, or some combination of updates like these).
Problem 7: The same as Problem 2, but we have updates that change the elements of ranges.
Time limit: ~4s
Memory limit: 256MB~512MB.
$$$(1 \le n, q \le 500 \space 000, 1 \le A_i \le 10^9)$$$
I'm not sure how hard/easy these problems are. I'll update the blog with founded solutions in the future.
Hello Codeforces' people
Since Innopolis Open Olympiad for this year is starting soon, I decided to share some of my favorite problems from this olympiad alongside solutions and hints.
This blog contains problems from the first qualification rounds only. I might post other blogs for the second qualification rounds and the finals before their respective contests this year if I got positive feedback on this.
If you currently have a set, and its answer is equal to $$$x$$$.
How can you increase $$$x$$$ by possibly changing existing elements and adding new ones?
Try to think about invariants to follow when building the set.
An invariant which might help:
All the numbers of our current set are less than $$$2^b$$$ for some $$$b$$$.
Now how can we benefit from this invariant to increase $$$x$$$ by one in an easy way?
How can we increase $$$x$$$ quicker than this?
Let's try to figure out a way to double the current set's answer and a way to increase it by one.
Our set is initially empty, and while building it, all numbers must be less than $$$2^b$$$ for some $$$b$$$.
Increasing the answer by one is easy, as we can add a new element equals $$$2^{b + 1} - 1$$$.
Doubling the answer is also not that hard. We will modify the existing elements of our current set.
We will first add a new (unused before) bit to all the existing numbers in our current set. Following our invariant, this bit will be $$$2^b$$$. Then we will add a new number that will have the newly added bit turned off and all other bits used before turned on. This way, every subset that doesn't include the newly added number will have the new bit turned on, and all subsets that include it will have the new bit turned off.
Knowing how to double the answer and increase it by one, we can build the set in a way similar to binary exponentiation.
In the implementation below, the global variable bit
represents the lowest bit that is still unused in the current set.
#include <bits/stdc++.h>
using namespace std;
int K, s, bit;
vector<long long> res;
void bld(int k) {
if (k & 1) {
if (k - 1 > 0) {
bld(k - 1);
}
bit += 1;
res.push_back((1LL << bit) - 1);
return;
}
bld(k >> 1);
for (int i = 0; i < (int) res.size(); i++) {
res[i] |= (1LL << bit);
}
res.push_back((1LL << bit) - 1);
bit += 1;
}
int main() {
scanf("%d %d", &K, &s);
bld(K);
printf("%d\n", (int) res.size());
for (int i = 0; i < (int) res.size(); i++) {
if (i > 0) {
printf(" ");
}
printf("%lld", res[i]);
}
puts("");
return 0;
}
The first thing that I thought about after I've read the problem was: $$$k=$$$ knapsack capacity.
Do segments really intersect?
Imagine this: ()()()()()...
This pairing is the one that covers the minimal distance.
We can change ()() to (()), which adds the distance between the second and the third ones to the answer.
So now we want to choose a subset of the brackets and join them together.
The problem now became a 0/1 knapsack problem, and to fit in the memory limit, we will use bitsets to store our choices since we need them to construct the pairings.
#include <bits/stdc++.h>
using namespace std;
int n, k, x[14004];
bitset<30001> dp, pd, c[7003];
int main() {
scanf("%d %d", &n, &k);
for (int i = 0; i < 2 * n; i++) {
scanf("%d", &x[i]);
}
vector<int> a;
for (int i = 1; i < 2 * n; i += 2) {
a.push_back(x[i] - x[i - 1]);
}
vector<int> b(1, 0);
for (int i = 3; i < 2 * n; i += 2) {
b.push_back(x[i] - x[i - 2]);
}
dp[0] = 1;
for (int i = 0; i < n; i++) {
for (int j = k; j >= 0; j--) {
pd[j] = 0;
if (i > 0 && j >= b[i] && dp[j - b[i]]) {
pd[j] = 1;
c[i][j] = 1;
}
if (j >= a[i] && dp[j - a[i]]) {
pd[j] = 1;
c[i][j] = 0;
}
}
swap(dp, pd);
}
if (!dp[k]) {
puts("NO");
return 0;
}
vector<pair<int, int>> res;
for (int i = n - 1; i >= 0; i--) {
if (c[i][k] == 0) {
res.push_back({2 * (i + 1) - 1, 2 * (i + 1)});
k -= a[i];
continue;
}
int j = i - 1;
k -= b[i];
while (c[j][k] == 1) {
res.push_back({2 * (j + 1), 2 * (j + 1) + 1});
k -= b[j];
j -= 1;
}
res.push_back({2 * (j + 1), 2 * (j + 1) + 1});
k -= a[j];
res.push_back({2 * (j + 1) - 1, 2 * (i + 1)});
i = j;
}
puts("YES");
for (auto [f, s] : res) {
printf("%d %d\n", f, s);
}
return 0;
}
We are minimizing a summation of products. What number best minimizes products?
If we want to use as much of that number as we can, what are the values of the number of stones we are putting in each stove?
It's not obvious how we can use a greedy strategy to arrange the stones and the bounds aren't that big. What can we do?
It's most advantageous to (if possible) not put any stones, but we must use all of them.
We will still not put any stones, but only in some of the stoves, not all. So for sure, we want to have as many empty stoves as we can. So how can we achieve this?
We will put $$$v$$$ stones in non-empty stoves.
So now we are only choosing from three different options (instead of $$$v$$$) for each stove (i.e. $$$0$$$, $$$v$$$, and $$$s \space mod \space v$$$).
A straightforward dynamic programming solution would be for each stove to try all possible amounts of stones. The DP state will be:
$$$i$$$ is the current stove, $$$left$$$ is how many stones we must put in the remaining stoves, and $$$last$$$ is the number of stones in the previous stove. The answer for our problem will be: $$$min_{0 \le x \le min(v, s)}dp[n][0][x]$$$.
Since we noticed that we will only put $$$0$$$, $$$v$$$ or $$$s \space mod \space v$$$ stones in each stove our dp becomes:
The only difference is that $$$last$$$ is $$$0/1/2$$$ representing the values $$$0/v/s \space mod \space v$$$ respectively, and $$$smodv$$$ is a boolean flag that indicates whether we used the value $$$s \space mod \space v$$$ until now or not.
#include <bits/stdc++.h>
using namespace std;
const long long inf = (long long) 4e18L;
int N, S, V, p[1003];
long long dp[1003][1003][2][3];
long long sol(int i, int j, int k, int l) {
if (j == 0 && k == 1) {
return 0;
}
if (i == N) {
return inf;
}
long long& ret = dp[i][j][k][l];
if (ret != -1) {
return ret;
}
long long last = (l == 1) * V + (l == 2) * (S % V);
ret = sol(i + 1, j, k, 0);
if (j > 0) {
ret = min(ret, (i ? p[i - 1] * last * V : 0) + sol(i + 1, j - 1, k, 1));
}
if (k == 0) {
ret = min(ret, (i ? p[i - 1] * last * (S % V) : 0) + sol(i + 1, j, 1, 2));
}
return ret;
}
int main() {
scanf("%d %d %d", &N, &S, &V);
for (int i = 0; i < N; i++) {
scanf("%d", &p[i]);
}
int C = S / V;
memset(dp, -1, sizeof dp);
cout << sol(0, C, (S % V) == 0, 0) << '\n';
return 0;
}
What cases are there if $$$n = 2$$$?
Try to express other operations in terms of the operators allowed by the problem statement (e.i. {$$$+, -, *, /, abs$$$}).
What does the "K-th order statistic" actually mean?
By looking at the cases when $$$n = 2$$$, it's easy to notice that we need to represent the $$$max(a, b)$$$ and $$$min(a, b)$$$ functions in terms of $$$a$$$ and $$$b$$$. They are trivial:
The first idea that came to my mind is that the $$$k$$$-th order statistics is the minimum of all maximums of subsets of size $$$k$$$. We can implement this idea by iterating over all the subsets of size $$$k$$$ and nesting $$$max$$$ and $$$min$$$. The resulting string will exceed $$$10^5$$$ characters on the max tests, but it is enough to score 49.
Another thing to notice is that the $$$k$$$-th order statistics will win exactly $$$k$$$ (since the numbers are distinct) $$$max$$$ battels against other elements.
How to check if an element $$$a$$$ is winning a max battle against some other element $$$b$$$?
We need to check if $$$a == max(a, b)$$$. Thus we need the $$$==$$$ operator.
One can notice that two elements are equal if their difference is $$$0$$$, so taking the minimum between their difference and $$$1$$$ will give us the opposite of what we want. We can subtract that from $$$1$$$ and get our desired result.
$$$eq(a, b)$$$ will return $$$1$$$ if $$$a == b$$$ and $$$0$$$ otherwise.
Now for each element, we will test it against all the elements and sum up the results of the comparisons and check if it's equal to $$$k$$$ then we got our answer.
The only thing left is to count how many characters our resulting string will have in the max test. Here is the usage of characters for each of our functions in the implementation below:
$$$min/max(a, b): 12 + 2|a| + 2|b|$$$
$$$eq: 28 + 2|a| + 2|b|$$$
Where $$$|x|$$$ is the length of the string $$$x$$$.
#include <bits/stdc++.h>
using namespace std;
string max(const string& a, const string& b) {
return "(" + a + "+" + b + "+abs(" + a + "-" + b + "))/2";
}
string min(const string& a, const string& b) {
return "(" + a + "+" + b + "-abs(" + a + "-" + b + "))/2";
}
string eq(const string& a, const string& b) {
return "1-" + min(string(1, '1'), "abs(" + a + "-" + b + ")");
}
int n, k;
int main() {
scanf("%d %d", &n, &k);
string res = "", K = to_string(k);
for (char c = 'a'; c < char('a' + n); c++) {
if (c > 'a') {
res += '+';
}
string tmp = "", C(1, c);
for (char d = 'a'; d < char('a' + n); d++) {
if (!tmp.empty()) {
tmp += '+';
}
string D(1, d);
tmp += eq(C, max(C, D));
}
res += C + "*(" + eq(tmp, K) + ")";
}
puts(res.c_str());
return 0;
}
Sometimes you might need to use multiple segment trees over some set of elements, for example, you have to answer range queries on a single array from a lot of small arrays or to make a segment tree on a tree to answer path queries.
I knew that in cases like these, it might be more efficient to use a single segment tree to represent everything, for example, instead of building a segment tree on each one of the small arrays, you represent each array as a continuous range in one big segment tree.
I've used this whenever I needed an unknown/big number of segment trees, thinking that this is more efficient and uses less memory, but sometimes it wasn't the case as doing this has made my code slower, I once ended up doing a binary search on every query to find the actual borders of the queries, which I could've avoided by making a separate segment tree on each array.
I've thought about the advantages of using this technique, but I really couldn't find any.
I've found that, in both ways, I'm using the same amount of memory ($$$4\sum n = \sum 4n$$$), and both had the same speed.
So what I want to ask is, when does this technique give me real practical advantages to not use multiple segment trees in those cases? (other than HLD)
How to solve this?
You have queries of the following three types:
$$$add(i, v)$$$: add an element with value $$$v$$$ at index $$$i$$$.
$$$query(l, r)$$$: count the number of distinct values of elements on the range from $$$l$$$ to $$$r$$$ (inclusive).
$$$remove(i, v)$$$: remove one of the elements with value $$$v$$$ from the index $$$i$$$.
Notes:
let $$$Q$$$ be the number of queries of first and the third types, and $$$Q'$$$ be the number of queries of the second type, $$$1 \le Q \le 10^5$$$, $$$1 \le Q' \le Q\space log\space Q$$$.
$$$1 \le v \le 10^5$$$.
$$$0 \le i, l, r \le 10^8\space\space(l \le r)$$$.
in $$$add$$$ queries some index might have multiple elements at the same time and some may share the same value.
in $$$remove$$$ queries it is guaranteed that there will be at least one value at index $$$i$$$ which equals $$$v$$$.
$$$query$$$ queries should be preformed online, but the the other two types can be preprocessed if needed.
notice the unusual constrains over $$$l$$$, $$$r$$$ and $$$i$$$.
Is there is any way to do this in $$$O(log\space n)$$$ time for the queries of the second type and $$$O(log^2 n)$$$ or faster for the first the third types?
Hello, I was solving the problem 461B - Appleman and Tree but misread the problem statement — thinking that I have to calculate the number of ways such that each subtree has at least one black node, but I couldn't find a solution to this. Can anyone help me with this version of the problem?
On this problem 1277E - Two Fairs, there is t test cases and I am using a vector<vector> ed(N) to store the edges of the graph, so in end of each test case I need to clear my vector ed so I created another one vector<vector> em(N) and it's empty all the running time, in the end of each test case I did ed = em to save time, but I were always getting a TLE on the 2nd test, and I don't know why. In the first submission 68468115, I did
vector<vector<int> > ed(N), em(N);
int main() {
cin >> t;
while(t--){
...
...
...
ed = em;
}
return 0;
}
But when I did the following in this submission 68489443, I got an AC.
vector<vector<int> > ed(N);
int main() {
cin >> t;
while(t--){
...
...
...
for(int i=0; i<n; i++) ed[i].clear();
}
return 0;
}
Can someone explain why I were getting a TLE on the first submission, even that in the first submission I were doing one operation but in the second one I were doing N operations.
Name |
---|