Why do you have so many down votes? QwQ

it's the same words as the first one who got 14 up votes...

whats up with the down votes

In the C++ substring function, the arguments are (start index, length), not (start index, end index). Since we trim a prefix and a suffix of length L from the string, the length should in fact be size — 2 * L.

I get the conclusion in the tutorial by Hall Theorem during the contest.

This is my understanding: To check whether answer is $$$x$$$, we consider the largest $$$n-x$$$ number, and link edges to the bombs on it right, so we need to check whether there is a perfect match. According to Hall Theorem, every subset of these number $$$A$$$, and it links bombs set $$$B$$$, $$$|A| \le |B|$$$. Actually, we do not need to check all the subset, we only need to check all the suffixs, and this is the conclusion in the tutorial. And you can see, if all the suffixs satisfy this condition, all the subset also satisfy it.

I divided question into two parts

1.Till how much prefix and suffix are same

2.Using manchers algorithm find longest palindrome at each point

Then for each index check if it touches with common prefix points and it's your solution.

My Solution — 74734509

First try understanding that for every $$$x \lt = k$$$, the string $$$s[1..x]$$$ is equal to reverse of string $$$s[n-x..n]$$$, and for any other $$$x \gt k$$$ the string $$$s[1..x]$$$ is not equal to reverse of string $$$s[n-x..n]$$$. So that lets iterate over $$$i$$$ from 1 to $$$n/2$$$, if the strings were equal, then $$$k \gt = i$$$, otherwise $$$k \lt i$$$, it can be done in $$$O(n)$$$, if $$$s_i == s_{n-i+1}$$$ then just continue iterating, otherwise break the loop, $$$k$$$ will be the biggest $$$i$$$ before breaking.

Now we have $$$k$$$, try finding maximum palindrome prefix and maximum palindrome suffix using prefix-function(or hashing) on string $$$w = s[k+1..n-k] + "*" + rs[k+1..n-k]$$$, where $$$rs$$$ is the reverse of string $$$s$$$.

What is wrong about it? Are you sure you just don't misunderstand the explanation?

We will form the number with just 2s and 3s, For a number to be divisible by 2, it should have 2 at the end. So we will keep 3 at the end. Thus it is not divisible by 2 now. For a number to be divisible by 3, its digit's sum should be divisible by 3. So sum of digits of our number is of the form 3k + 2, which can never be divisible by 3 for any value of k.

It's probably just some guess work. The way I thought about it is that instead of thinking of a lot of digits, why can't we just have a lot of digits which keep repeating? This highly simplifies your solution space. So suppose your number has only one digit, let's say a; then your number is aaaa....aaa but in that case, it is divisible by a. That means, we should think of having two digits in the number. Clearly 1 can't be a digit. What else do we have? If we take 2 as one of the digits, the other digit can be 3(as in the solution) or 5 or 9. I hope this gives you some form of intuition in regard to the problem.

233...33, is not divisible by 2 as number must end with 2 to be divisible by 2 and number is also not divisible by 3 as the sum of digits is never gonna divisible by 3 as it always short by 1 number.

There is another AC solution. We just need to write n-1 times ‘9’ and at the end we should write ‘8’. Why this works? Because of rule of divisor 8 (find it yourself, my English level not good enough to explain my thoughts).

I intuitively think it's OK to just choose an odd number and an even number. For example, "2.... 3" or "4.... 3" or "5.... 8" or "8.... 9". Can anyone prove it?

Let's denote the places of the largest elements by stars, and the other elements by dashes. For example, it might look like:

--*--**--*-

Then our goal is to count the number of ways to add dividers that split up all the stars. For example:

--*-|-*|*--|*-

The i-th divider must be between $$$a_{i}$$$ and $$$a_{i+1},$$$ so it has $$$a_{i+1}-a_i$$$ places it can go. The choices for all dividers are independent, so we multiply all these numbers together.

Lets first solve the following problem, you have $$$n$$$ different eggs in a row, you want to take a prefix from eggs(probably empty or all eggs), how many ways you can choose the prefix?, lets say that we want to choose a border and then our prefix is the eggs in the left of the border(border is just a stick between two eggs or before or after all eggs), you can choose the border in $$$n+1$$$ ways.

Now go back to the problem $$$C$$$, its easy to see that every segment must have exactly one number bigger than to $$$n-k$$$, so lets change it a little bit, we want to find exactly $$$k-1$$$ borders, such that first border is between $$$a_1$$$ and $$$a_2$$$, second border is between $$$a_2$$$ and $$$a_3$$$ and so far, what you think the answer will be?($$$a_i$$$ is $$$ith$$$ number in the array which is bigger than $$$n-k$$$), choosing border are independent, there is exactly $$$a_{i+1} - a_i$$$ ways to choose $$$ith$$$ border.

Yeah! about that, the more one thinks the harder it gets. These first questions are really surprising these days.

Your solution is very intuitive. Thanks a lot.

I noticed that bombs could be modeled as ')' and numbers greater than current ans i.e 1s as '('. Now this question is similar to regular bracket sequence.

