Countertest 3 3 4 5 5 6. Your greedy gets 4 while it is possible to get 6.

After taking 5 4 we have 1 3 3 5 6. Then take 1 3 and 3 5 and its obvious how to get 6 from 2 2 6

I've submitted somewhat uniformly distributed integers in range [0, 10^9]:

int x = 0;
cout << 0;
for (int i = 1; i < n; ++i) {
    x += i + n * 9;
    cout << ' ' << x;
}

Ternary search in N is ok. But you should consider all edges of triangle and run ternary searches separately for each one. Because sometimes it is better to enter into triangle from the rear side.

There is solution that works in per query of the 1st type and answers in O(1) to queries of the 2nd type.

Detailed analysis is quite long, but here is some hints:

To achieve this complexity one should be able to compute and (where p = (r - l + 1) is range of houses, k₁ — old limits for heights and k₂ is new limits) in and just multiply obtained polynomails to the resulting polynomial.

Same here. I was wondering why F is F, cause it seemed to be too easy for one of the hardest problems. Now I see that the trickiest part of the problem was "read the statement carefully and do not forget to handle corner cases" )

Hm. I think that everything is fine here. This line returns m!w! And we know for sure that either m = 0 or w = 0.

Maybe I'm missing something ?

Dunno. Overflow maybe? Btw, I have #define int int64_t in my code ))

Don't know what did you mean exactly. But the solution for this problem is also a formula ;). I computed it in O(p) and didn't try to reduce the complexity and simplify:

inline int C(int n, int k) {
    return f[n] * fi[n - k] % MOD * fi[k] % MOD;
}

// number of ways to split n items to k groups
inline int D(int n, int k) {
    if (k == 0) return n == 0 ? 1 : 0;
    return C(n + k - 1, k - 1);
}

int solve() {
    if (p == 0) {
        if (m && w) return 0;
        return f[m] * f[w];
    }
    int res = 0;
    for (int i = 1; i <= p; ++i) {
        int x = i / 2 + 1, y = (i + 1) / 2;
        int g = w - i, b = m - i;
        int t = (D(g, x) * D(b, y) % MOD + D(g, y) * D(b, x) % MOD) % MOD;
        res += t * C(p, i) % MOD * f[i] % MOD * f[g] % MOD * f[b] % MOD;
        if (res >= MOD) res -= MOD;
    }
    return res;
}

I started with counting sequences where parentheses and brackets are non-distinguishable.

Then I noticed that if we fix some correct brackets sequence then we can insert parentheses sequences into it in 2x + 1 positions. In each position we can insert sequence of length l_i (Σ l_i = y), and there is catalan[l_i] such sequences.

These considerations lead me to the easy dp to count number of ways to split y items into 2x + 1 groups, which could be computed in O(Y³logX) using matrix exponentiation. But it was too slow.

Then I printed answers for different inputs and noticed that output is very familiar sequence: it was a catalan's triangle with well known formula to compute ;)

There is a formula for 6th task. My solution looks like this

int solve(int x, int y) {
    int n = 2 * x + y;
    int val = Comb(n + y, n) * (n - y + 1) % MOD * pmod(n + 1, MOD - 2) % MOD;
    return catalan[x] * val % MOD * factorial[x] % MOD * factorial[y] % MOD;
}

There is section with Explicit solutions.

My solution uses the following order of columns in backtracking search and finds solution faster than 10ms:

bool fl = n % 12 == 3 || n % 12 == 9;
for(int i=1 + fl * 2; i < n; i += 2) p.push_back(i);
if(fl) p.push_back(1);
int k = p.size();
for(int i=0; i < n; i += 2) p.push_back(i);
if(n % 12 == 2) {
    swap(p[k], p[k+1]);
    for(int i=k+2; i + 1 < (int)p.size(); ++i) p[i] = p[i+1];
    p[p.size() - 1] = 4;
}

A: https://en.wikipedia.org/wiki/Eight_queens_puzzle

B: instead of making reflection continue moving in the flipped (horizontally or vertically, depends on contacting border) board. So the movement of the ball is a straight line. We should check if point ( ± x_c + 2x₁k_x,  ± y_c + 2y₁k_y) lies on this line for some integers k_x and k_y.

I: if initial number is odd and removing last digit keeps it odd then Second player wins. Otherwise game continues until string is empty.

Assume our graph has one connected component, then we can create roads.

Hint: try to solve for a tree

More detailed explanation

I've got AC with O(Qlog²Q) in upsolving. So I think O(QlogN) can pass.

Solution for this problem briefly discribed here in Russian. Anyway this might be useful.

I had the same issue in Safari. The problem was

QuotaExceededError: DOM Exception 22: An attempt was made to add something to storage that exceeded the quota.

so in my case clearing browser's local storage resolved the issue

Quite strange behavior of the testing system.

During systests this submission gets TL15: 9311938. The same code in upsolving gets RE15: 9326201. And in my local Unix system this buggy code runs correctly.

Small fix makes this solution Accepted: 9326316

Is there any explanation?

Calculate centroid of tetrahedron and consider its projection to the surface z=0: 1) If it lies outside of triangle formed by the first 3 coordinates, then the answer is 'Falling'; 2) if it lies on the edge of triangle, then the answer is 'Unstable'. 3) if it lies strictly inside of triangle, then the answer is 'Standing'

Here http://codeforces.me/contest/379/submission/5585359