**UPD**: Solutions are added.

1480A - Yet Another String Game

**Tutorial**

**Solution**

**Tutorial**

**Solution**

1479A - Searching Local Minimum

**Tutorial**

**Solution**

**Tutorial**

**Solution**

1479B2 - Painting the Array II

**Tutorial**

**Solution**

**Tutorial**

**Solution**

**Tutorial**

**Solution**

**Tutorial**

**Solution**

Will this round be unrated?

The problem A is same as find-local-minima-array. The problem B2 is similar to CF802A.

seems like GFG have been headache for problem setters.

Problem C is noice!

Huh? The contest has exactly one constructive problem.

why do people downvote?

Look at the first revision of the comment

Thanks

Div 1A/2C was a nice use of binary search!

but was available on gfg

Very nice pretests, also!!!

Thank you for the original problems and strong pretests.

Now I understood the

hidden meaningof this line.. xDI guess he should have rejected 1-2 more problems. :)

Sad Reality!

apparently somebody doesn't understand sarcasm

Thank you for the speedy and high-quality editorial with elaborate proofs :) . Keep up the good work!

For problem D, you don't need to consider an xor of 4 paths; we just have $$$f(u, v, l, r) = f(1, u, l, r) \oplus f(1, v, l, r) \oplus \mathbf{1}_{A_{lca(u,v)}}$$$; then you can special case $$$A_{lca(u,v)}$$$ and the rest just needs to find one unequal index, which doesn't require any special mod 2 properties of XOR.

have the same doubt. I think div2 B and div1 D both wrong questions or no proof they have for correctness. so MikeMirzayanov u gonnna re test all submissions with test case

Spoiler1 1 1000000000 10 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

or no? tell fast. even many top rankers have different answer for the test case. tell me

I don't think we're talking about the same thing, I'm giving a simplification to the solution of Div 1 D.

Hello.

What is the answer for this test (Div.2 B) :

1 1 10

