Hello Codeforces. I was about to participate in today's Edu round, but I noticed it suddenly disappeared without notice. Was the round cancelled or something? I'd like to know what the problem was.

Thanks in advance :-)

Recently we have seen many blog posts about the war. Some people think this is not the place to discuss such issues, and there are others who think it is not bad to write about politics on Codeforces. Thinking well, blogs conform something like a forum, and forums in general do have an off-topic section to discuss about various unrelated issues. What about adding something like that on Codeforces? Users who are upset of political issues can just see the regular blogs, and users who are interested in discussing about politics, war, etc, can get into the off-topic section. We could have two sections, one for CS and programming talks and the other for general topics.

What do you think? Write about it in the comments below!

Hello to the Codeforces community. I've been thinking if I should try to become red, since it would advance the competitive programming level in my country, besides improving my programming skills. However, there are other things I could do with the time and energy that training requires, like developing real applications or doing research. For red coders reading this, what your motivations were for becoming red? If you could return back in time, would you use your time on CP or on something else?

Thanks for reading ;-)

In interactive problems, pay attention to the limit of queries. It may give you a clue about the kind of queries to make.

I would like to ask for the option of making our practice solutions private to other people, if we don't want to show them for any reason. In that way user's privacy would be more respected.

Thanks in advance

Hello Codeforces community! I've been thinking on the possibility of a judge that runs in the user's machine. This would have many practical advantages like configuring the judge to support any programming language or adding custom compilation commands. Would be possible to develop a program like that? I hope someone with experience in the development of online judges could illuminate me with their knowledge.

Thanks in advance

Hi Codeforces! I've been asking myself how the best CPers in the world practice regularly. The general advice for practicing consist in solving problems with a slightly higher rating than the own, but the highest rating problems have in this website is *3500, and currently there are five active users with more than such rating. I'd like to know what they do for improving their level.

Thanks for reading.

Hi! Does someone from Latin America + Spain + Portugal know if there is a tutorial for this year's CIIC? I've been trying to solve the problems but I've been stuck for days.

Thanks in advance

Hi! I was upsolving a recent contest on CodeForces, and in one problem I received Accepted in the hard version but Wrong Answer in the easy one, because of test 47. I suggest adding that test to the hard version too, for a better judging.

Hi! I'd like to share with the community the template I use for competing in Codeforces rounds. It's very simple, so is easier to learn to use it.

I hope it helps someone :-)

#include <bits/stdc++.h>
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define fi first
#define se second
#define rep(i, a, b) for(int i=a;i<b;++i)
#define all(x) x.begin(), x.end()
#define sz(v) (int)(v.size())
#define feq(a, b) (fabs(a - b) < eps)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;

const ll INF = 1e18, MOD = 1e9+7;
const int int_max = 1e9;
const ld eps = 1e-9;

void solve() {
	
}
int main() {
	cin.tie(0) -> sync_with_stdio(0);
	int T = 1;
	cin>>T;//You can comment this if you don't need it
	while(T--) {
		solve();
	}
}

Hello everyone! I found some problems of the practice contest quite interesting, and I decided to share what I have done to solve them.

Update: The official solutions are available here.

Gift

First, we have to observe that if $$$x[i] = 2 (\forall 0 \leq i \leq n-1)$$$, then we can alternate between red and blue. For example, $$$answer[0] = 'R', answer[1] = 'B', \ldots$$$. This way, any interval of type 2 with a size larger than 1 is satisfied. So if there is a type 2 interval of size 1 the solution must return 0.

Each element in the same type 1 must be the same ('R' or 'B'), but there are overlapping intervals of type 1, which all must be of the same color. For doing that I sorted all the type 1 intervals according to their first element in non-decreasing order, then I iterated for each interval in the sorted vector comparing it's first element with the largest last element of the previous intervals, and in the case of being lower or equal I "mixed" both intervals into one and stored it in another vector of pairs, where the first element of each pair is the last element of the interval ans the second element is the first element of the interval (to run binary search on it later). This takes $$$O(n \log{n}) + O(n)$$$ time.

