True. These rounds and div3 rounds take a lot of time. maybe because of hacking phase.

Me after solving ABCD:

I'm not aware of this: I don't see this contest taken into account on rating because it's not yet processed?

Yes, it's unbelievable.

Yeah,12 at night

Uchiha Madara, you have to be LGM

me too but the rating update is a bit slow

sure

hahah

A was greedy, B was a math problem, C use binary search. 1 out of the first 3 problems of a div 2 round being math problems doesn't imply that a contest is "Mathforces" dumbass. Also, atleast don't be green and talk shit about a contest not having enough DSA problems.

Considering your past rating you shouldn't have had any trouble doing A, B, or C... idk man skill issue

Think about binary search approach

Huh? I have 0 corner cases.

(now someone will definitely hack me xd)

190436527 No corner cases whatsoever.

It can be easily solved via hashes. Great example 190367922

My solution is to count number of 1-s in array and print n — (count_1 / 2).

Only double 1-s pair in the array can decrease operation times, so all you need to do is just count the pair's amount.

You can kill monsters of health 1 in pairs and remaining you can kill individually.

Counterexample:

8
2 3 1 7 8 4 5 6

Output should be 2. Pick (2, 7), then pick (1, 8). Your code seems to output 3.

If $$$a = 0$$$, output $$$min(1, a + b + c + d)$$$.

Else the answer is $$$a + min(b, c) * 2 + min(a + 1, b + c + d - min(b, c) * 2)$$$

How is DP being involved? Do you store the answers so that you do not insert a permutation again?

If you are talking about D, straightforward polynomial hashing (without the mod) would do.

If you use map with vector it also works

Think in terms of binary search. Can we solve the problem with $$$i$$$ operations? Now think what should the last operation be? What should the second to last operation be, and so on so forth ...

My reasoning was that if we select some elements, we will always select 1, n, 2, n-1, etc... The order we select them should not matter because some optimal ordering should exist anyways. So I created a queue and popped off elements while it was sorted. Then, whenever it was unsorted, I removed elements i and n-1-i from the array and continued to pop while it was sorted. The number of times you remove i and n-1-i is the answer.

Submission: 190357765

You can see that you can not use operation on numbers that are close to each other and ordered for example 4,5,6. 4,5,7 and 6,5,4 will not go. So if array is like this 4,8,7,5,3,2,1,6 you can do operation on every other number except these 3 numbers = 4,5,6, and answer will be max(min(numbers)-1, n-max(numbers)) = max(4-1, 8-6) = 3.

Just do n/2,n/2+1;n/2-1,n/2+2;... if n%2==0 or do n/2,n/2+2;... if n%2==1 and skip the first operations if they are already in place.

You have to find the longest MIDDLE subarray.

5
1 2 5 3 4

The longest you can find is 2 3 4.

Yes, 2 pointers is fine my submission.

Stored all aj in a trie and searched for aj^-1, didn't realize the solution during contest. :(

D: Sort the permutations and For every prefix of every permutation, binary search permutations that match this prefix and use segment tree to update range (l <= i <= r) a[i] = max(a[i], x). 190359788

two pointers

Don't know for sure that this is the intended solution.

First, find all the divisors by brute force as the maximum number of divisors for (large) n cannot exceed cube root n. And for every divisor x below 1e9, remove the divisors of x until x*1e9 iteratively and update the answer.

Generate all divisors of $$$m$$$ (there's about $$$10^5$$$ of them in the worst case). For every divisor, instead of the minimum row where it appears, let's search for the maximum column (it's easy to see that these two are equivalent). So, for every divisor, we need to find its maximum divisor which is not greater than $$$n$$$.

This can be done with the following dynamic: $$$dp[d]$$$ is maximum divisor of $$$d$$$ not exceeding $$$n$$$. If $$$d \le n$$$, then $$$dp[d] = d$$$, otherwise iterate on the prime divisor $$$p$$$ in the factorization of $$$d$$$ and find the maximum of $$$dp[d/p]$$$.

Why binary search tho? You can just DFS down the trie, and the answer would simply be where the DFS end.

The problem F of last contest also be passed by some O(n^2) solutions.

Unfortunately, looks like really fast templates for modular arithmetics do the trick. I haven't come up with the D&C+FFT solution, the model one has slower asymptotics than D&C+FFT. So, basically, I could try one of the following two things:

• let only solutions with very optimized FFT and modular arithmetics pass;
• let solutions with more "normal" implementations of FFT and modular arithmetics pass, but risk that someone with a very strong modular template will squeeze $$$O(n^2)$$$ in

I still think that 2nd is better choice. Maybe my mistake was even trying to distinguish $$$O(n^2)$$$ and $$$O(n \sqrt{n \log n})$$$. I am sorry for that, but I hope not a lot of participants were affected by the issue.

In fact we can directly get a formula using lagrange inversion. the final result (plus 2) is the $$$x^{n-1}$$$ coefficient of $$$2(n-1)!(\frac{x}{2x+1-e^x})^n$$$

I concatenated values in array and stored them in hashmap, but I did it because golang doesn't support custom key types in hashmap.

Yup! I did.

your answer would have been fine if r_j = p_qj