1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Can anyone tell me why my solution for Div2B is wrong? (https://mirror.codeforces.com/contest/1480/submission/106778511)

Edit 1: It's fixed now. This solution gave WA during the contest but they rejudged it later and it's now AC.Apparently the problem-setter's code didn't correct for the possible long long overflow which occurs when taking a sum of all the damage the Hero is going to take.

The problem Div 1A/2C , could be many local minimals ?

Yes, you need to print any one of them

Div1 B caught me completely off guard.

good problems but weak pretests

If you like videos, here's one that happens to have all the div. 2 solutions

Nice Div1 B1 editorial

Man my Div2 C/Div1 A Binary Search solution with 5*Log2(n) gave TLE on test 11 this is not right man. can anyone tell me the reason for TLE in this solution https://mirror.codeforces.com/contest/1480/submission/106790379

Was anyone able to figure out why TC 11 of problem C gives FST?

You are not storing the values after the query. This results in repeated queries. I did the same thing. :`(

Yeah but I'm using only 3 queries at max. each time before reducing binary search range,which happens 18 times(worst case). That is still less than 60 queries.

That's exactly what I thought. But the accepted solutions I have seen differ from mine in just this one aspect. Well the sys tests are almost over. Let's see what was the reason.

the test case is 1

What's the proof of div2C why is binary search working here

Imagine it as hills. If you are at a valley, you don't need to move. If you are at a peak, you can go in either direction. If you are at a slope, just go down the slope until you get to a valley.

for n=7, if the array is — 3 4 5 6 7 1 2 ,then the only local minima is element 1 at index 6.but firstly the mid is element 6 ,which is greater than the previous element 5,so,according to gfg solution i have to go to the left portion doing high=mid-1,but there is no local minima in the left. Can you explain this?

3 is also a minimum since the ends are +inf (in the question).

but will the solution work if the numbers are not distinct?

Idts there will be cases of flatland and you wouldn't know if it is a plateau or a basin. It also depends on the way you define local minimum. Since 3 points at same height can be considered local minimum then this idea should work.

Can hos.lyric and maroonrk explain their solutions to Div1E? It seems that they used different solutions from the one in the editorial (which uses very advanced generating function techniques).

(I know maroonrk's solution got TLE, but the fact that it only failed on test 76 indicates that it is probably a correct solution with a high constant factor.)

My solution is light $$$O\left(\sum_{i=1}^m a_i + m \log \mathit{MOD}\right)$$$.

The calculation of the potential function is the same as the editorial. After that (using the notation of the editorial) we keep track of $$$g(0) + \cdots + g(a)$$$ as a fraction with denominator $$$(n - 1) \cdots (n - a)$$$ so that we can compute the numerator and the denominator without division modulo $$$998244353$$$. We only conduct divisions only when $$$f(a_i)$$$ or $$$f(n)$$$ is actually needed. The bottleneck is $$$3 n$$$ multiplications modulo $$$998244353$$$, which I hoped to pass.

There's a simple form for $$$f(a)$$$. Define $$$prod(r,l)=l\cdot (l+1)\cdots r$$$. From the editorial, $$$f(a)=0$$$ and

You can verify that

Looks like maroonrk precomputed some factorials to evaluate $prod(r,l)$ quickly, but as noted above, this is not necessary to pass.

https://mirror.codeforces.com/contest/1479/submission/106861209

I think the editorial is a little long winded; here's my high level summary.

## Section 1 of the editorial: finding a closed form

First, it's not too hard to convince yourself that the expected stopping time from any state is of the form $$$f_n(n) - \sum f_n(a_i)$$$ for some function $$$f_n$$$. We can write out a system of linear equations using the transition probabilities, and explicitly solve it to get a solution $$$f_n(0) = 0$$$ and $$$f_n(k) - f_n(k-1) = \prod_{i=0}^{k-1} \frac{2n-i}{n-i}$$$. (Note that there are actually many solutions, $$$f'_n(k) = f_n(k) + ak$$$ is a valid solution for any $$$a$$$, and we can even pick it so that $$$f'_n(n) = 0$$$ so that the stopping time is just $$$\sum -f'_n(a_i)$$$. This is the simplest form though.)

## Section 2 of the editorial: evaluation

All that remains is to evaluate $$$f_n(\cdot)$$$ efficiently. The submissions you're referring to all just evaluate $$$f_n$$$ in $$$O(n)$$$ time using the formulas given above; if you take some care to avoid doing modular divisions, you can just squeeze it through. That's why these submissions look so much shorter than the editorial; they are using the exact same closed form though.

The editorial describes ways to evaluate everything in $$$\tilde{O}(\sqrt{n})$$$ time. These are very similar to the techniques to compute large factorials quickly; essentially, you expand the product of $$$\prod_{i=0}^{\sqrt{n}} (x+i)$$$ as a polynomial in $$$x$$$, and then use multipoint polynomial evaluation with FFT to evaluate it for $$$x = \sqrt{n}, 2\sqrt{n}, \ldots, n$$$. The formulas in this version are slightly more complicated, but the techniques are pretty much the same.

I haven't seen anyone else fail for test 55 for problem C, could someone point me in the right direction/test case as to why my solution is wrong? I can't see the test for it as of yet.

submission:

I've considered the case for n == 1 & 2.

I'm not using an array to store the values which apparently could lead to repeated queries, but people seem to be getting a TLE in an earlier test case for this.

Perhaps my binary search implementation is skipping over an element for the minimum.

As always, apologies for the god awful formatting, it's my first time solving an interactive problem.

You're querying for out of bound indices. When

`mid = 1`

, you'd query for index`0`

as well.Solution of Div1 B1 is so... big.

Any idea why my code fails for Test Case 55?

Did somebody order a heartbreak?B passed on rejudging! ily liouzhou_101.

liouzhou_101 I feel my submission is wrong. And there are many submissions like mine. The mistake I did is I checked if the hero's health before giving the final blow is >= 0 instead of > 0 (i.e. totalAttack — max(a) <= B instead of < B).

Please rejudge (I know I'll lose my rating but a mistake is a mistake :))

Ah yes, I did the same mistake but got AC in B. I guess they trimmed the test cases in a hurry. Should rejudge or just revert the ratings. Latter would be easier I guess.

My incorrect solution passes for D1.. Weak main tests as well :/

Could anyone please help me understand why I got a WA? 106825850. I can see that my fundamental understanding of binary search is wrong, but I'm not able to understand why there's a problem when taking the range as [l m-1] instead of [l m]

When you update the range to [l m-1] instead of [l m] in the case a_m < a_m+1, you disregard the possibility that a_m might be a local minima itself(it's already lower than a_m+1, it could be lower than a_m-1 making it a local minima) and exclude it from your range.

liouzhou_101 I don't think changing the constraint after the contest makes sense, as we solved for the given constraints only and overflow wasn't handled then I think the author should rejudge with correct answers instead of changing constraints after the contest.

I think authors would rather change constraints and keep the round rated than get 90% (according to Anton) of solutions FST and a massive outrage.

But how is that fair to remaining 10%. Also, the reason for massive outrage wouldn't be 90% FST but the weak pretest leading to such outcome.

Anyway please avoid such solutions in future.

I can see your point, and I understand why you would be upset about the changing of the constraints. However you also have to look at it from the authors' perspective. They really only have three options:

What would you do?

Alternate solution for Div1B/Div2D, works for both versions of the problem:

Consider painting the array one element at a time, from left to right. After painting $$$a_i$$$ either white or black, one of the two subsequences $$$a^{(0)}$$$ or $$$a^{(1)}$$$ must have $$$a_i$$$ at its back. Since the only relevant properties of the subsequence are their last elements and total number of groups so far, we can almost solve the problem with a DP, where $$$dp[i][x]$$$ is the largest (smallest for B2) number of groups that can be achieved after coloring $$$a_1, \ldots, a_i$$$ such that the two elements at the end of the subsequences are $$$a_i$$$ and $$$x$$$. The DP transitions are not hard to figure out, but are a bit messy. This isn't quite enough to solve either problem, though, because the bounds are too large for an $$$O(n^2)$$$ DP to pass directly. But for all values of $$$i > 0$$$ and $$$x \neq a_{i-1}$$$,

...and by keeping only the most recent row of $$$dp$$$, and storing it as a segment tree, all $$$n$$$ transitions of this type for a given value of $$$i$$$ can be performed in $$$O(\log n)$$$ with a single lazy range-increment. The value of $$$dp[i][a_{i-1}]$$$ can be calculated using a few range-max queries (range-min in B2), also in $$$O(\log n)$$$ time. This leads to a total time complexity of $$$O(n \log n)$$$.

For ugly nearly-identical implementations, compare 106829611 with 106850293.

I do solved Div1B1 also using DP but with a little trick.106809164

My DP was $$$O(N^3)$$$ dp[i][last value painted white][last value painted black]. Which is TLE/MLE obviously.

I had to reduce it so I renumerate the array a with numbers 1,2,3,4.

If an element is different from the last three I renumerate it with a value not in the set of new values of the last three elements.

Else I renumerate it with the same new value of the one that match it in the last three.

Then I run my O(N*4*4) DP and get the answer .

I don't know if my idea is correct or the system test are weak. But I passed system test (^_^). Anyway my delta is -13 and I get back to expert(-_-).

Any idea why your solution does not work for B2? BTW, I really liked your solution. Mine was...........quite nasty.

check this testcase-

n = 11

array a = 2 3 10 3 3 8 9 2 11 10 3

array b would now be = 1 2 3 2 2 1 3 4 2 1 3

so when we perform dp on this new array for example the 1 at index 5 can get merged with 1 at index 0 which is not originally possible for array a and the result will be less than original answer

Also, this idea can be implemented in $$$O(n)$$$ without a segment tree, consider the changes to dp array, you will add 1 to each but one element, or change only one element, so you'll need a variable that stores a lazy value, the dp array, and the minimum dp (or maximum), see my D1B2 code for further understanding.

Can you please elaborate your solution and approach?

As i said, my idea is the same as the one explained here, for the implementation I used the Venice Technique, you can find more information about this in this tutorial.

Hey! Thank you for providing the tutorial for the technique.

In the original solution it is mentioned "The value of dp[i][ai−1] can be calculated using a few range-max queries"?

I understand the transition of dp[i][x], can you explain how are we calculating dp[i][ai-1] perhaps?

Could you please explain what you meant by storing the dp array as segment tree? I am new qto this approach, it'll be great help. Thanks

Can anyone give a test-case for which my code fails (Div2 B)?

"In each fight, the hero can select an arbitrary living monster and fight with it."You can check this.

10 10 2

11 5

5 5

The Answer will be "YES" if he fight with the second monster first and then the first monster.

I liked the problemset

Especially div2 C, it increased my understanding of binary search.

I loved solving div2 C.

Hi, could you please help me with this

Your program stops for all cases where the array is a[i]=i (1-based) without outputting any "! x" prompt.

You need to output variable "hi" after the binary search if you are unlucky enough.

Ahh, I got it now, thank you!! In general though, I'm not able to understand why sometimes, the range is fixed as [l mid] [mid r] or at other times like: [l mid] [mid+1 r] or like how I'd mentioned earlier (I've tried variants earlier and realised they either get a WA or TLE). Are there are generalisations to binary search? Could you also clarify that/ suggest any resources where they've explained this?

It depends if you round down or up when getting the "mid" value. If you round down, you need to have [l mid][mid+1 r] (For example range [2,3] and you round down to mid=2, [2,2] and [3,3]) but if you do [l mid-1][mid r] you either get a case where r<l or an infinite loop (TLE).

Ahh! All the while I was only thinking that we take the range as [l, mid-1] because we don't require the mid value (if eg, mid > x) and likewise for eliminating the unnecessary mid value in the higher end, the range is made [mid + 1, r]. I now understand that it's also about maintaining proper values in the boundary.

How exactly to round down though? Or is it recommended to round up? One more query... how to find when to round up/down.

C++ automatically rounds down when there is a decimal if the data type is int. There is no difference to round up or down in time complexity or ability to find the target, you just need to change the ranges. Therefore, you can choose to round up or down in any case

Please help me to find bug in my code it's failing at test case 21

div2 C

106868099

UPDATE: GOT IT, I was printing '?' instead of '!' at one place

106841211 why does my submission for div2 D1/div1 B1 fail ?

I am not asking if my binary search is correct because I sort of just believed the pretest would sort it out for me. But I think its impossible my loop breaks without having found the answer.

It said my answer was wrong instead of query limit exceeded. So it must have broke but it wasnt the answer?

https://mirror.codeforces.com/contest/1480/submission/106784965

You are comparing the query responses as strings rather than as ints.

I know a solution for div1D that is not randomised. I know that it's correct but I can't make it fit the TL a little bit. It works 6.1 seconds on codeforces.

Let

`cnt[i][j] = s(v, 0, j) mod 2`

. This array takes O(n^2) memory so we have to make it smaller. We can do this using persistent segment trees and dfs. Now we can calculate cnt in O(n log n) time and memory.How to answer queries using cnt? The answer is any non zero number in

`(cnt[u] ^ cnt[v] ^ [1 if k == a[lca(u, v)] else 0 for k in range(n)])[l..r]`

Let's change

`a[lca(u, v)]`

th bit in`cnt[u]`

, then we need to find any different bits in 2 isomorphic segment trees from l to r. That can easily be done using perfect hashing on subtrees of segment trees.Sorry for my English. If you have any questions feel free to ask.

Choose one.

You can do non-randomized perfect hashing on binary trees.

Suppose that we have only 0 and 1 as values at leafs. This values will be leaf vertices’ hash. Every other vertex has two subtrees. If you don’t know the hash of some tree you calculate hash of left subtree, then of right subtree, then look up at some map:

`hash[{left_hash, right_hash}]`

. If the map has no such key you set it’s value to counter++, which is set to 2 in the beginning. Otherwise, you already know the hash.So my solution is still not randomized.

Hey, I also have a deterministic $$$O((N+Q)\cdot \sqrt{N})$$$ solution, it passes in 3 seconds on codeforces. For the queries on a path, you can use Mo's algorithm on trees. Then when we do Mo's algorithm, we keep track of the evenness/oddness (0/1) of all the minerals. On top of that we keep for each block of $$$\sqrt{N}$$$ minerals the sum of the minerals' oddness values. We can update this structure in $$$O(1)$$$ and check if there is an odd mineral in a range in $$$O(\sqrt{N})$$$. We update many times, but we query only Q times. This makes the above time complexity.

Edit: I just saw that mohammedehab2002 had exactly the same idea...

So you either use an unordered_map which is randomized, or usual map, which adds extra log, so good luck fitting that into TL.

Even though unordered_map is randomized, it still has some merit as "better randomized" because it turns the algorithm from Monte Carlo (could be wrong) to Las Vegas (only runtime is randomized). Also, I think the existence of a deterministic dictionary is still open, so we can hold out hope.

Only runtime is randomised, so it's not $$$O((N+Q) \log)$$$.

Optimized AC solution: 106873608. The lesson here is probably not to use std::unordered_map for anything, ever (except maybe strings), because

holy crapit's slow. Use __gnu_pbds::gp_hash_table or __gnu_pbds::cc_hash_table instead.I had a few problems where I tried to use gp_hash_table to speed up my solution but it didn't help at all. It only slowed it down. Also strings are not hashable by default so you can't use unordered_map for them.

The following seems to be working for me (for example):

So I don't understand what you mean by that statement; maybe you were referring to something else?

Oh, I thought strings can't be used that way like vectors and pairs. That's pretty cool actually.

How to prove Div1A/Div2C mathematically? I mean how can we prove that there exists a local minima in the left side of the array if $$$a_{mid} < a_{mid + 1}$$$?

Consider the current mid $$$m$$$, if $$$a[m] > a[m-1]$$$ then the values in the left side (a[m-1] , a[m-2] , ...) must be decreasing untill some index $$$idx$$$ then increasing, then it will be guarnteed that a[idx-1] > a[idx] and a[idx] < a[idx+1].

You can proof the right side in the same way.

Apply Rolle's Theorem

In Div2B, my Submission with the condition max(H(k)) >= 0 works. But I believe the correct condition is strictly greater than zero as is mentioned in the editorial. Is this hackable or am I missing something?

Hello, Can anyone tell me why my solution to Div2 problem B got

wrong answerontest 2?I tried alot, but couldn't find the mistake.

I guess you have a similar mistake that is described in this comment

There's a problem with the comment link that you've attached.

It shows me "forbidden"

Oh, this is a link on mirror of cf, try that

Tester here. I have another solution for 1D using MO's algorithm on trees. If you don't know what this algorithm is about, it flattens a tree so that for each path, there's an interval (or maybe a union of $$$2$$$ intervals) in the flattened array such that the nodes in the path occur exactly once in it, and the rest of the nodes occur $$$0$$$ or $$$2$$$ times. And then you use the normal MO's algorithm on the flattened array. Tbh, I thought this problem was custom made for this algorithm, but apparently I was wrong.

So in MO's algorithm, we extend or shrink an interval, and then we update the value on the boundary. Here, we'll flip the parity of the number of occurrences of $$$c_u$$$, where $$$u$$$ is the node on the boundary, and then we want any color that occurs an odd number of times in an interval. So the problem turns into an update-query problem on a binary array which says:

Now, this is easy with segment trees, but the complexity will be $$$O(q\sqrt{q}log(q))$$$. However, notice that the number of updates is way bigger than the number of queries. You do $$$O(q\sqrt{q})$$$ updates, but you only do $$$O(q)$$$ queries, so we can instead try to do the updates quickly, on the expense of the queries.

The idea is to use sqrt decomposition instead. Divide the array into blocks of size $$$\sqrt{q}$$$, each maintaining the sum of the elements in its range. Now, you can do the updates in $$$O(1)$$$, but the queries will take $$$O(\sqrt{q})$$$.

Code

Can anyone help me? Why are these two solutions different?(first, second). Same idea, but different verdict.

Can someone explain the last line in the Greedy Strategy 1 under the intuitive proof of Div2 D1. It says, "Suppose $$$b$$$ results in the two subarrays $$$s′xzs′′$$$ and $$$t′yt′′$$$, while there is indeed another optimal assignment that agrees with our strategy and results in $$$s′xt′′$$$ and $$$t′yzs′′$$$ ".

I don't understand how did our strategy result in $$$s′xt′′$$$ and $$$t′yzs′′$$$ ", why are $$$s′′$$$ and $$$t′′$$$ interchanged and why is this also considered optimal?

have you figured it out? Can you tell me?

Lol no I haven't figured it out yet, no one replied, so I'm still in the same doubt.

You have to see the difference that it creates.

With greedy strategy we have

$$$s'xt"$$$

$$$t'yzs"$$$

let's say answer for greedy strategy is $$$ans_{greedy}$$$

And as for optimal sequence $$$b$$$ we have

$$$s'xzs"$$$

$$$t'yt"$$$

let's say answer for optimal sequence is $$$ans_{optimal}$$$

Now, $$$t'yzs"$$$ will have one more contribution in the answer than $$$s'xzs"$$$ (x==z). And till now we have $$$ans_{greedy}$$$=$$$ans_{optimal} + 1$$$

And now in the worst case, $$$t'yt"$$$ will have one more contribution than $$$s'xt"$$$ (worst case is when $$$t"=xt_1$$$ i.e. $$$t"$$$ start with $$$x$$$).

And now for the worst case we can have $$$ans_{greedy}$$$=$$$ans_{optimal}$$$.

So, we have shown that our answer with greedy strategy is not worse than optimal sequence.

Tell me if I am wrongYeah I understand what you're saying, but my main doubt still remains, why is the answer for the optimal strategy $$$s′xzs′′$$$ and $$$t′yt′′$$$? I don't understand what is it in the optimal answer that leads to the exchange of $$$s′′$$$ and $$$t′′$$$ from the greedy answer. According to me, the answer for the optimal answer should be written in the form $$$s′xzu$$$ and $$$t′yv$$$ where $$$u$$$ and $$$v$$$ are arbitrary sequences which are not related in any way to $$$s′′$$$ and $$$t′′$$$.

Editorial is using exchange arguments here. The point is, you're trying to decide whether some decision ( like, where to place $$$z$$$ in case $$$x=z$$$ ) is not worse than the optimal one.

So, now you say, let's suppose the optimal answer contains criteria other than what our strategy tells us, that is, the optimal answer has form $$$s'xzs^{"}$$$ and $$$t'yt^{"}$$$, where $$$x=z$$$ and $$$y \neq z$$$. Now, this is against our strategy, so we show that if we had also placed $$$z$$$ according to our strategy, we could have made a possible assignment that would not be worse than the optimal. Our assignment would say $$$s'x$$$ and $$$t'yz$$$ and then we have to place the remaining elements, but using a generic $$$u$$$ and $$$v$$$ like you said, you can't compare it to the optimal assignment in question, so we consider 2 assignments specifically ( keeping the internal result of $$$seg(s^{"})$$$ and $$$seg(t^{"})$$$ constant ). (Assuming first characters of $$$s^{"},t^{"}$$$ as $$$S,T$$$ respectively )

Assignment 1$$$s'xs^{"}$$$ and $$$t'yzt^{"}$$$

Here, optimal has $$$ [y \neq T] $$$, whereas our assignment has $$$ [y \neq z] + [z \neq T] $$$, since we know that $$$y \neq z$$$, we have $$$ 1 + [z \neq T] \ge [y \neq T] $$$.

Assignment 2$$$s'xt^{"}$$$ and $$$t'yzs^{"}$$$

Here, optimal has $$$ [y \neq T] $$$, whereas we have $$$ [x \neq T] + [y \neq z] = [z \neq T] + 1 \ge [y \neq T]$$$

So, both assignments show that our strategy is not worse than optimal. Also, the editorial just happens to mention one, but any placement of $$$s^{"}$$$ and $$$t^{"}$$$ turns out to work.

Yeah now I understand, thank you. They should include this in the editorial that would be really helpful. Now that you explain it, it seems so obvious, dunno what I was thinking. Nevertheless, thanks a lot!

liouzhou_101 doesn't look like the Contest Materials have been updated with the link to this editorial post — just FYI.

Thanks for the great contest! Really enjoyed the problems :D

i wasted all my time on problem B div. 2 because in the contest it told me that my solution had not passed the pretests, and now I see that my solution has been accepted, ok ....

I became red in the round and I'm so happy!!!

But I have to say I didn't like D very much — its Mo's algorithm on tree solution require not much thinking but the limits were quite tight. My first solution ran for 4960ms and I was afraid that it would fail system tests so I resubmitted after optimizing constant factors (making me rank 70 -> 150) but it turned out that the pretests were just all system tests.

I have an alternative $$$O(n)$$$ greedy solution for Div2D12/Div1B12, which is different from editorial and is

pretty short, but I am still trying to prove that.Div2D1/Div1B1: 106865184

Div2D2/Div1B2: 106845535

The preprocessing is combining the same neighboring elements and store it as {$$$val, len$$$} in first problem and {$$$val$$$} in second problem. We call this new array as $$$b$$$.

The basic idea for both questions is that, we want to greedily choose better result when we process current element $$$b[i]$$$ (need proof).

Besides, when we process $$$b[i]$$$, we know $$$b[i-1] \neq b[i]$$$ in our preprocessing. $$$b[i-1]$$$ is the last element in one color, so for another color we want to see what potential elements we can choose. We will maintain a set $$$alter$$$ to record potential available elements. We want to choose a different element in first problem and a same element in second problem.

The elements in $$$alter$$$ can be placed in same or different color with $$$b[i-1]$$$. We can reorder to place any element in $$$alter$$$ to the end of another color. For example, if we have $$$b[i-1]=3$$$ and $$$alter=[1, 2, 4]$$$, then we can make $$$1$$$ as last element of one color by reordering two colors like: $$$[..., 2, ..., 4, ..., 3]$$$ and $$$[..., 1]$$$.

For first problem: when $$$len \geq 2$$$ for some $$$b[i]$$$, then we will distribute it to both colors (need proof). When $$$len = 1$$$ for some $$$b[i]$$$, we need to decide which color to place it. We know that $$$b[i-1] \neq b[i]$$$, so we want to check can we find an element in another color that is different from $$$b[i]$$$, so we check $$$alter$$$. If so, it means that we can place $$$b[i]$$$ in either color, so $$$b[i-1]$$$ is in same color or different color with $$$b[i]$$$, so we can place $$$b[i]$$$ into $$$alter$$$. If not, it means that $$$b[i-1]$$$ must be placed before $$$b[i]$$$, so $$$b[i-1]$$$ is fixed.

Second problem has the same idea and even simpler. We just need to check whether $$$b[i]$$$ in $$$alter$$$ and update $$$alter$$$.

Can you please check my code and tell me the error in my logic for Div2 D1 :/ https://mirror.codeforces.com/contest/1480/submission/107013163

Whose solution for problem D yesterday did not use

`long long`

and WA on pretest #2？Because of this，I waste almost 40min ……

Did anyone else solve div1B2 with min cost max flow?

The data of Div1.D is not strong enough cause my solution with complexity $$$O(n\sqrt{q})$$$ can pass.

Link of my solution -> https://mirror.codeforces.com/contest/1479/submission/106839336

Why "not enough"? With 5s I think sqrt is one of the expected solutions. For example: https://mirror.codeforces.com/contest/1479/submission/106913527 this is mohammedehab2002's code with the same complexity and it's barely slower than 2s.

Hello, could anyone help me with my Div2.C? I used the ideas from gfg after contest but I still get the wrong answer on test 11.Thank you!My submission-> https://mirror.codeforces.com/contest/1479/submission/106868187

thanks for all. But editorial could be better. You could explain better.

can somebody tell why my solution fail for problem 1479B1?

https://mirror.codeforces.com/contest/1480/submission/106875875

in case:

6

2 2 1 3 2 2

The answer is 6 but your output is 5

Can anyone find out the error in my submission in DIV2D2 ? https://mirror.codeforces.com/problemset/submission/1479/106881116 THANK YOU!

I have already understand my error in the problem D2,When we use the vector or other data sturctures to solve this problem,We should update the Nxt[i](It's that the next a[i]'s position) when we push or merge to number ,such as this:[1,1],when we make them both are color 0,we should update the Nxt[color0[color0.size()-1]].

If you have this error,you will be Wrong Answer in test 6.

Div1A/Div2C

After Learning L02 — Peak Finding, I write this code submission 106878273 but get WA on test 22.

Can anyone give me a hand?

Try for: 6 5 4 3 2 1

a[n + 1] should be inf.

Oh! This little bug.

My mistake

`a[0] = a[n] = INF`

, it should be`a[0] = a[n + 1] = INF`

.Thanks a lot.

For Div2 C, My submission got TLE on 7th pretest. I had the same intuition and implemented as given in tutorial. If someone can find out the mistake, it will be a great help. Thanks in advance.

Submission Link : 106890877

You are not changing the values of left and right for the case when curr > left && curr > right.

Oh Yes! I checked. Just If I had put a simple else it would have got AC. Thanks a lot dude for your time. Really appreciate :)

Problem authors please next time google your problem or select testers for it

problem:1479B2

I think there is a typo in editorial, in line before lemma 1, f(i) = max (g(j)) should me min if I am not wrong.

Best contest ever!

You can watch this https://youtu.be/sUFMuqQlL6M if you are stuck in C

I am facing some problems finding why my program is failing for

test case 6inPainting the Array I(Div2 — D1) problem. If anyone could point out what's going wrong, it would be great. Thanks in advance!!Link:- (http://mirror.codeforces.com/contest/1480/submission/106896644)

change this line

return upper1 — occurences[num].begin(); ===> return *upper1

I have another explanation (or solution) for Div1B1/Div2D1. Sorry I'm not very good at English, you can just read my code(106872452).

First, let $$$a^{(0)} = a$$$(all elements in a) and $$$a^{(1)} = []$$$(empty). Let's move some elements from $$$a^{(0)}$$$ to $$$a^{(1)}$$$. If a segment in $$$a^{(0)}$$$ has two or more elements, then we can move one element in this segment to $$$a^{(1)}$$$. After that, $$$\mathit{seg}(a^{(0)})$$$ will not decrease and $$$\mathit{seg}(a^{(1)})$$$ will increase or stay unchanged. For example, If $$$a^{(0)} = [1,1,2,3,4,4]$$$, after such operations, $$$a{(0)}$$$ became $$$[1,2,3,4]$$$ and $$$a^{(1)}$$$ became $$$[1,4]$$$. Let answer = $$$\mathit{seg}(a^{(0)})+\mathit{seg}(a^{(1)})$$$.

But that's not enough. Consider a case $$$a = [1,1,2,3,1,1]$$$. We can construct $$$a^{(0)} = [1,2,3,1], a^{(1)} = [1,1]$$$ using the method above. But we can move $$$2$$$ in $$$a^{(0)}$$$ to $$$a^{(1)}$$$, decreasing $$$\mathit{seg}(a^{(0)})$$$ by $$$1$$$ and increasing $$$\mathit{seg}(a^{(1)})$$$ by $$$2$$$. So we should perform another type of operation. If there exists $$$a_i$$$ between two segments($$$seg_x$$$ and $$$seg_y$$$), and all elements in $$$seg_x$$$ and $$$seg_y$$$ are equal to one value $$$v$$$, and $$$a_i \neq a_{i-1}, a_i \neq a_{i+1}, a_{i-1} \neq a_{i+1}, a_i \neq v$$$, then we should increase answer by $$$1$$$, because we can move $$$a_i$$$ from $$$a^{(0)}$$$ to $$$a^{(1)}$$$.

ExamplesCan you explain it again I didn't get that

I added some examples to explain it.

I used same method but instead of checking this much inequalities,if we have A[i]!=A[i+1] && A[i]!=v&&A[i+1]!=v because if this is true then we can simply break sequence here only. And this condition is enough because only structure of example which don't follow this looks like 1 1 5 1 2 1 2 1 3 1 1, Here we can see no a[i]!=v && a[i+1]!=v simultaneous.(v) is 1 here. In this case answer will increase only by 1 always otherwise always by 2 if we break sequence at i and i+1. For example [1 1] 5 1 2 (4 2) 1 3 [1 1] sequence a can be like 1 5 1 2 4 1and sequence b be like 1 2 1 3 1.

For a testcase like this for problem B, the answer should be "NO" since the hero dies after the 3rd round. However, the solution given in the editorial gives us "YES".

This is confusing. Am I missing something?

The hero can choose the order.

Explain this please

Corner case that is inside the new limits removed..

Problem D2B

This was Test #23 earlier

1

3 10 1

2

16

liouzhou_101 MikeMirzayanov

In the editorial of D, what does "consistent segment tree" mean? Is it persistent segment tree?

in Div2 C how come we sure that when l==r that is minimum?

We are not required to find the global minimum, just a local minimum which is defined as — a[i] < min(a[i-1], a[i+1])

— or equivalently — a[i] < a[i-1] and a[i] < a[i+1].

Notice that before and after every step of binary search the range [l,r] satisfies the condition: — a[l-1] > a[l] and a[r] < a[r+1].

Hence when l==r we obtain a local minimum

Div1 C reminds me of this problem on AtCoder.

In Div2.D1 I submitted this code and got AC. But in fact it's quite different from the tutorial! Can anyone hack it or prove it right? Thanks!

PS: I had run thousands of testcases on my computer with n<=20, and it is always right.

Sorry for my bad English :(

Super short solutions for Div1.B:

B1: https://mirror.codeforces.com/contest/1479/submission/106918887

B2: https://mirror.codeforces.com/contest/1479/submission/106919669

can you explain it please?

I will describe the full solution for B1 that I came up during the contest and simplify it.

Let $$$dp[s][i-1] = (v_{s,i-1}, k)$$$ be the state of current solution when $$$a[i-1]$$$ is added to the sequence $$$s$$$ ($$$s \in \lbrace 0,1 \rbrace$$$), in which $$$v_{s,i}$$$ is the best score ending at $$$i-1$$$ and $$$k$$$ is the index of the last item of the other sequence $$$s' = 1-s$$$ (of course, $$$k < i-1$$$ and $$$k = 0$$$ when $$$s'$$$ is empty as I read the input into an 1-indexed array).

Let's focus on $$$s = 0$$$. When reaching item at index $$$i$$$, we have two options:

1.1 Adding $$$a[i]$$$ to the sequence $$$0$$$: we update $$$dp[0][i] = (v_{0,i-1} + [a[i] \neq a[i-1]], k)$$$

1.2 Adding $$$a[i]$$$ to the sequence $$$1$$$: we update $$$dp[1][i] = (v_{0,i-1} + [a[i] \neq a[k]], i-1)$$$ as now $$$a[i]$$$ is appended to sequence $$$1$$$ that is ending with $$$a[k]$$$ .

Similarly for $$$s = 1$$$, we have two updates:

2.1 $$$dp[1][i] = (v_{1,i-1} + [a[i] \neq a[i-1]], k)$$$

2.2 $$$dp[0][i] = (v_{1,i-1} + [a[i] \neq a[k]], i-1)$$$

So, $$$dp[0][i]$$$ can be updated by one of two ways 1.1 and 2.2. Of course, we choose the one giving the better score, so $$$dp[0][i] = max((v_{0,i-1} + [a[i] \neq a[i-1]], k), (v_{1,i-1} + [a[i] \neq a[k]], i-1))$$$ (1)

In 1.2, there one important point is that there can be many values $$$k$$$ that yield the same best $$$v_{0,i-1}$$$. In this case, $$$a[i] \neq a[k]$$$ is always true as we are always able to chose one $$$k$$$ that $$$a[i] \neq a[k]$$$. The trick I did is, as the input array is 1-indexed, and $$$a[0] = 0$$$, when updating $$$dp[0][i]$$$ by formula (1), if two scores are equal and $$$k \neq i-1$$$, I set $$$k = 0$$$ , so $$$a[i] \neq a[k]$$$ is always true for subsequent steps.

SimplificationThere are two simplifications to make the code shorter:

The idea for B2 is similar.

Thank you!

Can someone explain Div2/ D2 problem?

I solved it the following way. First of all, i merged every contiguous segment of equal elements into one (since every segment of the form $$$[5, 5, 5, 5]$$$ will always belong to either $$$a0$$$ or $$$a1$$$). Then let $$$dp[i]$$$ be the minimum total number of segments up to position $$$i$$$. For each element $$$a[i]$$$, we either append it in the same set of the previous element $$$a[i-1]$$$, so we get $$$dp[i] = dp[i-1] + 1$$$ or we try to append it to the previous occurrence of this value (if there is any), therefore having : $$$dp[i] = dp[lst[a[i]+1] + i -lst[a[i]] - 2$$$ ($$$lst[a[i]]$$$ is the index of the last occurrence of this value in our array), because we need to put all elements between two equal numbers in a different set. Finally, the transition for each $$$i$$$ is:

$$$dp[i] = min( dp[lst[a[i]+1] + i -lst[a[i]] - 2, dp[i-1] + 1)$$$.

Solution code : https://mirror.codeforces.com/contest/1480/submission/106923311.

I hope i made myself clear.

Could someone explain how you get $$$\mathcal{O}((n + q) \log n)$$$ in div 1 D?

The way I see it, with the persistent segment tree solution, for a fixed path, you can check in $$$\mathcal{O}(\log n)$$$ time whether there is a working value in the range $$$[l, r]$$$. Don't you need to binary search for what that value actually is, thus taking $$$\mathcal{O}(\log^2 n)$$$ time?

Additional binary search is not necessary. You can get what the value is through a binary search on segment tree.

The 20th input of test #2 for problem '1480B — The Great Hero' reads:

320995

-540333783399 76765 77638

140538 647490 973129

That is, the hero is dead on arrival since B is negative. Yet the answer for the 20th token is YES. How can the hero start fighting when he is already dead? Shouldn't the answer be NO?

I am sure I fail to grasp something, but it eludes where I am wrong.

You got B = -54033 after you changed its value. Move your check to the beginning of program, or localize B variable.

Thank you for very clean solution codes and pretty understandable tutorials!

Liked problem C. If anyone wants the reason that solution works - http://www.dsalgo.com/2013/02/index.php.html

"O(MO)" — One more alternative approach (or explanation) for Div.2

D1.Step 1. It is obvious that we can remove all excesses of consecutive equal elements from an initial array without influencing the result. The excess is when >2 equal elements come in a row. We then reduce to 2 elements.Now every second element would come to different array except of the pathological pattern (step 2).

Step 2. We search for patterns`/OO(MO)+O/`

. Here M stands for "not`O`

" or for`.`

(i.e. any element) because of reduction by step 1. The middle side`O(MO)+`

gives us one unsqueezable array, and`concat('O','O')`

gives us another which is sqeezable by one (so it reduces an answer by one). Patterns may overlap by 2 elements.Answer is a number of elements in reduced array (after step 1) minus a number of patterns found (in step 2). $$$O(n)$$$

Btw, 22 vertices is sufficient in div1C.

Can someone please check my code and tell me the error in my logic for Div2 D1:/ https://mirror.codeforces.com/contest/1480/submission/107013163

I wrote the following part to get random numbers. (Div.1 D)

It failed to pass test 7.

After debugging for a really long time, I changed it into the following.

Then it got AC but I haven't known why. Can someone please explain the reason that the first one failed but the second one passed? Thanks in advance.

PS: You can have a look at the two submissions here and here.

How do you conclude D in $$$O(n \log n)$$$ time? I did basically what you have described but my final complexity is $$$O(n \log^2 n)$$$ and squeezing it into TL was pretty painful. Each of these values $$$f(1, u, l, r)$$$ that you mention I compute in $$$O(\log n)$$$ but in order to find desired $$$c$$$ I perform binary search on this interval which adds extra log. And tree that you describe is called persistent, not consistent. To be precise, in my tree "time" corresponds to colors, I have a root for every single segment tree corresponding to vertices with colors $$$\le r$$$ and in particular I compute $$$f(1, u, l, r)$$$ as $$$f(1, u, 1, r) \oplus f(1, u, 1, l - 1)$$$

Here's my $$$O(n \log n)$$$ solution:

First notice $$$f(u,v,l,r) = f(1,u,l,r) \oplus f(1,v,l,r) \oplus f(lca(u,v),lca(u,v),l,r)$$$ (note that $$$f(lca(u,v),lca(u,v),l,r)$$$ is simply $$$X_{a_{lca(u,v)}}$$$ if $$$l \leq a_{lca(u,v)} \leq r$$$ and $$$0$$$ otherwise).

Therefore it's enough to maintain a persistent segment tree for each vertex $$$u$$$ which answers queries $$$f(1,u,l,r)$$$, I'll denote its root as $$$ST_u$$$. We can get $$$ST_u$$$ from $$$ST_{parent(u)}$$$ by updating position $$$a_u$$$ with $$$X_{a_u}$$$.

To answer a query for path $$$(u,v)$$$ of mineral resources in $$$[l,r]$$$, we can as usually split this into $$$O(\log n)$$$ ranges $$$[l_1,r_1],\dots,[l_k,r_k]$$$ which correspond to the segment tree nodes. Then notice that a range $$$[l_i,r_i]$$$ will contain the answer iff $$$f(1,u,l_i,r_i) \oplus f(1,v,l_i,r_i) \oplus f(lca(u,v),lca(u,v),l_i,r_i) \neq 0$$$. Therefore, while querying, when we're in some range, we can see whether the current range contains an answer without descending further. Then, to retrieve it, we only need to descend one of these $$$O(\log n)$$$ ranges (any one for which we know it contains the answer), adding $$$O(\log n)$$$ to the complexity (since at each step of the descent we know which subtree will contain the answer), and together it's still $$$O(\log n)$$$ per query. Turns out this is very easy to implement, we can always just check if an answer exists in the left subtree, if it does return it, otherwise try finding it in the right subtree of the current segment tree node. All we need for a query is $$$ST_u$$$, $$$ST_v$$$ and $$$lca(u,v)$$$.

Full code: 107109427

Oh wow, it makes perfect sense, thanks. The difference between your and mine approach is that I created persistent trees in a line by adding colors from left to right and each tree is over space of preorders, but your persistent trees create original tree since you are adding persistent tree for each vertex of a tree and each tree is over space of colors. I didn't think you could pull off tricks like that

In the case 2 of the intuitive proof of the div.2D, how do you guarantee that t1 must be following z when putting z after x according to your greedy strategy? what if next(z) > next(y)?

Thanks a lot for including such a detailed proofs!

Can you please tell me the meaning of this line in B1: Suppose b results in the two subarrays s′xzs′′t′yt′′, while there is indeed another optimal assignment that agrees with our strategy and results in s′xt′′t′yzs′′.

Update:Got it.Managed to solve ProblemD deterministically using (MO's on tree + sqrt decomp) to find first odd beteween l and r. Is not very hard solution 108831828. Is it intended to not pass, since it it $$$(N+M)sqrtN$$$. However I have to admit I quite like more the author's solution since it has high enough probability and is faster, and probability of success could be increased easily.

sorted

With C++ 20, the slower $$$O(q\sqrt{n})$$$ solution for 1D can actually run in <1 seconds which is quite faster than most implementations of the $$$O(n\log{n})$$$ intended solution.

About the editorial for 1479E — School Clubs, what is an event, and what is does ϕ(At+1)−ϕ(At)∣A0,A1,…,A mean?

Can anyone give a counter test for this submission of Div-2 D1

https://mirror.codeforces.com/contest/1480/submission/227039682