It is somehow difficult to count the number of such subsequences in an arbitrary string. Can you think of strings where it is trivial?
The number of such subsequences can be $$$0$$$.
Key observation: A bitstring where all $$$\mathtt{1}$$$ bits come before all $$$\mathtt{0}$$$ bits is perfect as it has no $$$\mathtt{101}$$$ or $$$\mathtt{010}$$$ subsequences.
You can fix the number of $$$\mathtt{1}$$$ bits to be $$$k$$$ and then put $$$n-k$$$ $$$\mathtt{0}$$$ bits after them. This achieves a perfect bitstring with the number of $$$\mathtt{1}$$$ bits being $$$k$$$.
The answer matrix will have permutations in every row and column. Can you think of such a matrix?
Let our final matrix have all cyclic shifts of the identity permutation in each row. Can you perform a cyclic shift using $$$3$$$ operations?
One of the operations performed on each row becomes redundant.
Key observation: You can cyclic shift an array using $$$3$$$ operations.
The operations to achieve this are "$$$1$$$ $$$n$$$", "$$$1$$$ $$$i$$$", "$$$i+1$$$ $$$n$$$". Perform these with a different $$$i$$$ for each row, you will obtain all cyclic shifts of the identity permutation. To optimize it to $$$2n$$$ operations observe that performing "$$$1$$$ $$$n$$$" on each row does nothing.
Think in binary.
Let $$$x$$$ be an integer. What is the smallest number $$$y \gt x$$$ that is more beautiful than $$$x$$$?
$$$y$$$ always equals $$$x$$$ with the smallest valued $$$0$$$ bit set to $$$1$$$.
Key observation: To increase the beauty of a number, it is always optimal to set the least valued $$$0$$$ bit to $$$1$$$.
Let our number be $$$x$$$ and call the least valued $$$0$$$ bit special. Let $$$y$$$ be $$$x$$$ with the special bit set to $$$1$$$. To increase the beauty, we must increase $$$x$$$ by at least $$$1$$$. This will set the special bit to $$$1$$$, and all bits with a smaller value to $$$0$$$. Until we reach $$$y$$$, there will always be at least one $$$0$$$ bit with a smaller value than the special bit while the bits with a higher value stay the same. This means that no number is more beautiful between $$$x$$$ and $$$y$$$, showing that the observation is correct.
From this, we can construct a solution. Let us count the number of $$$0$$$ bits at each position. Iterate from the least valued bit to the highest. Greedily set one such bit to $$$1$$$ until we run out of $$$0$$$ bits or the remaining $$$k$$$ is less than the value of the bit.
This solution has a time complexity $$$O(N\log{10^{18}})$$$.
2118D2 - Red Light, Green Light (Hard version)
Divide the problem into some subproblems:
- Find the next traffic light efficiently.
- Detect cycles efficiently.
For D1 it is enough to do the first subproblem in $$$O(N)$$$, the second subproblem with $$$O(N)$$$ calls of the first subproblem. For D2 we need to do better.
Try to simulate the problem by hand.
Iterate over all traffic lights and check if we would collide with it if we don't turn. Then we can select the next traffic light in the correct direction. This is $$$O(N)$$$.
If we collide with the same traffic light from the same direction twice than the answer is no. For detecting cycles we can store visited traffic lights that we collided together with direction. Notice that we can only collide with a specific traffic light in a unique time modulo $$$k$$$.
This solution has a time complexity $$$O(Q*N^2)$$$.
First, let's quickly find the next traffic light in the positive direction. Imagine movement by moving along diagonals, refer to the images in the statement for a visual representation. Group the traffic lights by $$$(d_i-p_i)\bmod k$$$, when at position $$$x$$$ at time $$$t$$$ you will collide with the group of $$$(t-x)\bmod k$$$. We can binary search the next position on this. To do the same for the anti-diagonals you can group by $$$(d_i+p_i)\bmod k$$$ and search by $$$(t+x)\bmod k$$$.
We can still simulate each query, but after finding out the answer you can store for each state the result. In later queries, you can refer to the already checked states. In total, you will only check each state at most once.
Alternatively, you can notice that after colliding with a traffic light in a specific direction, the next traffic light will always be the same. From this you can build a graph and detect cycles before reading queries.
Both solutions have a time complexity of $$$O(N\log{N})$$$.
Why is it important that both $$$N$$$ and $$$M$$$ are odd?
Try generalizing the trivial case when $$$N=1$$$.
Try extending the solution from a smaller case... in a literal sense.
Key observation: Having $$$N \ge M$$$ and N, M both odd, an $$$(N - 2) \times M$$$ grid can easily be extended into a $$$N \times M$$$ grid
To achieve this first color a cell in the middle of both of the $$$M$$$ long sides. By this we ensure that the rectangle will be so wide that its side will be at maximum chessboard distance from each other. This means that any cells colored next to one of its sides can only increase the penalty of cells of the opposite side. By coloring cells alternating up and down on each side (similarly to the solution to the case $$$N=1$$$) we can ensure that every cell gets at most $$$2$$$ penalty.
This only leaves the corners as corner cases (as they can be increased from two sides), but they can also be solved by choosing the order of vertical and horizontal extensions correctly.
Some interesting observations:
- It can be observed that order that ordering the points from the center (and always deciding the ties in the right manner) can also yield a solution.
- There actually exists a solution which works for even sized boards
- As an extra challenge it can be interesting to find a solution where no cell has more than 2 penalties.
The order of two elements only matters if the absolute value of their difference is at most 1. Try to store the positions of elements with value $$$v$$$ relative to elements with value $$$v+1$$$. (The next hint will be about what to do with these.)
We want to somehow hash the relative positions. (The next hint will be about a thing you might not have known you can hash.)
It is possible to hash rooted trees, see Vladosiya's blog post. Note: the structure you hopefully came up with using hint 2 will certainly not be a single rooted tree, use this algorithm more as a guide. (The next hint will be about how you can check if two strings are rotations of each other.)
We'll consider the arrays cyclic: $$$a_1$$$ and $$$a_n$$$ are also adjacent.
For each array, let's build rooted trees where the children of each vertex are ordered. Each vertex corresponds to an value in an array. For each index $$$i$$$, let its children be the occurrences of the value $$$a_i - 1$$$ in order between the $$$i$$$-th element and the next occurrence of the value $$$a_i$$$. The roots of the trees will be nodes with value $$$m$$$ in an array. We hash each tree, then compare if the sequences of hashes are rotations of each other (for example using KMP).
For hashing a tree, see Vladosiya's blog post.
This solution has a time complexity $$$O(N\log{N})$$$ if you use a map for deterministic hashing.
first.
4 th approach
In reference to extra for E bullet 1:
My construction for problem E was sort all the coordinates first by checkerboard distance from the center with ties broken by Manhattan distance from the center. Then all further ties broken by sorting the tied points in clockwise order alternating starting from 12 and 6 for each of these ties broken sequentially.
This is exactly the same as my sollution was (I was a tester)
The last tiebreaker isn't much of a deal right, for cells with the same max distance and manhattan distance from the center, we can choose any of them. I just sorted them in order of i and j indices.
As a side-note, this problem saved my ass, I almost thought my rating was cooked.
nice try diddy
what does from 12 and 6 mean
Numbers on a clock, north and south, respectively.
Thanks
Almost implemented D1 during contest, but debugged bugs for too long(
How to do it I tried via recursion got stuck hard af then tried apply iterative approach still got fked af
Here is my submission: https://mirror.codeforces.com/contest/2118/submission/324142498 You just need to maintain reverse flag, and go forward or backward to next light (depends on reverse flag), maintain time variable to decide whether you need to reverse or not on current light and also visited array, so when you visit same light twice with same reversed flag, you are in loop and the answer is no. And when you are on lights array index which is out of range, then the answer is yes.
Fastest editorial I have seen (only slower than um_nik's one)
woooow! fastest editorial
Amazing contest! B was awesome! This was my first time participating in a CF round and I really enjoyed it!
B was an interesting problem. It's one of those problems where you just suddenly get a solution in your mind.
yeah B was good
Actually!!
In B, I first fixed the first column to be 1 2 3 ... n by reversing [1, i] on row i. Now, the second column was close to a permutation (like 2 1 2 3 ... n — 1), so I reversed [1+1, n] on row 1, this lead me to reverse [i+1, n] on row i. This way, each column gradually becomes a permutation. Total 2n — 1 operations.
My solution : 324069981
I did some calculation and used 2n-3 operations. I started from the bottom row and the gradually moved up to the top. [n, 1, n] --> [2, 1, 2] This will give us n-1 operations. After this I moved from top to bottom. [1, 2, 3] --> [n-2, n-1, n] This will be n-2 operations. Adding up we get a total of 2n-3 operations.
Got it, i just did two more operations which were choosing just one element and reversing, I guess you skipped this cuz it makes no difference.
I went from [n, 1, n] --> [1, 1, 1] it will give n operations similarly one more form top to bottom. But getting this logic is totally random.
UPD in 2025/6/15: fix bugs and reformat.
Below is one solution to problem E which satisfys the tighter restriction: no more than two operations per cell.
Assume that $$$n \geq m$$$. Also, reverse the whole operation and consider deleting one cell at a time and reducing the furthest cells by one. There are mainly three steps to go:
Use the method below:
In this example, the number of times each cell is reduced is as follows (you can try to derive this result step by step):
It can be noticed that the top and bottom rows are reduced by no more than 2 and each corner is reduced by no more than 1. The remaining grids form a subproblem in which only two corners are reduced by 1 in their positions, so the subproblem also satisfies the condition of Step 1 (and 2).
After using several times of Step 1, the initial grid can be shrinked to a square. The strategy is trivial when $$$n = m = 1$$$, but some discussion should be done when $$$n = m \geq 3$$$.
Use the same method:
It can be noticed that the top and bottom rows are reduced by no more than 2 and each corner is reduced by no more than 1. The remaining grids form a subproblem (here, $$$m \gt n$$$ holds, so we need to swap them) and the number of each corner is reduced by 1, so the subproblem also satisfies the condition of Step 1.
This time, we can alternate between Step 2 and Step 1 to reduce the side to 3. As this method failed when $$$n = m = 3$$$, we need the third step:
This step can only be reached from initial step or Step 1. Consider the worse case:
which can be deleted in the following order:
While coding, you need to be careful of the position of the cells with the number $$$1$$$ and properly rotate or symmetry the strategy. A possible implementation: 324437128
Hi, I am a bit confused about the case where $$$n=3$$$ and $$$m=3$$$ (the sample input). Are you doing the removals like this:
So your adding order is like:
And then the final penalty matrix becomes:
If I misunderstood your approach, sorry. Could you please provide a detailed example for the case when $$$n=3$$$ and $$$m=3$$$?
Actually I havn't thought about this corner case. Maybe some special strategy should work for this case.
I see now. The original strategy failed when $$$n=m$$$. These cases should be considered independently. I'll try to find out the solution for this.
I believe your approach only works when $$$n=1$$$ or $$$m=1$$$; it fails for other cases. You are using induction, but your approach fails on the base case.
You're right. I've slightly adjusted the strategy and thus fixed the issue. Sorry for the inconvenience.
Yes, now it is working 🎉: 324418651
But I want to add something:
The main reason for these problems is that you need to consider the position of the grid where the number 1 is written. Here is my implementation: 324437128
https://pastebin.com/LWEC8Ai4 what wrong in this code..? i am trying to convert each number into a nearest number in which all bits are set (2^i — 1) and simultaneously decreasing k
actually strategy is flawed, there could be a solution sometimes when you have to set only a few bits of some number, for that notice that adding 1<<x, where x is the unset bit is the fastest way to set a bit, so simply keep track of positions of all unset bits, and then sort them and subtract one by one from k.
Ok! Understood Thanks m_manasc
Wasted so much time on B, I solved D just 2 min after the contest was over. Btw nice contest.
I got D1 after 2 minutes too. :(
If we reach the same traffic light from the same direction twice than the answer is no.can someone explain it. I was thinking that if we reach the traffic light twice with same time modulo k with same direction then only answer in no. Thanks in advance.
they are same as light only turns when
time modulo k = delay .. so if you reach it twice you will reach whentime modulo k = delay` only ..so if you reach it twice you will reach when time modulo k = delay onlyI am unable to grasp it. Can you provide a proof ?
oh the light only turns red when
time = k.l + delaysotime % k = delay % k = delaybecause it is given thatdelay < kso if you meet a red light .. then
time % k = delay... not just for twice.. anytime you meet a red light this has to follow from the given equationi have another condition that didn't work: if we leave the traffic light in the same direction twice, then the answer is no. Would appreciate if someone how it's different from editorial condition
if you are at a red light initially ... then you will immediately reverse.. did you handle this case ?
Aree just think it this way,.. u are proposing that we need to make sure we reached the traffic light both the times with same (t%k) value. But the point is, when u reach a red light, t%k should be d... Else it's green isn't it. So t%k always d, whenever u crash the same red light.
If you reach the light twice from the same direction. Then it means you have completed a whole loop which takes
x*ktime where,x>=1. As you reverse direction after visiting it the first time and then somehow make it back again. It can be concluded that you are stuck in an infinite loop.Can someone share beautiful and clean code for D1?
My Submission
here t is time we reach that pos and dir is direction we are moving. we are checking what will be the light when we reach that pos.
Thank you!
324134942 I first precomputed for every traffic light for every time modulo k with direction if it can be left eventually with simple state transitions. Ignore all those parameters being passed for each function call.
Thanks!
dfs brute force — submission
324146023
thank you for a superfast editorial
Here's how I came up with the solution to problem F. The text is too long, so I put it into the spoiler:
The first operation is equivalent to the fact that the array is ringed, while the second operation is essentially telling us:
For any $$$x$$$, all positions of the numbers equal to $$$x$$$ or $$$x+1$$$ are relatively invariant on the ring.
I'll walk through an example of this. Consider the following example:
Considering only the positions where the numbers are equal to $$$1$$$ or $$$2$$$, we find that their order on the ring is
1 -> 1 -> 2 -> 1 -> 2 -> 1. Since there are no loop sections in this order, we know exactly which 1/2 of the second array corresponds to each 1/2 of the first:But the order between $$$2$$$ and $$$3$$$ cannot be satisfied under this mapping, so this example corresponds to “NO”.
In practice, there may be more than one of these mappings (e.g., when the order appears to have loop sections). In this case, we need to use the properties given earlier to construct a graph and determine its isomorphism.
Consider the following graph construction:
This way of connecting edges actually implies the positional constraints given earlier, and it can be shown that the output is “YES” if and only if the graph obtained from the two series is isomorphic. Continuing to look at the graph, it can be seen that the graph is actually a rooted pseudotree, with positions on the rings corresponding to positions with numbers equal to $$$1$$$. At the same time, each node of this tree has no more than two children (since the position $$$i$$$ will only be concatenated by the first occurrence of $$$a[i]$$$ or $$$a[i] + 1$$$ to its left), which guarantees a complexity of $$$O(n \log n)$$$.
So it is straightforward to determine whether two trees are isomorphic, and hence the answer to the question, by calculating the hash value of each part of the pseudotree directly from the deterministic tree isomorphism, and finally obtaining the unique identifier of the pseudotree from the minimal representation.
P.S.: I added an
asserton the number of child nodes after ACing F and submitting it again, but forgot that Codeforces only counts the last AC, which caused me to drop from first to third on the standings board :(Translated with DeepL.com (free version)
What's an assert?
It's a built-in macro in C++ to check if a statement holds true. See https://en.cppreference.com/w/cpp/error/assert.html
Hopefully i reach pupil after this contest :)
neat problems B and C
misread D rip
rip lol
Hopefully i'll get there next time. ＞︿＜
Damn you have solved 1000 problems. Respect!!
couldn't even try d properly, only 20 mins were left.
nice problems A bit of tricks into each one of them! Thumbs up for the problemsetter.
Hello, My implementation for problem C is this -> 324129946. It was giving WA in pretest 5 . Can anyone please point out the mistake .
I just modified this loop with break and it worked correctly.. but why do i need a break statement .. its quite obvious that if at the jth iteration sum exceeds k then at j+1th also it will exceed
It will overflow and get junk values
324106167
Rank 9, PAPABOLO has a very interesting submission order. A, (incorrect B), (incorrect C), (incorrect B), D1, E, D2, (incorrect C), B, (incorrect C), (incorrect F), C
Its a real story of overcoming adversity to achieve such a high place with this submission history and starting the contest 30 minutes late.
or ai use idk
Hey, I started coding 2-3 minutes into the competition. And then after that, because previously I was hitting like incorrect solutions and facing penalties on previous competitions, so I was building my own test cases, so by the time half an hour was complete I believe I had already coded up the first few problems which I thought would be easier for me to solve, and they were running on different test cases(mine). So once that was done I submitted them in the order the test cases I made stop running.
Too many mistakes in word "ChatGpt"
Hello, My implementation for problem D is this -> 324142473. It was giving WA in test 10 . Can anyone help me in this?
can anyone provide a proof for why sorting by distance from centre works for problem E
okay so my observation is that if we take the middle element and then go layer by layer, for any layer k, only the cells of the layer k-1 will be penalized (think about it).
now as we are going layer by layer we will compare the chessboard distance of that specific layer from the middle element and then go from in to out.
and as the problem itself suggests that the tiebreaker is manhattan distance, we will then choose those cells with the highest manhattan distance for adding the penalty.
let m = n = 3
initially we choose the middle element.
from the middle elements all the cells of layer 1 are equidistant, but the closest are the adjacent cells and then the diagonal ones(bcs of manhattan distance)
now if we choose the the diagonal ones first then for every next coloring of element the penalty of any diagonal cell will exceed 3
as one can see that the top left cell exceeds 3. so the better approach is to go from in to out(from closer cells to farther according to the tiebreaker)
thus we will extend this for multiple layers
now this can be easily done by sorting the coordinates with the first key as chessboard distance and the second key as manhattan distance.
324160206
E was basically guessforce and it alone was worth more than D1 + D2...
just me or you can't view solution for e?
we cant view any of the implementations
Hi! Sorry for the delay, the issue should be fixed.
Can someone point out the error in my logic in problem C
f(x, j) = minimum cost to make x having at least j bits on by definition if x have already n bits on, then if j < n f(x, j) = 0
we can say that if x is fixed f(x, j + 1) — (x, j) >= f(x, j) — f(x, j — 1)
meaning making j-th bit on costs more or equal than (j-1)-th bit on
so we can just sort by f(x, j + 1) — f(x, j)
then greedily take till which we can, taking one element means ans++
it gets WA at tc 9 Edit Got AC [was a silly mistake]
Your logic is okay, but you're not decreasing k, so it will give WA for for any 0 . Just do k -= wow3[i].ss while adding to the answer.
The main problem is that you're counting up to 60 bits, but it can never actually make all 60 bits high, because k can be at most 1e18 — which can set at most 59 bits. Your logic is doing now — pre, so the delta of 2^60 can end up being less than k.
so you code is adding 2^60 which is impossible to add
yeah u got me, it was just an overflow issue
is there some way to make integers like 1 act like 1LL in C++ without explicit type casting? i have lost more time because of this overflowing during 1<<bit than i would like to admit
I mean when you use the integer with some ll quantity during multiplication, addition and all, it behaves like a long long number, otherwise using 1LL is the only way, it doesn't take any time also.
I bricked B very hard, other than that very cool problemset
Nice contest.Fast Editorial
F is very cool!!!! D is good too
Great problemset!
in E, can someone please explain that what are the key differences when n,m are both even or 1 even 1 odd??
Why is $$$1 \leq n \leq 5000$$$ in problem C, why not higher constraints?
maybe checker need it.
I am curious about this, can you please explain ??
how does checker affect the limits used in the problem
Uh, not this problem. I've seen some of these problems before.
oh ok, np
Problem B can be 10^6, but only 5e3, this may cause by the checker.
Problem C doesn't need a checker? There is only one correct answer in C. The system just needs to compare your output to the official one.
Originally we used $$$n\le 2\cdot10^5$$$, but some $$$O(N\log^2{N})$$$ python solutions had a hard time passing, so we decided the lower the constraints a lot lower.
For A, it was crazy how you could just output all 1s and then all 0s as a binary number and that'd be a valid output cuz the number of 101s and 010s are gonna be 0 for both
How can example 2 in problem B be valid? since it's not permuting the first and last row such that every column will have 2 identical elements: e.g. two 1s in the first col and two 2s in the second col...etc
matrix size is
4... no. of operations used in the answer is5Ah! You’re right. Thanks for pointing out
yeah, np!!
Can someone share your D2 code, please a readable code. Thanks a lot
thanks
can you explain a little the inv part please the last check what means?
When I click on the implementation, it shows me some submission and when I click it it says, "You are not allowed to view submission" or smth like this, what do I do? Please help. Thanks :)
is not you, if you want to check some implementation ask here in comments, or wait writers fix that
All the code in Implementation seem to be linked to submissions in a private gym contest. So we just couldn't view any of them until someone fix it.
It's not really obvious to me why the solution of problem F works. Why is the idea of building the rooted trees equivalent to the original problem?
Firstly, let's imagine that the vertices of the trees have their identities tied to the identities of elements on the array. Let the vertex corresponding to index $$$i$$$ have label $$$a_i$$$.
We can show that the solution is correct by proving 2 things:
(Necessity) The cyclic sequence of the trees remains invariant under the operation. This is because no vertices can ever move to a different parent nor can the order of them change underneath the same parent.
(Sufficiency) This is the harder part — we want to show that $$$a$$$ can be transformed into any array that satisfies the same invariant. A nice trick to make this easier is to establish a "canonical" representation for the invariant, and proving that every array satisfying the invariant can be transformed into the canonical representation. Thankfully, there's a pretty natural one here: the pre-order traversals for all of the trees concatenated together in cyclic order, starting at an arbitrary tree; I'll call this $$$c$$$.
Consider any array $$$a$$$ that doesn't equal $$$c$$$. First, let's rotate $$$a$$$ so that $$$a_1$$$ corresponds to the root of the starting tree in $$$c$$$. Since preorder traversals start at the root, it follows that all occurrences of $$$m$$$ are in the correct place. If something else doesn't match, consider the first $$$i$$$ such that $$$a_i \neq c_i$$$. Let $$$j \gt i$$$ be the index of the first occurrence of $$$c_i$$$ in $$$a$$$ after index $$$i$$$. We'd like to swap $$$a_j$$$ to the left until it reaches $$$i$$$, but might run into something with value $$$a_j + 1$$$ or $$$a_j - 1$$$.
$$$a_j + 1$$$ is impossible — since the preorder traversal of the tree matched $$$a$$$ up until $$$i$$$, $$$a_j$$$'s parent must be in the correct place. Thus running into another $$$a_j + 1$$$ would mean that $$$a_j$$$ belonged to a different parent.
$$$a_j - 1$$$ is also impossible — since we know there's no occurrence of $$$a_j$$$ in $$$a_i, a_{i + 1}, ..., a_{j - 1}$$$, it must be true that its parent lies within $$$a_1, a_2, ..., a_{i - 1}$$$ and thus it must've occurred earlier in the traversal.
It follows that $$$a_j$$$ can be swapped to the left until it reaches $$$i$$$, and repeating this procedure would eventually yield $$$c$$$.
Why cant I open the code solution?
This blog may help you:
https://www.zhihu.com/question/3258240803/answer/27316958173E could be solved easily by just sorting all possible pairs using this
can someone show the graph implementation for D2? the solution in the editorial isn't loading for me(permission error)
i tried to see all problem implementation but it shows this error "You are not allowed to view the requested page".How to fix?
You are not allowed to view the requested page
What happened?
Getting the same error
Problem D2. Red Light, Green Light (Hard version) Giving wrong answer on test2. Can anyone explain the reason. Please.
I solve D2 in O(N) with offline the query, basically just go from largest starting point to smallest starting point and use hashmap to keep track the nearest light point that can be collided with current starting point. My submission: 324206877
Still have to sort queries, not O(N)
can anyone explain the problem E , my idea was trying to use bfs from the center of grid, but it seem to be a wrong solution, pls help me, thanks in advance
i cant view the solution it says you are not allowed to view the requested page Can someone help?
324106193 Could someone please explain why this dp approach for C doesn't work?
why I click the implementation and it shows "You are not allowed to view the requested page"
Easy solution for
2118BThe proof of optimality for the greedy solution to problem C is quite interesting.
The editorial already mentions that there is no number more beautiful between $$$x$$$ and $$$y$$$. Let's define a move as a sequence of operations that increases the beauty of a number by $$$1$$$ (i.e., transforms $$$x$$$ into $$$y$$$). The cost of a move is the number of operations required to perform it.
Now, a natural question arises: how does greedily selecting the move with the minimum cost lead to a maximum total beauty? Let me explain this in two steps:
Consider a variation of the classic 0/1 Knapsack Problem in which all items have the same value. In this setting, a greedy strategy of always selecting the lightest available item first is optimal. Now, at first glance, it might seem that this does not minimize the leftover capacity (i.e., the "gap") in the knapsack. However, the solution remains optimal in terms of total value.
Suppose we construct an optimal subset by including a heavier item instead of a lighter one. If we then replace that heavier item with the lighter one:
So, any optimal solution using heavier items can be transformed into an equally optimal solution using lighter items. Therefore, greedily selecting the lightest items results in an optimal solution.
In this problem, each move increases beauty by exactly $$$1$$$, and we are allowed to perform at most $$$k$$$ operations. Thus, every move has the same value (i.e., +1 increase in beauty), while the cost (number of operations) varies from move to move. This maps directly to the knapsack variation described above.
There is just one difference. In our problem, not all moves are available from the beginning. As we perform moves, we discover new moves as the transformed number can now get a new transformation (ex., after transforming $$$45$$$ to $$$47$$$, it can then be transformed into $$$63$$$).
Let’s compare what happens when we use our strategy in two scenarios: the actual one, where moves are discovered gradually, and an ideal one, where all moves are available from the start. The only potential concern is that we may miss a minimum-cost move in the actual scenario because it hasn’t been discovered yet. But in our setting, there is a guarantee that this will never happen.
The cost of a move is $$$2^{\text{position of rightmost 0}}$$$. Once a move is used on an element, the position of the $$$\text{rightmost 0}$$$ must increase. So, the newly discovered move from that element always has a higher cost. At any point, the minimum-cost move among all currently available moves is guaranteed to have the globally minimum cost (as the unavailable future moves will have higher cost).
Therefore, the greedy strategy of always applying the minimum-cost move maximizes the number of beauty-increasing moves that can be performed within the budget of $$$k$$$ operations. This proves the optimality of the greedy solution.
Note:
0/1 Knapsack Problem — Given a knapsack with capacity $$$c$$$ and $$$n$$$ items, where each item has a weight and value, the goal is to choose a subset of items such that the total value is maximized, maintaining the constraint that the total weight of items in the subset does not exceed $$$c$$$.
In 2118B - Make It Permutation, is the most optimal solution not 2*n -1 instead of 2*n? (Just curious)
I think it is 2*n-3 which is coming like this for all rows except row 1,row n-1 and row n cost is 2 so 2*(n-3)=2*n-6 and for those 3 rows it is 1 per row ,so total 2*n-6+3=2*n-3
an 'interesting' way d1 could be 'ACed' is by running 2500000 sec on every query i knew this from my friend TranSiQuy who ACed this way
Hey, Can someone help me out ?
I am unable to see the solutions for this contest.
When I click on the Implementation code, it says "You are not allowed to view the requested page"
Pls help me out.
Can any explain the graph approach for D2.
First observation you need is that if you hit a specified light from the left the next red light you hit will always be the same one, independent to which point in time you hit the red light (same goes for the right side). So if the next red light is predetermined you can construct the following graph: for node i you store which red light you will hit first if you hit a red light at node i and a) turn left, b) turn right. From this you can either dfs down this graph and store a query-s answer in each of the visited nodes, or find all nodes that go into a cycle.
Is 2118B - Make It Permutation a ad-hoc problem?
I don't understand why my submission of problem C is wrong[submission:324087417]. Can someone help me!
rejdioglava09 orz for being soooo skibidi sigma i got hot watching you send solution for problem b
by the way, I don't have access to the implementations of C and D. I assume it's also the case for others. please fix it when you get chance. thanks.
@szilb
Should be fixed, sorry for the delay.
good contest !
You are not allowed to view the requested page. when i try to see solution how to fix
I thought the editorial for D2 was a little confusing. I couldn't quite understand what d[y]-y and (t-x) had to do with each other. The diagonal imagery helped though, and after a while it made sense to me. The idea became clear to me after drawing a small example on the graphic. If anyone else is still confused, this might help. It then becomes clear how (t-x) and (d[y]-y) relate and why we're interested in hashing them into the same bucket.
c: https://youtu.be/pHimy6XqPTA?si=9ULxwp37CcDDJB_t
Maybe someone knows if it’s possible to compute F without constructing the trees?
I had the following idea: for each s in [2,m], consider an array where the ith value is the number of occurrences of s between the ith and (i+1)th occurrences of s−1. Let's call such arrays linkings. Then, the linkings of A and B should be rotations of each other, and we can detect this using FFT. Moreover, we can determine which shifts are viable: they will be of the form kd+r, where d is a divisor of the number of occurrences of s−1.
The problem is that we can’t rotate different linkings independently. Maybe someone has ideas on how to resolve this? Or are these trees essentially the only way?
Let's transform the array such that $$$a_i \gt a_{i+1}-2$$$ for every $$$i$$$. You may notice that the cyclic shift of this transformed state is unique. From this, you can construct a solution: transform both $$$a$$$ and $$$b$$$ into this form and check whether they are cyclic shifts of each other. This can be done in $$$O(N)$$$: 324451173.
Thank you! That's super elegant.
does anyone have the implementation of the second solution for D2??
I do: 324284287. It's a bit overengineered, but essentially the same.
Thanks!
I have solved D2 in O(n) using Unordered_map<ll,vector> and vector to find nextGreater and nextSmaller. Store the queries in array along with all positions and iterate backwards.
Dear Codeforces Team,
My submission (#324131839) for Problem 2118A in this contest has been flagged for similarity to other submissions. I want to clarify the following:
I have great respect for Codeforces’ rules and the spirit of fair competition. If this similarity resulted unintentionally (e.g., due to coincidental logic structure), I kindly request a reconsideration of my submission.
Thank you for your time and understanding. I will be more diligent in the future.
Sincerely,
Niloy_Chakraborty
Codeforces handle: Niloy_Chakraborty
Hi, I received a plagiarism warning regarding my submission [324124484] for Problem 2118C. I want to clarify that I did not intend to break any rules. I wrote the solution independently and did not share it with anyone. However, if it unintentionally became accessible possibly through a public IDE or an oversight on my part—I sincerely apologize. I respect the Codeforces platform and will be extra careful moving forward to ensure there’s no chance of unintentional leakage. I kindly request that this be taken into consideration. Thank you for your understanding.
This won't be happening again from contest 1032 I Sincerely apologize For unknowingly violating the rules . I guarantee you this was not gonna happen from the contest number 1032. Thanks for understanding
About C: log10^18 is a constant, you don't need to write it in O-notation.
Sorry, i don't know how to use LaTeX in comments.
please someone tell me the issue with my code
https://mirror.codeforces.com/contest/2118/submission/327422523
The second problem has not answer code
the diagonal idea was amazing
I got an different approach for C. we can use vector <bitset<64>> to represent each number and the n just greedily iterate on each lsb which is 0. if we have enough operations then we flip the bit otherwise we exit the code as we have lesser than required operations.
finally use bitset.count() to get our answer
For problem E, I had really achieved a solution with penalties in every cell not more than 2!
Code Link
B can also be done with** 2n-3** operations.