We don't need divide and conquer in F. We can use only convex hull trick. This way the solution has better complexity and is easier to implement.

Let's say that S1 is a normal prefix sum array, that is S1[i]=A[1]+A[2]+...+A[i] and S2 is again a prefix sum array but this time every element is multiplied by its index, that is S2[i]=A[1]+2*A[2]+3*A[3]+...+i*A[i]. Let's choose some R which will be the right end of our chosen interval. Now we are looking for the L that minimizes S2[R]-S2[L-1]-(L-1)*(S1[R]-S1[L-1]) which is a standard use of CHT — http://codeforces.me/contest/660/submission/17245184.

The complexity is O(NlogN).

sum_so_far += t[i];
score_so_far += sum_so_far;
Fun f = Fun{mid - i + 1, score_so_far};

sum_so_far can be N * 10⁷

score_so_far can be N² * 10⁷

When we will calculate f.a*f.b it can be N³ * 10⁷, which is bigger than 10²².

Am I missing something?

My approach for Problem F is as follow (It didn't work, but I can't find the bug in this algorithm):

We can determine the stop point (deleted suffix) by looping back from n to 1:

for(int i=n; i>=1; i--) {
        sum += ts + a[i], ts+=a[i];
        if (sum < 0) {
            sum=0, ts=0;
            if(a[i] < 0) 
                bef[i-1]=1;
            else 
                bef[i]=1;
        }
    }

then I implemented this for loop to get the best stop point for every i:

bef[n]=1;
    int last = 1; 
    for(int i=1; i<=n; i++) {
        if(bef[i]) {
            for(int j=last; j<=i; j++) go[j] = i; 
            last = i+1; 
        }
    }

So now go[i]+1---> n will be the deleted suffix for item i.

I think if this part of code works , I think this problem can be solved in O(n) Complexity, And if it doesn't work, my approach will fail entirely.

So, what is wrong with my code?

In C problem, why complexity O(n + k)? even if k > n it will be O(n).

For D, another interpretation is to count pairs (dx, dy) for all pairs of points and then for each such pair add to answer count * (count - 1) / 2. Since the parallel sides are parallel and has same length. But we will count each parallelogram twice, so divide the answer by 2.

Названия задач E и F не из этого контеста. Копипаста-с :)

How can you solve Problem E?

Out of A,B,C,D guess which one I found the hardest? That's right! A. FML ;_;

There is another method of solving B with sorting. Some people might find it easier and shorter to code

17235532

For Problem F you can just make a form of slope such that (p[j] — p[k]) / (j — k) <= s[i], where p[i] = i * sigma(a[i]) — sigma(i * a[i]), s[i] = sigma(a[i]). then you can make a convex hull, for each i, you just to use binary search to find the best choice and update the answer. this complexity is O(nlogn)

for E ,in 5th line ,there should be m - 1 choices for each of them but not k-1 choices.

Here's just a funny story I want to tell you guys.

I solved problem F by a weird O(N) algorithm, which is not correct.

http://codeforces.me/contest/660/submission/17264773 (Accepted)

Maybe test cases are weak, so my solution passed 52/54 tests (failed on 2 tests, I had to write "if n=... cout..." in order to AC). Seem crazy right ?

An O(n) alternative for E:

    LL powr = 1;
    LL current = 1;

    ii (n) {
        current = ((2*m)*current - (current - powr)) % MOD;
        powr = (powr * m) % MOD;
    }

    cout << current << '\n';

This is more direct from the statement of the problem. We build the set of all sequences, element by element, from left to right, and current tracks the count of distinct subsequences within all the sequences (visualise a different room for each sequence maybe). At each step for each room we create m new rooms. Also, in each room, each subsequence splits into two: one with the newly added element, and one without. Except we have just created some subsequences that were already there; all of them, in fact (except the empty ones), so we subtract them (the number of empty ones is powr, which is m**i).

Seems to work: 17242031.

For B, you say "There are no tricks." What about 17246985?

thank you)

I don't understand why the problem D is complexity O(n^2*logn), I know that the n^2 is there because we have to compare every segment with every other segment but I don't understand why the log(n).

Кину камень в огород человеку, писавшему решения.

Что это за "магические" define, которые не добавлены в решение?

Неужели было так трудно написать нормально циклы?

