Идея: vovuh
Разбор
Tutorial is loading...
Решение (vovuh)
for _ in range(int(input())):
n = int(input())
print(1 + (n == 1) if n <= 3 else (n + 2) // 3)
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
for _ in range(int(input())):
n = int(input())
p = [i + 1 for i in range(n)]
print(n)
for i in range(n):
print(*p)
if i < n - 1:
p[i], p[i + 1] = p[i + 1], p[i]
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
INF = 2 * 10**9
for _ in range(int(input())):
m = int(input())
a = [[int(x) for x in input().split()] for i in range(2)]
su = [[-INF for j in range(m + 1)] for i in range(2)]
for i in range(2):
for j in range(m - 1, -1, -1):
su[i][j] = max(su[i][j + 1] - 1, a[i][j], a[i ^ 1][j] - (2 * (m - j) - 1))
pr = a[0][0] - 1
ans = INF
for j in range(m):
jj = j & 1
ans = min(ans, max(pr, su[jj][j + 1] - 2 * j - 1, a[jj ^ 1][j] - 2 * m + 1))
pr = max(pr, a[jj ^ 1][j] - 2 * j - 1)
ans = min(ans, max(pr, su[jj ^ 1][j + 1] - 2 * j - 2))
if j < m - 1:
pr = max(pr, a[jj ^ 1][j + 1] - 2 * j - 2)
print(ans + 2 * m)
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int main() {
int n, k;
cin >> n >> k;
vector<int> dp(n + 1), ans(n + 1);
dp[0] = 1;
for (int mn = 0; mn + k <= n; mn += k++) {
vector<int> sum(k);
for (int i = mn; i <= n; ++i) {
int cur = dp[i];
dp[i] = sum[i % k];
(sum[i % k] += cur) %= MOD;
(ans[i] += dp[i]) %= MOD;
}
}
for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
}
1716E - Swap and Maximum Block
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int K = 18;
struct node
{
long long sum, pref, suff, ans;
node(const node& l, const node& r)
{
sum = l.sum + r.sum;
pref = max(l.pref, l.sum + r.pref);
suff = max(r.suff, r.sum + l.suff);
ans = max(max(l.ans, r.ans), l.suff + r.pref);
}
node(int x)
{
sum = x;
pref = suff = ans = max(x, 0);
}
node() {};
};
int a[1 << K];
vector<node> tree[2 << K];
void build(int v, int l, int r)
{
tree[v].resize(r - l);
if(l == r - 1)
{
tree[v][0] = node(a[l]);
}
else
{
int m = (l + r) / 2;
build(v * 2 + 1, l, m);
build(v * 2 + 2, m, r);
for(int i = 0; i < m - l; i++)
{
tree[v][i] = node(tree[v * 2 + 1][i], tree[v * 2 + 2][i]);
tree[v][i + (m - l)] = node(tree[v * 2 + 2][i], tree[v * 2 + 1][i]);
}
}
}
int main()
{
int n;
scanf("%d", &n);
int m = (1 << n);
for(int i = 0; i < m; i++)
{
scanf("%d", &a[i]);
}
build(0, 0, m);
int q;
scanf("%d", &q);
int cur = 0;
for(int i = 0; i < q; i++)
{
int x;
scanf("%d", &x);
cur ^= (1 << x);
printf("%lld\n", tree[0][cur].ans);
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int N = 2043;
int dp[N][N];
int add(int x, int y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
return x;
}
int sub(int x, int y)
{
return add(x, -y);
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
int binpow(int x, int y)
{
int z = 1;
while(y > 0)
{
if(y % 2 == 1) z = mul(z, x);
x = mul(x, x);
y /= 2;
}
return z;
}
int inv(int x)
{
return binpow(x, MOD - 2);
}
int divide(int x, int y)
{
return mul(x, inv(y));
}
void precalc()
{
dp[1][1] = 1;
for(int i = 1; i < N - 1; i++)
for(int j = 1; j <= i; j++)
{
dp[i + 1][j] = add(dp[i + 1][j], mul(dp[i][j], j));
dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]);
}
}
int solve(int n, int m, int k)
{
int way1 = (m / 2) + (m % 2);
int curA = n;
int ans = 0;
int ways_chosen = way1;
int ways_other = binpow(m, n - 1);
int invm = inv(m);
for(int i = 1; i <= k; i++)
{
ans = add(ans, mul(mul(curA, dp[k][i]), mul(ways_chosen, ways_other)));
curA = mul(curA, sub(n, i));
ways_chosen = mul(way1, ways_chosen);
ways_other = mul(ways_other, invm);
}
return ans;
}
int main()
{
int t;
cin >> t;
precalc();
for(int i = 0; i < t; i++)
{
int n, m, k;
cin >> n >> m >> k;
cout << solve(n, m, k) << endl;
}
}
My $$$O(n\sqrt n)$$$ solution for problem D that works in just 78 ms!
The expression 'sum[q] -= (sum[q] >= mod) ? mod : 0' will be auto-vectorized in GCC with AVX enabled so that's a reason I guess.
My approach for problem C, Binary search the waiting time before starting to move. https://mirror.codeforces.com/contest/1716/submission/166993379
can you explain your approach. Thank you
sorry I don't know how to make a new line... The idea is if I can check whether I can walk through all the grid without getting stuck with a certain starting waiting time.
I came out with a greedy approach in O(m).
First you go with snake and if it get stuck at the position x
case 1:
then there is only one possible way to work around
case 2:
way to work around
I renamed some function and deleted some useless code to make it a little bit more readable: https://mirror.codeforces.com/contest/1716/submission/167143217
royhahayayaha Awesome approach bro !!
I was looking for binary search sol and came across yours.
my implementation https://mirror.codeforces.com/contest/1716/submission/167190887
awesome !!!
Solution to 1716F - Bags with Balls using the multinomial theorem.
Let $$$ B $$$ iterate through all the ways $$$ (b_1,\dots, b_n) $$$ to take the balls out of the bags and define $$$ g(x):= x\text{ mod } 2 $$$, and $$$F(B):=\text{# of odd balls}$$$. The answer we want to compute is
Now suppose $$$c$$$ of the $$$n$$$ indices are positive, there are $$$\binom{n}{c} $$$ ways to choose them. Also notice that we can just erase the indices equal to $$$ 0 $$$ from the multinomial coefficient (the answer remains the same). So rewriting the sum
we can compute the last part since the indices of the bags from which we pick odd balls are fixed
We arrive at finall formula we can compute in $$$O(k)$$$ (not taking in account the precomputations) after noticing that
Where $$$ S(i,j) $$$ is the stirling numbers of the second kind.
If it isn't Saucy Jack!
In problem C, at least for me, letting a_ij+1 be the time limit instead of aij is somehow frustrating, and the lack of explanation for samples make it even worse.
video Editorial for Chinese:
Bilibili
Question on problem D. There is an approach that calculates the same as in the editorial, but in a slightly different way, and gets WA. The solution is the following: let's calculate $$$dp_i,_j$$$ — the number of ways to achieve $$$i$$$ using $$$j$$$ steps. $$$dp_0,_0 = 1$$$. Transition is presented in full form and can be calculated faster.
$$$dp_i,_j$$$ = $$$\sum_{w=1, q=k+j-1}^{i - wq >= 0} dp_{i - wq},_{j - 1}$$$
What is the difference between calculated $$$dp_i,_j$$$ from the solution described above and calculated $$$dp_s,_i$$$ from the editorial?
I'm a little confused by the expression, since it has a single summation controlled by two variables, so do you mean that we try every possible combination of $$$w$$$ and $$$q$$$ that satisfies $$$w \geq 1$$$, $$$q \geq k + j - 1$$$, and $$$i - wq \geq 0$$$?
I think a simple counterexample is $$$dp_{3, 1}$$$ for $$$k = 2$$$ (the third entry in the sample output 2 of the problem). Your formula would include $$$dp_{0, 0} = 1$$$ ($$$w = 1$$$, $$$q = 3$$$) in the summation, but the actual value of $$$dp_{3, 1}$$$ is $$$0$$$.
My guess is that your approach allows skipping steps, e.g., it allows you to take a step of size $$$(k + i + 1)$$$ without taking a step of size $$$(k + i)$$$. The problem requires that you must take at least one step for each value between $$$k$$$ and the largest step size inclusive.
I think what they mean by the 2 variables is that, $$$q$$$ is the constant denoting the number whose multiple was the last step length, i.e, $$$q = k + (j - 1)$$$ and $$$w$$$ varies freely. Hence for $$$dp[3][1]$$$, $$$q$$$ can't be 3.
Romiros : Your approach is correct (and is in fact the same as the editorial solution, except that your DP takes contribution from old states, while the editorial's solution provides contribution to new states).
You have 2 small bugs in your implementation though. You can take a look at Ticket 15995 from CF Stress for a counter example.
There are 2 possible ways to reach 12 for the given counter example. $$$(0 \rightarrow 12)$$$ and $$$(0 \rightarrow 3 \rightarrow 7 \rightarrow 12)$$$.
Try to print the entire DP table and take a look at entries $$$dp[12][3]$$$ and $$$dp[7][2]$$$ and $$$dp[3][1]$$$.
Your precompute a safe limit for $$$cnt$$$ by iterating with the smallest steps. You even multiply it by 3 to handle off by one errors. However, your current implementation results in a value of $$$cnt$$$ that is way smaller than the correct count that should be used.
Got it, thanks. But why are $$$cnt$$$ steps not enough?
$$$sum1 += K$$$ implies that the step length is $$$K$$$. Therefore, $$$K$$$ should be overwritten with $$$k+1$$$ at each stage. However, $$$K + = k + cnt$$$ makes it increment by that amount instead of overwriting it.
Oh, my bad, thanks again.
Thanks a lot
Summation controlled only by variable $$$w$$$ and continues until $$$i - wq >= 0$$$, $$$wq$$$ is length of the move on $$$j$$$-th step, $$$q$$$ is the number that should divide length of the move on $$$j$$$-th step.
The solution passes pretests and gets WA3. Somehow it counts fewer number of ways than needed.
Would any kind-hearted person mind explaining to me why "the sum of F^k over all possible combinations is equal to the sum of G(t) over all possible tuples t"? I am not able to figure out why they are equal, what is the intuition behind and how could we prove it (the rest is straightforward tho, just can't comprehend the rephrased problem)
In essence, the problem asks for you to get the sum of F^k for all combination of ball selection. However, if you look at a specific selection with F odd numbers, the number of tuples of length k, where each element is an index of a bag from which we have taken an odd ball is exactly F^k.
So in order to get the sum of all F^k, we can just look at each possible tuple, and look how many times this tuple appear across all ball selection, which is the definition of G(t).
Can anyone who used prefix sums for calculating $$$dp[i][j]$$$ for D share their code? I'm having trouble implementing it.
Here is my submission
There is a commented while block that may be easier to read, since it builds the entire 2D table instead of maintaining only 2 rows. It still uses a colsum vector that keeps track of the sum of each column so far.
In problem $$$A$$$, can anybody explain solution using modulo. I don't want to deal with rounding. It's confusing for me. If $$$n$$$ $$$mod$$$ $$$3 = 0$$$ then answer is $$$\frac{n}{3}$$$, else if $$$n$$$ $$$mod$$$ $$$2 = 0$$$ then answer is $$$\frac{n}{2}$$$. But what in other cases ?
If $$$n \bmod 3 = 0$$$, then the answer is $$$\frac{n}{3}$$$.
If $$$n \bmod 3 = 1$$$, then there are two cases. For $$$n = 1$$$ (the only special case), the answer is $$$2$$$. Otherwise, the answer is $$$\frac{n - 4}{3} + 2$$$. Since we excluded the special case of $$$n = 1$$$, the value of $$$n$$$ must be at least $$$4$$$, and $$$n - 4$$$ must be divisible by $$$3$$$. So we can keep taking $$$3$$$-length steps until we have $$$4$$$ left, which we can cover with two $$$2$$$-length steps.
If $$$n \bmod 3 = 2$$$, then the answer is $$$\frac{n - 2}{3} + 1$$$. Keep taking $$$3$$$-length steps until you have $$$2$$$ left, which you cover with a single $$$2$$$-length step.
Note that your suggestion of using $$$\frac{n}{2}$$$ for $$$n \bmod 2 = 0$$$ is not necessarily optimal, e.g., you can reach $$$8$$$ using $$$3 + 3 + 2$$$, which is 3 steps instead of $$$\frac{8}{2} = 4$$$.
With how unusually long the editorial for C is, I'm surprised that the problem-setters still felt it was appropriate to keep it as a Div2C.
For D, the editorial should probably mention how we need to keep track of the first non-zero value in each row (variable $$$mn$$$ in the solution) and only start filling it up from there, since it seems like starting from the beginning resulted in many TLEs.
I think I maybe overexplained things for C. A lot of people got stuck in it, so I decided it's reasonable to explain just everything in the problem as thoroughly as possible.
Really, I think half of these things are pretty intuitive and the other half is neither that hard to come up with, nor is the only way to come to the solution.
No, keeping first non-zero element is not necessary. I didn't do that, and had not big time.
Does anyone have a testcase that breaks my submission for C? 167164510
Check these:
Your submission returns [19, 28, 20, 22], result is [17, 26, 18, 20]
wait, shouldn't the top left element in each grid be 0?
fixed it
Thanks, I had swapped my row variable with my col variable.
F can be solved more easily by using Stirling Number and Descending Power.
There is a much easier way to solve F.
A classic conversion is that:
Using the above formula:
Consider the combinatorial meaning of the red part. It chooses some boxes to take out balls with odd numbers, then it chooses $$$i$$$ of them, and calculate the number of ways. Let's reverse the steps, we can find out that the answer to the red part is equal to the number of ways to perform the following steps:
Thus, the answer can be simplified as follows:
which can be solved in $$$\mathcal{O}(k^2)$$$.
Amazing solution, thanks for the help!
But when I read your code, I see your formula is (n!/i!) instead of i!. Can you help me ? (Sorry for bad English T_T)
fixed the formula.
How to solve problem C if you can visit the sell more than once?
How to solve problem C if you can visit the cell more than once??
Problem C can also be solved in super ugly way using binary lifting and segment tree.
can you explain ur idea,Thank You.
First, let's normalize the array in such a way that the order of elements is $$$(0,0) => (1,0) => (2,0)...=> (m-1,0) => (m-1, 1) => (m - 2, 1) => ... (0,1)$$$ (zero-indexed). Let this array be $$$a_{i}$$$ and let' call this way of ordering forward order. Similarly, let the reverse of $$$a_{i}$$$ be $$$b_{i}$$$ and let's call way of ordering be backward order. Let's consider the case when we enter the cell $$$(i,0)$$$ in time $$$t$$$ and til then we moved snakely(?). Then, what we want to compute is:
Similarly, when we enter the cell $$$(i,1)$$$ in time $$$t$$$ then what we want to compute is:
Now, these two cases are almost equivalent, so I'll ignore the latter case here. Let's call an element $$$a_{j}$$$ blocking to $$$a_{i}$$$ if we enter $$$a_{i}$$$ in time $$$a_{i}+1$$$ we cannot move to $$$a_{j}$$$ without being stuck (which means that we cannot enter $$$a_{j}$$$ without being stuck at $$$a_{j-1}$$$). Then it is obvious that $$$a_{j} \gt a_{i} + j - i$$$ must hold. We only need to consider blocking elements to $$$a_{i}$$$ because the total time taken to reach $$$a_{2m-i-1}$$$ from $$$a_{i}$$$ only depends on the last blocking element with position less than or equal to $$$2m-i-1$$$ (Let's call this position $$$p_{i}$$$). Now, it follows that:
And if we let $$$q_{i}(t)$$$ be the first position of blocking element to $$$a_{i}$$$ when we enter $$$a_{i}$$$ in time $$$t$$$, then it also follows that:
Notice that if we store $$$a_{i}-i$$$ for each $$$i$$$ then $$$q_{i}(t)$$$ can easily be calculated using segment tree (we only need to find the first position $$$j (\gt i)$$$ such that $$$a_{j} - j \geq t - i$$$). Also, if we store position of $$$2^k$$$th blocking element to $$$a_{i}$$$ when we enter $$$a_{i}$$$ in time $$$a_{i}+1$$$ for each $$$i$$$ and $$$k$$$, $$$p_{i}$$$ can also be calculated easily using binary lifting. The formulas are quite ugly but I tried my best to explain my logic.
Video Solution for Problem C.
[submission:1716C] Can somebody help with this submision, It takes O(m) time and again says time limit.
Can somebody help with this submision, It takes O(m) time and I get time limit. https://mirror.codeforces.com/contest/1716/submission/167315560
You fill the calc array until N in each test case, that's why it takes so much time — it now works in $$$O(tN)$$$
Thank you!!
F can also solved this way: The answer can be represented as:
If we let $$$p$$$ $$$=$$$ $$$ \frac {\lceil {m/2} \rceil}{(m - \lceil{m/2}\rceil)}$$$ then our objective is to compute the following sum:
Let:
Then it's clear that the answer is $$$dp(k) (m - \lceil{m/2}\rceil) ^ {n}$$$. Now it follows that:
where $$$s(i,j)$$$ is stirling number of the first kind. If we let $$$g_{i} = f_{i}(p) p^{i}$$$, then:
where $$$S(i,j)$$$ is stirling number of the second kind.
How to solve Question D during contest because I'm not able to think about such transitions between sum[] and dp[] array?
Can anyone explain how to approach these kind of dp questions?
У меня решена задача F, однако я в корне по понимаю второе предложение в ее разборе. Почему вдруг F^k можно биективно отразить в такие наборы, как это вообще связано логически? Объясните, пожалуйста.
немного рассуждений: Если посмотреть на любой набор из F нечетных и n — F четных, то таких (i1,...,ik) последовательностей сгенерируется F*F*F...*F = F^k, это вроде да, но с другой стороны, другой набор из F нечетных сгенерирует хоть и столько же наборов, но при этом могут быть совпадения. Например k = 4, и наборы (индексов) при F = 2: {1, 2} и {1, 3}. Первый набор {1, 2} сгенерирует (1, 1, 1, 1) и много других, и набор {1, 3} тоже сгенерирует (1, 1, 1, 1), поэтому у нас уже вклады размываются и это не будет F^k + F^k разных последовательностей (i1, ..., ik) на два этих набора, не сходится, значит неверно трактую
Объясните, пожалуйста, что это вообще значит и откуда берется, это же какая-то крайне запутаная вещь имхо
For problems like C, I found it's incredibly time-consuming for me to get every +1/-1/0 right, like the indices starting from 0/1, the number of steps required starting from the first cell/before the first cell. Does anybody have suggestions for dealing with this?
Is D's time limit too strict? Just adjusting some int/long long representations and whether printing the newline operator can change TLE to AC.
I replaced long long with int everywhere and it didn't give TLE (T_T).