Wow that helped!

What does "Unexpected verdict" means in hack verdict?

thanku i got d this tym. :)

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

thanks for the information :(

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

"It will be held on extended ICPC rules"

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

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.

ll getLog(ll v) {
    double z = log2(v)/log2(k);
    ll a = (ll)z;
    if(fabs(z-(a+1)) < 1e-9)
        return a+1;
    return a;
}

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?

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.

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)$$$.

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

What was it really?

Its something like

2 4

21 16

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 ).

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.

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

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 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.

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?

me, too. thought can used only once.

same thing hold me for 20 minutes

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.

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:

if( val(arr[i : z]) ==   val(arr[z+1 : j])):

    val(arr[i : j ] ) =  val(arr[i : z ] ) + 1

yes same problem

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

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

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.

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

i did the same

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

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

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 :)

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

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.

Happens bro :(

(probably) checker failed while judging

yes same here

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)

Could you please explain your solution

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?

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

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 ?

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

Done :P

WEAK testcases. Really weak in my opinion.