I didnt understand the samples in the question for E, could someone help me out here?

Can someone elaborate on the following from problem E's editorial?

The closed formula being referred to in problem E is:

$$$ans = m^n + \frac{m}{m-1}((2m-1)^n - m^n)$$$.

It doesn't work when $$$m = 1$$$ (because of division by 0). But in that case, since there is only a single sequence of length $$$n$$$ comprising of all $$$1$$$-s, the answer is simply $$$(n + 1)$$$.

A note for Problem E: Different Subsets For All Tuples

What got me stuck on the problem is that I initially considered the sequence x1, x2 .. xk but I said xi cant appear in the range (position of xi-1, position of xi+1), but that completely ignored cases in which the value appears multiple times in the same segment.

So usually, in combinatorics we like to rephrase things and identify things, so the idea for cases in which the sequence appears multiple times is to only consider the sequence with the smallest lexicographical position vector. this is what allows for the described approach.

Since math is hard, I have a solution for $$$E$$$ which requires basically no math and is really easy to implement! I can't prove the correctness of it in any nice way.

So first is to try out small $$$(n, m)$$$ and brute force the answers, probably using some computer program or something. That way, we can try to find a pattern.

#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <map>
#include <algorithm>
#include <climits>
#include <cstring>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <cstring>
#include <random>
#include <array>
#include <chrono>

using namespace std;

vector<vector<int>> vec;

int ds (vector<int> v) {
    int dp[v.size() + 1];
    dp[0] = 1;
    map<int,int> last;
    for (int i = 1; i <= v.size(); i++) {
        dp[i] = 2 * dp[i - 1];
        if (last.count(v[i - 1])) {
            dp[i] = dp[i] - dp[last[v[i - 1]]];
        }
        last[v[i - 1]] = i - 1;
    }
    return dp[(int)v.size()];
}

void rec (int n, int m, vector<int> v) {
    if (v.size() == n) {
        vec.push_back(v);
        return;
    }
    for (int i = 1; i <= m; i++) {
        v.push_back(i);
        rec(n, m, v);
        v.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, M;
    cin >> N >> M;
    rec(N, M, {});
    int a = 0;
    for (auto& v: vec) {
        //for (int i: v) {
            //cout << i << ' ';
        //}
        //cout << '\n';
        //cout << ds(v) << '\n';
        a += ds(v);
        //cout << '\n';
    }
    cout << a;
}

If you put this in a table, we get:

2 4 6 8 10 12

3 14 33 60 95 138

4 46 174 436 880 1554

5 146 897 3116 8045 17310

6 454 4566 22068 73030 191706

I index the table such that the column index represents $$$m$$$ and the row index represent $$$n$$$.

Let's read the table column by column. The third column is:

6 33 174 897 4566

Notice that everything seems to be around $$$5$$$ times bigger than the previous number. There's a little bit of an offset, though. The offsets are powers of $$$3$$$.

The fourth column:

8 60 436 3116 22068

Notice that everything seems to be around $$$7$$$ times bigger than the previous number. There's a bit of an offset, by powers of $$$4$$$.

And that's the main observation.

$$$\boxed{f(n, m) = f(n - 1, m) \cdot (2 \cdot m + 1) + m^{n - 1}}.$$$

Easy to constructive recursive solution from there.

DP solution for Problem E:

For a specific sequence $$$a_1, a_2, a_3, ... $$$, it's known that $$$dp[i] = dp[i-1] * 2 - dp[j-1]$$$ in which $$$j$$$ is the latest position that $$$a_j = a_i$$$.

Now, let $$$dp[i]$$$ represent the sum of $$$dp[i]$$$ sequence whose last element is specific $$$x$$$. $$$x$$$ may be any number between $$$1$$$ to $$$m$$$, but it doesn't matter. $$$dp[i] = dp[i-1] * m * 2$$$ is hold for every sequence. And we should subject some $$$dp[j]$$$ from it. We can iterator the latest $$$j$$$, count the number, so we can get:

$$$dp[i] = dp[i-1] * 2 - \sum_j dp[j-1] * m * {(m-1)}^{i-j-1} $$$

And the sum is very easy to maintain when we loop it.

146751249

Here's insight into "parallel summing" in problem e solution: https://codeforces.me/blog/entry/104172