Thank you for participating in our round! We hope you enjoyed the problems. We are really sorry for the inconveniences caused by the English statement of problem B.
A total of 30 problems were proposed for this round
E was proposed as C, and C as B
Idea: Fakewave
Note that maximizing the sum of numbers in the table is equivalent to maximizing the number of chosen pairs that specify a valid cell.
Without loss of generality, we assume that $$$h \leq l$$$. For any cell of the table $$$(x, y)$$$, $$$1 \leq x \leq h$$$, $$$1 \leq y \leq l$$$. Let $$$cnt_h$$$ be the number of elements in the array not exceeding $$$h$$$, and $$$cnt_l$$$ be the number of elements in the array not exceeding $$$l$$$. Then, firstly, the answer does not exceed $$$cnt_h$$$, since each pair must contain a number not exceeding $$$h$$$. Conversely, the answer does not exceed $$$\displaystyle \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$$$, since both numbers in each pair must not exceed $$$l$$$. It remains to be seen that $$$\displaystyle min(cnt_h, \Big\lfloor \frac{cnt_l}{2} \Big\rfloor)$$$ pairs can be obtained. To do this, let's consider two cases.
if $$$\displaystyle cnt_h \leq \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$$$, then it is sufficient to pair each number $$$x \leq h$$$ with its own number $$$h \lt y \leq l$$$, and there will be $$$cnt_h$$$ pairs. This can be done since there are at least as many suitable numbers $$$y$$$ as there are suitable $$$x$$$.
if $$$\displaystyle cnt_h \gt \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$$$, then we need to pair each number $$$h \lt y \leq l$$$ with its own number $$$x \leq h$$$. After this, split the remaining numbers $$$x \leq h$$$ into pairs (there may be one extra number left over). We'll get exactly $$$\displaystyle \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$$$ pairs.
Note that the problem is equivalent to minimizing the number of rollbacks to reach a point with a number $$$\geq x$$$. (Consider the moment when the frog first reached the point $$$\geq x$$$. Instead of a full jump, the frog could have jumped not the full distance, but exactly to the point $$$x$$$). We then assume that the frog always jumps $$$a_i$$$ units forward using the $$$i$$$-th type of jump.
First, the frog can use the $$$i$$$-th type of jump $$$b_i-1$$$ times without any rollbacks. Let $$$r$$$ be the number of units remaining to the number $$$x$$$ after these jumps (if $$$r \leq 0$$$, then $$$0$$$ rollbacks are required).
Now, any jump will cause a rollback. However, note that after one jump with rollback, if we used the $$$i$$$th type of jump, we can use the same jump $$$b_i-1$$$ more times without rollbacks. After that, we'll find ourselves in the same situation (any jump creates a rollback), but we have moved $$$a_ib_i-c_i$$$ units. Therefore, it's always worth using the jump with the maximum value of $$$a_ib_i-c_i$$$.
Let $$$m = \max(a_ib_i-c_i)$$$ over all $$$i$$$ from $$$1$$$ to $$$n$$$. Then, if $$$m \leq 0$$$, we can't move forward (as we first get a rollback of $$$c_i$$$, and only then move by $$$a_ib_i$$$), and the answer is $$$-1$$$. Otherwise, $$$\displaystyle \Big\lceil \frac{r}{m} \Big\rceil$$$ rollbacks will be required.
2189C1 - XOR Convenience (Easy Version)
Idea: Fakewave
First, note that $$$p_i = p_j \oplus i$$$ is equivalent to $$$p_i \oplus i = p_j$$$. For $$$i = n-1$$$, the only possible $$$j$$$ is $$$j = n$$$. Let's try to construct a permutation such that for all $$$i$$$, the corresponding $$$j$$$ is $$$j = n$$$. That is, we want to ensure that for all $$$i \geq 2$$$, the condition $$$p_i \oplus i = p_n$$$ holds. Take $$$p_n = 1$$$. Then we notice that at position $$$2k$$$, the value must be $$$2k \oplus 1= 2k+1$$$, and at position $$$2k+1$$$, the value must be $$$(2k+1) \oplus 1 = 2k$$$. Thus, the numbers split into pairs $$$2k$$$ and $$$2k+1$$$.
Let's examine two cases:
If $$$n$$$ is even, take $$$p_1 = n$$$, $$$p_{2k} = 2k+1$$$, $$$p_{2k+1} = 2k$$$ ($$$1 \leq k \leq \frac{n}{2} - 1$$$);
If $$$n$$$ is odd, take $$$p_1 = n-1$$$, $$$p_{2k} = 2k+1$$$ ($$$1 \leq k \leq \frac{n-1}{2}$$$), $$$p_{2k+1} = 2k$$$ ($$$1 \leq k \leq \frac{n-3}{2}$$$).
The cases differ in the number remaining for $$$p_1$$$.
For example, for $$$n = 9$$$: $$$[8, 3, 2, 5, 4, 7, 6, 9, 1]$$$, for $$$n = 10$$$: $$$[10, 3, 2, 5, 4, 7, 6, 9, 8, 1]$$$.
2189C2 - XOR-convenience (Hard Version)
First, let's prove that no example exists when $$$n = 2^x$$$ ($$$x$$$ is an integer).
Suppose $$$n$$$ is at position $$$i$$$. Assume $$$i \lt n$$$. Then $$$p_i \oplus i = p_j$$$ for some $$$j$$$. But $$$p_i \oplus i \ge n$$$, since $$$p_i = n = 2^x$$$, while $$$p_j \lt n$$$---a contradiction. Hence $$$i = n$$$. But then $$$p_{n-1} = p_n \oplus (n-1)$$$. However $$$p_n \oplus (n-1)$$$ is larger than $$$n$$$, while $$$p_{n-1}$$$ is smaller---again a contradiction.
For $$$n \neq 2^x$$$, we show that an example does exist.
Consider the examples from part C1. Notice that for odd $$$n$$$, the example works, because $$$p_1 = n-1$$$, and somewhere later the number $$$n$$$ occurs, and $$$n \oplus 1 = (n-1)$$$. Now consider the example for even $$$n$$$.
Write $$$n = 2^x + r$$$, where $$$r \lt 2^x$$$ (in other words, $$$x$$$ is the highest bit of $$$n$$$). Then let us swap $$$p_1$$$ and $$$p_r$$$. Let's see what has changed. Since for all $$$i \ge 2$$$ earlier the only $$$j$$$ was $$$n$$$, the only number that could be broken is the one at position $$$r$$$. But now $$$p_r = n$$$. Notice that $$$2^x \oplus r = n$$$, and the number $$$2^x$$$ is at position $$$2^x+1$$$. Thus, for $$$i = r$$$, a suitable $$$j$$$ is now $$$j = 2^x+1 \gt r$$$.
It remains to check that $$$i = 1$$$ has a suitable $$$j$$$. Take $$$j = r + 1$$$. Since $$$n$$$ is even, $$$r$$$ is even. Then $$$p_j = r$$$ and $$$p_1 = r+1$$$. Indeed: $$$r+1 = r \oplus 1$$$.
2189D1 - Little String (Easy Version)
Let's consider which permutations $$$p$$$ satisfy the condition of the string $$$w$$$. It is obvious that if $$$w_1 = \texttt{0}$$$ or $$$w_n = \texttt{0}$$$, there are no suitable $$$p$$$ (in any permutation, there is a subsegment with only the number $$$0$$$ and a subsegment with all numbers), so we will assume that $$$w_1 = w_n = \texttt{1}$$$. Let's construct $$$p$$$, starting with $$$p = [0]$$$ and sequentially inserting the numbers $$$1, 2, \ldots, n - 1$$$ into some positions.
Suppose we have placed the numbers $$$0, 1, \ldots, k - 1$$$ and are now going to insert the number $$$k$$$ relative to them. We have $$$k + 1$$$ options for where to insert it.
If we insert $$$k$$$ before all the numbers or after all the numbers, we can always choose all remaining numbers as a segment and get $$$\operatorname{mex} = k$$$ (note that inserting subsequent numbers will not affect the $$$\operatorname{mex}$$$ of this segment, since all subsequent values are $$$ \gt k$$$).
However, if we insert $$$k$$$ between some values, we will have a situation where there is a value $$$ \lt k$$$ both to the left and to the right of $$$k$$$. Then, to achieve $$$\operatorname{mex} = k$$$, we need to collect all numbers $$$ \lt k$$$, but since they exist both to the left and to the right, we will include $$$k$$$, resulting in $$$\operatorname{mex} \gt k$$$.
In total, we have $$$2$$$ options for ensuring $$$w_k=1$$$, and $$$k-1$$$ options for $$$w_k=0$$$. We have derived that
In this version of the problem, $$$w = s$$$, so we only need to check whether $$$f(w)$$$ is divisible by $$$c$$$. To do this, we will iterate through all $$$i$$$ and reduce $$$c$$$ by the greatest common divisor of the current factor and the number $$$c$$$. If we end up with $$$c = 1$$$, then the answer is $$$-1$$$. Otherwise, the answer is $$$f(w)$$$.
2189D2 - Little String (Hard Version)
From D1 we have:
We will calculate the product of the multiplicative terms for all symbols $$$s$$$ that are given (\texttt{0} or \texttt{1}), and we will call this number $$$b$$$; the product of the remaining terms will be called $$$x$$$. The remaining symbols can be chosen, so we need to find the smallest value
that is not divisible by $$$c$$$. We can eliminate $$$b$$$, $$$x$$$ must not be divisible by $$$c' = \frac{c}{\gcd(b, c)}$$$. (In the implementation, to obtain $$$c'$$$, we divide $$$c$$$ by the gcd with each term of the product $$$b$$$ to avoid overflow.) If we can choose $$$s_2$$$, we will choose $$$s_2 = \texttt{1}$$$, which will make one of the terms in the product equal to $$$1$$$ — this will not cause divisibility and will not increase the number. In the end, we need to choose for several $$$j \ge 2$$$ (for $$$j = i - 1$$$, where $$$s_i = \texttt{?}$$$) to multiply $$$x$$$ either by $$$2$$$ or by $$$j$$$, so that the product is minimal and not divisible by $$$c'$$$, and the answer will be $$$bx$$$.
Let's consider two cases.
- $$$c'$$$ is a power of $$$2$$$. For all even $$$j$$$, we will choose to multiply by $$$2$$$, since multiplying by $$$2$$$ instead of a positive even number will not cause divisibility and will not increase the product. We will greedily choose to multiply by $$$2$$$ for the largest of the remaining $$$j$$$ as long as possible (while $$$c'$$$ still does not divide $$$x$$$) to minimize $$$x$$$.
- $$$c'$$$ is not a power of $$$2$$$. Then, by choosing to multiply by $$$2$$$ each time, $$$x$$$ will not be divisible by $$$c'$$$, and the product will be minimal, since each time we chose the smaller of the possible factors ($$$2 \le j$$$).
Final asymptotic complexity: $$$\mathcal{O}(n \log n)$$$.
Let's start by saying the answer is $$$-1$$$ if the string consists only of $$$0$$$'s.
Suppose we performed $$$k$$$ operations, where the $$$i$$$-th operation cost $$$a_i$$$. Then
$$$(a_1 - 1) + (a_2 - 1) + \dots + (a_k - 1) = n - 1$$$ (the number of characters that need to be removed), so
$$$cost = a_1 + a_2 + \dots + a_k = n - 1 + k$$$.
Thus the problem reduces to finding the minimal number of operations $$$k$$$ needed to achieve the goal. The answer will be $$$n - 1 + k$$$.
We show that $$$k \le 4$$$.
Let $$$s_i = 1$$$. Replace substrings $$$[1, i-1]$$$ and $$$[i+1, n]$$$ with some characters. Now we have the string $$$x 1 y$$$. Replace the substring $$$[1, 2]$$$ with $$$1$$$, giving $$$1 y$$$. Finally replace it with the string $$$1$$$.
Now we determine when the minimal number of operations is $$$k = 0, 1, 2, 3$$$ (otherwise $$$k = 4$$$).
By the difference of a string we mean the difference between the number of $$$1$$$'s and $$$0$$$'s.
It is claimed that $$$k$$$ operations are sufficient if:
$$$k = 0$$$ When $$$s = 1$$$.
$$$k = 1$$$ The string's difference is nonnegative.
$$$k = 2$$$ Either the string has a prefix or suffix with positive difference (then the remaining part can be replaced with any symbol, after which the whole string can be turned into $$$1$$$ in one move),
or the string's difference equals $$$-1$$$ (if the first condition does not hold, then we can replace substring $$$[1, n-1]$$$ with $$$1$$$ — its difference is $$$0$$$ because $$$s_n = 0$$$ — obtaining the string $$$10$$$, which can be changed to $$$1$$$ in one operation).$$$k = 3$$$ Either the string has a prefix or suffix with nonnegative difference (then the remaining part can be replaced by $$$0$$$, that part can be turned into $$$1$$$, resulting in string $$$10$$$ or $$$01$$$, after which one operation suffices),
or there are two consecutive $$$1$$$'s (then replace the prefix before them and the suffix after them with something, obtaining a string with difference $$$\ge 0$$$, which can be turned into $$$1$$$).$$$k = 4$$$ Otherwise.
Now we proceed to the proofs for $$$k \ge 2$$$:
$$$k = 2$$$
Assume the goal cannot be achieved in $$$k \lt 2$$$ operations, but can in $$$k = 2$$$, under the conditions that the difference is not $$$-1$$$ and there is no prefix/suffix with positive difference.
If the first operation is on a prefix or suffix, then that substring's difference is $$$\ge 0$$$. To finish in one more operation, the remaining part must have difference $$$-1$$$ (if it had difference $$$\ge 0$$$, the whole original string would have nonnegative difference; if $$$ \lt -1$$$, the total after the first operation would be $$$ \lt 0$$$). In this case the whole original string's difference would also be $$$-1$$$.
If the first operation is on some middle substring, then after it the difference $$$\le -1 + 1 + (-1) = -1$$$, so winning becomes impossible.
$$$k = 3$$$
Assume the goal cannot be achieved in $$$k \lt 3$$$ operations, but can in $$$k = 3$$$, under the conditions that no prefix/suffix has nonnegative difference and there are no two consecutive $$$1$$$'s.
Let the initial difference be $$$z$$$. Suppose the first operation is on substring $$$[l, r]$$$. Let the difference in $$$[1, l-1]$$$ be $$$a \lt 0$$$, in $$$[l, r]$$$ be $$$b$$$, and in $$$[r+1, n]$$$ be $$$c \lt 0$$$.
Case $$$b = 0$$$
Now the difference becomes $$$a + 1 + c$$$.
If $$$a + c + 1 = -1$$$, then $$$a + c = -2$$$ with $$$a, c \le -1$$$, so $$$a = c = -1$$$. But then if substring $$$[l, r]$$$ starts and ends with $$$0$$$ (otherwise prefix $$$[1\ldots l]$$$ or suffix $$$[r\ldots n]$$$ would have nonnegative difference). Then substring $$$[l+1, r-1]$$$ has difference $$$2$$$, so its length is even (if zeros $$$= x$$$, ones $$$= 2 + x$$$, total $$$= 2 + 2x$$$). Group adjacent pairs $$$(l+1, l+2), \dots, (r-2, r-1)$$$. In each pair difference $$$\le 0$$$ (since no two consecutive $$$1$$$'s), so difference of the whole sub-substring cannot be $$$2$$$ — contradiction.
Otherwise, suppose a positive prefix/suffix emerges after the operation (w.l.o.g., a prefix).
Let $$$T$$$ be that positive prefix. It contains the $$$1$$$ produced from $$$b$$$ plus some part $$$M$$$ from suffix $$$[r+1\ldots n]$$$ with difference $$$d \gt 0$$$. Then $$$T$$$'s difference is $$$a + 1 + d \ge 1$$$, so $$$a + d \le 0$$$. We already know $$$d \le 1$$$ (otherwise there would be two consecutive $$$1$$$'s), so $$$a \ge -1$$$, hence $$$a = -1$$$. Then $$$M$$$ starts with $$$0$$$ (otherwise $$$a + b + 1 = 0$$$ giving a prefix with nonnegative difference). Thus the used part $$$M$$$ must have difference $$$2$$$, so it contains two consecutive $$$1$$$'s — contradiction.
Case $$$b \lt 0$$$ If difference becomes $$$-1$$$, then $$$a - 1 + c = -1 \implies a + c = 0$$$, impossible.
Otherwise, suppose a positive prefix emerges (w.l.o.g., a prefix).
If $$$l = 1$$$, then suffix $$$[r+1\ldots n]$$$ remains. We get $$$0$$$ + a prefix from $$$M$$$, so that prefix must have difference $$$\ge 2 \implies$$$ two consecutive $$$1$$$'s — contradiction.
Otherwise, the new prefix includes $$$[1\ldots l-1]$$$ + $$$0$$$ (from $$$b$$$) + prefix $$$M$$$ from $$$[r+1\ldots n]$$$. That prefix would need difference $$$\ge 3$$$ (since $$$[1\ldots l-1]$$$ has difference $$$\le -1$$$ and we add a $$$0$$$), so again two consecutive $$$1$$$'s — contradiction.
2189F - Zhora the Vacuum Cleaner
Idea: yanb0
We call a vertex dead if it has $$$0$$$ nuts, and if we root the tree in it, among the subtrees of its children, there is at most one subtree with a positive sum of the numbers of nuts.
We denote the movement operation for a vertex $$$v$$$ as $$$\operatorname{c}(v)$$$.
Let $$$A$$$ be the forest consisting of all living vertices. We prove that $$$A$$$ is always connected, i.e., it is a tree. Suppose for a contradiction, $$$A$$$ has at least two connected components, then the path between them must contain a dead vertex $$$v$$$. However, $$$v$$$ is alive, since both connected components are in different subtrees of $$$v$$$'s children when the tree's rooted in $$$v$$$, a contradiction, q.e.d.
Let $$$\deg(v)$$$ be the degree of $$$v$$$ in $$$A$$$. It's easy to see that when applying $$$\operatorname{c}(v)$$$, $$$a_v := a_v + \deg(v)$$$, and for all other vertices $$$u \in A$$$, $$$a_u := a_u + \deg(u) - 2$$$. If $$$v \not \in A$$$, then $$$a_v := a_v + 1$$$, $$$a_u := a_u + \deg(u) - 2$$$, $$$a_p := a_p + \deg(p) - 1$$$, where $$$p$$$ is the closest vertex from $$$A$$$ to $$$v$$$. $$$[*]$$$
For a sequence of operations, we define the tree $$$L$$$ as $$$A$$$ at the moment after all $$$\operatorname{c}(v)$$$ operations and before the nuts are eaten.
Suppose we have a sequence of operations (including the eating) that results in no nuts remaining. Let us prove that the last operation $$$\operatorname{c}(v)$$$, where $$$v \not \in L$$$, can be replaced by $$$\operatorname{c}(u)$$$, where $$$u \in L$$$. In this case, $$$A$$$ becomes a non-strict subset of itself, and again, there are no nuts left. Consider the moment before applying $$$\operatorname{c}(v)$$$. There are two options:
$$$v$$$ is alive. Then, when replacing $$$\operatorname{c}(v)$$$ with $$$\operatorname{c}(u)$$$, $$$a_v$$$ decreases by $$$2$$$, and $$$a_u$$$ increases by $$$2$$$ according to $$$[*]$$$.
$$$v$$$ is dead. Let $$$p$$$ be the closest vertex in $$$A$$$ to $$$v$$$. Then, when replacing $$$\operatorname{c}(v)$$$ with $$$\operatorname{c}(u)$$$, $$$a_v$$$ and $$$a_u$$$ will decrease by $$$1$$$ (become equal to $$$0$$$), and $$$a_p$$$ will increase by $$$1$$$ according to $$$[*]$$$.
In both cases, all $$$a_x$$$ for $$$x \not \in L$$$ will decrease, and it is easy to see that the sequence of operations after $$$\operatorname{c}(v)$$$ will also bring all nuts into $$$L$$$, after which the same eating operations will remove all nuts, q.e.d. Thus, all operations of type $$$\operatorname{c}(v)$$$, where $$$v \not \in L$$$, can be (sequentially from the end) replaced by $$$\operatorname{c}(u)$$$ for some $$$u \in L$$$.
Now we have to solve the following problem:
We need to choose a subtree $$$L$$$ of the original tree, then repeatedly apply $$$\operatorname{c}(u)$$$, $$$u \in L$$$, to make all vertices not in $$$L$$$ dead, and then apply the eat operation to all $$$v \in L$$$. Note that by $$$[*]$$$, all vertices not in $$$L$$$ will become dead regardless of which vertices in $$$L$$$ we choose; in other words, we can apply all $$$\operatorname{c}(v)$$$ to only one vertex $$$v$$$.
Consider the dynamics along directed edges $$$xy$$$, $$$dp[x][y]$$$: the smallest number of $$$\operatorname{c}(v)$$$ operations, where $$$v$$$ is on the $$$x$$$ side of $$$xy$$$, needed to make all vertices on the $$$y$$$ side (including $$$y$$$) of $$$xy$$$ dead. The value of $$$a_y$$$ can only decrease when $$$\deg(y) = 1$$$, so $$$dp[x][y] = \sum_{i=0}^{k}dp[y][ch[i]]$$$, that is, $$$dp[x][y]$$$ is equal to the sum of $$$a_v$$$ over all $$$v$$$ in the subtree $$$y$$$, if we hang the entire tree on $$$x$$$.
For all vertices $$$v \not \in L$$$, at some point and always after that, $$$a_v = 0$$$. It is also possible that $$$a_v = 0$$$ before all operations; $$$a_v$$$ is never equal to $$$0$$$ again.
We define $$$zero[y]$$$ to be the smallest number of $$$\operatorname{c}(v)$$$ operations required for $$$a_y = 0$$$ after any number of $$$\operatorname{c}(v)$$$ operations at least equal to $$$zero[y]$$$. $$$zero[y] = \min_x({dp[x][y]})$$$ for all $$$x$$$ adjacent to $$$y$$$, and $$$zero[y] = 0$$$ if $$$a_y = 0$$$ and $$$\deg(y) = 2$$$ initially. This is true because if $$$a_y \ne 0$$$ or $$$\deg(y) \ne 2$$$, $$$y$$$ will finally "zero out" only when it becomes dead. $$$\min_x({dp[x][v]})$$$ is greater than $$$dp[v][u]$$$ for all, possibly except one, vertices $$$u$$$ adjacent to $$$v$$$, and therefore is greater than $$$\min_t({dp[t][u]})$$$ for $$$t$$$ adjacent to $$$u$$$ adjacent to $$$v$$$. Therefore, applying $$$\operatorname{c}(v)$$$ to $$$v$$$ with the largest $$$zero[v]$$$, each $$$a_u$$$ will become equal to $$$0$$$ after $$$zero[u]$$$ operations.
Thus, either there are no $$$\operatorname{c}(x)$$$ operations, and the eating operation must be applied to all $$$y$$$ with initial $$$a_y = 0$$$, or there are $$$\operatorname{c}(x)$$$ $$$k$$$ operations, and the eating operation must be applied to all vertices $$$y$$$ with $$$zero[y] \ge k$$$. For the first case, we simply calculate the cost of this sequence of operations. For the second case, we sort $$$zero$$$ in $$$O(n \log n)$$$, then iterate over the number of "zeroed" vertices, iterating over $$$zero$$$, and calculate the answer as $$$(n - i) \cdot q + zero[i - 1] \cdot p$$$. The answer to the problem will be the minimum of the obtained ones.
Total complexity: $$$O(n \log n)$$$.
thanks for the fast editorial
First
Great contest C2 and A made me cry
C1, C2 good problems.. B was so greedy... I think A is better than B A was interesting
D1 was easy Should try more.
if (s[i] is 1) ans *= 2; else ans *= i — 1;
B statement was too rubbish !!!
This change later --> bith , 2*bith ,..
that made things actually clear
Was B easier than A?
nah
clearly no
No
nuh uh. tho A seemed interesting
they kinda felt similar in difficulty
no
nah, i'd win
goated niche reference, gonna make sukuna suffer a like div 2 D.
Nice problems, english could be better. Would be better if it was 2.5 hrs.
Great contest! Explanation given in questions could have been better.
Thanks for the contest. It was hard, i was stuck on A for two hours, felt like i should be able to solve at least A. I mean its supposed to be the easiest. After reading the fun fact, it made me think juts how much I need to practice more.
Ps: Someone plz confirm if this contest was really authored by high school students, i mean damn!
same here bro I couldn't even solve A during contest but somehow I managed to solve B 30 min before contest end. Happy to know many people felt the same. Now I am more pumped to practice more.
I consider A is not so hard.I made it in 30 minutes and got ac for the first submission.But i was stuck in B and C for 1 hour.I saw the Tutorial after the contest and now i think B is easy indeed,but i was so stupid.
Yep B was easy but difficult to understand I suppose. Although I couldn't spend time on C1 bcz my morale just broke in start as I couldn't solve A and was finding B to be difficult to understand.And yes A is ezy now as I read its tutorial but I never got the intuition for it during contest.
tbh, when i saw the editorial it still didn't made full sense, but the logic they used was just amazing, i mean its something simple, and a logical but it just didn't hit me at that time. i was handling the complexity of how to count numbers less than h and l without duplicates and so.
yeah i mean the sheer demotivation of not solving A was too much for me, I never used so much brain on A, though it feels good to know i have to work on.
it make sense that this contest was made by high school student.I know a student who learnt c plus plus in middle school.
This is some text.
The rest of the text. I don't know why I can pass just by swapping the first and last numbers in the output.
My first contest, unable to solve C2. Hope I can get better next time.
Maybe D1 is not so complex?
Maybe you can compute answer modulo c and check if it is 0 like this?
Sorry for my bad english :(
I used a two pointer approach to solve A https://mirror.codeforces.com/contest/2189/submission/359430375 ~~~~~ #include <bits/stdc++.h> using namespace std;
int main() { cin.tie(0)->sync_with_stdio(0); //clock_t tStart = clock(); int T; cin>>T; while(T-- > 0) { int n, l, h; cin>>n>>h>>l; vector<int> v(n); for(auto &num : v) cin>>num; sort(v.begin(), v.end()); int mx = max(l, h); int mn = min(l, h); int left = 0, right = n-1; int res = 0; while(left < right) { if(v[left] > mn) break; if(v[right] > mx) { right--; continue; } res++; left++; right--; } cout<<res<<'\n'; } //printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC); return 0; }~~~~~
Yes, I also used two pointers for problem A : 359421026
// i think this is an easier approach ~~~~~~~~~~~~~~~~~ void solve(){
ll n, h, l; cin >> n >> h >> l; ll x = min(h,l), y = max(h,l); ll a[n], small=0, big =0; for(ll i=0; i<n; i++){ cin >> a[i]; if(a[i]<=x )small++; else if(a[i]<=y)big++; } if(small >= big){cout << (small+big)/2 << endl;} else{cout << small << endl;}} ~~~~~~~~~~~
i see you are first counting the smaller elements in the array, and if they are not small, you check if they are bigger or not, so you have count of all elements smaller than h, and all elements smaller than l excluding elements from h count, so wouldn't the straightforward way will be min(small,big), because i am not getting the logic in this line if(small >= big){cout << (small+big)/2 << endl;}.
Yeah, same two pointers -
B>C I did the question C by observing a pattern for the even and the odd numbers though i did C after the contest ,But B was a nightmare for me in the contest i couldn't even understood it for the first 30 minutes and eventually leaved it as it is.
Can Anybody Explain the last part of my code, initial part i have written in the observation part but after that i am little bit confused in the ceil of (x-pos) part, I will be grateful for your help.
My Submission
If you need to travel 4 units of distance and your best operation is (2,2,1) then you will travel 3 units per cycle , so to cover 4 units you will require 2 cycles , one with 3 units and the other with 1 unit to reach the target.
I've done a unbelievable weird job during this round
solved 6 but ranked 850+
because of 10+ penalties
I suspect I'm not a human being
Can someone explain c2 ? printing -1 approach is cleared, just explain how to generate all numbers.
An intuitive way to approach problem C2 after C1 is to observe n = odd works as it is, n = power of 2 will lead to generating values greater than n, hence not possible. For n even, keeping the C1's solution intact and just swapping the first value with another will work, maintain a set for the same.
I could be the only person to solve A with two pointers ~~~~~ 359372727 ~~~~~
how will we solve the A question if it said, any cell can be chosen maximum one time? can anybody help me with the solution pls
you can use a number to form a pair only once my solution which I commented uses two pointers for solution we can start making pairs with maximum values that are strictly lower than bigger h l value and pair them with smaller values as possible
Oh you use python but main Idea I used was like that I hope it helped
thats also what i did xd
Problem A was easy but problem B was way more tough or the language of the question was not clear , i don't know
Totally a pretty tough contest
Problem E, I came up with the conclusion for the case where the number of operations ≤ 4, but how can one come up with the necessary and sufficient conditions for k = 2 and k = 3?
You can look at cases which operations could have been applied and come up with sufficient and necessary conditions for those cases.
If $$$k = 2$$$, then some operation $$$[l, r]$$$ was applied after which the operation was applied on the whole string. Suppose that the majority value in $$$[l, r]$$$ was 1. Then we can show that we could have finished in one operation. Therefore the majority value in $$$[l, r]$$$ must have been 0. Let $$$z$$$ / $$$o$$$ be the number of zeroes / ones outside $$$[l, r]$$$, respectively. Then $$$z + 1 \leq o$$$ or in other words $$$z \lt o$$$, since we finished in one operation after applying $$$[l, r]$$$. From here you can show that either prefix before $$$l$$$ or suffix after $$$r$$$ has strictly more ones than zeroes. Similarly, with this condition on prefix/suffix you can show that you can finish in 2 operations. Hence, these are sufficient and necessary.
If $$$k = 3$$$, two operations $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$ applied before finishing with operation on the whole string. Let $$$[l_2, r_2]$$$ represent the range applied in the second operation corresponding to the range from the initial string. We can consider two cases here:
If $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$ intersect, then we could have taken the union of the ranges instead as one operation and finished in 2 operations instead. We can show this by considering the cases of majority values in these ranges.
If $$$r_1 \lt l_2$$$ (i.e. ranges do not intersect), then with the similar argument as above, if at least one of the operations had 1 as majority, we could have finished in 2 operations. Hence, 0 was the majority value in $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$. Let $$$z_l$$$, $$$z_m$$$, $$$z_r$$$ denote the number of zeroes in ranges $$$[1, l_1 - 1]$$$, $$$[r_1 + 1, l_2 - 1]$$$ and $$$[r_2 + 1, n]$$$ respectively. Similarly, let $$$o_l$$$, $$$o_m$$$, and $$$o_r$$$ denote number of ones in the same ranges. Then $$$z_l + z_m + z_r + 2 \leq o_l + o_m + o_r$$$. Which means that either $$$o_m \geq z_m + 2$$$ or $$$o_l \geq z_l$$$ or $$$o_r \geq z_r$$$. Since we can show that if these conditions hold we can finish in 3 operations, just by removing one of the operations from case with 4 operations, we have showed that these are necessary and sufficient conditions.
Hope it helped. Feel free to ask any questions if some parts are unclear.
In the case of $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$ intersecting for the case $$$k = 3$$$, the idea that we could have finished in 2 operations by taking the union is not correct. Thanks to xyzt8988998 for reaching out with the mistake. The right claim is:
Claim: If the ranges intersect then there is either a prefix or a suffix that has as many 1 as 0.
First of all, since after applying $$$[l_1, r_2]$$$ the range is compressed into one element, if $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$ intersect, then $$$l_2 \leq l_1$$$ and $$$r_1 \leq r_2$$$.
B: ceil == wa case 9 No ceil == acepted
The problem statement is almost bullshit
I understood the problem B during contest in just one read through and still couldnt solve it lol Im wondering what the rating of problem B will be
Hey everyone!
I’ve prepared detailed articles for Problem A and Problem B, explained in both English and Hinglish to make them super easy to follow.
What makes these articles useful?
Simple, beginner friendly language
Starts with understanding the problem clearly
Builds intuition step by step
Derives the formula logically
Provides a code template so you can try coding on your own
Ends with the complete solution for verification
The goal is not just to solve the problem, but to learn how to think and approach similar problems in the future.
Check them out here:
Problem A: - https://www.xorthax.com/codeforces-articles/round-1075-div-2-problem-a
Problem B: - https://www.xorthax.com/codeforces-articles/round-1075-div-2-problem-b
I genuinely hope you find these helpful. Do give them a read and let me know your feedback!
If you want more articles like this, do comment below.
I finally understood. How to do A..
A was easy, solved it pretty fast. However, it took me quite a lot of time to think about B. Therefore, I have no time left to think about C, and I'm kinda sleepy too cuz it's late at night in my country. Anyways, I did improve, cuz in the past I only solved A.
About D1, you can reconcile the idea and the code like this: the real constraint isn’t simply “you can’t insert in the middle,” but that any insertion must not break an already satisfied prefix w condition (mex = k). The loop from i = 0 to n − 2 is effectively counting how many insertion positions are safe before the first position where inserting would destroy the existing prefix property. When m = 1, a full segment with mex = k must remain intact, so only the two ends work; when m = 0, as long as the prefix hasn’t reached mex = k yet, inserting won’t affect it, giving i valid positions. From this perspective, the code is implicitly checking the previous w-state rather than explicitly reasoning about “middle vs ends,” so the implementation and the intended logic do line up—just from different angles.
I have a boring solution in F:https://mirror.codeforces.com/contest/2189/submission/360273407
The editorial for problem F seems too overwhelming. Is this normal, or is there something wrong with me? Also, is there any easier approach?
can anyone tell me how someone can get an intuition on C1?
great contest and editorial
D1: Need some help with the intuition for the solution
I understand these conditions and got them myself: • If s[i] = 1, then the value i must be placed entirely to the left or entirely to the right of all values 0..i−1. • If s[i] = 0, then the value i must be placed strictly between the values 0..i−1
I’m confused about the leap from these conditions to the construction. In particular, I don’t understand why constructing the permutation from 0 upward works, nor how one is supposed to come up with this idea during the contest. "Let's construct p, starting with p=[0] and sequentially inserting the numbers 1,2,…,n−1 into some positions." <- how do you get to this idea when solving yourself.
I think I have a simpler solution for F, correct me if it's the same as in the editorial. However I don't have a proof for it, though there is some intuition.
I have two claims. First — we need to do operations in at most one vertex. Maybe it's provable from the facts in the editorial, but idk. Before the second claim we need to understand some properties. Suppose the tree is rooted at the vertex $$$r$$$ and we look at the subtree of vertex $$$v \neq r$$$. Let $$$s_v$$$ be the sum of all $$$a_u$$$ in the subtree. Then after applying the operation the number of nuts in the subtree is $$$\max(s_v - 1, 0)$$$. From this fact it can be shown, that if we apply at least one operation, then we need to do at least $$$s_v$$$ to get rid of the nuts in vertex $$$v$$$ in 2 cases:
$$$a_v \ge 0$$$ and there is at least one non-negative $$$a_u$$$ in the subtree.
$$$a_v = 0$$$ and there is at least two non-negative $$$a_u$$$ in the subtree.
So there are $$$O(n)$$$ "events" which change the number of distinct vertices after operations among all roots (it's basically all possible values of $$$s_v$$$).
Let's find all these events. Now the plan is to bruteforce every possible root and find the optimal answer for each one. To bruteforce roots we'll do rerooting and to find the minimum among $$$O(n)$$$ values fast we'll use segment tree. Let $$$c_i$$$ be the i-th unique value in the sorted array of events. Initially the answer for $$$c_i$$$ operations is $$$c_i \cdot p$$$ plus the number of vertices with nuts. Vertex $$$v \neq root$$$ contributes $$$q$$$ to every $$$c_i \lt s_v$$$, so we add $$$q$$$ on a prefix.
Then if we reroot from $$$v$$$ to its child $$$u$$$, only their $$$s$$$ and number of non-empty children subtrees change, so we can update this information and do certain additions (and subtractions) in the segment tree. This part is technical so instead of writing in detail I'll just give my submission 362825458.
Time complexity $$$O(n \log n)$$$ memory $$$O(n)$$$.
A made think a lot. Not expected this easy solution
Can someone explain why for B, you would commit to one jump type immediately? It seems to me you could travel t = sum(a_i(b_i — 1) for all i) at the beginning. Essentially you travel as much distance as possible using each jump type before incurring a penalty (rollback). Only after do you commit to one jump type, this doesn't seem disallowed to me by the problem statement. I have a submitted solution using this solution which passed all testcases. This appears to give strictly more distance than committing to one type from the beginning.Is there a constraint or reasoning I’m missing that makes combining moves like this suboptimal or invalid?