Hello Codeforces!

On Mar/09/2020 17:35 (Moscow time) Educational Codeforces Round 83 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be **rated for the participants with rating lower than 2100**. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given **7 problems** and **2 hours** to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|

1 | mhq | 7 | 135 |

2 | MiracleFaFa | 7 | 145 |

3 | neal | 7 | 161 |

4 | uwi | 7 | 191 |

5 | CWOI | 7 | 196 |

Congratulations to the best hackers:

Rank | Competitor | Hack Count |
---|---|---|

1 | MarcosK | 134:-15 |

2 | _apurv_ | 28 |

3 | racsosabe | 24:-1 |

4 | sv_restart | 18:-3 |

5 | Norrius | 16 |

And finally people who were the first to solve each problem:

Problem | Competitor | Penalty |
---|---|---|

A | hochesh | 0:00 |

B | Kirill22 | 0:02 |

C | i.e | 0:03 |

D | neal | 0:08 |

E | andrew | 0:09 |

F | MiracleFaFa | 0:33 |

G | gisp_zjz | 0:31 |

**UPD:** Editorial is out

Good luck everyone!

Wow that helped!

Why do people feel the need to be snark over benign well-wishes?

Well, he's DankCommenter.

What does "Unexpected verdict" means in hack verdict?

thanku i got d this tym. :)

7 problems in 2 hours! sounds like high rating :3

You think 7 problems in 2 hours is a lot? It is not a lot compared to that

But in this contest there were 3 bilateral questions (B1 and B2), (C1 and C2), (D1 and D2).

That is true, but after this contest everyone complained about too much subtasks. It doesn't make sense for 3 problems to have subtasks in 1 contest! Codeforces is not

OIstyle. It is supposed to beCPCstyle! You might need to check this and thisthanks for the information :(thanks a lot..awoo

Wasn't this contest supposed to be like 3 weeks ago?

I remember registering to an Educational Round and it dissapeard, and I really wondered why.

Yes,it is.And I guess there is a problem of test data found by careful questioners.

I hope this contest will help me forget the past few contests and get over them. The setters look good for this one, although a few names are somewhat a matter of concern.

Seems more like a Speed Test.. XD

We want short description.So please.......

thanks for so many upvotes :)

.

Hope to get blue today!

Hi, just wanted to know when will the scoring distribution be put up?

"It will be held on extended ICPC rules"

Thanks.

What's the imaginary scoring distribution

Each problem is worth [10000 — # of minutes to solve] points.

ME: After 1 successful submission. Let's see friends standing :)

speedforces

I really need to code more because I got the idea of C in one min but it took me more than an hour to code it correctly it's my fault

why C is giving right answer on my ide and WA on codeforces ide for test case 1??please tell

Because of precision error. Output can sometimes be 4.99999999999 while its actually 5. So just ciel if the difference is less than an epsilon value like 1e-9, else just floor.

thanks but it's late...no problem next time

Well you weren't going to get a response during the contest anyways. Would be considered cheating I guess.

no but it's not accepted...btw and I didn't copy the logic...and I during the contest I thought...the leading team will be answing..not the contestants

I faced the same issue. Thanks for the info, ll take care of it next time. A doubt though, why are the other online ides giving the correct answer?

I'm not sure tbh but I'd guess it depends on the compiler or PC architecture or maybe even just luck.

Just be careful when using doubles and always use the difference instead to checking equality directly or try to avoid using them whenever possible.

Imagine being able to solve problems yourself ;) http://www.usaco.org/index.php?page=viewproblem2&cpid=648 (Problem E)