Now, it is possible there's a type 2 interval completely inside a type 1 interval or a "mixed" interval, and in that case we have to return 0. For each type 2 interval we run a binary search to find the "nearest" type 1 "mixed" interval (the one with the minimum last element larger than the one of the type 2).

Finally we "paint" each block alternating between red and blue as follows: keep an index of the current "mixed" interval. Iterate for each block: if it's inside the current "mixed" interval and the previous block too, paint the current block with the same color you painted the previous one, else paint it with the other color. After all of that call $$$answer$$$ with the final string.

Total running time for this full solution is $$$O(n \log{n})$$$.

Squares

For the first subtask we can set $$$k = 1000$$$ and in each query, the answer will be the number of $$$-1$$$ of the given array.

For a better solution, we must notice each subarray (of std::vector labels) of size $$$k$$$ must be different to every other subarray of size $$$k$$$. The idea I had is to iterate for each element of labels from $$$k$$$ to $$$n-1$$$ (inclusive) and put $$$0$$$ unless is necessary to put $$$1$$$, that is, when the first or second element of such sub-array is $$$1$$$, because if we put $$$0$$$ in that case we aren't going to increase the number of $$$1$$$s in the next iteration, a necessary datum for finding $$$x$$$ later.

After doing what I explained in the last paragraph, our subarrays should look like that: $$$[0, 0, \ldots, 0], [0, 0, \ldots, 1], [0, 0, \ldots, 1, 0], \ldots, [0, 1, \ldots, 0, 0], [1, 0, 0, \ldots, 1], [0, 0, \ldots, 0, 1, 1], [0, 0, \ldots, 0, 1, 1, 0], \ldots, [1, 1, \ldots, 1, 1]$$$. Note that with this methods we're gonna have $$$k-1$$$ different sub-arrays of size $$$k$$$ with $$$m$$$ $$$1$$$s, for each $$$m$$$ from $$$1$$$ to $$$k-1$$$, so tthis method works for an array with size less than $$$(k-1)^2$$$, which is enough for subtasks 1, 2, and 3.

In each query, we first look for the index of the first $$$-1$$$ in the input vector. Being $$$i$$$ such index if it exists, we return $$$n-i$$$. Else we continue counting the number of $$$1$$$s. Being $$$m$$$ such number we return $$$m*(k-1) + k-j$$$ where $$$j$$$ is the index of the first $$$1$$$ after a $$$0$$$.

Please write the full solution in the comments below, because I didn't find it.

Update (full solution): The main idea is to create an array $$$p$$$ of $$$0$$$s and $$$1$$$s of size $$$n$$$ such that every sub-array of size $$$k$$$ is unique. We can store the starting position of every possible sub-array in another array of size $$$2^k$$$ (with $$$k = 10$$$ if we want to get full score), accessing the indexes of that array using bit-masks. For example, let $$$r$$$ be the position array, $$$r[11]$$$ stores the position of the sub-array $$$[0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0]$$$. In that way, is enough to "translate" the input array in find_location to an integer $$$val$$$ (in this case, a bit-mask) and return $$$r[val]$$$, but first is necessary to check if the input array has some $$$-1$$$. Now you may be asking, how to generate $$$p$$$ in first place?

That problem is equivalent to building a De Brujin sequence with $$$A = {0, 1}$$$. You can read the G4G article if you want more details, but in summary we can do it by constructing an implicit directed graph such that each node represents a sub-array of length $$$k-1 = 9$$$ (again, is better to use bit-masks rather than vectors) and has two edges: one representing $$$1$$$ and the other representing $$$0$$$. Each of them "adds" its associated number to the original sub-array, and "eliminates" the first one. Note that both the in-degree and the out-degree of each vertex is equal to 2, so we can run a modified DFS to find an Eulerian circuit while storing the number associated with each node traversed (representing a sub-array) and after that create the sequence from the Eulerian Circuit. For more details you can check the official solution.

Routers

In this problem we have to implement binary search to find the location of routers in $$$O(\log{l})$$$ time each one. This works for Subtasks 1 and 2.

