BERNARB.01's blog

By BERNARB.01, 4 days 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.

Read more »

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

By BERNARB.01, 2 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

Read more »

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

By BERNARB.01, 7 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)

Read more »

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

By BERNARB.01, 8 months 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?

Read more »

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

By BERNARB.01, 10 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?

Read more »

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

By BERNARB.01, history, 2 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.

Read more »

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