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 <= k$$$, the string $$$s[1..x]$$$ is equal to reverse of string $$$s[n-x..n]$$$, and for any other $$$x > 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 >= i$$$, otherwise $$$k < 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.

*D1

maybe you forgot to module 998244353?

The number 998 224 353 appears three times in the problem and it is long and strange enough for you to discover it.

By doing this, if some problem of the contest uses NTT, the modulo won't give it away.

Summary

• Find the longest matching prefix and suffix, where suffix = palindrome(prefix)
• Find the longest inner substring that is a palindrome and touches the prefix or suffix (or both)
• Combine these as final answer

Steps

1. From both ends of the string, find a prefix and suffix that are mutual palindromes. Store that for the final answer
2. Strip off these matching prefix and suffix (if any) so you're left with just the inner string
3. Run Manacher's algorithm on the inner string
4. Using the output from step 3, find the max value (i.e. max palindrome length in inner string) that touches the prefix or the suffix (or both).
5. Return [prefix] + [longest internal palindrome that touches either prefix or suffix] + [suffix]

Manacher's Algorithm

• This algorithm finds all palindromes in the string in O(N). It treats each index as a "center" and finds the "radius" (or half length) of the palindrome around that center. It stores this radius for each index in the string. For instance, for "aba", the values returned would be [1, 2, 1]
• The algorithm starts off with a brute force palindrome search (i.e. from the first point, expand linearly in both directions to see how far the palindrome stretches). Then for the next point, first re-use pre-computed information, if that exists. Then continue linearly expanding to see how much further the palindrome stretches. Store this palindrome length ("radius") for that index.
• The key observation that's used here is that if the current index lies to the right of a known palindrome and falls within that palindrome's range, then you can simply copy over the pre-computed values from the left half to the right half, and then continue expanding on the right to see how much longer the palindrome on the right stretches. This is because the left half is an exact mirror image of the right.
• For eg. if the string is "abcdcba", then since we have a palindrome around "abc[d]cba" and both b's fall within its radius, palindrome_len("abcdc[b]a") = palindrome_len("a[b]cdcba") + {any additional palindromic text to the right}
• Side observation: it's sort of a DP equivalent approach where for any index, you first read what has been partially pre-computed (by virtue of the current index falling under the radius of a prior index), then manually expand beyond that, then save that value, then repeat for next index.

References

• https://www.youtube.com/watch?v=nbTSfrEfo6M
• https://tarokuriyama.com/projects/palindrome2.php
• D2 solution with comments: https://codeforces.com/contest/1326/submission/73836144

You can check out prefix function here : https://youtu.be/nJbNe0Yzjhw

with base=29 and mod=1e9+7 my solution failed for test case 104, I then modified my mod to 998244353 and it passed.

The same happened for lots of people, for example my friend davooddkareshki, it seems that it was kind of anti-hash test cases.

Try this 471D

How can a number ending on $$$3$$$ in decimal representation be divided by $$$2$$$?

partitioning — divide the complete array into continuous ranges. segment — a continuous range of the array or a portion of the array. partition value — sum of maximum values in each partition.

Unfortunately there is no way of downloading the full test data, but your implementation is O(n^3) so is likely to be slow for large test cases. Also recursion is quite slow in Python, and best avoided as far as possible.

This can be reduced to O(n^2) by breaking the problem into parts:

1. find how much of the start of the input string matches the reversed end of the string, this will be the start and reversed end of the result.

2. find the longest palindrome at the start or end of the middle section of the string and put it in the middle of the result string.

My solution following this strategy is here

So you want the k largest numbers to be in separate partitions so the total partition value is the greatest. Because a is a permutation of numbers from 1 to n, the k largest numbers are n, n-1, n-2 ... n-k+2, n-k+1 (n-k is the k+1th largest number as n-1 is the second largest)

It is true, that for random strings the length of the answer isn't big, because you have a very very small probability to get the long string in the answer (there are many pairs of symbols that should be equal). So, in the generation of the random strings, you will never get some extreme test cases.

About test generation strategy: it's hard to share it because I had some generators, which are not obvious to understand. But some idea of how to generate the string with the long string in the answer: just generate some palindrome first, after that split it randomly and add some symbols between the parts.