Author: zidder
Preparation: _LeMur_
Editorial: zidder
Official solution: 238752794
What is the minimum product that we can get, when one of the given numbers is equal to $$$0$$$.
How is the absolute value of the integer changed, when we apply the given operation on that integer?
We can always make the product as small as possible with at most $$$1$$$ operation.
First, let's find the minimum product we can get. If one of the numbers is or becomes $$$0$$$, then the product will be $$$0$$$. Otherwise, all the numbers don't change their sign during the operation. So the initial product won't change its sign as well. Also, we can note that the absolute value will not increase after an operation. That means if the initial product is negative, we cannot decrease it. In this case the necessary number of operations will be $$$0$$$.
If the initial product is positive, then we know the product won't become negative, therefore we will make it zero with $$$1$$$ operation, which will be the answer and the operation will be changing any number to $$$0$$$. If the initial product is zero, then we don't need to change anything, so the number of operations needed is $$$0$$$.
1917B - Erase First or Second Letter
Author: _LeMur_
Preparation: _LeMur_
Editorial: zidder
Official solution: 238752759
Do we need to use the first operation after the second operation?
Try to fix the number of the applied first operation. How many different strings can be obtained?
When can two reached strings be the same?
Try to consider the first occurrence for each letter.
Let's first see, that applying the second operation and then the first is equivalent to applying the first operation twice. In the former case the string will become $$$s_1s_2s_3 \ldots s_n \to s_1s_3 \ldots s_n \to s_3 \ldots s_n$$$, and in the latter case: $$$s_1s_2s_3 \ldots s_n \to s_2s_3 \ldots s_n \to s_3 \ldots s_n$$$. As we are concerned with only the number of distinct resulting strings, let's assume that the second operation is never done before the first operation. This means we do $$$op_1$$$ first operations (possibly zero) and then $$$op_2$$$ second operations (possibly zero).
Let's now find the result of applying $$$i$$$ of the first and then $$$j$$$ of the second operations. It's easy to see, that the result is $$$s_{i+1}s_{i+j+2}s_{i+j+3} \ldots s_n$$$.
The only remaining question is in which cases two sequences of operations such that the first operation always comes before the second result in the same string. Consider for the $$$(i_1, j_1)$$$ pair, the resulting string is the same as for the $$$(i_2, j_2)$$$ pair. We can see that $$$i_1+j_1 = i_2+j_2$$$, because the number of erased letters should be the same to get strings of the same length. Next, $$$s_{i_1+1} = s_{i_2+1}$$$ as those are the first letters of two resulting equal strings. It's easy to see that these conditions are also sufficient for the result to be the same string.
If after applying the first operation $$$op_1$$$ times the first letter is not its first occurrence, then any subsequent result could have been achieved by less operations of the first type by removing first character until reaching that letter and then by removing the second character until we reach $$$op_1$$$ operations in total. This means we need to consider using the second operation only at the first occurrence of the letter.
The final solution can look like this: for each letter $$$a \ldots z$$$ find it's first occurrence. If the letter is found, any number of second type operations lead to a different result. Thus we can just calculate the number of second operations that is valid and add that to the answer.
Author: IgorI
Preparation: IgorI
Editorial: IgorI
Official solution: 238743155
Assume that you are starting with array $$$a=[0, 0, \ldots, 0]$$$.
Can your score increase by more than $$$1$$$ in this case?
Note that array $$$a$$$ is non-increasing after each operation and $$$[1, 2, \ldots, n]$$$ is strictly increasing.
Try fixing the first day you make reset operation on.
Can your score increase by more than $$$n$$$ on reset operation?
Let's first solve this problem if we start with the array $$$a=[0, 0, \ldots, 0]$$$. This array is non-increasing and adding $$$1$$$ to any of its prefixes keeps it non-increasing. On the other hand, array $$$[1, 2, \ldots, n]$$$ is strictly increasing. This means that if $$$a_i=i$$$ and $$$a_j=j$$$ then $$$i=j$$$ (because if $$$i<j$$$ then $$$a_i \ge a_j$$$ and both conditions cannot hold simultaneously). Thus you cannot increase your score by more than $$$1$$$ in one reset operation. Also you cannot increase your score by $$$1$$$ in two operations in a row, because array $$$a$$$ will be equal to $$$[0, 0, \ldots, 0]$$$ before the second of this operations. Similary, you cannot increase your score on the first day. Thus, the maximum score you can get is $$$\lfloor \frac{d}{2} \rfloor$$$. On the other way, you can always achieve this score by alternating operations.
So once we fixed the first day $$$i$$$ we are making reset operation on, we can easily compute the maximum total score we will get for all the further days. Trying all $$$d$$$ possibilities of the first day $$$i$$$ we are making reset operation on is too slow. But do we need to wait for this for more than $$$2n$$$ days? Actually no because then we will get at most $$$n$$$ score for waiting for $$$2n+1$$$ days, but we can get the same (or the greater) score by doing the first reset operation on the first day.
Thus, we can solve this problem in $$$\mathcal{O}(n\min(n,d))$$$.
Find the number of ways to achieve the maximum score.
Solve this problem for the larger $$$n$$$.
1917D - Yet Another Inversions Problem
Author: IgorI
Preparation: IgorI
Editorial: IgorI
Official solution: 238743552
How to count the number of inversions in the permutation of length $$$n$$$ in $$$\mathcal{O}(n \log n)$$$?
Consider two arrays $$$x_1, x_2, \ldots, x_k$$$ and $$$\alpha x_1, \alpha x_2, \ldots, \alpha x_k$$$ for some positive $$$\alpha$$$. How does the number of inversions in one of them correspond to the number of inversions in the other of them?
Consider splitting array $$$a$$$ into subarrays of the length $$$k$$$.
Let's say you have two arrays $$$[11, 22, 44, \ldots, 11 \cdot 2^m]$$$ and $$$[13, 26, 52, \ldots, 13 \cdot 2^m]$$$ of the same length. How many inversions are there in their concatenation $$$[11, 22, 44, \ldots, 11 \cdot 2^m, 13, 26, 52, \ldots, 13 \cdot 2^m]$$$?
Consider the merging process of arrays $$$[11, 22, 44, \ldots, 11 \cdot 2^m]$$$ and $$$[13, 26, 52, \ldots, 13 \cdot 2^m]$$$ into the sorted array (as in the merge sort).
What if the first elements of the arrays you concatenate are not $$$11$$$ and $$$13$$$ but some odd positive integers $$$x$$$ and $$$y$$$? Merging processes for some pairs $$$(x, y)$$$ look quite similar.
The number of inversions in the array $$$[x, 2x, 4x, \ldots, 2^m x, y, 2y, 4y, \ldots, 2^m y]$$$ depends only on $$$\lfloor \log_2(\frac{y}{x}) \rfloor$$$ and $$$m$$$. You don't need to think about rounding of $$$\log_2(\frac{y}{x})$$$ because $$$x$$$ and $$$y$$$ are odd in this problem. Also, $$$m$$$ is the same for all merges.
Consider the following $$$\mathcal{O}(n \log n)$$$ algorithm to find the number of inversions in the permutation: make a segment tree corresponding to this permutation and fill it with zeroes. For all $$$i$$$ from $$$1$$$ to $$$n$$$ find $$$j$$$ such that $$$p_j=i$$$, increase the $$$j$$$-th element of this segment tree by $$$1$$$ and add the sum of elements on the right of the $$$j$$$-th element to the number of inversions. Improve this algorithm to count the number of inversions in array $$$a$$$ assuming $$$q=[0,1,\ldots,k-1]$$$.
The problem can be solved in $$$\mathcal{O}(n \log n \min(\log n, k) + k \log k)$$$. The order of elements in $$$q$$$ matters only on the inversions inside the blocks of length $$$k$$$ you chosen in the hint $$$2$$$.
Let's split the array $$$a$$$ into subarrays of the length $$$k$$$. The relative order of the elements in each of them is the same (as in permutation $$$q$$$), so the number of inversions is the same, too. You can find the number of invesions in one of them as described in the hint $$$7$$$. By multiplying this number by $$$n$$$, you count all the in-block inversions.
All the remaining inversions are formed by pairs of elements from the distinct blocks. You may assume that $$$q=[0, 1, \ldots, k-1]$$$ now for simplicity: it won't change the number of such inversions.
Let's fix two elements $$$x$$$ and $$$y$$$ of $$$p$$$ and count the number of inversions $$$(i, j)$$$ such that $$$a_i = x \cdot 2^{\alpha}$$$ and $$$a_j = y \cdot 2^{\beta}$$$ for some $$$\alpha$$$ and $$$\beta$$$. It is equivalent to counting the number of inversions in the array $$$[x, 2x, 4x, \ldots, 2^mx, y, 2y, 4y, \ldots, 2^my]$$$.
Consider merging two arrays $$$[x, 2x, 4x, \ldots, 2^mx]$$$ and $$$[y, 2y, 4y, \ldots, 2^my]$$$ with $$$x < y$$$ ($$$x$$$ and $$$y$$$ are odd) into one sorted subarray:
- if $$$\color{blue}{x} < \color{red}{y} < \color{blue}{2x}$$$, then the resulting array would look like $$$[\color{blue}{x}, \color{red}{y}, \color{blue}{2x}, \color{red}{2y}, \color{blue}{4x}, \color{red}{4y}, \ldots, \color{blue}{2^mx}, \color{red}{2^my}]$$$;
- if $$$\color{blue}{2x} < \color{red}{y} < \color{blue}{4x}$$$, then the resulting array would look like $$$[\color{blue}{x}, \color{blue}{2x}, \color{red}{y}, \color{blue}{4x}, \color{red}{2y}, \color{blue}{8x}, \color{red}{4y}, \ldots, \color{blue}{2^{m-1}x}, \color{red}{2^{m-2}y}, \color{blue}{2^mx}, \color{red}{2^{m-1}y}, \color{red}{2^my}]$$$;
- if $$$\color{blue}{4x} < \color{red}{y} < \color{blue}{8x}$$$, then the resulting array would look like $$$[\color{blue}{x}, \color{blue}{2x}, \color{blue}{4x}, \color{red}{y}, \color{blue}{8x}, \color{red}{2y}, \color{blue}{16x}, \color{red}{4y}, \ldots, \color{blue}{2^{m-1}x}, \color{red}{2^{m-3}y}, \color{blue}{2^mx}, \color{red}{2^{m-2}y}, \color{red}{2^{m-1}y}, \color{red}{2^my}]$$$;
- ...
You can see several blue elements in the beginning, followed by alternating blue and red elements, which are followed by several red elements. The number of blue elements in the beginning is equal to the number of red elements in the end and equal to the largest $$$z$$$ such that $$$2^z x < y$$$. Furthermore, this $$$z$$$ is also limited by $$$\log n + 1$$$ because $$$x$$$ and $$$y$$$ are both positive integers less than $$$2n$$$.
If $$$x > y$$$ the situation is similar, but the order of colors is reversed.
Going back to inversions, we have some array $$$[\color{blue}{x}, \color{blue}{2x}, \color{blue}{4x}, \ldots, \color{blue}{2^mx}, \color{red}{y}, \color{red}{2y}, \color{red}{4y}, \ldots, \color{red}{2^my}]$$$. Inversions are formed by a large blue element and a small red element.
- if $$$x < y < 2x$$$, then there are $$$0+1+2+\ldots+m=\frac{m(m+1)}{2}$$$ inversions;
- if $$$2x < y < 4x$$$, the there are $$$0+0+1+2+\ldots+(m-1)=\frac{m(m+1)}{2} - m$$$ inversions;
- if $$$4x < y < 8x$$$, the there are $$$0+0+0+1+2+\ldots+(m-2)=\frac{m(m+1)}{2} - m - (m-1)$$$ inversions;
- ...
For $$$x > y$$$ the situation is similar, but we will start with $$$1+2+3+\ldots+m+(m+1)=\frac{(m+1)(m+2)}{2}$$$ inversions for $$$y < x < 2y$$$ and we will add $$$m, (m-1), \ldots$$$ terms instead of substracting them.
Well, now we can solve this problem in $$$\mathcal{O}(n^2 \log n)$$$: enumerate pairs $$$(x, y)$$$, find $$$\log_2(\frac{y}{x})$$$ and add some value to the answer.
Now let's add the inversion counting algorithm to solve this problem. Again, let's solve the problem for $$$x < y$$$ first. Let's enumerate the value of $$$y$$$ from $$$1$$$ to $$$2n-1$$$.
- the $$$x$$$-s on the right of $$$y$$$ should not be counted in now;
- each of the $$$x$$$-s on the left of $$$y$$$ such that $$$x < y$$$ adds $$$\frac{m(m+1)}{2}$$$ to the answer;
- each of the $$$x$$$-s on the left of $$$y$$$ such that $$$2x < y$$$ adds $$$\frac{m(m+1)}{2} - m$$$ to the answer;
- each of the $$$x$$$-s on the left of $$$y$$$ such that $$$4x < y$$$ adds $$$\frac{m(m+1)}{2} - m - (m-1)$$$ to the answer;
- ...
We can maintain a segment tree to compute the sum of the values we should sum up. To update this segment tree let's additionally maintain $$$\Theta(\log n)$$$ pointers that maintain the largest $$$x$$$ such that $$$2^z x < y$$$ for each $$$z$$$ from $$$0$$$ to $$$\lceil\log n\rceil$$$.
The solution is similar for $$$x > y$$$ pairs.
You should be careful when implementing this, because for small $$$k$$$ at some moment there becomes $$$0$$$ elements in the alternating segment of the blue-red array and you shouldn't substract anything further.
You are also given $$$s$$$ queries of the following two types:
- Swap $$$p_i$$$ and $$$p_j$$$
- Swap $$$q_i$$$ and $$$q_j$$$.
Perform these queries and maintain the answer.
You given three permutations $$$p$$$, $$$q$$$ and $$$r$$$ of lengths $$$l_1$$$, $$$l_2$$$, $$$l_3$$$ (of the first $$$l_1$$$, $$$l_2$$$ and $$$l_3$$$ positive integers correspondingly) and array $$$a$$$ is defined as $$$a[i \cdot l_2 \cdot l_3 + j \cdot l_3 + k] = p[i] \cdot 2^{q[j]} \cdot 2^{2^{r[k]}}$$$. Find the number of inversions in it.
Author: _LeMur_
Preparation: _LeMur_
Editorial: _LeMur_
Official solution: 238752669
Does solution exist when $$$k$$$ is odd?
What can you understand when $$$k = 2$$$ or $$$k = n^2 - 2$$$?
How can we easily fill the matrix with $$$1$$$s, such that all problem conditions are satisfied when $$$k$$$ is divisible by $$$4$$$?
How will you solve the problem when $$$k = 6$$$?
Try to merge ideas of Hint $$$3$$$ and Hint $$$4$$$ together.
First, let's note that when $$$k$$$ is odd, the solution doesn't exist. It's obvious since in the solution the xors of all the rows are the same, it follows that the parity of the number of $$$1$$$s in each row is the same, and let's remember that $$$n$$$ is even, and from these conditions get that solution exists only when $$$k$$$ is even.
Second, let's note that for $$$k = 2$$$ or $$$k = n^2 - 2$$$, the solution exists only for $$$n = 2$$$.
For all other cases, a solution always exists.
- when $$$k \equiv 0 \pmod{4}$$$, we can fill $$$\frac{k}{4}$$$ submatrices of size $$$2 \times 2$$$.
- when $$$k \equiv 2 \pmod{4}$$$. Let's note that $$$k \geq 6$$$. Let's write $$$1$$$ in the following positions: $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(2, 1)$$$, $$$(2, 3)$$$, $$$(3, 2)$$$, $$$(3, 3)$$$. After this, we should fill the remaining $$$(k - 6)$$$ ones, and let's note that $$$(k - 6) \equiv 0 \pmod{4}$$$. There are obvious $$$\frac{n^2 - 16}{4}$$$ submatrices of size $$$2 \times 2$$$, which aren't filled yet — outside the top left $$$4 \times 4$$$ submatrix. If $$$k < n^2 - 6$$$, then we can fill as many of those $$$2 \times 2$$$ submatrices as necessary, otherwise if $$$k = n^2 - 6$$$, we can also fill with $$$1$$$s the following $$$4$$$ positions too: $$$(1, 3)$$$, $$$(1, 4)$$$, $$$(4, 3)$$$, $$$(4, 4)$$$.
Can you solve the problem for odd $$$n$$$?
tourist solved it!
Author: _LeMur_
Preparation: _LeMur_
Editorial: _LeMur_
Official solution: 238752543
If a solution exists, then we can always construct a tree containing a diameter and edges incident to the vertex $$$v$$$ ($$$v$$$ is from diameter).
Try to consider the maximum of the given lengths.
What can we say when there exist two lengths with a sum greater than $$$d$$$?
If a solution exists, then there should be a subset of lengths with the sum equal to $$$d$$$.
Consider cases when there exists a subset of lengths containing the maximum length with the sum equal to $$$d$$$ and doesn't.
Knapsack with bitset.
Let's consider the lengths in increasing order: $$$l_1 \leq l_2 \leq \ldots \leq l_n$$$. We will discuss some cases depending on the maximum length $$$l_n$$$:
- If $$$l_n + l_{n - 1} > d$$$, then the solution doesn't exist since an arbitrary tree will have a diameter greater than $$$d$$$.
- There exists the subset of the given lengths $$$l$$$, such that the sum of the lengths of that subset is equal to $$$d$$$ (for making a diameter) and $$$l_n$$$ is in that subset. In this case, the solution always exists, since we can construct a tree for example in the following way: let's consider that the size of the found subset is equal to $$$k$$$, then we can connect the vertices from $$$1$$$ to $$$k + 1$$$, such that the vertices $$$i$$$ and $$$i + 1$$$ are connected by edge for each $$$1 \leq i \leq k$$$ and $$$length(1, 2) = l_n$$$. We have some remaining lengths that we haven't used yet, so we can add edges for each length incident to the vertex $$$2$$$. Added edges will not increase the diameter, since $$$l_n$$$ is greater than or equal to all the remaining edges and $$$l_n + l_{n - 1} \leq d$$$. To check if there exists a subset of lengths such that it contains $$$l_n$$$ and the sum of elements in the subset is equal to $$$d$$$, can be easily done by the knapsack algorithm.
- Here, we need to find the subset of the given lengths $$$l$$$, such that the sum of the lengths of that subset is equal to $$$d$$$ (for making a diameter and we also know that $$$l_n$$$ can not be in that subset). Let's consider that diameter consisting of the vertices $$$v_1$$$, $$$v_2$$$, $$$\ldots$$$, $$$v_k$$$, such that $$$v_i$$$ and $$$v_{i + 1}$$$ are connected by edge for each $$$1 \leq i \leq k - 1$$$. Now, we need to connect an edge with length $$$l_n$$$ to the one vertex $$$v'$$$ from diameter, such that both $$$dist(v', v_1) + l_n < d$$$ and $$$dist(v', v_k) + l_n < d$$$. All the other not-used lengths we can also connect to the vertex $$$v'$$$. To check this, we should write knapsack but with two states: $$$dist(v', v_1)$$$ and $$$dist(v', v_k)$$$.
Knapsack can be done using bitset and the final complexity will be $$$O(\frac{n \cdot d^2}{64})$$$. You can also optimize this two times, since we know that the minimum of $$$dist(v', v_1)$$$ and $$$dist(v', v_k)$$$ is at most $$$\frac{d}{2}$$$.
Auto comment: topic has been updated by _LeMur_ (previous revision, new revision, compare).
Just Missed C by implementation,and i thought i can solve problems that are implementation based easily...C proved i was wrong.
Same here bro :(
Thank you for the fast editorial! Also between this and Pinely round I have a huge Christmas backlog to upsolve.
Thanks for the fast editorial
problem E is wangba.
hello
What are you fking doing?
lol
why bitsets
Fixed it, thanks!
Oh it was bitsets. I was thinking how to get the two sets in better that $$$n d^2$$$ complexity.
Respect for the fast editorial.
Disrespect for a wrong number in contest's title
C was really frustraing. Anyways, nice idea and observation.
bitset in the author's solution,
I really don’t understand why after EVERY ROUND with a bitset in author’s solution, someone has to complain. Bitset is a very good optimization by at least a factor of 32, which is huge both in competitive programming and real life job programming: imagine google pages or apps loading 32 times slower! Bitset is also something quite easy to learn, a lot less advanced than (for instance) a segtree, so it appearing in a div2F or E should really not represent a problem. So why not use it when it is available and force contestants to know it as well?
Non c++ users are at disadvantage in these problems
i dont know but somehow a is more tougher than b
actually a just have few logical cases thats it and we miss that. in B one the idea was great to just traverse the array add chraacter to set and increment count variable by set size everytime
no :)
C's pretests are really weak, I did same thing with k instead of 2 * n +1; how this case couldn't create? Respect to authors but these are really unnecessary things for FST :(
whats FST?
Failed in System Test
fst round lets gooo
Overkilled and missed D by a few minutes.
any countertest for C 238728699 please?
you can do 1st type of opearation on 1st 9 days, then 2nd type operation on 10th day. ans will be 7 in this case.
who solve B with dp or something different from guide?
238697447
can you explain the intuition behind this solution?
simple observation of first and last test cases: in first — aaaaa all chr are same and ans is 5; in last -abcd.... all chr are unique and ans is 210;
so we can assume that initial ans should be sum of 1,2,3..n, and we need to subtract some value when we have same characters: so first test case ans is 5 (15 — x) x is 10 here right, and for last is 210 — 0. and if you continue you could find this x calculating from similar chr in s
Thanks!
How can we calculate x??
edgerunner
https://codeforces.net/contest/1917/submission/238697447
Intuition:
A string with all unique characters will have n(n+1)/2 distinct strings.
If any of the character pair repeats then they will produce duplicate set of strings. A 5 length string can produce 2 4 length strings if the character pairs are unique, but if they are same then they will produce only, 1 4 length string.
Try making a tree and you will see that on each level you are doing + 1 to the strings formed in previous level. But in case of repeating character you do + 0 to the strings formed in previous level.
A more intuitive solution for B is to iterate over string and find number of distinct characters from 2nd position onwards. At every index, number of distinct strings of length (n-i+1) that can be made is number of distinct characters. Time complexity will be O(N) as set will have constant time complexity(max size is 26).
your solution is far better than editorial
Thank you for the fast editorial and Merry Christmas to everyone celebrating!
E is nice.
It's nice to see that someone evaluates authors' work :)
Let see if Specialist is in sight!!!
Congrats!! :)
Thanks 619.
Can anyone explain why this works for B?
Read the editorial, because the problem reduces to for each $$$j$$$ count all possible $$$s_i s_j s_{j+1} \ldots s_n$$$ where $$$i<j$$$
and choices for $$$s_i$$$ are exactly the number of distinct characters in the prefix $$$s_1 \ldots s_{j-1}$$$
For a string of remaning suffix length l, you can take remove any (n-l-1) elements from (n-l) elements, so only one character is left , thus (l+1) length string with number of distinct character at starting
The idea is based on the fact that every new character encountered introduces new possibilities for generating distinct strings.
First let us suppose all characters are distinct eg. abc then possible strings will be abc, bc, ac, c, b, a. See we have 1 occurrence of length 3, 2 occurrence of length 2 and 3 occurrence of length 3. So what we are doing is we are selecting the Substring from [0,i) and deleting it except one character which gives one occurrence. There are total i ways to select one character between [0,i) substring. Therefore, we need the count of distinct characters at every position of i and add it to our answer.
Rare rare contest where system test cases are tricky. I can't remember the last time so many people got their submissions rejected. Unfortunately Problem $$$C$$$ test case $$$26$$$.
https://codeforces.net/contest/1917/submission/238696258 Can anyone tell why my sol gives wrong answer
Look at the constraints !! It says $$$a_{i} \leq 10^9$$$. Suppose all $$$a_{i}$$$ have that upper bound value. Their multiplication will be $$$10^{900}$$$ which can't be represented as $$$long$$$. There will be overflow leading to unexpected behavior.
I guess C was the toughest problem.
a little bit deceptive
"You are not allowed to view the requested page."
I got this message when I click on Official solutions: A, B, E, F
The only reason I managed to solve B was pattern recognition. I coded a slow solution, and saw that the amount of possibilities that got added on with each new character of s were equal to the amount of unique characters encountered so far.
solved D for the transpose matrix instead, it was a cool problem too :D
Can you give intuition behind it? i was thinking same in contest.
consider two rows, if the difference between the q values of both of them is more than 20, the one with the higher q value will have all of it's element greater than the other. now for each difference from 1 to 20, you pre-calculate the number of inversions the cases when the lower q is ahead of the higher one and vice versa. rest can be handled using segment/fenwick trees
The submissions of problems A,B,E and F aren't puplic, Only C and D are (I guess it could have been submitted in the manager mode or something). _LeMur_
Nice contest, sadly I was busy so I managed only to attend the last hour :", (that is why I though of doing it in reverse).
I liked the problems F,E,D (in order)
Fixed it, thanks!
Div.2 E
wrong?
It is not wrong, but there can be multiple solutions, you can print any
l printed. Verdict: wrong.
You got wrong answer, because you print “YES” instead of “Yes”.
OK. I see
Great tutorial! Especially I loved the hints.
I have a question regarding my solution for problem C: Why it was enough for me to check for min(2 * n, d)?
full code
You don't need 2*n (you don't even need n actually), the only thing you're interested in is if your first reset could be made more optimal by adding a bunch of stuff so you have a better alignment. Let's say at time 0 you have 5 index that have the same value (so you're score is 5), you only need to check for 2*(n-5) (potentially), because past that, you can make up the point difference by spamming rule 1->2 which will give you 1 point every 2 steps.
For B, all final strings will be of the form of a single character and a suffix to the right, or just a suffix by itself. For the suffix case, just add n to your answer since there are n suffixes. For the other case, iterate over the suffix and count the #of characters to its left that aren't the same as the one immediately to its left and update the answer by that much to make sure we only consider unique strings.
My approach is a little bit different.
Assuming the answer will always have at least two letters. Then it will be one character and a suffix to the right.
So the answer would be for each suffix, add the number of distinct characters to its left.
Lastly, we add the number of distinct letters for answer that only has one letter.
Not being able to understand why 2*n works in Problem C.
actually crying about C, I had the entire solution up until the 2n+1 part which should be so obvious :(
can you please explain why 2n+1?
2*n because max count of ai==i is n and if you take days more than 2*n ratio of score to days will be less than considering alternating operations which will give 1/2 as score to day ratio
Thank you for the help
Exactly the same situation here !!
Can someone please explain why checking till the $$$(2*n + 1)$$$ th day is sufficient in Problem C?
https://codeforces.net/blog/entry/123721?#comment-1097328
first reset and use op1 and op2 operations for (2*n+1) days, max possible score of n can be achieved. We are trying to get maximum score from initial array of size n by applying op1 in (say x days) and get score y by using (x+1) days. So maximum score from initial array can be n, and this score can be achieved by simply using first op1 and then op2 for (2*n+1) days, so checking beyond (2*n+1) days to get maximum score from initial array by applying op1 is not helpful!
Can somebody explain me, why we are performing first type2 operation in min(d , 2 * n) days?? why 2*n?
Doing the first type2 operation can get at most n points. By doing opration(1,2) n times(2n times operations), you can get n points, too. So if you doing the first type2 operation on (2n+1)th day, why not doing 1+n*(1,2) instead?
Thank you for the help.
FST on C ..... [sad]
could someone help to find why my code have TEL?https://codeforces.net/contest/1917/submission/238891629
I use a set instead of log(k) pointers to find numbers, it should have a complexity of O(A*n*log(k)+k*log(k)).
in C problem if we take t=10^3 and n=2^103 then the total time complexity will be tc->10^3 * 2*10^3 * 2*10^3 ie O(t*n*(min(d,2*n))) ie finally tc->4*10^9 so how it is not giving tle as according to me 2sec->2*1e8 operations
"It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2000$$$"
You can't have $$$1000$$$ test cases each with $$$n = 2000$$$ as the sum of $$$n$$$ over all test cases would be greater than $$$2000$$$.
For the bonus part of problem E (n is odd). We can solve the problem as follows := First we note that if we have found a construction for k , then by inverting every bit we get another valid construction for k'= n ^ 2 — k.Let us handle odd k , for k >= n and k <= 2n — 1 . we can easily find solution for k = n , for k = n + 2 , we can place 1s at (1,1) ; (1,2) ; (1,3) ; (2,1) ; (3,1) and place rest of them on the diagonal i.e. a[i][i] = 1 for i >= 4. Now by filling 2 × 2 squares , we can get the solution for all odd k in [n, 2n — 1]. For even k <= (n-1)^2 , the problem reduces to the original problem E. Also note we can't have even k > n * (n — 1). For k in [(n-1)^2 + 1 , n * (n — 1)] we can reduce the problem to odd k' = n^2 — k. and we have already solved that. Similarly odds > 2n , can be solved by interting bits for k' = n^2 — k.
My screencast & editorial. Only problems A, B, C, but it's more than nothing.
here why we did a[l]++ we have to set it zero na then increment it ? pls help
Because you are calculating maximum possible score you get using first operation After second operation you can only get 1 point for 2 days (d-i-1)/2 where i is number of operations you perform of first type
In the editorial of C it was said we need to wait for atmax 2n days if 2n < d.Can someone explain this because i think atmax n days would be sufficient. Is there anything which i am missing ? 238724490
https://codeforces.net/blog/entry/123721?#comment-1097328
Hey thanks but can someone give a theoretical explantion.
Refer This comment
Problem C
For all who are confused regarding why we are iterating 2*n times instead n times, you can try this test case.
5 6 7
0 1 2 3 4
1 1 1 1 1 5
if you will iterate only n times, then you will get maxscore=3. But correct answer is 4.
In order to get correct answer you have to iterate more than n times
D is hard to write code
Can someone help with C. 238738762
I know that can be solved by $$$ O(n^2) $$$, but can be there other solutions than authors?
I used $$$ dp[i] $$$ like when $$$ a[i]==i $$$ and $$$ dp2[i] $$$ when $$$ (a[i]==i+1) $$$.
My solution is $$$ O(n*log2(k)+k*log2(k)+n^2) $$$
Can anyone give an example where min(d,n+2) fails and min(d,2*n+2) will pass and proof for 2*n
238785353
here you go
8 11 12
2 1 2 3 4 5 6 7
1 1 1 1 1 1 1 1 1 1 8
correct answer should be 7 but if you will iterate only till n+2, then you will get 5 as result which is wrong.
My solution for problem D is exactly $$$\mathcal O(n \log n \log V)$$$, which is the same as the tutorial. But it gets TLE on test 6, can anyone tell me why? thanks!
238788200
Can anyone explain in C why it is required to iterate up to 2*n???
Because after 2*n , We can't gain more than value of 'n' from type one operation . But we can gain more than 'n' from type two and one alternatively . So its optimal to not choose operation 1 after 2*n onwards . So we stop when it reaches 2*n .
see we know that after doing our first op2(if it is optimal),we need to repeat op1 and op2 for the rest of the days. But our score can be atmost n for the first op2.This is because we have n integers,so n positions can have ai=i atmost. So, n can be the max score from out first op2.Now,we know after doing our first op2 we will add (d-i)/2 to our score.if 2*n days have occured,this means if we directly start from repeating op1 and op2 we will get our score as 2*n/2=n and dont need to check for first op2 anymore.As after 2*n days we will always get an answer greater than n which cant be acheived anyhow by the most optimal score of first op2.so after 2*n days our most optimal approach will be to repeat 1st and 2nd operation .
the best reply for this question,finally solved my puzzle
true
helped me alot. Tks 4 this
Welcome
I read many comments till now and yours was the one that finally made me understand why 2*n. Thank you for the wonderful explanation.
for C , why cant we stop the loop for checking it by brute force just when the count (arr[i]==i) is more than possible(arr[i]<i)?
238793450
giving an WA
understood, it wont work for all sequence 1,1,1,1,1,1,1,1....
Can someone share how to solve B using DP?
For bonus part of C, you can refer to my solution. Time Complexity: $$$O(n\;log(d)\;log(k) + n\;log(n))$$$.
https://codeforces.net/contest/1917/submission/238793642
hi , for C, if we want to add to score on the first day , isnt it the best option if we have elements with arr[i]==i more than elements with arr[i]<i?, 238793450 if i remove line 38 it will pass , can you help me? thanks
NVM, as soon as i add the comment i get it:)
C got you
I was getting (WA) on test case 26 for Problem C
I solved C with going till $$$max(min(n,d),k)$$$ and it passed. You can try to hack, submission id: 238742923
Hacked.
You beat me. I was about to submit my hack
https://codeforces.net/contest/1917/submission/238804436 can someone help with reducing the time complexity of this code for the E problem since the time limit exceeds in 2nd test case
Problem B. Erase First or Second Letter ***** in second pretest ababa i am getting 10 strings please correct if i am wrong-->
ababa,baba,aaba,bba,aba,ba,aa,ab,b,a
It's not possible to get "b" and "ab" from your list
"This array is non-increasing and adding 1 to any of its suffixes keeps it non-increasing ". Isn't performing the first operation will increase its prefixes rather than its suffixes?
For Problem C.
How come the answer for this test case is 1 and not 3 ?
on the first day you will perform operation 1 and increase to make the array as 1 2 3 and on the second day, since all 3 numbers are equal to it's index, we will get answer as 3 and knock everything down to 0.
The answer should be 3 right ? please someone help me out here, I am attaching the link to my code as well : My code
Because in my opinion the answer must be mp[x]-(days-x-1)/2 where mp will store the number of terms with difference i+1-arr[i] if positive.
you misunderstood the question read it again
A Silly mistake in C ruined my contest
For C, if the waiting days >= 2n + 2, we can get n scores at most by way 1, but we must get n + 1 at least by way 2, so waiting days <= 2n + 1.
Great contest, in problem C when I try n times and get WA on test 3, I have a lucky guess 2*n and get AC :)
I have a 2n proof for C.
The min ans if we do reset at the begin is floor((d-1)/2).
The max ans if we wait after 2n op is n+floor((d-2n-1)/2)<=n+floor((d-1)/2)-n=floor((d-1)/2).
So we only try waiting at most 2n op.
great see by the way !!!
Can some explain why number of inversion in $$$[x, 2x, 4x, ..., 2^mx, y, 2y, 4y, ..., 2^my]$$$ depends on $$$\log_{2}\frac{y}{x}$$$?
Is it something like $$$x > y$$$ -> $$$x <= 2^m * y$$$ -> $$$m >= \log_{2}\frac{y}{x}$$$ but how does it affect the entire array ?
FOR THOSE WHO ARE CONFUSED WHY AUTHOR CHOOSED 2*N RATHER THAN N SUPPOSE WE ARE GIVEN A TEST CASE
9 12 12
9 1 2 3 4 5 6 7 8
1 1 1 1 1 1 1 1 1 1 1 9
SO FOR FIRST 11 DAYS WE WOULD APPLY OPERATION 1 AND THEN ON LAST DAY WE APPLY OPERATION 2 SO WE GET SCORE OF 8. BUT BY CHANGING ARRAY INTIALLY TO 0 AND APPLYING OPERATION 1 AND AGAIN OPERATION 2 WE GET ANSWER 6.
Now consider if case was for 18 days. We would get 9 by using second technique and 8 using first technique.
I hope it clears.
I did D as given in the tutorial, but I counted inversions using merge sort logic and it gave me TLE. Whereas it passed when I counted using fenwick tree logic. Both methods are O(nlogn) right?
_LeMur_
In the Solution of "1917D — Yet Another Inversions Problem", there are some mistakes:
Similarly, correction needed in "if 4x<y<8x"
IgorI can you check it?
I love writing complexity O as follows
like flamestorm and mesanu (Writers of Div.4) Did 😄
hello everyone, is there a site that tells you how many greedy problems and how many DFS problems have you solved?
Try CF Analytics Extension for chrome
Could someone provide a comprehensive breakdown of the DP formulation used to address 1917F - Construct Tree?
While I managed to reach a similar conclusion as outlined in the editorial, focusing on finding subsets whose sums and their complements sum to specific values, particularly ignoring the largest element, the critical aspect of formulating the DP remains elusive to me. In my opinion, the editorial lacks sufficient detail in explaining it.
Upon examining tourist's solution 238702895, $$$dp[i][j]$$$ seems to represent whether there exists a subset of sum $$$i$$$ such that ignoring it allows obtaining a sum of $$$j$$$ (the maximum element obviously is never being considered). However, the intuition and the exact process behind filling the DP table are unclear to me.
Let consider diameter consisting of the vertices $$$v_1$$$, $$$v_2$$$, $$$\ldots$$$, $$$v_k$$$ (let's consider that $$$v_i$$$ and $$$v_{i + 1}$$$ are connected for each $$$1 \leq i \leq k - 1$$$) and some vertex in the diameter (let's denote it $$$v'$$$). Now the state of dp will be the following two lengths: $$$dist(v_1, v')$$$ and $$$dist(v_k, v')$$$, we want to find all possible pairs $$$(x, y)$$$ such that we can construct diameter which will have some vertex $$$v'$$$ on it, such that $$$dist(v_1, v') = x$$$ and $$$dist(v_k, v') = y$$$.
In tourist's solution, the same thing is done. So he tries to find all pairs $$$(x, y)$$$ without using the length of the largest one. And then just checking if there exists one pair $$$(x', y')$$$ such that both $$$x' + l_n \leq d$$$ and $$$y' + l_n \leq d$$$ (because only in this case we can construct tree, we will create edges for all remaining lengths incident to the same vertex $$$v'$$$ in our case).
I hope, it's already more clear for you :)
Got it! Your clarification was indeed helpful. The phrase "taking a diameter of length $$$k$$$ and listing its nodes" in the editorial momentarily made me question the solution's direction.
Framing the DP thinking about any partition of size two for any diameter could potentially simplify comprehension.
Specifically, identifying the node in between those two partitioned subsets as the one where we connect all non-used edges could add clarity to the explanation. To elaborate further, your example of length $$$k$$$.
Hence, in understanding the solution, $$$dp(x, y)$$$ represents the possibility of forming two disjoint subsets with specific sums $$$x$$$ and $$$y$$$, utilizing the given set elements (excluding the greatest one).
min(2*n+1,d), because the maximum score can only be n. so, floor(d/2)=score ; floor(d/2)=n ; d=2*n+1 ; this means to achieve the max. score we should only check up till min(2*n+1,d) as above this value, the max. score (n) is already explored in the previous days which means exploring above this value is redundant.
I ended up writing a solution to C that runs in O(nlogk + klogk) if anyone is curious (Bonus 2). Could also be modified to solve Bonus 1 as well.
Solution: https://codeforces.net/contest/1917/submission/238896629
The problem C is so great, love from fst :)
Somehow during the contest I thought I must do better than O(n^2) in C, and so I missed it despite figuring out the solution a long time ago. But can someone help me with solving it in better than O(n^2)?
_LeMur_
F solution without bitset
Hacked.
nope
now HACKed :(
get a life nerd L + ratio
C is illusion, B is truth, though both are nice problems!
problem D is very cool and educational
Problem D is terrible. I just modified the inversion counting algorithm and passed. I can't see any reason to use a segment tree.
In problem C , Can anyone explain how only in 2*n times we get the break point. I am unable to thnink.
Can anyone explain how to solve Problem B? Tutorial isn't helpful.
thanks for including a buncha hints so that people who are stuck don't have to get the entire prob revealed.
Can anyone please give me the DP solution of Problem B
if you do get the solution please tell i tried creating some approach of dp state but it failed
D can be solved without segment trees by first calculating the amount of inversions in between elements of P, then adding num_inversions(Q) * n.