I believe I have an $$$O(n \log n)$$$ solution to 1312E - Array Shrinking. Here's the code: 72938462
The main idea is to find all segments of the array that can be reduced to a single number. We do that via this DP:
reduce(start, x) = the end of the range starting at start that can be reduced to the single value x, or -1 if no such range exists. You can then solve this DP with the recurrence reduce(start, x + 1) = reduce(reduce(start, x), x).
The key claim is that there can be at most $$$n \log n$$$ such segments, no matter what the $$$a_i$$$ are. In fact, the maximum possible number of such segments seems to be exactly the number of segments when all of the $$$a_i$$$ are equal. This version of the code adds an assertion to test this claim: 72938781. It passes every small random test case I've given it.
Unfortunately I don't have a proof of this claim yet, but it feels like there should be a nice proof. Can anyone come up with something? One approach could be to prove a slightly stronger claim, that there are at most $$$n \log n$$$ segments where $$$\displaystyle \sum{2^{a_i}}$$$ is a power of two.
This problem looks similar to problem WEAPONS from SnackDown 2017 Onsite Finals. Its editorial indeed proves that the number of reducible segments is $$$O(n \log n)$$$.
Have a good day my idol <3
Why I get so many downvotes, I just want to wish him a good day ;-;
I have insprirational feeling when seeing GrandMaster Rating Graph. And I want to be a good coder one day like those the guys (maybe Master is enough). So cant I call him or any GM else as my idol ? My definition for idol is just like that, I dont mean anything. Sorry if I mind you guys T_T
Dude can you stop commenting so much? No one gives a fuck about your feelings
Do not make an idol for yourself, whether in the shape of anything in the heavens above or on the earth below or in the waters under the earth.
Oh I am so sorry, I think the better word I should say is something like
Admire someone. I dont good at English but now I thinkidolis not what I should say, sorry.Is
idolmeaning something bad ? If it is I dont really want to say so. I just admire him and thinking about those the people who are high-ranker must have been worked so hard, so I sayWish a good day.How can I say it, like
proudand want to slowly improve myself to get closer to the one who are better than me a far distance, likefeel admireand have motivation not giving up on the Competitive Programming way <3What should I better say for the same meaning. Thank you.
Sorry everyone, it is my fault for bad English knowledge. Have great days coders <3
Smh, your english is fine. Don't have an idol, work hard to be good yourself so you don't have to look up to someone else.
The argument in that editorial can be slightly modified to verify the conjecture that the maximum number of reducible segments is achieved when all of the $$$ a_i $$$ are equal.
Let $$$ h(n) $$$ denote the number of reducible segments in an array of length $$$ n $$$ with all $$$ a_i $$$ equal to one another and let $$$ f(n) $$$ denote the maximum possible number of reducible segments in an array of length $$$ n $$$. Then, the block compression argument from the linked editorial shows that for $$$ n > 0 $$$,
where $$$ h(k) $$$ is the number of (removed) internal good intervals in a to-be-compressed block of length $$$k$$$, and $$$ h(\lfloor \frac{k}{2} \rfloor) $$$ is the number of (added) internal good intervals in the now-compressed block. Using the fact that $$$ h(n) - h(n-1) = 1 + \lfloor \log_2 n \rfloor $$$ is a nondecreasing sequence, it follows that for $$$ k \leq n $$$,
Substituting this into the inequality for $$$ f $$$ above allows one to easily prove by induction that $$$ f(n) \leq h(n) $$$, which is to say that no array has more reducible segments than one of the same size with all $$$ a_i $$$ equal to one another.
Maybe this is what ur looking for?
I saw this link in the comments for the round. That's a slightly different problem, so the $$$O(n \log n)$$$ solutions from there don't apply to this one.
The $$$a_i$$$ in that problem are only up to 40, so the first solution uses the assumption that the eventual numbers won't exceed $$$40 + \log n$$$ (they use a constant of 70). In this problem, the $$$a_i$$$ can be bigger than $$$n$$$, so that idea doesn't apply. For any single start point you can have way more than $$$\log n$$$ possible segments:
1 1 2 3 4 5 6 ...The other difference with the USACO problem is the goal is to maximize the single largest number at the end. This leads to the greedy idea described in the second solution in your link, but that idea doesn't apply when trying to minimize the length.
Gennady's link above is correct. I suspect there's another proof using the $$$\displaystyle \sum{2^{a_i}}$$$ idea.
Can anyone share the code of Fusing Weapons which tourist have mentioned.Thanks in Advance!
https://www.codechef.com/status/WEAPONS?sort_by=All&sorting_order=asc&language=All&status=15&handle=&Submit=GO