Sure, naive multiplication does the job pretty well here. Expected complexity in this problem is $$$O(n^2)$$$.

We tried FFT with divide and conquer but the precision error is too big to handle up to 2^63 -1. In the end 10^4 for 0.1 seconds troll us :P

If a client i is sent an email k*(1e9 + 7) times, dp[i] is zero, but that client still needs to be counted towards the "number of emails after the improvements".

You should count separately the number of messages before the optimization and after the optimization because of the mod. Test case that breaks this solution was added one day before the competition.

Problem G could be easily solved with Suffix Automaton, you could build a Suffix Automaton of S in $$$O(n*log(n))$$$ and then for each query start at the root of the automaton and do the following:

• If there is a transition from the current node with the current letter of the query, move through it.

• Otherwise, if you are not on the root, go to the root and add $$$1$$$ to the answer, if you are on the root, then the answer is $$$-1$$$.

For Problem F, you have to solve the problem recursively. Consider you'll be putting floors from bottom to top, if you have $$$s$$$ remaining blocks and the last floor you put had $$$n$$$ blocks then the number of ways to put the rest is:

This is, if the next floor doesn't start in the first block of the last floor, then there are $$$dp(s, n-1)$$$ ways to put the rest, otherwise, you can pick any valid size for the next floor and you know where it will be.

This is $$$O(n^3)$$$ if implemented naively, but it can be optimized to run in $$$O(n^2)$$$ by pre-calculating some sums.

Another way to solve F is the following. First, you can ignore the first level of blocks. Let $$$DP(s,b)$$$ be the number of ways to put the remaining blocks. To calculate this you look at three cases:

• The first level of blocks is full

• The leftmost stack is empty

• The rightmost stack is empty

You can calculate the first case by simply ignoring $$$s$$$ blocks. The second and third case are analogous, and you can calculate them by ignoring one stack. However, the cases eventually overlap, since the scenario where both the leftmost stack and the rightmost stack are empty can be reached from both cases. This can be solved by subtracting the value for the overlap. This is the formula:

$$$DP(s,b) = DP(s, b-s) + 2 \cdot DP(s-1, b) - DP(s-2, b)$$$

For problem G another option is to use suffix array. Build a suffix array of the main string in $$$O(n \cdot log(n))$$$, and then for each query iterate over its characters and each time do 2 binary searches (a lower bound and upper bound) so that each time you keep narrowing the range of suffixes that still match with the query. To make it clearer, you start with the first character of the query, and with 2 binary searches you find the range of all suffixes having the first character as prefix, then you do 2 additional binary searches and find the range of all suffixes having the first 2 characters as prefix (inside the previous range) and so on. If the range becomes empty, increase your counter by 1 and start all over again from where you left off. In case you can't match even 1 character, then print -1.

- A {Algorithm Teaching}          {Marcelo Fornet, Cuba}
- B {Build the Perfect House}     {Marcelo Fornet, Cuba}
- C {Cut Inequality Down}         {Mariano Crosetti, Argentina}
- D {Dazzling Stars}              {Mário da Silva, Brasil}
- E {Eggfruit Cake}               {Moroni Silverio, México}
- F {Fabricating Sculptures}      {André Amaral de Sousa, Brasil}
- G {Gluing Pictures}             {Nicolás Álvarez, Argentina} 
- H {Hold or Continue?}           {Pablo Zimmermann, Argentina}
- I {Improve SPAM}                {Paulo Cezar Pereira Costa, Brasil}
- J {Jumping Grasshopper}         {André Amaral de Sousa, Brasil}
- K {Know your Aliens}            {Mário da Silva, Brasil}
- L {Leverage MDT}                {Carlos Mendoza, Peru}
- M {Mountain Ranges}             {Vinicius Santos, Brasil}

I can only come up with an $$$O(n^2 \cdot log(n))$$$ solution which should be good enough in theory but I'm getting TLE due to the constant :(. The idea is to iterate over all possible directions counter clockwise ($$$O(n^2)$$$ directions) and for each direction we have all straight lines parallel to this direction and for each straight line we have all the points intersected by this straight line (we can compute all this in $$$O(n^2 \cdot log(n))$$$ by considering each pair of points $$$p_i$$$ and $$$p_j$$$ and computing the vector $$$p_j - p_i$$$ and a hash for the straight line defined by them and storing things in maps / unordered_maps). Then we initially rank points based on the first direction in $$$O(n \cdot log (n))$$$ (given a direction vector, we can rotate it 90 degrees ccw and then sort everything by projecting using dot product) and then in $$$O(n^2)$$$ we can count how many pairs of points are wrongly ranked. Then we iterate over all remaining directions, so when we transition from one direction to the next direction ccw the points that were collinear in the previous direction now are ranked in a strictly increasing order, so we sort those subranges and check quadratically the ranking conflicts in those subranges, and the points that become collinear in the current direction they no longer have ranking conflicts. If at some point the counter of ranking conflicts becomes 0, we print "Y", otherwise we print "N". I think this should work but I'm getting TLE. How can I improve it?

