Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
s = input()
for (d, k) in zip("RGB", "rgb"):
if s.find(d) < s.find(k):
print("NO")
break
else:
print("YES")
1644B - Anti-Fibonacci Permutation
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cout << i;
for (int j = n; j > 0; --j) if (i != j)
cout << ' ' << j;
cout << '\n';
}
}
}
1644C - Increase Subarray Sums
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
INF = 10**9
for _ in range(int(input())):
n, x = map(int, input().split())
a = list(map(int, input().split()))
mx = [-INF for i in range(n + 1)]
mx[0] = 0
for l in range(n):
s = 0
for r in range(l, n):
s += a[r]
mx[r - l + 1] = max(mx[r - l + 1], s)
ans = [0 for i in range(n + 1)]
for k in range(n + 1):
bst = 0
for i in range(n + 1):
bst = max(bst, mx[i] + min(k, i) * x)
ans[k] = bst
print(" ".join([str(x) for x in ans]))
Idea: BledDest
Tutorial
Tutorial is loading...
Solution 1 (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int MOD = 998244353;
int main() {
int t;
scanf("%d", &t);
forn(_, t){
int n, m, k, q;
scanf("%d%d%d%d", &n, &m, &k, &q);
vector<int> xs(q), ys(q);
forn(i, q) scanf("%d%d", &xs[i], &ys[i]);
int ans = 1;
set<int> ux, uy;
for (int i = q - 1; i >= 0; --i){
bool fl = false;
if (!ux.count(xs[i])){
ux.insert(xs[i]);
fl = true;
}
if (!uy.count(ys[i])){
uy.insert(ys[i]);
fl = true;
}
if (fl){
ans = ans * 1ll * k % MOD;
}
if (int(ux.size()) == n || int(uy.size()) == m){
break;
}
}
printf("%d\n", ans);
}
return 0;
}
Solution 2 (awoo)
from sys import stdin, stdout
MOD = 998244353
ux = []
uy = []
for _ in range(int(stdin.readline())):
n, m, k, q = map(int, stdin.readline().split())
while len(ux) < n:
ux.append(False)
while len(uy) < m:
uy.append(False)
xs = [-1 for i in range(q)]
ys = [-1 for i in range(q)]
for i in range(q):
x, y = map(int, stdin.readline().split())
xs[i] = x - 1
ys[i] = y - 1
cx = 0
cy = 0
ans = 1
for i in range(q - 1, -1, -1):
fl = False
if not ux[xs[i]]:
ux[xs[i]] = True
cx += 1
fl = True
if not uy[ys[i]]:
uy[ys[i]] = True
cy += 1
fl = True
if fl:
ans = ans * k % MOD
if cx == n or cy == m:
break
for i in range(q):
ux[xs[i]] = False
uy[ys[i]] = False
stdout.write(str(ans) + "\n")
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
def calc(s, n):
ld = s.find('R')
res = ld * (n - 1)
y = 0
for i in range(len(s) - 1, ld - 1, -1):
if s[i] == 'D':
res += y
else:
y += 1
return res
for _ in range(int(input())):
n = int(input())
s = input()
if s.count(s[0]) == len(s):
print(n)
continue
ans = n * n
ans -= calc(s, n)
ans -= calc(''.join(['D' if c == 'R' else 'R' for c in s]), n)
print(ans)
Idea: BledDest
Tutorial
Tutorial is loading...
Approach of D problem was great
yup, somewhat similar to this question's approach( two contests ago) https://mirror.codeforces.com/problemset/problem/1638/D
In problem D why we process the queries backward?
When you process backwards, the query is equivalent to "color all squares in this row and column which are not yet colored". This way, each square will be colored at most once. So now your answer will be $$$k$$$ raised to some power(which is actually the number of queries where at least one square was colored).
I processed all the queries forwards but ended up getting WA, but I am unable to understand how is there a difference between processing it forwards or backwards? Even if we are doing it forwards then, yes it might be possible that some square is getting colored more than once but in the end I am counting the different number of colors for all the squares so that shouldn't make a difference.
For each query you want to determine something that happens in the future — in the later queries. So to tell something about query $$$i$$$, you have to first process queries $$$i+1$$$..$$$q$$$. That is exactly the same as going backwards over queries: you first determine the status of the query, then add the information about it to some data structure.
looks legit
upd. already fixed
Can anyone help why is this giving me TLE for D 147473308 ?
You have initialized arrays visr and visc of size n and m respectively. Hence your time complexity is O(t*(n+m)) or larger, which in the worst case will be 2*1e9 since there is no limit on sum of m,n over all test cases.
Woah! I was facing the same issue. I would've never figured this out without your comment.
Can anyone please explain problem E?
No need for FFT in problem since we need only sum of those Stirling's number and this can be done in O(i): Since S(i,j) = sum(1<=t<=j) C(j,t) * t^i * (-1)^(j+t) / j! we have:
S(i,1)+S(i,2)+..+S(i,k) = sum(1<=j<=k,1<=t<=j)( t^i * (-1)^(j-t)/((j-t)! * t!) ).
Let d = j-t, then ans = sum(1<=t<=k,0<=d<=k-t)( (t^i/t!)*((-1)^d / d!) ) iterate over t and sum(0<=d<=k-t) ((-1)^d / d!) can be precomputed
I really like this formula. It is elegant and works under any prime modulo. Thank you for sharing it!
Here's a more detailed explanation and another way to look at it: Let $$$n \geq 1$$$ be a fixed integer.
As in tutorial, let $$$p_i = \frac{(-1)^i}{i!}$$$ and $$$q_j = \frac{j^n}{j!}$$$.
Then $$$S(n, k) = \sum\limits_{i+j=k} p_i \cdot q_j$$$.
Consider a matrix $$$M$$$ in which $$$M_{i, j} = p_i \cdot q_j$$$ for $$$0 \leq i, j \leq n$$$.
Then $$$S(n, k)$$$ is the sum of entries on the antidiagonal $$$i+j = k$$$.
Suppose we want to find $$$S(n, 0) + S(n, 1) + ... S(n, k)$$$ for some $$$k$$$.
That is to sum the entries above the antidiagonal $$$i+j=k$$$.
We can sum these values column by column.
For a fixed column $$$j$$$, the sum is $$$q_j \cdot \sum\limits_{i=0}^{k-j} p_i$$$.
Thus, $$$S(n, 0) + S(n, 1) + ... S(n, k) = \sum\limits_{j=0}^{k} q_j \cdot \sum\limits_{i=0}^{k-j} p_i$$$.
To compute this efficiently, note that $$$\sum\limits_{i=0}^{k-j} p_i$$$ is just the sum over a prefix of $$$p$$$.
My implementation: https://mirror.codeforces.com/contest/1644/submission/148117254
I have a question, though. To compute $$$S(i,1)+S(i,2)+...+S(i,k)$$$, the formula requires to find $$$t^i$$$ over $$$t=0,1,...,k$$$. Can this be computed (or precomputed) in $$$O(i)$$$?
Oh I get it.
We can use linear sieve to find all primes $$$p$$$ and compute $$$p^i$$$.
For a composite $$$x = a \cdot b$$$, compute $$$x^i$$$ as $$$a^i \cdot b^i$$$.
This is $$$O(k \log i / \log k) = O(i)$$$
C can be done with 2D DP. My submission is linked below 147347109
Note that I only used the custom "getbigger" function instead of the max function because the max function was being annoying for me.
Could you explain the idea of your code?
Here are two alternate solutions for F. (Neither one uses any prior knowledge about the Stirling numbers.)
As in the main editorial, consider the related problem with only operations of type $$$G$$$. Applying several operations of type $$$G$$$ to an array is equivalent to applying some permutation to the codomain $$$\{1 \ldots k\}$$$ of the array. Since these operations are invertible, and we need to count equivalence classes with respect to this operation, it makes sense to try Burnside's lemma. That gives an explicit formula:
For a given permutation $$$\sigma \in S_k$$$, we have that $$$a = \sigma \circ a$$$ if and only if $$$a$$$ maps $$$\{1 \ldots n\}$$$ into the set of fixed points of $$$\sigma$$$. So the formula can be simplified to
Each permutation on $$$\{1 \ldots k\}$$$ with exactly $$$i$$$ fixed points is uniquely determined by the set of its fixed points, and by the derangement (no-fixpoint-permutation) it induces on the other $$$k - i$$$ points in its domain. So, the formula further reduces to
Counting derangements is easy and well-known, so this formula allows direct calculation of $$$A_i$$$ in $$$O(k \log{i})$$$. But since it is impossible to use more than $$$i$$$ different values in an array of length $$$i$$$, this can be reduced to $$$O(i \log{i})$$$ by just replacing $$$k$$$ with $$$\min(i, k)$$$.
The solution to the original problem in terms of $$$A_i$$$ is the same as described in the main editorial.
Implementation: 147499995
The editorial describes how to solve the problem in terms of $$$\sum_{j=0}^k S(i, j)$$$ for various values of $$$i$$$. This is another way to compute only that quantity.
Let $$$g_j(t) = \sum_{i=0}^\infty S(i, j) \frac{t^i}{i!}$$$ as a formal power series. It is the EGF of the $$$j$$$-th column of the Stirling numbers. Since multiplication of EGFs corresponds to partitioning, it can be seen that $$$g_j(t) = \frac{(g_1(t))^j}{j!}$$$: The $$$j!$$$ in the denominator forgets the order in which the sets were used in the partition. It's also easy to see that $$$g_1(t) = e^t - 1$$$.
To solve the problem, we need to calculate $$$\sum_{j=0}^k S(i, j)$$$ for various values of $$$i$$$. So, we can consider the function $$$h(t) = \sum_{j=0}^k g_j(t) = \sum_{j=0}^k \frac{(g_1(t))^j}{j!}$$$ and calculate its coefficients. There is obviously not enough time to evaluate all terms of this sum; we will have to cancel most of them out and then undo this. One way to achieve this by noticing that $$$h(t)$$$ is almost the same as $$$\exp{(g_1(t))}$$$. So, $$$h$$$ satisfies $$$h'(t) \approx h(t) \cdot g_1'(t)$$$. We can calculate the exact value easily and then solve the resulting ODE as follows:
\displaystyle h'(t) - g_1'(t) \cdot h(t) & \displaystyle = - \frac{d}{dt} \frac{(g_1(t))^{k+1}}{(k+1)!} \\
\displaystyle e^{-g_1(t)} \cdot (h'(t) - g_1'(t) \cdot h(t)) & \displaystyle = - e^{-g_1(t)} \cdot \frac{d}{dt} \frac{(g_1(t))^{k+1}}{(k+1)!} \\
\displaystyle e^{-g_1(t)} \cdot h(t) & = \displaystyle e^{-g_1(0)} \cdot h(0) - \int_{s = 0}^t e^{-g_1(s)} \cdot \left(\frac{d}{ds} \frac{(g_1(s))^{k+1}}{(k+1)!}\right) ds \\
\displaystyle h(t) & = \displaystyle e^{g_1(t)} \cdot \left( 1 - \int_{s = 0}^t e^{-g_1(s)} \cdot \left(\frac{d}{ds} \frac{(g_1(s))^{k+1}}{(k+1)!}\right) ds \right)
\end{array} $$$
This formula can be directly implemented in $$$O(n \log n)$$$, at least if you have access to a library/template for the necessary formal power series/generating function operations. Implementation: 147380982
In problem D, why is the answer equal to k to the power of valid queries that have at least one cell belong to them? I am unable to understand. Why is "to the power"?
In problem D, why TLE with vector(int) and AC with vector(bool) , time complexity doesn't change. AC code with bool,
TLE code with vector
UPD: People already answered this in Announcement for this contest
As for problem F, I think the solution described in the tutorial is in $$$O(n\sqrt{n}\log n)$$$ time complexity, because we have $$$O(\sqrt{n})$$$ $$$\lceil\frac{n}{i}\rceil$$$ s, and calculating each of them takes $$$O(n\log n)$$$. But the solution of F says it takes $$$O(n\log^2n)$$$, am I wrong or the tutorial made a mistake? Can anyone help me?
The polynomial describing $$$A_i$$$ has $$$\min(i, k) + 1$$$ terms, so the complexity of calculating $$$A_i$$$ is $$$O(i \log i)$$$ and the total complexity is $$$\sum \limits_{i = 1}^n O(\frac n i \log \frac n i) = O(n \log^2 n)$$$.
Oh, I see! Thanks!
I am doing question D the same way, but getting a wrong answer. I have used a set to store the rows and columns and then proceed with the maximum size among the two. Can anyone help me out, please? Link for my solution: https://mirror.codeforces.com/contest/1644/submission/155271519
Failing testcase: Ticket 6147
My submission for problem D. https://mirror.codeforces.com/contest/1644/submission/157867234 Anybody please tell me where and why the code fails
Isnt there a dp approach to problem D?