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://codeforces.com/problemset/problem/1638/D
It seems that many problems that are related to doing some specific operation could be done by inverting the whole process
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).
Got it thanku
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.
Failing testcase for your approach: Ticket 587
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.
Thanks for the help I didn't noticed that.
Woah! I was facing the same issue. I would've never figured this out without your comment.
but it is same know, what is the difference between maintaining a vector or a map, we are maintaining two of them , please explain more clearly https://codeforces.com/contest/1644/submission/150437245
I appreciate all the work that all problem setters and editorialists put in creating problems and writing editorials, but I want to know why there's a delay of almost a day between contest ending and editorials getting out? The excitement and the curiosity fade away (at least for me) due to such a long delay...
That holds true only for certain contests, for some contests the editorial is out as soon as the round ends bro.
Can anyone please explain problem E?
The editorial explains it in quite detail. Try to trace out on paper/whiteboard where you're unclear (I did and it helped me a lot!). If you still have doubts, I can help you resolve them.
If you are/were getting a WA/RE verdict on any of the problems from this contest, you can get a small counter example for your submission on cfstress.com
Problems added: "A, B, C, D, E, F".
If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.
contest id 1644 problem index C submission id 160707248
getting WA in test case 9
Take a look at Ticket 12285 from CF Stress for a counter example.
thanks
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://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
Can someone help me understand why we need the break condition in D? What are those cases requiring that break?
Let's say after i'th query you get all rows (column can be anything) in the query. This would mean that whatever colours were present in all the cells before, are updated (possibly to the same colour but updated for sure) so any query that was processed before i'th query is no longer relevant to the final state. If however, we do process them in reverse order, it will update colour of some cell which shouldn't have been the case. Same goes for queries covering all columns instead of rows hence we have to check for both.
Break condition is required when we have painted either all the rows or all the columns since after that final colour of a query would remain same.
Queries are being processed backwards
I am getting TLE for problem C but Idk why. My submission 147508883
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"?
Because for each valid query you have k different choices and these choices are independent to the ones that selected so far.
Apparently an O(n^2) solution is what is wanted by C... I guess I should have just went for it. I tried finding a solution where I was trying to basically mask the array and use those masks to find the respective points and values of the sums. Good problem overall, just didn't realize it could only be solved with O(n^2) and that was good enough.
can anyone help in telling me what is wrong in my solution for Problem B 147407485. This solution is working on visual studio community and i have checked my times that it gives distinct anti-Fibonacci permutations only. but when submitted on codeforces online judge it shows "wrong answer on test 2".
Failing testcase: Ticket 633
thanks for reply.`` When i compile the program on visual studio with same input as shown by you, visual studio is showing different output.
link provided by you is showing two same permutations but visual studio is showing all distinct permutations.
It's because you are initializing the seed dynamically (based on current time). It's entirely possible that it produces one answer on your machine, another on mine, and a completely different one on Codeforces. Hence, you can't guarantee it to produce a correct solution.
thanks again . look at this submission 147594424 in this i have removed seed but even then it is not accepting the answer. now it is showing that test case 7 is not anti-fib permutation. However this is not the case as one can easily verify that in case 7 program is printing anti-fib numbers only.
You removed the seed, but you did not remove the randomization (see the random_shuffle function). Hence, your program can still produce different answers based on the seed chosen during runtime.
The error message does not mean that your program anti fibonacci permutation for $$$n = 7$$$. It means, that it prints an anti fibonacci permuation for some $$$n$$$ which is present in testcase 7.
If you have any more doubts, you can simply use my website to get failing testcases for your submission. For example, your latest one fails on Ticket 636
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
the solution for question C gives TLE. Didn't expect it to be like that in editorial.
Can somebody help me that where is the bug in my code? (Problem A).
Try this. This is exactly same code but with better punctuation marks. Your else-if statements for char — R G B have problem as if block in these may not be recognized by compiler correctly. ~~~~~
#include <bits/stdc++.h> #define disabled { f = 0; break; } using namespace std; bool key[3]; int main() { int t; cin >> t; while (t--) { for (int i = 0; i < 3; i++) key[i] = 0; string s; cin >> s; bool f = 1; for (char ch: s) { if (ch == 'r') key[0] = 1; else if (ch == 'g') key[1] = 1; else if (ch == 'b') key[2] = 1; else if (ch == 'R'){ if (!key[0]){ disabled}} else if (ch == 'G'){ if (!key[1]){disabled}} else if (ch == 'B'){ if (!key[2]){disabled}} } if (f) puts("YES"); else puts("NO"); } return 0; }~~~~~
Thanks. I know that where is the bug. If i change the code as the following, you can know what i mean.
I Accepted the code. Thank you very much.
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!
Can someone please help me with this solution? I am not getting why this sol isn't working, it would be great if someone can suggest a test ( of reasonable length)case in which it fails .151373734
PS: I tried finding the array with the largest possible sum and its length (**let l **) and for all values of k <= l, I added k*x to the max sum and for all k > l, I checked for subarray of size k with the largest sum and printed max of ( prev_sum, (cur_sum + k*x)).
Failing testcase: Ticket 2989
Thanks, got it finally .
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://codeforces.com/contest/1644/submission/155271519
Failing testcase: Ticket 6147
My submission for problem D. https://codeforces.com/contest/1644/submission/157867234 Anybody please tell me where and why the code fails