I don't know what was the intended solution. Mine uses a segment tree to keep track of biggest and smallest prefix sum. Then (in $$$O(log(n))$$$) we can find the first moment in which we need to "cut" our value if we start at position $$$X$$$ with value $$$Y$$$. Then, precompute "jumps" between cuts with a sparse table and you are done.

This problem was planned as the most or second-most difficult of the set (with Problem J). There isn't any greedy approach.

This problem is really beautiful and shows that a problem can be hard and simple

I don't know if this is the official solution but here it goes:

You need to get a square sub-matrix where each row is either full with G or full with B. Now, you can create a new matrix $$$B$$$ with $$$N$$$ rows and $$$M-1$$$ columns, where $$$B_{i,j}$$$ is 0 if $$$A_{i,j} = A_{i,j+1}$$$ and $$$1$$$ otherwise.

Now, a square submatrix with side $$$L$$$ in $$$A$$$ will be a submatrix with $$$L$$$ rows and $$$L-1$$$ columns in $$$B$$$. You need to find the biggest $$$L$$$ such that there is a submatrix in $$$B$$$ with $$$L$$$ rows and $$$L-1$$$ columns full with zeros.

You can do this with some preffix sums and binary search. Or you can even ignore the binary search, keeping track of the biggest $$$L$$$ you have found so far.

An interesting and simple solution in $$$O(n*m)$$$, which is really similar to the algorithm used to find the biggest square of ones in a matrix of 0's and 1's:

$$$dp(i,j)$$$ = longest side of a valid square having lower-right corner in $$$(i,j)$$$

We have two cases:

• $$$\underline{S_{i,j} == S_{i,j-1} \land S_{i-1,j} == S_{i-1,j-1}:}$$$ $$$dp(i,j)=max(dp(i-1,j),dp(i,j-1),dp(i-1,j-1))+1$$$

• $$$\underline{Otherwise:}$$$ $$$dp(i,j)=1$$$

Note that the first condition is the only one necessary to extend by one the length of a valid square. Here is my code :)

I think my solution is the same as MarcosK

Let $$$h[i]$$$ be the prefix sum of $$$a[i]$$$.

Now write a segtree which can perform the following query: $$$query(l, r, x, y)$$$ returns the smallest index $$$i$$$ in the range $$$[l, r)$$$ such that $$$h[i]$$$ is outside of the range $$$[x, y]$$$. It also returns a type $$$t$$$ which is 0 if $$$h[i] < x$$$ and 1 if $$$h[i] > y$$$. This segtree can be used to find the first time the amount owned overflows (goes above U) or underflows (goes below L)

Next build a sparse table $$$f[t][i][j]$$$.

$$$f[0][i][j]$$$: assuming that, at time $$$i$$$ we owned $$$L$$$, this stores the $$$2^j\text{-th}$$$ smallest time $$$k$$$ such that there is an over/underflow on index $$$k$$$. It also stores a type, 0 if it was an underflow, and 1 if it was an overflow.

$$$f[1][i][j]$$$ stores the same thing, except we assume that at time $$$t$$$ we owned $$$U$$$.

We can initialize $$$f[0][i][0]$$$ and $$$f[1][i][0]$$$ using the segtree.

Then $$$f[0][i][j]$$$ and $$$f[1][i][j]$$$ can be computed as usual with a sparse table.

Now, for each query:

First, use the segtree to find the first location $$$i$$$ after the beginning day where we encounter an overflow/underflow.

Next, use the sparse table to find the last location $$$j$$$ before the end day where we encounter an overflow/underflow.

Finally, we know that between time $$$j$$$ and the end day, there are no underflows or overflows (Otherwise $$$j$$$ would have been larger). So we can just use $$$h[end]-h[j]$$$ to find how much the amount owned changed.

There's an alternative really nice solution that avoids a segtree entirely by doing the queries offline, and simulating all the queries at once.

We can sort the start/end times of the queries, and sweep from month 0 to the last month.

As we encounter start times, we maintain the values for all of these queries by storing the values in a sorted list (a set), with a global OFFSET variable. After each month we can increment all our query values with the OFFSET variable. This might cause some values to exceed the bounds, so we can use our set to check if any queries exceed U-OFFSET or L-OFFSET, and merge those elements into one element (with a DSU or similar thing) since every element can be merged at most once.

This way, we know the exact value for those queries when we encounter an end time.

I submitted your solution using c++17 and it was AC. I presume the problem with c++11 is in the last line:

cout << dp( 1 ) << ' ' << leafs.size() << '\n';

In this case you are populating leafs container inside the function dp, but maybe it is undefined the order in which dp(1) and leafs.size() is evaluated, or simply it changed from c++11 to c++17.

Fixing it for c++11 should be straight forward, split it in two statements:

cout << dp( 1 ) << ' ';
cout << leafs.size() << '\n';