pakhomovee's blog

By pakhomovee, history, 15 months ago, In English

We hope you liked our problems!

1858A - Buttons

Tutorial
Code

1858B - The Walkway

Tutorial
Code

1858C - Yet Another Permutation Problem

Tutorial
Code

1858D - Trees and Segments

Tutorial
Code

1858E2 - Rollbacks (Hard Version)

Tutorial
Code

Note: At about 20 minutes into the round one of our testers (SomethingNew) came up with a linear solution for problem E2, and jiangly implemented the same solution shortly after the contest! For further details, see 219001999. The main idea (as jiangly pointed out in the comments) is that we can use prefix sums instead of the Fenwick tree.

Full text and comments »

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

By pakhomovee, 15 months ago, In English

Hello, Codeforces!

We are glad to invite everyone to participate in Codeforces Round 893 (Div. 2), which will be held on Aug/15/2023 17:35 (Moscow time).

Please note the unusual start time of the round. This round will be rated for the participants with rating lower than 2100.

Our round is completely set by SIS (Summer Informatics School) students. We did our best to prepare interesting and creative problems. You can check out some of the previous rounds prepared by SIS students: Codeforces Round 816 (Div. 2), Codeforces Round 815 (Div. 2),Codeforces Round #694,Codeforces Round #612,Codeforces Round #530.

Task authors and developers: Daria arbuzick Grekova, Petr green_gold_dog Losev, Yaroslav Kihihihi Semenyuk, Artem ArtAlex Alexeev, Anton NToneE Egorov, Fedor FedShat Shatokhin, Timofey IzhtskiyTimofey Izhitskyi, Egor salyg1n Salygin, Vladimir plagues Gerasikov under the guidance of Evgenii pakhomovee Pakhomov

We are very thankful to

You will have 5 tasks and 2 hours to solve them. We recommend you read all the problems. The contest may contain interactive problems! Make sure to read this post.

The scoring distribution is $$$500-1250-1500-2000-(1750+1000)$$$

Note that the round has been moved one hour later. The contest start time is Aug/15/2023 17:35 (Moscow time)

We hope that you will enjoy our tasks!

Good luck!

UPD: Editorial

UPD 2: Congratulations to the winners!

Div. 2:

  1. dong_liu

  2. yydtq

  3. wk______tzc

  4. qwesda

  5. Van_Dijk

Div. 1:

  1. jiangly

  2. neal

  3. BucketPotato

  4. kotatsugame

  5. YocyCraft

First solves:

A. ball_of_wool

B. ecnerwala

C. nigus

D. jiangly

E1. grass8sheep

E2. yydtq

Full text and comments »

  • Vote: I like it
  • -62
  • Vote: I do not like it

By pakhomovee, 4 years ago, translation, In English

Mo's algorithm

Problem 1
Problem 2

Let's solve the first problem. We can solve it using persistent data structures, but we want to be able to solve problem 2 as well.

Algorithm 1

Let's solve the task offline. We need to sort the queries using the <$$$\frac{l}{k}$$$, r> comparator, where k is a fixed integer. It is quite obvious that we can easily add/delete one integer (we can do that using another array B, $$$B_{i}$$$ equals to the number of occurrences of integer i). Let's divide the queries into blocks, $$$i_{th}$$$ block contains all queries, which have $$$\left \lfloor \frac{l}{k} \right \rfloor$$$ equal to $$$i$$$. There are $$$O(\frac{n}{k})$$$ blocks. Let's assume that we have somehow calculated the answer for segment $$$[L; R]$$$. We can get the answer for segment $$$[L'; R']$$$, if we move the left and the right borders, until they are equal to $$$L'$$$ and $$$R'$$$. It is obvious that for each block the left border can move by $$$O(k)$$$ positions only for a single query, the right border — $$$O(n)$$$ positions in total, because the right borders are sorted in the increasing order. In total the left pointer will move by $$$O(q \cdot k)$$$ positions, the right border — $$$O(\frac{n^{2}}{k})$$$. If we set $$$n = q$$$, $$$k = \sqrt{n}$$$, we get the total complexity of $$$O((n + q)\cdot\sqrt{n})$$$.

Sample code

This code has a couple of problems. Firstly, it is quite slow.

Think about the second problem yourself.

The problem

Algorithm 2

Let's sort the queries the same way as in the first algorithm.

Let's call a block all the queries with the same $$$\left \lfloor \frac{l}{k} \right \rfloor$$$. There are $$$O(k)$$$ blocks in total. Let's answer the queries of length $$$\leq k$$$. We can answer each query in $$$O(k)$$$. Now, we need to answer the queries with length $$$> k$$$. For each query like that the position $$$k \cdot \left \lceil \frac{l}{k} \right \rceil$$$ is in the query. It is obvious that for each block we can move the right border as in the previous algorithm. For this we need the add operations only. For every query in the block we need to move the left border by $$$O(k)$$$ positions only, if we set $$$L = k \cdot \left \lceil \frac{l}{k} \right \rceil$$$ (the left border we need is $$$L'$$$) and try to make $$$L = L'$$$ by moving $$$L$$$ to left left. To sum up, we need $$$O(k)$$$ for each query to move the left border, $$$O(n)$$$ for each block to move the right border. This makes the complexity of $$$O(q \cdot k + \frac{n^2}{k})$$$ in total (assuming $$$n = q$$$). if we set $$$k = \sqrt{n}$$$, we get $$$O((n + q) \sqrt{n})$$$.

Some notes

3D Mo

Let's solve the second task.

Algorithm 1.

We can use sqrt decomposition while using Mo's algorithm. Let's divide the queries into blocks of size $$$k$$$. Inside each block we can use Mo's algorithm. The final complexity is $$$O(\frac{q}{k} \cdot (k^{2} + \frac{n^{2}}{k}))$$$. If we set $$$n = k$$$, we get $$$O(nk + \frac{n^3}{k^{2}})$$$. If we set $$$k = n^{\frac{2}{3}}$$$, we get $$$O(n^{\frac{5}{3}})$$$.

Sample code

Algorithm 2.

Let's sort the queries by <l / k, r / k, i>. Each of the query borders is located in a fixed block (the blocks are defined as in the previous algorithms). For each pair of blocks we can answer the queries. Let's look through the queries in the chronological order. For each pair of blocks we look at all the change queries. We move the pointers as in the first algorithm. To do all of this fast, we can maintain the index of the last query we have already checked. The total complexity is $$$O(\frac{n}{k} \cdot \frac{n}{k} \cdot q + qk)$$$, because every l/r pointer can move by $$$O(k)$$$ steps per query. If we set $$$n = q$$$, we get $$$O(\frac{n^{3}}{k^{2}}+qk)$$$. If we set $$$k = n^{\frac{2}{3}}$$$, we get $$$O(n^{\frac{5}{3}})$$$.

Sample code

Algorithm 3.

Let's sort by <i / k, l / k, r>.

Let's call a block all the queries with the same i / k and l / k. For each block we can look at all the change queries, which we haven't already processed and which are connected with this block. The left pointer can move by $$$O(k)$$$ positions per query, the left pointer can move by $$$O(n)$$$ positions per block. If we set $$$n = q$$$, we get $$$O(\frac{n^{3}}{k^{2}} + nk)$$$. If we set $$$k = n^{\frac{2}{3}}$$$, we get $$$O(n^{\frac{5}{3}})$$$.

Some more problems.

Problem 1
Problem 2
Problem 3
Problem 4
Problem 5
Problem 6

Full text and comments »

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