this round educated me on how to organize my folders better... I spent so long looking for my 262144 code ((

In that problem, the move is the same, but the goal is to maximize the max element. Is it necessarily true that the resulting array is also the shortest possible array?

The goal of both the problems seems bit different. In today's question, they asked to minimise the length of array, whereas in the link they have asked to maximise the largest remaining element. Am I missing something?

No you are not missing something, but the dp in both problems is exactly the same if you read the solution except this problem requires one more (obvious) step.

[Deleted]

How to solve E?

bruh read comment above smh http://www.usaco.org/current/data/sol_262144_platinum_open16.html

I know it's some stuff about Sprague–Grundy theorem, but I still can't solve it.

I think you are thinking of F...

Oh, you're right, E is the last second problem in most Div2...

How to solve D problem?

Let's construct the answer step by step. Consider a sorted array of length $$$n - 1$$$ for a moment, which contains no repetitions and whose elements range from $$$1$$$ to $$$m$$$.

There are $$${m}\choose{n - 1}$$$ different arrays with this property (since there are no repetitions, one choice of $$$n - 1$$$ numbers from $$$m$$$ available corresponds to exactly one ordering of them).

Now we can pick the maximum and throw some elements from the array to its right (in decreasing order), others remaining to its left. There is a total of $$$2^{n - 2}$$$ subsets of numbers that we can position to the right of our maximum, each subset corresponding to exactly one ordering (length $$$n - 1$$$, and we're not considering the maximum itself).

Finally, we pick one of the numbers (but not the maximum) and add its duplicate to our array. There are $$$n - 2$$$ different choices for this. Also we must consider that we don't care whether the chosen element is on the right or on the left, since its copy will appear on another side, and we cannot distinguish between them. So, we need to divide the final answer by $$$2$$$.

Thus, the answer is $$${m}\choose{n - 1}$$$$$$ \cdot 2^{n - 3} \cdot (n - 2)$$$.

Didn't understand why you divided the answer by 2 at the very end. For example, 1 2 5 4 3, we can have 1 as duplicate and get 1 2 5 4 3 1 and do the same for every n-2 number (1,2,3,4). So why divide by 2?

"There is a total of $$$2^{n−2}$$$ subsets of numbers that we can position to the right of our maximum".

If you choose $$$1$$$ as the duplicate, you'll get the same resulting array if you move $$${1, 3, 4}$$$ to the right and if you move $$${3, 4}$$$ to the right in step 2 — either way there will be a $$$1$$$ on both sides.

Another way of seeing this is, the repeating element has to be on both the sides of the peak element. For each of the non repeating element, you have 2 choices, either the left side or the right side. Therefore, (n-3) elements having 2 options each giving 2^(n-3) ways in total.

This is equivalent to chosing a subset of elements placed on a given side

Thanks for an excellent explanation. Understanding this made me realize that there's another way to think about it (minor differences) :

Nice explanation, Thanks!

can you tell why are we taking n — 1 elements from m and not n elements`

`

The reason for n-1 instead of n is that one of these will eventually be duplicated, resulting in a total of n (explained above by @sh_maestro).

How to calculate it without overflowing long long? I can take the modulo when I multiply but it can make the result incorrect when I divide.

The correct way to do division is using modular inverse.

You can exclude the duplicate element from the set along with the maximum, so that you consider a set of $$$n-3$$$ elements. Then you don't need to divide by 2 afterwards.

Helped alot!! Thanks.

Very nicely explained went straight into my head thanks for it!!

I have found the formula $$$C_{m}^{n-1} (n-2) 2^{n-3}$$$.

What was test case 4 of problem C??

What was it really?

Its something like

2 4

21 16

Is D is formula based ?? if yes!! then what's the formula

Yes! The answer is: $$$ m\choose (n-1)$$$$$$ * (n-2) * 2^{(n-3)} $$$

We choose $$$ ( n - 1 ) $$$ values from $$$1$$$ to $$$m$$$. Except the max value, each value can be chosen to duplicate ( in $$$(n-2)$$$ ways ). The remaining $$$(n-3)$$$ values ( except the max and duplicate value ) can be split into two ways, either on the left or right of the max value ( $$$2^{(n-3)}$$$ ways ).

can you explain why 2^(n-3)?

Each element is given 2 options, either to be on the left or right of the max value. For example, if there is 1 element. It can either be L or R of the max value. If there are 2 elements, there are 4( $$$2^2$$$ ) ways: LL, LR, RR, RL. Similarly for $$$n-3$$$ elements, there are $$$2^{n-3}$$$ ways.

Can somebody tell me if a[l]~a[r] can be merged to one element.Whether this element is fixed?

Yes, this element seems to be fixed. Proof : define a quantity for your array S = sum of all 2^(a[i]) where a[i] is an array element Then notice, that in one operation, two nearby elements each with value x contributing 2^x each to the sum disappear and leave x+1 in their place which contributes 2^(x+1) as 2^x + 2^x = 2^(x+1) therefore this quantity which we defined, S never changes hence if a[l] to a[r] is merged into a single element, it is uniquely determined.

Solved problem E in $$$O(n^3 \cdot \text{MaxValue}/64)$$$ with bitsets. submission

Whether AMAX matters a lot?? I pass the pretests in O(n^3) .

Just dp...

F, What's the tail-period-length of $$$(x,y,z)$$$? or just prep a $$$5^3$$$ offline memo?

If you bruteforce period, you will see that it never exceeds 10. So you can precalculate all answers for all $$$(x, y, z)$$$ for numbers up to LCM(2, ..., 10) = 2520, and with this you can easily answer queries.

I know it never exceed 10. I wanna know is there a relation $$$f(x,y,z)$$$... but wow, prep a long array is great.

since I just got a naive idea, prep a length about 100, then for >100, use period-length to fit in (50..100).

I found G much easier than E and F

I arrived at G's solution within 5 minutes after reading the question, whereas I spent 40+ minutes on F during and I'm still totally clueless.

At last, I found one of my sons. I hope I also find my right child soon.

For me E is much easier than D, F or G... I stuck at D for 50mins, but I solved E in just 10mins.

Can you give me some hints on G?

Problem F sentence was SUPER. HARD. TROLLING.

"previous" and "no matter when" at the same sentence.. So It can be translated many ways.

I spend more than 1 hours at this problem...T^T

me, too. thought can used only once.

same thing hold me for 20 minutes

http://www.usaco.org/index.php?page=viewproblem2&cpid=648

why following logic is not working for question D??

I guess, you're forgetting the 2^(n-3), you should multiply the answer obtained above with 2^(n-3). Have a look at the following submission.

it worked ,but why we considered 2^(n-3) ,shouldn't it be 2^(n-2);

as we arranging n-2 d/f types of elements??

Look at lollihunter's comment above and the two comments below it. https://codeforces.com/blog/entry/74572?#comment-587286

Bro, how to find Combination Fast, formula is working for smaller values ,but when input is large ,it takes very long time to get answer, and hence TLE??

https://cp-algorithms.com/combinatorics/binomial-coefficients.html

Can someone explain solution of E in detail. Thanks in advance.

Dp Solition:

for every subarray check if it possible to convert it into single integer value denote this as val(arr[i : j ]) => integer for any i , j pair 0 <= i <= j < n

for every subarray [i, j]

iterate over i<= z < j such that:

What Test case 4 of C problem....?? question seemed easy but still was not able to pass it :-(

yes same problem

No Screencast? tmwilliamlin168

I accidentally turned on my facecam when I recorded my screencast, and I'm not sure if I want to make it public :/

I still made explanations, for those who are interested: https://www.youtube.com/watch?v=ytOManO7GO0

Thank you..!

I would love to see screencast of your face, even without sound and code ^_^

Hii Can anyone plsss check this submission. He obfuscated all the codes. Is this Cheating https://codeforces.com/contest/1312/submission/72814153

No it shouldn't be...

What language is this???

Thank you for making this explanation video! It is nice to learn from a high ranked coder like you by tracing your thought process. Subscribed to your youtube channel :)

Why there is an "Unexpected verdict" when I try to hack solution of C?

How to solve F? I recalled Grundy Number technique, but the range is too large to use Grundy Number. Thus I tried to find the period, but I cannot find any period.

I think the period is quite obvious once you print them out. https://i.imgur.com/NsO0kXP.jpg

Wow! Thanks for sharing your idea

For Div2 E, I tried a greedy solution using stack, going left to right, and it failed.

Can someone help me how to prove it wrong ?

7 7 5 5 6 8

Going left to right gives, 8 7 8 Optimal Strategy gives, 7 9

Try 1 1 1 2

Greedy wont work. If processing left to right -> 5 3 3 3 4 -> 5 4 3 4. Whereas, you could have, -> 5 3 4 4 -> 5 3 5

Same problem if you process right to left. Just invert the array.

SpeedForces.

Why this wont work for D:

nCr(m-i,n-2)*(n-2) for i>=1

Fix 2 ends with a number i, so we have to fill n-2 places with numbers from i+1 to m (ie nCr(m-i,n-2)) , and we can have n-2 positions for the biggest number so multiply by n-2

This assumes that the repeat number is necessarily the smallest number, which is not necessarily the case.

You know what's wrong with this approach — We fix the value $$$v$$$ and position $$$p$$$ of the peak value. Numbers on left of peak are $$$p-1$$$ and on right are $$$n-p$$$. Now we have to choose total of $$$n-2$$$ values less than $$$v$$$ to place on non-peak position. Let

. Then

.

It's fine — You missed a multiplying factor $$$x$$$ because you can choose any of them on the bigger side. 72880191

i did the same

Missed E by 2 minutes

Can D be solved with DP, if yes please share dp states

If it can, then I think it will be only as a by-product of the closed form solution.

I hate the fact that in educational codeforces we dont get the editorial before the next day.

Hii Can anyone plsss check this submission. He obfuscated all the codes. Is this Cheating https://codeforces.com/contest/1312/submission/72814153

Bad girl doing bad things.

I think there is something wrong with checker of problem C. I tried to hack one submission that should give WA and I got "unexpected verdict" (id of hack is 621220).

Oh, it seems the problem with the checker is when n=1. I tried to hack with n=2 and got successful hacking attempt. Please, fix that :)

What is the hack?

How to get 3 for the 4th string in the first testcase (problem G)? It looks impossible to me.

Apparently, to get 3 you need to type 'i', 'q' and then use autocompletion

Thank you!

In problem F, how to find upper bound on precalculation ?

What I did is calculate 3 grundy values for 3 different attacks for a particular castle. Since x,y,z <= 5 , we need atleast 5 states to repeat.

First value can be from 0 to 3 and 2nd,3rd value can be from 0 to 2. So I thought (4*3*3)^5 is an upper_bound which is not the case.

Brute force shows that the upper bound for the period and pre-period is at most $$$36$$$, but proving it can be really painful.

Well, one can prove some reasonable bounds like $$$10^5$$$ intuitively.

More reasonable bound should be around 10^4, given t <= 1000 and time 3s. Unless and until there is some magic :D

There is some magic.

Originally, when I was preparing this problem, I decided to set $$$x, y, z \le 3$$$ so it would be clear that there are not so many states — the most generous upper bound is $$$4^9$$$ in this case.

Then my colleagues told me that it could be possible to analyze all cases of $$$x, y, z$$$ since there were only $$$27$$$ of them, and most of them were symmetric to some other cases or trivial. I didn't want such solutions, so I've decided to check how far I could push the bounds.

At some point, the bounds were $$$x, y, z \le 20$$$, leading to really large upper bounds, but surprisingly small periods when checked by brute force (if I remember correctly, even on such large constraints the longest period with pre-period was less than $$$500$$$). But these constraints were (intuitively) very unreasonable, so I've decided to drop them to $$$5$$$.

I think that it's possible to prove that the period is something like $$$O(\max^2(x, y, z))$$$, but it surely will be a lot of work :)

Yes, good to keep it lower otherwise I would rather think about the different solution.

Nonetheless it was a good problem.

https://codeforces.com/contest/1312/challenge/72826639 Hack my solution... I assumed no of steps are <=35 :((

Happens bro :(

What is Unexpected verdict in Hacks?

(probably) checker failed while judging

Thank you!

Problem E, My greedy solution got WA on TC38 :( Can anyone help? Is the WA due to some corner case? Link

Seems like checker for problem C not works. I got "Unexpected verdict" while hack others.

WHY WHEN I HACK PROBLEM C I SEE "UNKNOWN VERDICT"?

yes same here

the verdict says illegal contest id

because maybe the checker itself fails for that test case like some sort of TLE or RE.

Try to hack it for multiple number of test cases(more than 1)

E can probably be solved in n^2 — 72819557

explanation: let $$$dp[i]$$$ be number of answer for subarray $$$i..n$$$. If $$$i..j$$$ can be combined to get a single value we can write $$$dp[i] = min(dp[i],1+dp[j+1])$$$, to check if $$$i..j$$$ can be combined to get a single value, we can greedily merge from left to right, means if we get two adjacent equal values (If multiple such take leftmost) , we can erase them both and write a single value in their place. I have implemented this using stack

Could you please explain your solution

I have added explanation to my comment

Do you know the proof for why if segment $$$i...j$$$ can be merged into one element, the order of operation won't matter and we will always get the same one element?

No, I don't know the proof

Every element x was there at the beginning, or it was merged by two x-1. Independend of any other elements.

Since the merge of two x-2 to one x-1 was

beforethe merge of the two x-1 to x, there is only one possible tree-like path of merge ordering.I've used the same approach (left-to-right greedy with stack merge of [L, R] into segment of length 1), though didn't bother optimizing from $$$N^3$$$ to $$$N^2$$$ 72829878

Since we always transform adjacent, $$$a, a$$$ into $$$a+1$$$, the $$$Sum(2^{a_i})$$$ is an invariant, so if $$$a_L, a_{L+1}, ... , a_{R}$$$ could be merged into some value $$$U$$$, then $$$U = log_2 (2^{a_L} + 2^{a_L+1} + ... + 2^{a_R}) $$$

(if I correctly understood Your question...)

Again, I'm not sure that I understood Your question, but I think it does: we can merge [1,1,1,1] into [3] ([1,1,1,1] -> [2,1,1] -> [2,2] -> [3]), but if we were to merge second and third 1, we would get [1,2,1] and no further merges are possible (but left-to-right greedy seems to work...)

Hii Can anyone plsss check this submission. He obfuscated all the codes. Is this Cheating https://codeforces.com/contest/1312/submission/72814153

Writing your variable names in Russian doesn't make it obfuscation.

No Its not Russian.

YPFARROLCS obviously means sexy llama in Russian

For each and everything defining it and making it not understandable is itself obfuscating. His accounts are aldready banned previously. Do check once His accounts are buihoatpt2k3provip buihoatpt2k3

Umm that doesn't look like russian ? lol. Even if it is.. why tf would you replace a

+sign with`ECFEFMHJACSV`

lmaoYes . For each and everything. Previously his 2 accounts are banned

This contest was weird. G was trivial tree DP with segment trees and hashing whereas A was way too hard for a div2A.

One of the author's solution for the problem C had stupid bug so there are many hacks with unexpected verdict. Now everything is fixed and you can hack this problem. The round most probably will be rated because the initial test set didn't contain the tests that cause the bug. We are deeply sorry for this issue.

Hii Can you plsss check this submission. He obfuscated all the codes. Is this Cheating https://codeforces.com/contest/1312/submission/72814153

Greedy + Divide and conquer solution for E :

The greedy observation is that, minimum value in the array must be combined if possible.

Now consider a subarray having equal minimum elements.

Case 1 : It's length is even, then combine each pair is optimal

Case 2 : It's length is odd, then you should combine first few even elements, left one element which will break array into two, combine last remaining even elements.

Now call solve function for these 2 partitioned array, Do this for each possible breaking element at odd positions in subarray.

During contest, for Case 2, I called solve for the whole array again instead of 2 partitioned array. Which I hacked after the contest.

Update : Sorry, but this solution is also hacked by me.

I was thinking along these lines but couldn't complete it. The obstacle for me was in case 2 when you have exactly three identical elements, say 1 1 1. In that case you should combine either the left two 1's, or the right two 1's: for instance with

$$$A = [1,1,1,2]$$$, it is optimal to combine the right two: 1 (1 1) 2 $$$\rightarrow$$$ 1 2 2, but:

$$$A= [3,2,1,1,1,2]$$$, it is optimal to combine the left two: 3 2 (1 1) 1 2 $$$\rightarrow$$$ 3 2 2 1 2

In general it seems hard to decide whether the left or right is better. Maybe you should count how long the consecutive "boundary" sequence 1,2,3,... is on both sides; like in the last example it extends till 3 on the left side but only till 2 on the right, so we chose left. But deciding this seems hard in general, since you can also have a sequence like 1,2,(2,2),4,5,6,(chain of 64 2s),8, which is equivalent to 1,2,...,8. (then I gave up)

Isn't the case 2 makes it exponential ? What is the time complexity then ?

Yes it is. Initially it passed at around 30ms so I thought there must be some magic, but when I calculated time complexity I got exponential so I hacked it.

Can anybody suggest similar equation-finding problems as D.

I think you can find similar problems in many Permutation and Combinations books of high school.

Why the test cases for C problem were so bad? Is it necessary for problem creators to add weak test cases so that participants will try to hack others?

Hack my C if you're cool

Done :P

Is "hack me" used in place of "bite me" in the local slang?

On E Will time n^3 hack?

can explain me problem g sample one? how build a 10th string with 3 operation? i think i dont understand problem.

Why are so many solutions for C failing?

WEAKtestcases. Really weak in my opinion.That's true.I forgot an important situation and it still pass the test.

Same here !!

Yes I also made a silly mistake.

I've hacked you. sorry

Can anyone hack this brute force solution of mine and get TLE? https://codeforces.com/contest/1312/challenge/72834695

How to solve problem E ?

Can sb hack my C?

your code seems correct for now

thx homie

How to solve problem D ?

Since one element has to be repeated, choose any (n-1) numbers from 1 to m to fill the array. This can be done in $$$\binom{m}{n-1}$$$ ways.

Out of these n-1 numbers, one has to be repeated. Since we need a peak element, it cannot be repeated leaving us with n-2 numbers. Hence we can choose the repeating element in $$$\binom{n-2}{1}$$$ ways.

We are left with (n-2) elements to be arranged on both the sides of the peak. Notice that we require strictly increasing and decreasing sequences on the left and right of the peak element, therefore the repeating element will never be on the same side. For the remaining (n-3) non repeating elements, every element has 2 options : to go either on the left or on the right of the peak. Therefore, number of ways of doing this is $$$2^{n-3}$$$.

Final answer : $$$\binom{m}{n-1}$$$ x $$$\binom{n-2}{1}$$$ x $$$2^{n-3}$$$

Hello Sir, I would like to bring your notice to the fact that some people are using multiple accounts for participating in contests and they hack their own solution to get points.

For Instance: https://codeforces.com/profile/rajankur this user has another account with URL as follows: https://codeforces.com/profile/CryBaby This is his secondary account and he used his primary account to hack his own solution which he submitted from his secondary account.

Hacked Solution- https://codeforces.com/contest/1312/submission/72825800 Same solution from different account- https://codeforces.com/contest/1312/submission/72845580

Just wanted to inform you about all these things going on and I hope that serious actions will be taken against such people (cheats).

Thank You

Indian people suck, especially you, fuc you

Can anyone hack my C ?

How to solve problem D? Explain please

has been answered previously..

there should be marks for successfully Hacking.

I wonder if there is any official editorial or somrthing

Usually it becomes available just after hacking phase, when the contest is finished.

How to solve C with Bitmask ?? Can anyone help?

Instead of keeping the count for the ith index, just set it to 1. such that pow(k ,i) is needed

if any ith index is required and in bitmask if it is already set to 1, in that case you can't use it again simple print("NO"), return

after iterating all over the index in array

print("YES") , if not return

Why it is showing participants with rating more than 2100 in the official standing?

Select [Division 2] in top right

Then also it is showing participants with rating mare than 2100 in division 1 official standing.

It was official contest for everyone but rated for only division 2.

What's wrong with my solution to C, i get runtime error?

please write the link of your solution in your comment.

just erase break in line 43 and you will get accepted.

after using break at that line, last of your current input used for next query and sometime result will be run time error.

Sorry i should've done that, and thanks for the help that was really dump

When will the editorials be released?

Please somebody tell the editorial releaser to do his job!

awoo when are the editorial gonna be published?

My solution for E: I did not have enough time to implement complete solution during the contest because I realized it after good amount of time.

So here it goes,finally minimum reduced sequence will have each element constituting some contiguous ranges of number. So for all ranges we need to figure out if that range could be reduced to a single number.Now here is a tricky part, if the range can be reduced to a single number?If we can do so, then frequency of all contiguous equal elements in the range must be a power of 2 or so, because it cannot be odd at any step of reduction or something like that.But the key point is, now we can greedily pick the elements and merge them using a stack, ie, push element to stack, merge top 2 elements of stack till you can and so on.So for each range check if the range becomes stack reducible and using a 1d dp, we can implement the rest of simpler part.

Edit : Time Complexity = O(N^2)

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).TNX!

An off-topic question — can I undo an upvote made by mistake?

Actually, both accounts are mines. For some problem, I submit that from my both account. I am really sorry and I ensure that this type situation will not be repeated.

great round!!!! short statements and very combinatorics I wish every round were like this

When will the questions of the competition be put into the question bank?

I would like to share another problem E's solution solving in $$$O(n^2)$$$.

Submission: 72874158

Without loss of generality, I assumed all numbers are combined to the

right.I changed

`dp[L][R]={can combine?, val}`

into three arrays, all of the indexs below are 0-based.`ans[i]`

: minimum length from $$$0 \text{~} i$$$`dp[i][k]`

: the minimum length if the $$$i$$$'th element was combined to $$$a[i]+k$$$, 0 represents it's unachievable`came[i][k]`

: if the $$$i$$$'th element was combined to $$$a[i]+k$$$,`came[i][k]`

equals to the left boundary of this combination( aka.Lin`dp[L][R]`

andRrepresents $$$i$$$)If the array is [7, 5, 4, 4, 6].

`came[3][1]=1, dp[3][1]=3`

`came[3][2]=0, dp[3][2]=2, ans[2]=2`

`came[4][1]=came[3][2]=1, dp[4][1]=2`

`came[4][2]=came[3][2]-1=0, dp[4][2]=1, ans[4]=1`

So the answer is ans[4]=1.

why all winners are div1 participants??