For reducing the number of queries when looking for the location of each router, I stored in a vector the minimum location where $$$use detector(x)$$$ appears each time I called $$$use detector$$$. In that way, I for each router $$$i$$$ I iterated for each element of the vector until I find an element and set the right bound of the binary search with that element. I also set the left bound with the position of the last router "discovered" plus one. Reducing the space search in that way I could get like 37 of 40 points.

Jelly

First of all, this is an optimization problem, because we have to maximize the different number of flavours we can buy with the given constraints. This is important, considering that we know we may approach the problem with dynamic programming or binary search, for example, depending on the constraints.

The source code of my solution can be found here. Feel free to download it and view it on your favourite text editor since it doesn't look well on the webpage.

Subtask 1

One of the most accurate ways to find the best answer is to try all possible combinations and then select the best of them. In this case, we can write two nested loops with $$$i$$$ and $$$j$$$, bit-masks representing the flavours we buy in Store A and in Store B, respectively (if a bit $$$k$$$ is equal to $$$1$$$ then we buy flavour $$$k$$$). In each iteration, we must check that the sum of costs of flavours bought don't surpass our budget ($$$x$$$ in the case of Store A, and $$$y$$$ in the case of Store B). After that, we update the answer variable if appropriate.

The time complexity of this solution is $$$O(n2^{2n})$$$, so it passes the system testing because in this subtask $$$n \leq 12$$$.

Subtask 2

The complete search approach described above won't work in this subtask because this time $$$n \leq 200$$$, but we can apply dynamic programming with a 3-dimension DP table. $$$dp[i][j][k]$$$ is the answer for the first $$$i$$$ flavours with $$$j$$$ budget in Store A and $$$k$$$ budget in Store B. We initialize the table with all values equal to $$$0$$$. After that, we iterate the table and updating each element with the maximum answer between not buying flavour $$$i-1$$$ ($$$dp[i-1][j][k]$$$), buying it in Store A ($$$1+dp[i-1][j-a[i-1]][k]$$$) and buying it in Store B ($$$1+dp[i-1][j][k-b[i-1]]$$$). After all iterations we return $$$dp[n][x][y]$$$ (I guess you realize why).

The time and memory complexity of this solution is $$$O(nxy)$$$, which is more or less $$$O(n^3)$$$.

Subtask 3

In this subtask, we have no budget for Store B, so unless flavour $$$i$$$ is free in Store B ($$$b[i] = 0$$$), we have to buy it in Store A. Of course, is convenient for us to buy the cheapest flavours possible to save money and buy the biggest quantity possible. We create another vector $$$c$$$ such that $$$c[i] = (a[i], b[i])$$$ and then sort it. Then we iterate $$$c$$$ from $$$0$$$ to $$$n-1$$$ adding $$$1$$$ to the answer each time we find a free flavour or a flavour that we can buy in Store A. We have to update our budget each time we buy some flavour in Store A.

The time complexity of this solution is $$$O(n lg n)$$$ or $$$O(n)$$$, depending on how we sort $$$c$$$.

Subtask 4

The solution for this subtask is like the one for the previous one but this time we only need to sort $$$a$$$, iterate it buying all flavours possible until we can't continue buying in Store A. Then we continue buying in Store B until buying all $$$n$$$ flavours or finishing with our budget for both Stores.

The time complexity of this solution is $$$O(n lg n)$$$ or $$$O(n)$$$, depending on how we sort $$$a$$$. Note is not necessary to sort $$$b$$$ since all elements in $$$b$$$ are equal.

Subtask 5

We have to note if we can buy $$$i$$$ flavours, then we can buy $$$i-1$$$ (if and only if $$$i > 0$$$) and if we can not buy $$$i$$$ flavours, then we can't buy $$$i+1$$$. Thus, we can implement a complete search solution trying to buy different flavours until we can't continue.

First, we have to sort $$$a$$$ and $$$b$$$ to select the cheapest flavours possible. Then we buy all possible flavours in Store A starting from 0 all possible flavours in Store B starting just after the last flavour we couldn't buy in A. After that, the idea is to "change" stores: instead of buying some flavours we already bought in A, we try to buy them in B (we can do it by iterating backwards, if $$$i$$$ is the flavour to buy, then we iterate from $$$i-1$$$ to $$$0$$$). This way, we can have more money to buy the next flavour in Store A. If that is not enough, then we reverse the change and we try to buy some flavours we already bought in B in Store A to save money to buy the next flavour in Store B. If even that is not enough, then we stop and return the number of flavours we could buy.

