Hope you enjoyed the problems.
The moves are symmetrical, so we can assume that $$$n≥m$$$. There is no solution if $$$m=1$$$ and $$$n≥3$$$, because one can only move up and down, but two consecutive down moves is required to reach $$$(n, 1)$$$.
Otherwise, there is a solution.
One should move downwards at least $$$n-1$$$ times, and it is forbidden to do that twice in a row, so another $$$n-2$$$ move is necessary ($$$1$$$ between each pair). So at least $$$n-1+n-2=2 \cdot n-3$$$ moves required. If $$$n+m$$$ is even, then one more, because the parity of $$$a+b$$$ changes after every move, and the parity is even before the first and after the last move, so the total number of moves should be even.
There is a construction for that lower bound:
Move alternately down and right. After reaching the $$$m$$$-th column, repeat the following sequence of moves: down, left, down, right. With this $$$4$$$ move long sequence, one can move down two times.
So we will reach $$$(n-1, m)$$$, then one more move is required, or we will reach $$$(n, m)$$$. If we add all of these moves, we get the formula: if $$$n+m$$$ is even then: $$$2 \cdot (m-1)+4 \cdot (n-m)/2=2 \cdot n-2$$$,and if $$$n+m$$$ is odd then: $$$2 \cdot (m-1)+4 \cdot (n-m-1)/2+1=2 \cdot n-3$$$.
#include <bits/stdc++.h>
using namespace std;
int t, n, m;
int main()
{
ios_base::sync_with_stdio(false);
cin >> t;
while (t--) {
cin >> n >> m;
if (n<m) {
swap(n, m);
}
if (m==1 && n>=3) {
cout << -1 << "\n";
} else {
cout << 2*n-2-(n+m)%2 << "\n";
}
}
return 0;
}
If there is no one between the $$$i$$$-th and $$$j$$$-th person then $$$max(a_i, a_j)$$$ free chairs should be between them.
So we should find a permutation $$$p$$$ of the array $$$a$$$, when $$$max(p_1, p_2)+max(p_2, p_3) ... +max(p_{n-1}, p_n)+max(p_n, p_1)$$$ is minimal.
We can assume that the array is non-decreasing ($$$a_i \leq a_{i+1}$$$). For each $$$i$$$ ($$$1≤i<n$$$) the $$$i$$$ largest elements from $$$a$$$ ($$$a_{n-i+1}$$$ ... $$$a_n$$$) will appear in the formula at least $$$i+1$$$ times. Every element occurs in two segments, and we only can count $$$i-1$$$ segments twice. So we get a lower bound for the number of free chairs: $$$a_2+a_3+...+a_{n-1}+2 \cdot a_n$$$.
This lower bound is reachable for the empty chairs if the permutation of $$$p$$$ is sorted. Because $$$max(p_1, p_2)=p_2$$$, $$$max(p_2, p_3)=p_3$$$, ... $$$max(p_{n-1}, p_n)=p_n$$$, and $$$max(p_n, p_1)=p_n$$$.
They also sit on $$$n$$$ chairs. If we add all of these, we get that the answer is YES if: $$$n+ \sum_{i=1}^{n}(a_i)-min(a_i)+max(a_i)≤m$$$. ($$$a_i$$$={$$$a_1, a_2, ... a_n$$$})
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
long long n, m;
cin >> n >> m;
long long sum=0, min_val=1e9, max_val=0;
for (int i=1; i<=n; i++) {
long long x;
cin >> x;
sum+=x, min_val=min(min_val, x), max_val=max(max_val, x);
}
cout << (n+sum-min_val+max_val<=m ? "YES" : "NO") << "\n";
}
return 0;
}
If the final array, is $$$b_1$$$, $$$b_2$$$ ... $$$b_n$$$, than the solution is surely unoptimal if there is an $$$2≤i≤n$$$, when $$$b_i>0$$$, and $$$b_i-a_i>b_{i-1}$$$, or $$$b_1>0$$$. Because there was one unnecessary move on $$$b_i$$$ or on $$$b_1$$$.
Similarly it is unoptimal, if $$$b_i<0$$$ and $$$b_i+a_i<b_{i+1}$$$ or $$$b_n<0$$$.
We can see, that there will be a $$$0$$$ in the final array. If we fix the position of the $$$0$$$ element, than we can set the other values greadily: find the smallest value for each element, which is bigger than the previous one, and similarly before that element.
We can fix each element, and calculate the answer for that in $$$O(n)$$$ time. The minimum of these values will be the final answer. So the final complexity is $$$O(n^2)$$$.
#include <bits/stdc++.h>
using namespace std;
long long n, a[5005], ans=1e18;
int main()
{
cin >> n;
for (int i=1; i<=n; i++) {
cin >> a[i];
}
for (int pos=1; pos<=n; pos++) {
long long prev=0, sum=0;
for (int i=pos-1; i>=1; i--) {
prev+=a[i]-prev%a[i];
sum+=prev/a[i];
}
prev=0;
for (int i=pos+1; i<=n; i++) {
prev+=a[i]-prev%a[i];
sum+=prev/a[i];
}
ans=min(ans, sum);
}
cout << ans << "\n";
return 0;
}
Let $$$dp_i$$$ be the answer for the first $$$i$$$ elements, and $$$v_{(i, j)}$$$ the value of the subarray $$$[i, j]$$$. With prefix sums it is easy to calculate $$$v_{(i, j)}$$$ quickly. With this we can get a $$$n^2$$$ solution: $$$dp_i=max(dp_j+v_{(j+1, i)})$$$ for $$$j<i$$$.
Lets call a segment winning, drawing, or losing, if the value of it is positive, $$$0$$$, or negative respectively. There is an optimal solution if the length of the drawing and losing segments are $$$1$$$. (The task is solvable without this observation, but it is harder to implement.) Proof: For a losing segment in the worst case we can get two losing segments with the same total length (the same value).
For a drawing segment with length $$$k$$$ if $$$k$$$ is even than the answer is the same if we split it into two segments with length $$$k/2$$$. For odd $$$k$$$ if the sum in the first $$$(k-1)/2$$$ or last $$$(k-1)/2$$$ elements is negative, than it is possible to increase the answer, otherwise one can split the segment into $$$(k-1)/2$$$, $$$1$$$, and $$$(k-1)/2$$$ long segments, and the answer for the new partition can't lessen.
So there is an optimal solution when only winning segments might be longer than $$$1$$$. It is easy to handle the $$$1$$$ long segments. For each $$$i$$$ ($$$1≤i≤n$$$) we have to find $$$j$$$, $$$0<=j<i$$$, where $$$v_{(j+1, i)}>0$$$, and $$$dp_j+v_{(j+1, i)}$$$ is maximal ($$$dp_0=0$$$).
If we store the prefix sums, and assign a permutation according to the prefix sums, than we can get all the positions $$$1≤j<i$$$, where $$$v_{(j+1, i)}>0$$$.
Than $$$v_{(j+1, i)}=i-j$$$.
So when we calculate $$$dp_i$$$, we should update with $$$dp_i-i$$$. This way, finding the optimal $$$j$$$ for each $$$i$$$ is just a prefix maximum. One can solve the problem with Fenwick tree or segment tree.
Final complexity is $$$O(n \cdot log(n))$$$.
#include <bits/stdc++.h>
using namespace std;
const int max_n=500005, inf=10000000;
int t, n, a[max_n], dp[max_n], ord[max_n], fen[max_n];
long long pref[max_n];
// Fenwick tree with prefix maximum
int lsb(int a) {
return (a & -a);
}
void add(int pos, int val) {
while (pos<=n) {
fen[pos]=max(fen[pos], val);
pos+=lsb(pos);
}
}
int ask(int pos) {
int val=-inf;
while (pos) {
val=max(fen[pos], val);
pos-=lsb(pos);
}
return val;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> t;
while (t--) {
cin >> n;
vector<pair<long long, int> > v;
for (int i=1; i<=n; i++) {
cin >> a[i];
pref[i]=pref[i-1]+a[i];
v.push_back({pref[i], -i});
}
sort(v.begin(), v.end());
for (int i=0; i<n; i++) {
ord[-v[i].second]=i+1;
}
// smaller prefix sum, smaller ord[i]
// if j<i they have equal prefix sums, than ord[i]<ord[j], this way we cannot count [j+1, ... i] as a winning segment
for (int i=1; i<=n; i++) {
fen[i]=-inf;
}
for (int i=1; i<=n; i++) {
dp[i]=(dp[i-1]+(a[i]<0 ? -1 : a[i]>0 ? 1 : 0));
// The last segment is 1 long.
dp[i]=max(dp[i], ask(ord[i])+i);
if (pref[i]>0) dp[i]=i;
// Segment [1, ... i] is winning, so dp[i]=i;
add(ord[i], dp[i]-i);
}
cout << dp[n] << "\n";
for (int i=0; i<=n; i++) {
a[i]=0, dp[i]=0, ord[i]=0, fen[i]=0, pref[i]=0;
}
}
return 0;
}
Let's assume that there is a solution for $$$k$$$ half-queens. There are at least $$$n-k$$$ rows, and columns, which contains no half-queen.
If the uncovered rows are $$$r_1, r_2, ... r_a$$$, and the columns are $$$c_1, c_2, ... c_b$$$, (in increasing order), each diagonal (when the difference is a constant) contains at most one of the following $$$a+b-1$$$ squares: $$$(r_a, c_1), (r_a-1, c_1), ... (r_1, c_1), (r_1, c_2), ... (r_1, c_b)$$$. So a different half-queen attacks these cells.
We know that: $$$a+b-1≤k, n-k≤a, n-k≤b$$$, so $$$2 \cdot n≤3 \cdot k+1$$$. We have a lower bound for $$$k$$$. It turns out, that there is a consturction, for this $$$k$$$.
For $$$n=3 \cdot x+2$$$, $$$k=2 \cdot x+1$$$, and we can place $$$x+1$$$ in the top left corner, diagonally, and $$$x$$$ half queens in the bottom right corner diagonally.
For $$$n=8$$$ an optimal construction could be: $$$(1, 3)$$$, $$$(2, 2)$$$, $$$(3, 1)$$$, $$$(7, 8)$$$, $$$(8, 7)$$$.
If $$$n=3 \cdot x$$$, or $$$n=3 \cdot x+1$$$ we can put one or two half-queens, in the bottom right corner, and use the previous construction.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
cout << n/3+(n+2)/3 << "\n";
if (n==1) {
cout << 1 << " " << 1 << "\n";
return 0;
}
while (n%3!=2) {
cout << n << " " << n << "\n";
n--;
}
int a=(n+1)/3;
for (int i=1; i<=a; i++) {
cout << i << " " << a+1-i << "\n";
}
for (int i=1; i<a; i++) {
cout << n-a+i+1 << " " << n-i+1 << "\n";
}
return 0;
}
When an edge is removed, the two neighbouring vertex have the same parity of edges. We say that an edge is odd, if the parity is odd, and the edge is even otherwise.
One can see, that a vertex with even degree will have the same amount of odd and even edges. For a vertex with odd degree, there will be one more odd edge.
Starting from the leaves, we can decide the parity of each edge (an edge connected to a leaf is odd).
If there is a contradiction somewhere than the answer is NO.
Otherwise, there is a construction.
In each vertex decide the removal order of the outgoing edges. Any order is good, when it always changes parity, and ends with an odd edge. Consider the directed graph with these conditions. One can see, that this graph is acyclic, so there is a topological order of that graph which will satisfy all the conditions.
Also, it is possible to solve it recursively.
#include <bits/stdc++.h>
using namespace std;
const int c=200005;
int t, n, up[c];
bool parity[c], vis[c], no_sol;
vector<int> edges[c];
void dfs(int a) {
vis[a]=true;
int cnt[2]={0, 0};
for (auto x:edges[a]) {
if (!vis[x]) {
up[x]=a;
dfs(x);
cnt[parity[x]]++;
}
}
if (a!=1) {
if (parity[a]=(cnt[0]>=cnt[1]));
cnt[parity[a]]++;
}
if (cnt[1]-cnt[0]<0 || cnt[1]-cnt[0]>1) {
no_sol=1;
}
}
void solve(int a) {
vector<int> p[2];
for (auto x:edges[a]) {
if (x!=up[a]) {
p[parity[x]].push_back(x);
} else {
p[parity[a]].push_back(a);
}
}
int si=edges[a].size(), id=si%2;
for (int i=0; i<si; i++) {
int val=p[id].back();
if (val==a) {
cout << a << " " << up[a] << "\n";
} else {
solve(val);
}
p[id].pop_back();
id=1-id;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin >> t;
for (int test=0; test<t; test++) {
cin >> n;
for (int i=1; i<n; i++) {
int a, b;
cin >> a >> b;
edges[a].push_back(b), edges[b].push_back(a);
}
dfs(1);
if (no_sol) {
cout << "NO\n";
} else {
cout << "YES\n";
solve(1);
}
for (int i=1; i<=n; i++) {
parity[i]=0, up[i]=0, vis[i]=0;
edges[i].clear();
}
no_sol=0;
}
return 0;
}
1667E - Centroid Probabilities
Let $$$S=\frac{n+1}{2}$$$, $$$binom_{i, j}=\frac{i!}{j! \cdot (i-j)!}$$$, $$$dp_i$$$ the result of some precalculation (see below) and $$$ans_i$$$ the final answer for the $$$i$$$-th vertex.
Root the tree in vertex $$$1$$$. It is easy to see that in the possible trees the parent of vertex $$$2≤i≤n$$$ is smaller than $$$i$$$. The cetroid will be the largest vertex, where the size of its subtree is at least $$$S$$$.
For each $$$i$$$ first calculate: how many times the subtree of vertex $$$i$$$ will be at least $$$S$$$ ($$$dp_i$$$).
If $$$i=1$$$, then $$$dp_i=(n-1)!$$$. If $$$i>S$$$ then the $$$dp_i=0$$$. Otherwise ($$$2≤i≤S$$$) $$$dp_i = \sum_{j=S-1}^{n-i} binom_{n-i, j} \cdot j! \cdot (n-j-2)! \cdot (i-1)$$$
Proof: Let's assume that the size of the subtree is $$$j+1$$$. Color the subtree of vertex $$$i$$$ except $$$i$$$ red. Color every other vertex except the first and the $$$i$$$-th one to blue. We have $$$binom_{n-i, j}$$$ differnt colorings, because we have to choose $$$j$$$ values between $$$i+1$$$ and $$$n$$$. ($$$binom_{n-i, j}$$$)
There are $$$k$$$ possibilities for the parent of the $$$k$$$-th smallest blue or the $$$k$$$-th smallest red vertex. ($$$j! \cdot (n-j-2)!$$$)
The parent of the $$$i$$$-th vertex can be anything. ($$$i-1$$$)
If we multiply all of these, we get the described formula.
Then $$$ans_i=dp_i-\sum_{j=i+1}^{n} \frac{ans_j}{i}$$$
Proof: if the subtree of $$$i$$$ is at least $$$S$$$, and the centroid is not $$$i$$$, than the centroid is in the subtree of $$$i$$$. If $$$j$$$ is the centroid, there is exactly $$$\frac{1}{i}$$$ chance, that the path from $$$j$$$ to $$$1$$$ will cross vertex $$$i$$$. So we have to subract $$$\frac{ans_j}{i}$$$ for each $$$j>i$$$.
This gives us an $$$O(n^2)$$$ solution, which is slow because of the two sum formulas.
$$$\sum_{j=S-1}^{n-i} binom_{n-i, j} \cdot j! \cdot (n-j-2)! \cdot (i-1) = \sum_{j=S-1}^{n-i} \frac {(n-i)! \cdot j! \cdot (n-j-1)! \cdot (i-1)}{j! \cdot (n-i-j)!} = \sum_{j=S-1}^{n-i} \frac {(n-i)! \cdot (n-j-2)! \cdot (i-1)}{(n-i-j)!}$$$
$$$(n-i)! \cdot (i-1)$$$ is a constant (for fixed $$$i$$$), and the difference between $$$n-j-2$$$ and $$$n-i-j$$$ is $$$i-2$$$, is also a constant for fixed $$$i$$$. If we reverse the inv array, then we can calculate $$$\sum_{j=S-1}^{n-i} \frac{(n-j-2)!}{(n-i-j)!}$$$ in $$$n \cdot log(n)$$$ time for $$$2≤i≤S$$$ with ntt.
We can do the calculation of $$$ans_i$$$ in linear time if we store the suffix sums of the latter values.
This gives us the final complexity: $$$O(n \cdot log(n))$$$.
#include <bits/stdc++.h>
using namespace std;
// ntt - this code is not mine
const int _ = 1 << 20 , mod = 998244353 , G = 3;
int upd(int x) {
return x + (x >> 31 & mod);
}
int add(int x , int y) {
return upd(x + y - mod);
}
int sub (int x , int y){
return upd(x - y);
}
int mul (int a, int b) {
return 1ll*a*b%mod;
}
int poww(long long a , int b) {
int tms = 1;
while (b) {
if(b & 1) tms = tms * a % mod;
a = a * a % mod; b >>= 1;}
return tms;
}
int dir[_] , need , invnd , w[_];
void init(int len){
static int L = 1; need = 1;
while (need < len) need <<= 1;
invnd = poww(need , mod - 2);
for (int i = 1 ; i < need ; ++i) dir[i] = (dir[i >> 1] >> 1) | (i & 1 ? need >> 1 : 0);
for (int &i = L ; i < need ; i <<= 1) {
w[i] = 1;
int wn = poww(G , mod / i / 2);
for(int j = 1 ; j < i ; ++j) w[i + j] = 1ll * w[i + j - 1] * wn % mod;
}
}
void dft(vector < int > &arr , int tmod){
arr.resize(need);
for (int i = 1 ; i < need ; ++i) {
if (i < dir[i]) swap(arr[i] , arr[dir[i]]);
}
for(int i = 1 ; i < need ; i <<= 1) {
for (int j = 0 ; j < need ; j += i << 1) {
for (int k = 0 ; k < i ; ++k) {
int x = arr[j + k] , y = 1ll * arr[i + j + k] * w[i + k] % mod;
arr[j + k] = add(x , y); arr[i + j + k] = sub(x , y);
}
}
}
if(tmod == -1) {
reverse(arr.begin() + 1 , arr.end());
for(auto &t : arr) {
t = 1ll * t * invnd % mod;
}
}
}
vector<int> multiply(vector<int> const& a, vector<int> const& b) {
init(a.size()+b.size());
vector<int> fa(a.begin(), a.end()), fb(b.begin(), b.end());
dft(fa, 1);
dft(fb, 1);
for (int i = 0; i < need; i++) {
fa[i] = 1ll * fa[i] * fb[i] % mod;
}
dft(fa, -1);
return fa;
}
const int max_n=200005;
long long n, fact[max_n], inv[max_n], dp[max_n], ans[max_n], suf, s;
vector<int> v1, v2, v3;
long long po(long long a, long long b) {
long long res=1;
while (b) {
if (b%2) res=res*a%mod;
a=a*a%mod;
b/=2;
}
return res;
}
int main()
{
cin >> n;
s=(n+1)/2;
fact[0]=1, inv[0]=1;
for (int i=1; i<=n; i++) {
fact[i]=fact[i-1]*i%mod;
inv[i]=po(fact[i], mod-2);
}
for (int i=0; i<s-1; i++) {
v1.push_back(fact[i]);
v2.push_back(inv[i]);
}
reverse(v2.begin(), v2.end());
v3=multiply(v1, v2);
dp[1]=fact[n-1];
for (int i=2; i<=s; i++) {
dp[i]=fact[n-i]*v3[i+s-4]%mod*(i-1)%mod;
}
for (int i=s; i>=1; i--) {
ans[i]=(dp[i]-suf*po(i, mod-2)%mod+mod)%mod;
suf=(suf+ans[i])%mod;
}
for (int i=1; i<=n; i++) {
cout << ans[i] << " ";
}
cout << "\n";
return 0;
}
Border: cells in the first or last row or first or last column. One can see that on the border both the black and the white part is connected. So there is no solution if there is a BWBW subsequence on the border.
Otherwise there is a solution.
Solve an easier task first. Assume that there is no colored cell on the border.
Then there is a nice construction. Color white all cells in the first column, and in the $$$4*k+2$$$-nd and $$$4*k+3$$$-rd row, which is not in the last column.
One can see that the stripes (2 consequtive white rows) are connected, because no two initially colored cell shares a corner. Also different stripes are connected to each other because of the left column. If there is a white cell in the middle of a black stripe, then it must be orthogonally adjacent to a white stripe.
Similarly the black cells will be connected too.
If there are colored cells on the border, than it is impossible to do exactly this. But the most of the cells might be the same: the white stripes, and the white column on the left side. In this way, the white part is connected. For the black part, there might be $$$3$$$ issues: the border is not connected to the black stripes, there are isolated black cells in the $$$2$$$-nd or $$$n-1$$$-th row, and different black stripes might be unconnected. All of these issues is solvable locally with changing the color of some cells from white to black and vice versa.
#include <bits/stdc++.h>
using namespace std;
const int c=505;
int t, n, m, fix[c][c], ans[c][c], rotcnt, change, old_cl, new_cl;
int fix2[c][c], ans2[c][c];
void color_boundary() {
for (int cnt=1; cnt<=2; cnt++) {
for (int j=2; j<=m; j++) {
if (!ans[1][j]) ans[1][j]=ans[1][j-1];
if (ans[1][j]!=ans[1][j-1]) change++;
}
for (int i=2; i<=n; i++) {
if (!ans[i][m]) ans[i][m]=ans[i-1][m];
if (ans[i][m]!=ans[i-1][m]) change++;
}
for (int j=m-1; j>=1; j--) {
if (!ans[n][j]) ans[n][j]=ans[n][j+1];
if (ans[n][j]!=ans[n][j+1]) change++;
}
for (int i=n-1; i>=1; i--) {
if (!ans[i][1]) ans[i][1]=ans[i+1][1];
if (ans[i][1]!=ans[i+1][1]) change++;
}
if (!ans[1][1]) ans[1][1]=1;
if (cnt==1) change=0;
}
}
void rotate_90() {
rotcnt++;
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
ans2[i][j]=ans[i][j], fix2[i][j]=fix[i][j];
}
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
ans[j][n+1-i]=ans2[i][j];
fix[j][n+1-i]=fix2[i][j];
}
}
swap(n, m);
}
void good_rotation() {
for (int cnt=1; cnt<=4; cnt++) {
bool same=1, opposite=0;
for (int i=1; i<=n; i++) {
if (ans[i][1]!=ans[1][1]) same=0;
if (1<i && i<n && ans[1][1]!=ans[i][m]) opposite=1;
}
if (!same || !opposite) rotate_90();
}
}
void color_the_stripes() {
for (int i=2; i<n; i++) {
for (int j=2; j<m; j++) {
if (!fix[i][j]) {
if (i%4==2 || i%4==3) ans[i][j]=old_cl;
else ans[i][j]=new_cl;
}
}
}
}
void avoid_touching() {
for (int i=1; i<n; i++) {
if (ans[i][m-1]==ans[i+1][m] && ans[i+1][m-1]==ans[i][m] && ans[i][m]!=ans[i+1][m]) {
if (!fix[i][m]) ans[i][m]=3-ans[i][m];
else ans[i+1][m]=3-ans[i+1][m];
}
}
}
void boundary_stripe_connection() {
int first=0, last=0;
for (int i=1; i<=n; i++) {
if (ans[i][m]==new_cl) {
if (!first) first=i;
last=i;
}
}
if (first==0 || (last>3 && first<n-2)) return;
if (last<=3 && fix[4][m-1]==old_cl) {
for (int i=3; i<=5; i++) {
ans[i][m]=new_cl;
}
return;
}
if (first>=n-2 && fix[n-3][m-1]==old_cl) {
for (int i=n-4; i<=n-2; i++) {
ans[i][m]=new_cl;
}
return;
}
int x=(last<=3 ? 2 : n-2);
for (int i=x; i<=x+1; i++) {
for (int j=m-1; j<=m; j++) {
if (!fix[i][j]) ans[i][j]=new_cl;
}
}
}
void connect_isolated_point(int x, int y) {
if (ans[x-1][y]==new_cl || ans[x+1][y]==new_cl || ans[x][y+1]==new_cl) return;
int x1=(x==2 ? 1 : n), x2=(x==2 ? 2 : n-1), x3=(x==2 ? 3 : n-2), x4=(x==2 ? 4 : n-3);
if (y<=m-2 && ans[x1][y+2]==new_cl) {
ans[x1][y]=new_cl;
ans[x1][y+1]=new_cl;
return;
}
if (y<=m-2 && ans[x2][y+2]==new_cl) {
ans[x2][y+1]=new_cl;
return;
}
if (fix[x4][y]!=old_cl) {
ans[x3][y]=new_cl;
} else {
int y2=(y+1<m ? y+1 : y-1);
ans[x2][y2]=new_cl;
ans[x3][y2]=new_cl;
}
}
void bridge_through_the_stripe(int x) {
for (int j=2; j<=4; j++) {
bool good=1;
for (int i=x-1; i<=x+2; i++) {
if (fix[i][j]==old_cl) good=0;
}
if (good) {
ans[x][j]=new_cl;
ans[x+1][j]=new_cl;
return;
}
}
for (int i=x-1; i<=x+2; i++) {
if (!fix[i][3]) ans[i][3]=new_cl;
}
if (fix[x-1][3]) {
ans[x-1][2]=old_cl;
ans[x][4]=new_cl;
}
if (fix[x+2][3]) {
ans[x+2][2]=old_cl;
ans[x+1][4]=new_cl;
}
if (fix[x][3] || fix[x+1][3]) {
ans[x][2]=new_cl;
ans[x+1][2]=new_cl;
}
}
int main()
{
cin >> t;
for (int tc=1; tc<=t; tc++) {
cin >> n >> m;
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
char c;
cin >> c;
fix[i][j]=(c=='B' ? 1 : c=='W' ? 2 : 0);
ans[i][j]=fix[i][j];
}
}
color_boundary();
if (change>=4) {
cout << "NO\n";
} else {
good_rotation();
old_cl=ans[1][1], new_cl=3-ans[1][1];
color_the_stripes();
avoid_touching();
boundary_stripe_connection();
for (int j=2; j<m; j++) {
if (fix[2][j]==new_cl) connect_isolated_point(2, j);
if (fix[n-1][j]==new_cl) connect_isolated_point(n-1, j);
}
for (int i=6; i<=n-6; i+=4) {
if (ans[1][1]==ans[i][m] || ans[1][1]==ans[i+1][m]) bridge_through_the_stripe(i);
}
while (rotcnt<4) rotate_90();
cout << "YES\n";
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
cout << (ans[i][j]==1 ? "B" : "W");
}
cout << "\n";
}
}
rotcnt=0, change=0;
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
fix[i][j]=0, ans[i][j]=0;
fix[j][i]=0, ans[j][i]=0;
}
}
}
return 0;
}
Great contest and lighting fast editorial l.thora to rukoo( wait a bit) , d was good almost did it in contest
what's there to downvote?
thanks for superfast editorial
Fastest editorial ?
I'm happy that I actually had some approach for problem D instead of being totally clueless, which is a huge improvement
Please, add option “VERY bad problem” to C
E is a lot worse
How would one come up with the solution of div1C? I can't get even remotely close to it
You think "how can I save k queens from the trivial solutions of n queens?". Then you note that the issue in doing so is that you have kxk region that is not covered by horizontal and vertical lines (determined by not necessarily consecutive rows and columns). The path of least resistance is to hope for arrangements when that region is simply a kxk square. You need to cover it by diagonals and you play a lil bit on paper with construction. Moving in knight's move fashion is an often trick when you are covering consecutive diagonals.
FFT in E? I believe I solved it in much easier way (15 seconds after the contest end though...)
big[i] is the probability that subtree of vertex i has at least (n+1)/2 vertices, cent[i] is the probability that i-th vertex is the answer
What is Newt()? Quick_Power?
https://codeforces.net/contest/1667/submission/154135370
For the big[] part, is it simply doing algebra or does it imply a prettier combinatorial explanation?
There is a nice combinatorial explanation. Note that there is an easy bijection between all permutations of n numbers, where numbers 1..i are in order and 1 has to be the first number of whole permutation and ways of how do you connect guys i+1..n — you start from 1,2,...,i and you insert next numbers one by one into some place in this permutation, but not at the beginning. The number before new number is the one it connects to. (We don't care how guys 1..i are connected between themselves in order to determine whether subtree of i is big). Let's remove that 1 from our permutation. In this bijection, the subtree of i is big if and only if all numbers 2..i are in the first half of that permutation, so the formula from my code follows.
Nice idea, Thanks!
What is the meaning of "If we store the prefix sums, and assign a permutation according to the prefix sums,..."?
Greter prefix sum — greater value in the permutation.
For example: array: $$$[1, 3, -5, 4, 2]$$$, prefix sums: $$$[1, 4, -1, 3, 5]$$$, permutation: $$$[2, 4, 1, 3, 5]$$$
Ok...
But still, "So there is an optimal solution when only winning segments might be longer than 1. It is easy to handle the 1 long segments. For each i (1≤i≤n) we have to find j, 0<=j<i, where v(j+1,i)>0, and dpj+v(j+1,i) is maximal (dp0=0)."
Why $$$v(j+1,i)$$$ has to be positive? Is this somehow different from the initial, $$$n^2$$$ solution? And how/why does this prefix-sum ordered permutation help finding $$$j$$$ ?
The paragraphs at the beginning of the editorial explain why it's optimal to only consider indexes $$$j < i$$$ such that $$$v(j+1, i)$$$ is positive or the case when the last element is in a segment by itself (that is $$$j = i-1$$$).
case 0:
The case when the last element is in a segment by itself, is covered by $$$dp_i = dp_{i-1} + v(i,i)$$$.
case 1:
If $$$v(j+1,i)$$$ is negative, then we can split the segment $$$[j+1,i]$$$ into $$$i-j$$$ segments of length $$$1$$$, and the sum of values over these segments of size 1 can't be less than $$$v(j+1,i)$$$. However, the scenario when $$$[j+1,i]$$$ is split into segments of size 1 is already covered in case 0.
case 2:
If $$$v(j+1,i) = 0$$$, we can also split $$$[j+1,i]$$$ into two or three segments, the last of which (ending at $$$i$$$) either has positive value, or is of size 1, and moreover the sum of values over these (two or three) segments is not less than $$$v(j+1,i)$$$. (Look at the editorial to understand how).
This means we don't have to worry about $$$j$$$ when $$$v(j+1,i)$$$ is not positive.
By the previous observation, $$$dp_i$$$ is either equal to:
$$$dp_i = dp_{i-1} + v(i,i)$$$ (last element is in a segment by itself), or
$$$dp_i = max_{v(j+1,i) >0} (dp_j + v(j+1,i))$$$ -- the maximum over all $$$j$$$ such that $$$v(j+1, i)$$$ is positive. By definition, if $$$v(j+1,i)$$$ is positive, then $$$v(j+1,i) = i-j$$$. But $$$v(j+1,i)$$$ is positive if and only if $$$pref(j) < pref(i)$$$.
So we can rewrite the second equality as:
$$$dp_i = max_{pref(j) < pref(i)}(dp_j + i - j)$$$.
How do we quickly find maximum of $$$dp_j-j$$$ over the interval $$$(-\infty, pref(i))$$$ ? We could use Segment Tree (or Fenwick Tree), but the values of $$$pref(i)$$$ can get very large. But we only need the relative order of $$$pref(i)$$$, so we can normalize the array $$$pref$$$ and replace it with values from $$$0$$$ to $$$N$$$.
Thanks for this detailed explanation!
How does one compute the permutation? I can think of O(nlogn) way but is there better?
I'm not sure if there is better, but O(n log n) is good enough for the bounds of this problem.
In the editorial of problem F of div1, Did the author know that no one will solve it because it's so hard, Or he has removed the editorial of it now?
I removed before the last minute.
Another optimal construction for C that's different from the editorial looks like alternating knights moves from the bottom left like this:
Yup. The motivation for me was to put one half-queen on an infinite board. Then try to repeatedly cover some of the closest uncovered squares, hence the knight move. All the while trying to keep the construction as square as possible, hence the alternating knight moves.
Additionally, this approach doesn't have special cases for $$$n = 1$$$ or $$$n = 2$$$.
KAN, have you really reviewed these problems carefully?
My solution for Div2D/Div1B uses a map instead of segment/Fenwick trees: 154120734 (hope it passes system tests :D UPD it did!).
Let $$$dp_i$$$ be the answer for the array $$$a_1, a_2, \dots, a_i$$$. Then
$$$dp_i = \max_{j < i} dp_j + (i - j) * sign(a_{j + 1} + ... + a_{i})$$$.
Since, as proven in the editoral, losing and drawing segments can always be of length 1, we can account for them just by initializing $$$dp_i$$$ as $$$dp_{i - 1} + sign(a_i)$$$. Now in our maximum we only have to consider segments which have a positive sum, because only they can improve $$$dp_i$$$. If the segment from $$$j + 1$$$ to $$$i$$$ has a positive sum, then $$$p_i > p_j$$$, where $$$p$$$ are the prefix sums. We can rewrite
$$$dp_i = \max(dp_{i - 1} + sign(a_i), \max_{j < i, p_j < p_i} dp_j + (i - j))$$$.
We can store pairs $$$(p_j, dp_j - j)$$$ in a map and find our maximum using lower/upper_bound on that map. We have to keep it sorted by $$$dp_j - j$$$. This is a known trick where on every insert we remove all the pairs which have larger $$$p_j$$$ but smaller $$$dp_j - j$$$. In total there will be at most $$$O(n)$$$ removals.
The final complexity is $$$O(n \log n)$$$.
Looks like a cool trick. Thanks for sharing.
Thank you! I wonder if your solution can be considered forward-style dp as opposed to the editorial's backward style dp.
I think by adapting the solution to more of a forward style, you get the one from the editorial. :)
If you manually update all of the relevant states every time, the solution will be $$$O(n^2)$$$, which is impossible to fit under the constraints. However, you can think of Fenwick/segment tree as a way of updating all the states at once. This is where you arrive at the editorial solution.
If you prefer command line, checkout CF Doctor for more flexibility and faster feedback.
If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.
Divison 2
Divison 1
If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).
Overall great contest. But I have a problem. I implemented the solution to div 2. C (make it increasing) which is same as the official one. The complexity is O(n^2). The problem is it is in Python and it gets timed out on pretest 4. Is there any better solution to the problem or is the solution to just code in C++?
Try pypy 3 64-bit.
Otherwise you have to switch to big int I think which is too slow.
I TLE'd too with pypy 2 once before resending with pypy 3 64-bit (the second submission AC'd).
Oh. That hurts even more. I didn't change anything and submitted and it got accepte. Kinda sucks that i was correct but not really...
Thank you for this information, I had the same issue. Why does this make it faster, though?
If the integers you work with get too large python switch to big int (something like an array of ints) which tends to be very slow. Using regular (32-bit) python or pypy, this happens when n>2^31 (somewhat more than 2*10^9). With 64-bit pypy you can go up to 2^63 (like a c++ long long).
For example, if you multiply two numbers mod 10^9+7 in a loop you should use 64-bit pypy because otherwise it can be slow (you'll go above 32-bits with big ints). Modular addition and subtraction stay within 32-bit so they're not an issue.
In problem C, the numbers could be as large as 5000*10^9 (or as low as -5000*10^9) so they wouldn't necessarily fit a 32-bit int and therefore you need to use 64-bit pypy.
It didn't even occur to me that the sum might exceed a 32-bit int! Thanks for explaining.
:( I did equivalent O(N^2) in C#. Stress tested it at ~950ms. Just in case decided to tune my code: removing silly stuff like getting value of an array too often, adding early terminations, moving from Int64 to Int32. Resulted in ~550ms on my stress test. Probably a good thing I did it.
Judge ver. of D1C is good (educational?) problem!
Next, let's define
$$$A$$$ := the set of rows that don't have any half-queen
$$$B$$$ := the set of columns that don't have any half-queen
(For example, $$$A=\{2,3\}$$$ and $$$B=\{3\}$$$ for the sample output 3)
If half-queens were rooks, just check whether at least one of $$$A$$$ or $$$B$$$ is empty. How to deal with the diagonal line?
If $$$A=\{4,6\}$$$ and $$$B=\{3,5\}$$$, $$$C$$$ is $$$\{-1,1,3\}$$$ .
This set can be found by using FFT or bitset (memo: in the previous example, use FFT like $$$(x^4+x^6)$$$ $$$\times$$$ $$$(x^{k-5}+x^{k-3})$$$ $$$=$$$ $$$(x^{k-1}+2x^{k+1}+x^{k+3})$$$).
Finally, for each element $$$x$$$ of $$$C$$$, if there are no half-queens at $$$(p+x,p)$$$, return WA. Otherwise, return AC.
Not exactly sure what you mean here, but this sounds as a bad checker design practice, so I want to comment on this. In general checkers should be as independed from the solution as possible; in this case it should first check that the queens indeed cover the board in both the model and the participant's solutions, and only after that compare the number of half-queens used, and return one of ok, wa, or fail verdicts.
But i don't consider your judging method an efficient and easy one...
peti1234 Thanks for the fast editorial. Problem 1668B - Social Distance is an interesting problem. Nonetheless, only the Note section shows that it is possible to permute the order of the $$$n$$$ people. It would have been better to clarify in the problem statement that it is required to find if there exists a permutation of the $$$n$$$ people that satisfies the given social distance constraints.
Here is my solution to C, with no casework, and very simple to implement.
For some arrangement of $$$k$$$ queens, if we only consider the row and column moves, there is a $$$(n - k) \times (n - k)$$$ subgrid that we must additionally cover. Notice that the cells in the bottom edge and left most edge of the subgrid must be covered by different diagonals. Therefore we get the condition $$$2(n - k) - 1 \le k$$$.
Let's now try constructing it. If we try to use the top right $$$(n-k) \times (n-k)$$$ grid, as our subgrid, we must place the queens on $$$(i, p[i])$$$ for $$$1 \le i \le k$$$, where $$$p$$$ is some permutation of $$${1\ldots k}$$$. Then we notice that we need all different values between $$$[-n+k+1, n-k-1]$$$ to be taken by $$$i - p[i]$$$ for some $$$i$$$.
If we reverse we get all even differences for an odd length array, and all odd differences for a even length array.
So we just reverse the first $$$\lceil n/2 \rceil$$$ elements of the identity permutation, then the next $$$\lceil n / 2 \rceil - 1$$$ of the new permutation. This gives us all odd and even differences needed.
Thanks for a nice contest!
Regarding Div1C/Div2E: How do you guys approach such problems? I went in a completely wrong direction:(. Can you perhaps recommend some problems(in a similar spirit) or resources?
I want to share a formal and more "maths-ish" proof for observation in div2B
Given an increasing array $$$a[1\dots n]$$$, and $$$p[1\dots n]$$$ is a permutation of $$$a$$$. Then:
$$$P=\sum_{i=1}^{n} max(p[i],p[i + 1]) \ge 2a[n]+a[n-1]+\dots + a[2]$$$
To prove it we need lemma 1:
With every $$$a$$$,$$$b$$$,$$$c$$$, we have the inequality: $$$max(a,b)+max(b,c)\ge b + max(a,c)$$$
Proof
Consider 2 cases: $$$b$$$ is the largest of all, and $$$b$$$ is not. In the first case the lemma is obvious. In the second case, we can assume $$$a$$$ is the largest number. Then we can check cases of $$$c$$$ (Q.E.D).
The inequality holds if and only if $$$b$$$ is between $$$c$$$ and $$$a$$$ in real axis.
This lemma can be extended to $$$\sum_{i=1}^{m}max(x[i],x[i+1])\ge max(x[1],x[m+1])+\sum_{i=2}^{m}x[i]$$$.
Notice that if we do some cyclic shift to $$$p$$$, $$$P$$$ remains. Then we can assume $$$p[1]=a[1]$$$. Also let $$$p[k] = a[n]$$$. Now according to lemma 1 we have:
$$$P=\sum_{i=1}^{k-1}max(p[i],p[i+1])+\sum_{i=k}^{n}max(p[i],p[i+1])$$$
$$$\ge max(p[1],p[k])+\sum_{i=2}^{k-1}p[i]+max(p[k],p[n+1])+\sum_{i=k+1}^{n}p[i]$$$
$$$=2a[n]+\sum_{i=2}^{n-1}a[i]$$$. (Q.E.D)
The equality holds if and only if two subsequences of $$$p$$$ from $$$1$$$ to $$$k$$$ is monovariate. Which means the sitting order along the circle does not necessarily need to be increasing. For example if we get $$$a[1\dots 7] = {1;2;3;4;5;6;7;8;9} $$$ we can arrange them as $$$1-3-4-6-9-8-7-5-2-1$$$.
So when we calculate $$$dp_i$$$, we should update with $$$dp_i−i$$$. This way, finding the optimal $$$j$$$ for each $$$i$$$ is just a prefix maximum. One can solve the problem with Fenwick tree or segment tree.
Can someone explain why should we update $$$dp_i - i$$$
Because our dp transition is: $$$dp_i = max(dp_j + i - j)$$$, since $$$i$$$ is independent, we can rewrite it as follows: $$$dp_i = i + max(dp_j - j)$$$. As you can see, we always need $$$dp_j - j$$$ and what's why we update with this value.
Can you please attach this editorial to the contest attachments? Currently we just have the announcement attached.
MikeMirzayanov, I believe there are some violations of the rules in div2. kirya_molodec1, kirya_molodec2, kirya_molodec3, kirya_molodec4, kirya_molodec7 and kirya_molodec6's code are really confusing and similar, and they submitted each problem almost at the same time.
There is a spellling error in the solution of D, can you find it?
In solution of D optimal partition, in case of drawing segment. I don't understand how "For a drawing segment with length k if k is even than the answer is the same if we split it into two segments with length k/2". I have tried proving this, but I could not. Can someone share a proof for this please?
Say your initial segment has size $$$2*k$$$ and is drawing (the sum is $$$0$$$), so it contributes $$$0$$$ to the answer. If you split it into two halves of size $$$k$$$, then either both halves are also drawing, or one half is winning and the other is losing. In either case, the combined contribution of the two halves is also $$$0$$$.
I Made Video Solutions for div2 A-D in Case someone is Interested.
Can anybody suggest me some online blogs or youtube channels or any sites from where I can learn about "parity". In the Problem A, the knowledge about parity is must needed, so from where I can learn that well for CP?
If the number is odd then the parity is 1, if even then 0. In on word, parity is the remainder of any number divided by 2.
consructionin the end of the solution of EC is a nice problem!
Div1E is a nice problem, btw, An O(n) solution without NTT exists.
Solution to Div2C which would have given wrong answer 154180260 passed system tests. (Here I checked for 0 position only till n-1th position.) So, in main tests, there is no testcase in which answer ends with 0.
Your solution is correct. There is no test, where the answer ends with 0. In that case you can set the n-1-th position to 0, and make 1 move on the last element. The answer will be the same.
The answer ending in 0 must be smaller than that ending in the penultimate 0, because the first penultimate 0 does not move, then all the previous ones must become negative. In other words, the second penultimate one will become negative at least once, but the first penultimate one will remain unchanged. Considering that the second penultimate one remains unchanged, it will be better if the first penultimate one becomes positive, because the second penultimate one becomes 0,0 > negative.
Let me pen down a Div1F draft solution outline. I have been thinking of this problem for the day. Might be wrong.
Consider the colored points in the parameter and put them in a circular array. Remove consecutive duplicates in the circular array. If the length if the array is more than 2, there is no solution.
One side of the parameter will be white and another side will be black (The parameter might be all of the same color, we need to resolve that case as well). Build a black tree from a black point on the parameter.
problme B
sort it is easier
The problem C have a faster solution ? I wrongly calculate 5000 * 5000 equals 2.5e8 , so at first I think the O(n^2) solution will TLE.
NICE ROUND.
I try to solve div1 E by using some math solutions. I get the expression of this:
we set $$$ k = \frac{n - 1}{2} $$$, then for a point id $$$ 1 < u \le k + 1 $$$, the answer is: $$$ (2k - u + 1)! (u - 1)! (C^{u-1}_k - \sum\limits_{x=0}^{k-1}\frac{1}{2k-x}C^{u-1}_x) $$$
($$$C^a_b$$$ means combination number $$$\frac{b!}{a!(b-a)!}$$$, and when $$$a > b$$$ we set $$$C^a_b = 0$$$)
I judged this expression is right. However, I don't know how to deal with the expression $$$\sum\limits_{x=0}^{k-1}\frac{1}{2k-x}C^{u-1}_x$$$, since that's an $$$O(n^2)$$$ implementation for all $$$1<u\le k+1$$$.
Can someone help me? Thanks a lot.
Thanks to newbin or playf, with her help, I solved div1 E with solve combinatorial math skills. Maybe it looks a bit long, but it's easy to think(Especially for anyone who are bad at DP like me) Here are my solutions:
We set $$$k = \frac{n-1}{2}$$$. Consider a point $$$u (1 < u\le k + 1)$$$, let $$$c$$$ be the number of point $$$v$$$ such that $$$v > u$$$ and $$$u$$$ is not an ancestor of $$$v$$$. And $$$t$$$ be the number of $$$u$$$'s son. So $$$u$$$ has son $$$v_1,...,v_t$$$. The size of subtree rooted by $$$v_i$$$ is $$$n_i$$$($$$1\le i\le t$$$. So the answer of $$$u$$$ is:
$$$(u-1)!\sum\limits_{c=0}^{k-u+1}C_{n-u}^c(u-1)u...(u-2+c)\sum\limits_{t=0}^{\infty}\frac{1}{t!}\sum\limits_{n_1+n_2+...+n_t=n-u-c,1\le n_i\le k}\frac{(n-u-c)!}{n_1!...n_t!}(n_1-1)!...(n_t-1)!$$$
Let $$$f(x) = x+\frac{1}{2}x^2+...+\frac{1}{k}x^k$$$, the expressions equals to:
$$$(n-u)!(u-1)!\sum\limits_{c=0}^{k-u+1}C_{u-2+c}^c\sum\limits_{t=0}^{\infty}\frac{1}{t!}\sum\limits_{n_1+n_2+...+n_t=n-u-c,1\le n_i\le k}\frac{1}{n_1...n_t}$$$
$$$=(n-u)!(u-1)!\sum\limits_{c=0}^{k-u+1}C_{u-2+c}^c\sum\limits_{t=0}^{\infty}\frac{1}{t!}[x^{n-u-c}]f^t(x)$$$
$$$=(n-u)!(u-1)!\sum\limits_{c=0}^{k-u+1}C_{u-2+c}^c[x^{n-u-c}]e^{f(x)}$$$
Note that $$$f(x)=\ln(\frac{1}{1-x})-\frac{1}{k+1}x^{k+1}-\frac{1}{k+2}x^{k+2}-...$$$, we have:
$$$e^{f(x)}=\frac{1}{1-x}e^{-\frac{1}{k+1}x^{k+1}-\frac{1}{k+2}x^{k+2}...}=(1+x+...+x^{2k})(1-\frac{1}{k+1}x^{k+1}-\frac{1}{k+2}x^{k+2}-...-\frac{1}{k+k}x^{k+k})(mod\ x^n)$$$
so $$$[x^{k+d}]e^{f(x)}=1-(\frac{1}{k+1}+...+\frac{1}{k+d})$$$ for $$$1\le d \le k$$$.
Let $$$d = k - u + 1 - c$$$, the expression is:
$$$(n-u)!(u-1)!\sum\limits_{d=0}^{k-u+1}C_{k-1-d}^{u-2}[x^{k+d}]e^{f(x)}=(n-u)!(u-1)!(\sum\limits_{d=0}^{k-u+1}C_{k-1-d}^{u-2} - \sum\limits_{d=1}^{k-u+1}\frac{1}{k+d}\sum\limits_{y=d}^{k-u+1}C_{k-1-y}^{u-2})$$$
$$$=(n-u)!(u-1)!(C_{k}^{u-1} - \sum\limits_{d=1}^{k-u+1}\frac{1}{k+d}C_{k-d}^{u-1})=(n-u)!(u-1)!(C_{k}^{u-1} - \sum\limits_{x=0}^{k-1}\frac{1}{2k-x}C_{x}^{u-1})$$$
$$$=(n-u)!(u-1)!(C_{k}^{u-1} - \frac{1}{(u-1)!}\sum\limits_{x=u-1}^{k-1}\frac{x!}{(x-u+1)!(2k-x)})$$$
Consider $$$F(x)=\frac{(k-1)!}{k+1}+\frac{(k-2)!}{k+2}x+...+\frac{(k-k)!}{k+k}x^{k-1}$$$, $$$G(x)=\frac{1}{0!}+\frac{1}{1!}x+...+\frac{1}{(k-1)!}x^{k-1}$$$
We can calculate $$$\sum\limits_{x=0}^{k-1}\frac{x!}{(x-u+1)!(2k-x)}$$$ for all $$$1<u\le k$$$ by calculate $$$F*G$$$ with $$$NTT$$$ in $$$O(nlogn)$$$. And this problem can be solved.
For div.1 E, we need to calculate $$$\sum\limits_{j=S-1}^{n-i}\dfrac{(n-j-2)!}{(n-i-j)!}$$$. But if we multiply it with $$$\dfrac{1}{(i-2)!}$$$, it turns to $$$\sum\limits_{j=S-1}^{n-i}\dfrac{(n-j-2)!}{(n-i-j)!(i-2)!}=\sum\limits_{j=S-1}^{n-i}\dbinom{n-j-2}{i-2}=\dbinom{n-S}{i-1}$$$, which can be calculated in $$$O(1)$$$ time without NTT. And total time complexity is $$$O(n)$$$.
What is the reason that ratings are temporarily rolled back? I have this a few times. I am curious about the reason.
To remove cheater and calculate rating again.
Could someone clarify on (D)Optimal Partitions?: "There is an optimal solution if the length of the drawing and losing segments are 1. Proof: For a losing segment in the worst case we can get two losing segments with the same total length (the same value)." I get the first sentence, don't quite get the proof tho.
If the sum is negative in a segment then each element counts as -1. It can't lessen if you split it into shorter segments. Exapmle: [-3, 0, -1, -2] (the value is -4) -> [-3, 0], [-1, -2] (the value is -2+(-2)=-4)
Ah, got it now. Thanks for the clarification
Can someone please explain why this solution is not working for Div2 — Problem C https://codeforces.net/contest/1667/submission/154462818
I am fixing the first element of array in some range as of now but can be fixed by binary search exactly and then trying to figure out minimum value for all possible values.
Hello, peti1234, in editorial of Div.1-C problem, can you please tell how you came up with the inequality (a+b-1 <= k), I spent a lot of time on it but did not get it. And can you elaborate on "Let's assume that there is a solution for k queens" line ?? (Does it mean the k queens for whole grid satisfying the given condition) and if it is true then how there will be left uncovered rows and columns and use of variables (a,b) ?? Sorry for tagging but couldn't understand after spending quite a time on it.
Each cell is covered if there is a half-queen in the same row, same column, or same diagonal. A cell in the intersection of a non-covered row and column must be covered diagonally.
I showed that there are a+b-1 cells (on different diagonals) which must be covered diagonally. A half-queen can only cover 1, so we get the a+b-1 <= k inequality.
Can somebody explain " Any order is good, when it always changes parity, and ends with an odd edge. " in Div1 D? I cannot fully understand.
For each vertex we care about the order of the removed edges. There are two good orders: odd-even-odd-even......-odd or even-odd-even-odd.... even-odd.
Could you elaborate a bit more on this part?
i.e. how does finding that there are no contradictions when labeling each edge as odd/even guarantee we can ultimately remove all the edges in some order (in particular, according to the way it's done in the editorial's implementation)
Each edge has a parity, and each vertex has the same number of odd and even edges (or one more odd). For example, the edges are o_1, o_2, ... o_k, and e_1, e_2.. e_k, then a good removing order can be e_1, o_1, e_2, o_2..... e_k, o_k around this vertex.
In the directed graph (where each vertex is an edge in the normal graph) we add the following directed edges: e_1->o_1->e_2->o_2....... e_k->o_k.
And we do the same for each vertex. One can see that this directed graph will be acyclic, because it is a tree. So there is a topological order. This topological order will satisfy all the removing conditions described above.
Thanks. But what's the principle to assign the directions of an edge?
Assign parity to each edge.
This is a pretty easy tree dp problem. For each vertex (x) calculate the parity of all edges in its subtree. Than it is easy to calculate the parity, between x and the parent of x. Because x will have the same number of odd and even edges (or one more odd).
Got it. Many thanks.
in question 2 it was given sum of n dont exceed 10^5 but i got correct only after using ll sum.i got wrong when i used int sum . am i correct or wrong
Sum of n will not exceed 10^5, because it is the size of the input. Sum of a[i] can be larger, than 2^31.
For div1B/div2D, I'm new to Fenwich tree I have some questions
All the top solutions use Fenwich tree, is there any advantage of it compare to segment tree, or it's just easier to implement ?
Is Fenwich tree used only in prefix sum or does it have other use ?
Little bit faster, and easier to implement. There are other applications, but that's more complicated.
In div1E part where we calculate answer
Why
$$$j$$$ is the centroid, and there is a decreasing path from $$$j$$$ to $$$1$$$. If this path crosses $$$i$$$, than $$$i$$$ is not the centroid, but we counted this case in $$$dp[i]$$$.
On the path there is a unique vertex $$$k$$$, where $$$k>i$$$ and $$$p[k]<=i$$$ (the next vertex on the path). $$$p[k]$$$ can be anything, between $$$1$$$ and $$$i$$$ equiprobable, so there is a $$$1/i$$$ chance, that the path will go through $$$i$$$.
Hello can someone please help with my program for div1 B. It is giving WA on test 5 and I am not sure why. It is here: https://codeforces.net/contest/1667/submission/157232098
In Social Distance can we try the approach in which instead of assuming it as the circular geometry of chairs can we consider it as a linear geometry of chairs. If the person i want a[i] person should not sit on the right and left side of him then there should be a count of the sum which adds 2*a[i] and if that sum> n.o of chairs then it means then the arrangement is not possible otherwise it is possible. 1668B - Social Distance
No, we can't add
2*a[i]. With that approach you are using more chairs than needed. Imagine two people, one of them wants three empty chairs around them and other one wants two chairs. They sit next to each other. It would mean that there are ten empty chairs between them, but it's optimal to put only three chairs and both of them will be satisfied. You can think about it this way: we will use empty chairs for person who needs more chairs, but the person who needs less chairs is also satisfied because it needs at leasta[i]number of chairs so it can use those chairs as well.Easier implementation of B: 162562808.
I wasn't able to understand the implementation of "Make it increasing" problem. So, implemented in my own way, using the same concept as provided by editorial. Link