### BERNARB.01's blog

By BERNARB.01, 5 months ago,

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.

• +266

By BERNARB.01, 16 months ago,

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!

UPD2: Both the contest and the mirror are now over.

UPD3: The final ranking has been announced, you can find it here.

• +119

By BERNARB.01, 20 months ago,

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.

• +87

By BERNARB.01, 22 months ago,

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.

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution
Code

Hint 1
Hint 2
Solution
Code

Hint 1
Hint 2
Hint 3
Solution
Code

### 101627E - K-th order statistic

Hint 1
Hint 2
Hint 3
Solution
Code
• +109

By BERNARB.01, 2 years ago,

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)

• +60

By BERNARB.01, 2 years ago,

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?

• +43

By BERNARB.01, 2 years ago,

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?

• +18

By BERNARB.01, history, 4 years ago,

### Hello codeforces,

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.

• +3