I was getting WA earlier as I was using -1 for bombs earlier. But this bomb cancels even numbers on the right. Hence we needed to maintain two values in the segment tree.

ABalobanov, can you provide a link to your submission? I'm having trouble understanding how the segment tree is maintained. Specifically, what information is stored at each index?

despite of partial retroactive priority queue, can you tell me which algo i need to know to solve E as a beginner

Instead of doing this

p = p + s[i];
pp = s[j] + pp;

Try doing this :

p += s[i];
pp += s[j];
reverse(pp.begin(),pp.end());

Cuz the above operations takes O(|p|) each time you add a character, but the this method appends the characters into string taking O(1) each time you add a character to string.

For example this 73757219 naive recursion with memoization. calc(mask, last) calculates the answer for the rest of the men (given by mask) with last being currently the last man in the sequence. Complexity seems to be O(n*2^(2n)) with a good constant.

I ran through all of the partitions of the people by two (almost) equal groups (there are C_14^7 of them, it's around 3500).

For the first half of every partition I pre-counted d[fin][res] – the number of ways to go through this half stopping in fin and getting a result mask equal to res.

For the second half of every partition I pre-counted d[start][res].

Now you can go through all of the partitions, but also through all of the end and start points and all of the result masks in every half. It works in #(partitions) * 7 * 7 * 2^6 * 2^6.

It's too long. So we also need to pre-count d[start_mask][res] for the second half of every partition. Here start_mask is a set of vertices where you can start.

Now once you fixed a fin you don't need to go through every start. You just need to look at the set of adjacent to fin and the set of all others. This will work in #(partitions) * 7 * 2 * 2^6 * 2^6 and gets AC.

We want to find the longest prefix which is also a palindrome, lets call it string $$$a$$$(the longest palindrome prefix). What do we do now?, we use prefix-function(prefix-function is an algorithm which can find the longest prefix of a string, which is also a suffix of the string and is not equal to the string itself, in $$$O(n)$$$, you can find it in cp-algorithms). Then lets run prefix-function on string $$$s[k+1..n-k]+"|"+rs$$$, where $$$rs$$$ is reverse of string $$$s[k+1..n-k]$$$.

Why the prefix-function's return is the longest palindrome prefix?, you can understand it yourself!!

Suppose the string $$$S=AB$$$, where $$$A$$$ is a palindrome. Then the code computes the KMP array for $$$S\text{#} S'=AB\text{#} (AB)'=AB\text{#} B'A.$$$ Note that $$$A$$$ is both a prefix and a suffix of the string, and the KMP array computes the longest proper prefix that is also a suffix. That is, the last KMP array value will be at least the length of $$$A$$$.

Conversely, suppose we have the longest prefix that is also a suffix of the string $$$S\text{#}S'.$$$ Clearly, it cannot contain the $$$\text{#}$$$, because it does not appear elsewhere in the string. So, we have the longest prefix of $$$S$$$ that is a suffix of $$$S'$$$. But these are just the same characters in reverse order, so we must have a palindrome!

Probably your solution on your machine didn't output just "qq", but "q<some control character, which is invisible in terminal>q" and did the same on the server, which is not considered a correct answer. And if not then you have some type of undefined behaviour.

No if $$$n-1$$$ is divisible by 9

Could the problem be:

memset(f,0,sizeof f);

since it is resetting the entire array for every single test case?

There isn't much difference between 982ms and 1000ms. Expect ~30ms difference. It may be due to overload on servers at that moment etc.... You soln is O(n) but input/output takes too much time here. It's close to 2MB (2^21 chars). I added this line for fast input output in your code and it runs in 124ms. 73749515

My code is similar to yours, but mine runs fast at the forth test case 73756081. Why your solution runs so slow is mainly because input/output takes too much time, as @aryanc403 said. In my code, output here is independent:

rep(i, 1, n) cout << a[i] << " ";

This will take advantage of IO buffers, which makes the compiler happy. To verify my conclusion further, I edited your code to become four versions. The first is your original code:

cin >> n;
rep(i, 1, n) {
	cin >> x;
	ll now = x + ma;
	ma = max(now, ma);
	cout << now << " ";
}
cout << endl;

It costs 826 ms at the test#4. 73757350

I add flush after cout << now << " "; in the second one. It costs 857 ms at test#4. 73757273

I extract the output part to make it independent in the third version, like my code. It costs 529 ms at test#4. 73756448

In the fourth version, I flush the IO stream after each outputs, in the basis of the third version. It costs 841 ms at test#4. 73756516

It is found that independent IO without flush runs fast, but with flush runs slowly; the in-independent IO without explicit flush runs slow, as well as the in-independent IO with explicit flush runs slowly.

It is shown that the in-independent IO runs flush implicitly, the independent IO does not run flush unless you specified explicitly. I guess the reason for the former is that there are both input and output in the for-loop, which makes the IO stream flush quickly.

Could someone who is familiar with the internal working mechanism about iostream in C++ tell me more? Thanks a lot.

I don't think so. You use 30 and 30 is not a prime.