The time complexity of this solution is $$$O(n lg n)$$$ or $$$O(n)$$$, depending on how we sort $$$a$$$ and $$$b$$$.

Subtask 6

First we create $$$c$$$ such that $$$c[i] = (a[i], b[i])$$$ and we sort $$$c$$$ in non-decreasing order. Also, we maintain two different 2-dimensional arrays or vectors, $$$dp0$$$ and $$$dp1$$$, $$$dp1[i][j]$$$ stores the maximum number of flavours from $$$i$$$ to $$$n-1$$$ we can buy in Store B with $$$j$$$ amount of money and $$$dp0[i][j]$$$ stores the minimum amount of money we need to spend in Store B to buy all flavours from $$$0$$$ to $$$i-1$$$ (inclusive) with $$$j$$$ amount of money. The idea of this is not having to decide between buying in A or in B because doing that would consume too much memory, since $$$x, y \leq 10000$$$. Also, since $$$c$$$ is sorted for Store A we know is cheaper to buy flavours with smaller numbers in the sorted $$$c$$$.

Thus, we can fill $$$dp1$$$ like in the knapsack problem but each flavour has a value of $$$1$$$, and $$$dp0[i][j]$$$ as the minimum between $$$dp0[i-1][j]+c[i-1].second$$$ (buying flavour $$$i$$$ in Store B) and $$$dp0[i-1][j-a[i-1].first]$$$ (buying flavour $$$i$$$ in Store A if we have enough money). After filling both tables, we iterate from $$$0$$$ to $$$n$$$ (inclusive) looking for the answer: if $$$i$$$ is our iterator, then we consider buying $$$i$$$ flavours plus the maximum number of flavours we can buy only in Store B from $$$i$$$ to $$$n-1$$$ with a budget of $$$y-dp0[i][x]$$$.

The time and space complexity of this solution are something like $$$O(n^2)$$$.

Now this "editorial" contains all problems, but some of them are poorly explained. Please comment if you want me to continue improving this, or ignore if you don't care.

Hi! I was trying to solve that problem but it gave me WA on subtask 3. Reading the official solution, I realized that it was pretty similar to what I did, but verifying that the two components have a size more than a. I verified that the remaining component (the one not used to assign vertices to A) had a size more than or equal to b.

Could someone tell me why the solution works? I just don't get it. Logically speaking (or writing lol), it would be impossible to assign b vertices from a subgraph of size less than b.

Update: Thinking very much, I realized why it works. Please correct me if I am wrong. If the size of the remaining component is greater or equal to a and lower than b, then we can use such component to assign vertices to A and the "original" one to assign vertices to B, because the size of the original component is greater than (a+b+c)-b = (a+c) >= b (remember b <= c so b <= a+c).

Hello CodeForces!! Today an update was released from the IC saying that IOI 2020 will be held online and Singapore will be the host for IOI 2021. It is sad to read that, especially since this year is going to be my final one. But it is much better than to cancel the contest.

Hi everyone! I've noted most recent CF problems have no rating. Is that made on purpose, or is a bug? If is the first case, why?

Hi again! I'd like to ask if competitive programming is useful as a preparation for computer science research, specially in the field of data structures and algorithms. If yes, what skills are the most used? I hope someone working in academia could tell me in which way CP helps or helped him/her in his/her regular work.

Thanks in advance <3

Hello CF community. I was asking myself which companies competitive/sport programmers are more attracted to, or if they run their own startups. In my case, I don't know where do I want to work yet, but I know Competitive/Sport programming is going to help me very much in my life.

Thanks for reading! :-)

When i submitted my solution, the judge throws me Runtime Error on test 8, more specifically with this test:

10 10
.........*
.........*
........**
.........*
.........*
.........*
.........*
.........*
.........*
.........*

But i ran the program with this test in my computer and it works correctly and the output is correct:

YES
3 10