BERNARB.01's blog

By BERNARB.01, 8 months ago, In English

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.

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +119
  • Vote: I do not like it

By BERNARB.01, 12 months ago, In English

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.

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +87
  • Vote: I do not like it

By BERNARB.01, 15 months ago, In English

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.

102436D - Subset ``AND''

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

102436C - Painting Plan

Hint 1
Hint 2
Solution
Code

102032D - Stones Distribution

Hint 1
Hint 2
Hint 3
Solution
Code

101627E - K-th order statistic

Hint 1
Hint 2
Hint 3
Solution
Code

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +109
  • Vote: I do not like it

By BERNARB.01, 20 months ago, In English

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)

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +60
  • Vote: I do not like it

By BERNARB.01, 21 month(s) ago, In English

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?

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +43
  • Vote: I do not like it

By BERNARB.01, 22 months ago, In English

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?

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +18
  • Vote: I do not like it

By BERNARB.01, history, 3 years ago, In English

Hello codeforces,

On this problem 1277E - Две ярмарки, 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.

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it