We'd like to thank you all for participating in the contest, and hope you enjoyed it. Hope to see you again next year!
The editorial for problem F will be added soon. It is now added.
1726A - Mainak and Array
Idea: anubhavdhar
Editorial: anubhavdhar
Which subsegments are relevant?
$$$a_n$$$ and $$$a_1$$$ can be taken up only by some combination of elements, not all.
#include<bits/stdc++.h>
using namespace std;
inline void test_case(){
int N;
cin >> N;
int A[N];
int ans = -1000000007;
for(int i = 0; i < N; ++i){
cin >> A[i];
}
for(int i = 0; i < N; ++i){
ans = max(ans, A[(i - 1 + N) % N] - A[i]);
}
for(int i = 1; i < N; ++i){
ans = max(ans, A[i] - A[0]);
}
for(int i = 0; i < N - 1; ++i){
ans = max(ans, A[N - 1] - A[i]);
}
cout << ans << '\n';
}
signed main(){
int test_case_number;
cin>>test_case_number;
while(test_case_number--)
test_case();
return 0;
}
t=int(input())
for _ in range(t):
n=int(input())
a=[int(x) for x in input().split()]
ans=max(a[-1]-min(a),max(a)-a[0])
for i in range(n):
ans=max(ans,a[i-1]-a[i])
print(ans)
1726B - Mainak and Interesting Sequence
Idea: anubhavdhar
Editorial: anubhavdhar
Which cases of $$$n$$$ and $$$m$$$ are easy to come up with a solution? Which cases is it easy to show that no solution exist?
What happens when $$$n$$$ is even but $$$m$$$ is odd?
#include<bits/stdc++.h>
using namespace std;
inline void test_case(){
int N, M;
cin >> N >> M;
if(((N % 2 == 0) && (M % 2 == 1)) || (M < N)){ // impossible cases, M < N and (M - odd, N - even)
cout << "NO\n";
}else if((N % 2) == 1){ // (N - odd)
cout << "YES\n";
for(int i = 1; i < N; ++i){
cout << "1 ";
}
cout << M - N + 1 << '\n';
}else{ // (N - even, M - even)
cout << "YES\n";
for(int i = 2; i < N; ++i){
cout << "1 ";
}
cout << (M - N + 2) / 2 << ' ' << (M - N + 2) / 2 << '\n';
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int test_case_number;
cin>>test_case_number;
while(test_case_number--)
test_case();
return 0;
}
import sys
input = sys.stdin.readline
t=int(input())
for _ in range(t):
n,m=map(int,input().split())
if n>m or (n%2==0 and m%2==1):
print("NO")
else:
print("YES")
ans=[]
if n%2==1:
ans.extend([1]*(n-1)+[m-n+1])
else:
ans.extend([1]*(n-2)+[(m-n+2)//2]*2)
print(*ans,sep=' ')
1726C - Jatayu's Balanced Bracket Sequence
Idea: Newtech66
Editorial: anubhavdhar
When can a connected component begin?
What when two '(' appear consecutively?
There are several ways to solve this problem (even bash-able with data structures like DSU and Segment Trees), but here is the one that is easiest to code.
#include<bits/stdc++.h>
using namespace std;
inline void test_case(){
int N;
string S;
cin >> N >> S;
N <<= 1;
int ans = 1; // ans = 1 + count("((")
for(int i = 1; i < N; ++i){
if(S[i] == '(' && S[i - 1] == '('){ // adding 1 for count("((")
++ans;
}
}
cout << ans << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int test_case_number;
cin>>test_case_number;
while(test_case_number--)
test_case();
return 0;
}
t=int(input())
for _ in range(t):
n=int(input())
s=input()
print(1+s.count("(")-s.count("()"))
1726D - Edge Split
Idea: Newtech66
Editorial: Newtech66
what does $$$m \le n + 2$$$ mean?
What if we look at a spanning tree?
Does any arbitrary spanning tree work?
#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
void dfs(int u,const vector<vector<pair<int,int>>>& g,vector<bool>& vis,vector<int>& dep,vector<int>& par,string& s)
{
vis[u]=true;
for(auto [v,idx]:g[u])
{
if(vis[v]) continue;
dep[v]=dep[u]+1;
par[v]=u;
s[idx]='1';
dfs(v,g,vis,dep,par,s);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
cin>>_;
while(_--)
{
int n,m;
cin>>n>>m;
vector<vector<pair<int,int>>> g(n+1);
vector<pair<int,int>> edges(m);
string s(m,'0');
for(int i=0;i<m;i++)
{
int u,v;
cin>>u>>v;
edges[i]={u,v};
g[u].push_back({v,i});
g[v].push_back({u,i});
}
vector<bool> vis(n+1,false);
vector<int> dep(n+1,0),par(n+1,-1);
dfs(1,g,vis,dep,par,s);
map<int,int> cnt;
for(int i=0;i<m;i++)
{
if(s[i]=='0')
{
cnt[edges[i].first]++;
cnt[edges[i].second]++;
}
}
if(cnt.size()==3)
{
int mn=2*n+5,mx=0;
for(auto [_,c]:cnt)
{
mn=min(mn,c);
mx=max(mx,c);
}
if(mn==mx && mn==2)
{
vector<pair<int,int>> can;
for(auto [v,_]:cnt) can.push_back({dep[v],v});
sort(can.rbegin(),can.rend());
int u=can[0].second;
int i,j; //replace edge i with edge j
for(auto [v,idx]:g[u])
{
if(s[idx]=='0') i=idx;
else if(v==par[u]) j=idx;
}
s[i]='1';
s[j]='0';
}
}
cout<<s<<endl;
}
return 0;
}
1726E - Almost Perfect
Idea: Newtech66
Editorial: Newtech66, anubhavdhar
How will the permutation cycles look like ?
Can we fix the number of the largest sized permutation cycles and calculate the number of perfect permutations?
How do we handle the smaller permutation cycles?
Key fact: There are only $$$3$$$ kinds of cycles in almost perfect permutations: $$$(i)$$$, $$$(i, j)$$$ and $$$(i, j, i + 1, j + 1)$$$.
Proof:
- Cycle size cannot be $$$3$$$: Take $$$(a, b, c)$$$ as a cycle with $$$a < b < c$$$, then $$$p_b = a$$$, $$$p^{-1}_b = c$$$, but $$$a < b < c$$$ implies $$$\lvert a - c \rvert > 1$$$.
- Cycle size cannot be more than $$$4$$$: Let $$$(a_1, a_2, a_3, a_4, a_5, \ldots, a_k)$$$ be consecutive elements of a cycle with size $$$k$$$ ($$$k \geq 5$$$). This means $$$a_1 \ne a_5$$$, but $$$\lvert a_1 - a_3 \rvert = 1$$$ and $$$\lvert a_3 - a_5 \rvert = 1$$$. For now assume $$$a_1 - a_3 = 1$$$ (proof of $$$a_1 - a_3 = -1$$$ is very similar). This means $$$a_3 - a_5 = 1$$$ (as $$$a_1 \ne a_5$$$) and similarly $$$a_7 - a_5 = 1$$$ and so on (if $$$k \leq 6$$$, $$$a_7$$$ is basically $$$a_{7 \bmod k}$$$; i.e. it wraps around). Now, we observe that if $$$a_1 = x$$$, then $$$a_3 = x - 1$$$, $$$a_5 = x - 2$$$, $$$a_7 = x - 3$$$. Therefore $$$a_{k + 1} = x - (k + 1)$$$. But since that cycle is of size $$$k$$$, $$$a_{k + 1}$$$ = $$$a_j$$$, for some $$$j \leq k$$$. Therefore $$$(x - (k + 1)) = (x - j)$$$, for some $$$j \leq k$$$; which means $$$(k + 1) \leq k$$$ — A contradiction.
- works for any $$$2$$$ sized cycles $$$(i, j)$$$: Proof is trivial.
- works for any $$$4$$$ sized cycles $$$(i, j, i + 1, j + 1)$$$: Proof is trivial.
- works only for $$$4$$$ sized cycles $$$(i, j, i + 1, j + 1)$$$: Consider cycle $$$(a, b, c, d)$$$. $$$\lvert a - c \rvert = 1$$$, $$$\lvert b - d \rvert = 1$$$. WLOG assume $$$a < c$$$ (therefore $$$c = a + 1$$$).
- Case I: $$$b < d$$$. therefore cycle is $$$(a, b, a + 1, b + 1)$$$ — of the given form.
- Case II: $$$b > d$$$. therefore cycle is $$$(a, d + 1, a + 1, d)$$$, which is same as $$$(d, a, d + 1, a + 1)$$$ — also of the given form.
Special thanks to Um_nik for sharing this solution!
Let's call $$$(i)$$$ as type $$$1$$$ cycles, $$$(i,j)$$$ as type $$$2$$$ cycles and $$$(i,j,i+1,j+1)$$$ as type $$$3$$$ cycles.
What we will do, is we will fix the number of type $$$3$$$ and type $$$2$$$ cycles and come up with a formula.
Let's say there are $$$s$$$ type $$$3$$$ cycles. We need to pick $$$2s$$$ numbers from $$$[1,n-1]$$$ such that no two are adjacent. The number of ways to do this is $$$\binom{n-2s}{2s}$$$. Then we can permute these numbers in $$$(2s)!$$$ ways and group the numbers in pairs of two, but these $$$s$$$ pairs can be permuted to get something equivalent, so we need to divide by $$$s!$$$. Hence we get:
Now, for the remaining $$$(n - 4s)$$$ elements, we know that only cycles will be of length $$$2$$$ or $$$1$$$. Let $$$I_k$$$ denote the number of permutations with cycles only of length $$$2$$$ and $$$1$$$. Then the final answer would be
Now, we would be done if we found out $$$I_k$$$ for all $$$k \in {1, 2, ... n}$$$. Observe that $$$I_1 = 1$$$ and $$$I_2 = 2$$$. Further for $$$k > 2$$$, the $$$k$$$-th element can appear in a cycle of length $$$1$$$, where there are $$$I_{k - 1}$$$ ways to do it; and the $$$k$$$-th element can appear in a cycle of length two, which can be done in $$$(k - 1) \cdot I_{k - 2}$$$ ways. Therefore we finally have:
This completes the solution. Time complexity: $$$\mathcal{O}(n)$$$.
Using the observations in Solution 1 this can be reduced to a counting problem using generating functions. Details follow.
Now, from the remaining $$$n-4s$$$ numbers, let's pick $$$2k$$$ numbers to form $$$k$$$ type $$$2$$$ cycles. We can do this in $$$\binom{n-4s}{2k}$$$ ways. Like before, we can permute them in $$$(2k)!$$$ ways, but we can shuffle these $$$k$$$ pairs around so we have to divide by $$$k!$$$. Also, $$$(i,j)$$$ and $$$(j,i)$$$ are the same cycle, so we also need to divide by $$$2^k$$$ because we can flip the pairs and get the same thing.
Finally, we have the following formula:
We can simplify this to get,
Now, observe that the answer is in the form of two nested summations. Let us focus on precomputing the inner summation using generating functions. We define the following generating function:
We can compute the first few terms of $$$e^x = \sum_{i \ge 0}{\frac{x^{i}}{i!}}$$$ and $$$e^{\frac {x^2}{2}} = \sum_{j \ge 0}{ \frac{x^{2j}}{2^j j!}}$$$; and using FFT, we can multiply these (in $$$\mathcal O(n \log n)$$$ time) to get the first few terms of $$$P(x) = e^{x + \frac{x^2}{2}}$$$.
Finally, we can get the answer (in $$$\mathcal O(n)$$$ time) as,
where $$$[x^m]F(x)$$$ is the coefficient of $$$x^m$$$ in the Taylor expansion of $$$F(x)$$$.
Time complexity: $$$\mathcal{O}(\max{(t_i)}\log{\max{(t_i)}} + \sum{t_i})$$$, where $$$t_i$$$ is the value of $$$n$$$ in the $$$i$$$-th test case.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
#ifdef LOCAL
#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
#define eprintf(...) 42
#endif
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
clock_t startTime;
double getCurrentTime() {
return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
const uint MOD = 998244353;
template<uint mod = MOD> struct mint { // 1000000007 1000000009
uint x;
mint() : x(0) {}
mint(ll _x) {
_x %= mod;
if (_x < 0) _x += mod;
x = _x;
}
mint& operator += (const mint &a) {
x += a.x;
if (x >= mod) x -= mod;
return *this;
}
mint& operator -= (const mint &a) {
x += mod - a.x;
if (x >= mod) x -= mod;
return *this;
}
mint& operator *= (const mint &a) {
x = (ull)x * a.x % mod;
return *this;
}
mint pow(ll pw) const {
mint res = 1;
mint cur = *this;
while(pw) {
if (pw & 1) res *= cur;
cur *= cur;
pw >>= 1;
}
return res;
}
mint inv() const {
assert(x != 0);
uint t = x;
uint res = 1;
while(t != 1) {
uint z = mod / t;
res = (ull)res * (mod - z) % mod;
t = mod - t * z;
}
return res;
}
mint& operator /= (const mint &a) {
return *this *= a.inv();
}
mint operator + (const mint &a) const {
return mint(*this) += a;
}
mint operator - (const mint &a) const {
return mint(*this) -= a;
}
mint operator * (const mint &a) const {
return mint(*this) *= a;
}
mint operator / (const mint &a) const {
return mint(*this) /= a;
}
bool sqrt(mint &res) const {
if (mod == 2 || x == 0) {
res = *this;
return true;
}
if (pow((mod - 1) / 2) != 1) return false;
if (mod % 4 == 3) {
res = pow((mod + 1) / 4);
return true;
}
int pw = (mod - 1) / 2;
int K = 30;
while((1 << K) > pw) K--;
while(true) {
mint t = myRand(mod);
mint a = 0, b = 0, c = 1;
for (int k = K; k >= 0; k--) {
a = b * b;
b = b * c * 2;
c = c * c + a * *this;
if (((pw >> k) & 1) == 0) continue;
a = b;
b = b * t + c;
c = c * t + a * *this;
}
if (b == 0) continue;
c -= 1;
c *= mint() - b.inv();
if (c * c == *this) {
res = c;
return true;
}
}
assert(false);
}
bool operator == (const mint &a) const {
return x == a.x;
}
bool operator != (const mint &a) const {
return x != a.x;
}
bool operator < (const mint &a) const {
return x < a.x;
}
};
template<uint mod = MOD> struct Factorials {
using Mint = mint<mod>;
vector<Mint> f, fi;
Factorials() : f(), fi() {}
Factorials(int n) {
n += 10;
f = vector<Mint>(n);
fi = vector<Mint>(n);
f[0] = 1;
for (int i = 1; i < n; i++)
f[i] = f[i - 1] * i;
fi[n - 1] = f[n - 1].inv();
for (int i = n - 1; i > 0; i--)
fi[i - 1] = fi[i] * i;
}
Mint C(int n, int k) {
if (k < 0 || k > n) return 0;
return f[n] * fi[k] * fi[n - k];
}
};
template<uint mod = MOD> struct Powers {
using Mint = mint<mod>;
vector<Mint> p, pi;
Powers() : p(), pi() {}
Powers(int n, Mint x) {
n += 10;
if (x == 0) {
p = vector<Mint>(n);
p[0] = 1;
} else {
p = vector<Mint>(n);
pi = vector<Mint>(n);
p[0] = pi[0] = 1;
Mint xi = x.inv();
for (int i = 1; i < n; i++) {
p[i] = p[i - 1] * x;
pi[i] = pi[i - 1] * xi;
}
}
}
Mint pow(int n) {
if (n >= 0)
return p[n];
else
return pi[-n];
}
};
template<uint mod = MOD> struct Inverses {
using Mint = mint<mod>;
vector<Mint> ii;
Inverses() : ii() {}
Inverses(int n) {
n += 10;
ii = vector<Mint>(n);
ii[1] = 1;
for (int x = 2; x < n; x++)
ii[x] = Mint() - ii[mod % x] * (mod / x);
}
Mint inv(Mint x) {
assert(x != 0);
uint t = x.x;
uint res = 1;
while(t >= (int)ii.size()) {
uint z = mod / t;
res = (ull)res * (mod - z) % mod;
t = mod - t * z;
}
return ii[t] * res;
}
};
using Mint = mint<>;
const int N = 300300;
Factorials F(N);
Mint F2[N];
Powers P2(N, Mint(2));
Mint invol[N];
void precalc() {
F2[0] = 1;
for (int i = 1; i < N; i++)
F2[i] = F2[i - 1] * (2 * i - 1);
invol[0] = invol[1] = 1;
for (int i = 2; i < N; i++)
invol[i] = invol[i - 1] + invol[i - 2] * (i - 1);
}
void solve() {
int n;
scanf("%d", &n);
Mint ans = 0;
for (int k = 0; 4 * k <= n; k++) {
Mint cur = invol[n - 4 * k];
cur *= F.C(n - 2 * k, 2 * k);
cur *= F2[k];
cur *= P2.pow(k);
ans += cur;
}
printf("%u\n", ans.x);
}
int main()
{
startTime = clock();
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
precalc();
int t;
scanf("%d", &t);
while(t--) solve();
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 300005;
/* PARTS OF CODE for fft taken from https://cp-algorithms.com/algebra/fft.html */
const ll mod = 998244353;
const ll root = 15311432; // which is basically 3 ^ 119
const ll root_1 = 469870224;
const ll root_pw = (1 << 23);
ll fact[MAXN + 1], ifact[MAXN + 1], sum_pow[MAXN + 1];
vector<ll> P(MAXN); // this will be the first few terms of e^(x + (x^2)/2).
ll fxp(ll a, ll n){ // returns a ^ n modulo mod in O(log(mod)) time
if(!n){
return 1;
}else if(n & 1){
return a * fxp(a, n ^ 1) % mod;
}else{
ll v = fxp(a, n >> 1);
return v * v % mod;
}
}
inline ll inverse(ll a){ // returns the modular inverse of
return fxp(a % mod, mod -2);
}
void init_fact(){ // initializes fact[ ] and ifact[ ]
fact[0] = ifact[0] = 1;
for(int i = 1; i <= MAXN; ++i){
fact[i] = fact[i - 1] * i% mod;
ifact[i] = inverse(fact[i]);
}
}
ll C(ll n, ll r){ // returns nCr in O(1) time
return (r > n || r < 0) ? 0 : (ifact[r] * ifact[n - r] % mod * fact[n] % mod);
}
// code for fft in O(nlogn)
void fft(vector<ll>& a, bool invert){
int n = a.size();
/// this does the bit inversion
for(int i = 1, j = 0; i < n; ++i){
int bit = n >> 1;
for(; j & bit; bit >>= 1){
j ^= bit;
}
j ^= bit;
if(i < j){
swap(a[i], a[j]);
}
}
for(int len = 2; len <= n; len <<= 1){
ll wlen = invert ? root_1: root;
for(int i = len; i < root_pw; i <<= 1){
wlen = wlen * wlen % mod;
}
for(int i = 0; i < n; i += len){
ll w = 1;
for(int j = 0; j < len / 2; ++j){
ll u = a[i + j], v = a[i + j + len / 2] * w % mod;
a[i + j] = u + v < mod ? u + v : u + v - mod;
a[i + j + len / 2] = u - v >= 0 ? u - v : u - v + mod;
w = w * wlen % mod;
}
}
}
if(invert){
ll n_1 = inverse(n);
for(ll& x : a){
x = x * n_1 % mod;
}
}
}
//multiplying two polynomials a and b using ntt in O(max(A, B)log(max(A, B))), where A, B are degrees of a, b respectively
vector<ll> mul(vector<ll> const& a, vector<ll> const& b){
vector<ll> fa(a.begin(), a.end()), fb(b.begin(), b.end());
int n = 1;
while(n < (int)a.size() + (int)b.size()){
n <<= 1;
}
fa.resize(n);
fb.resize(n);
fft(fa, false);
fft(fb, false);
for(int i = 0; i < n; ++i){
fa[i] = fa[i] * fb[i] % mod;
}
fft(fa, true);
while(fa.size() > 1 && fa[fa.size() - 1] == 0){
fa.pop_back();
}
return fa;
}
/* End of FFT Template */
inline void init(){ // precomputes the first few terms of P(x) = e^(x + (x ^ 2) / 2)
init_fact();
vector<ll> e_x(MAXN), e_x2_by2(MAXN);
ll modular_inverse_of_2 = (mod + 1) / 2;
for(int i = 0; i < MAXN; ++i){
e_x[i] = ifact[i]; // e^x = sum{x^k / k!}
e_x2_by2[i] = ((i & 1)) ? 0 : ifact[i / 2] * fxp(modular_inverse_of_2, i / 2) % mod; // e^((x^2)/2) = sum{(x^2k)/(k!.(2^k))}
}
P = mul(e_x, e_x2_by2); // P(x) = e^(x + (x ^ 2) / 2) = (e ^ x) . (e ^ ((x ^ 2) / 2))
}
void test_case(){
int N;
cin >> N;
ll ans = 0;
for(int s = 0; s <= N / 4; ++s){ // computing the answer for N using the precomputed P(x) polynomial
ans = (ans + fact[N - 2 * s] * ifact[s] % mod * P[N - 4 * s]) % mod;
}
cout << ans << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
init();
int test_case_number;
cin>>test_case_number;
while(test_case_number--)
test_case();
return 0;
}
1726F - Late For Work (submissions are not allowed)
Please note that it is no longer possible to submit solutions to this problem on Codeforces. You can read the details here.
Idea: little_angel
Editorial: Newtech66
The $$$d_i$$$ are irrelevant. Take partial sums and add them to each $$$c_i$$$ modulo $$$T$$$.
If your start time is fixed, it is never beneficial to wait at a green light. Drive whenever you can.
Visualise the problem as $$$n$$$ parallel lines, each coloured with a red and green interval. Now imagine the car moving up (and looping back at $$$T$$$) whenever it has to wait at a red light, and shooting to the right immediately when the lights are green.
You can model this as a shortest paths problem.
There are solutions to this problem using lazy segment trees, or say, sets and maps. I'll describe my own solution here, which converts the problem to a shortest paths problem.
First of all, the $$$d_i$$$ are irrelevant, since we can take partial sums and add them to $$$c_i$$$. In the final answer, just add the sum of all $$$d_i$$$.
Now, we can offset the green (or red) intervals by the modified $$$c_i$$$ to get new red and green intervals modulo $$$T$$$.
Imagine $$$n$$$ parallel lines of length $$$T$$$, with the corresponding intervals coloured red and green. Now, consider the intervals to be static. In this picture, the car can be visualised to be moving upwards along the line (looping back at $$$T$$$) when on red intervals and shooting to the right when it reaches a green interval. Notice that for a fixed starting time, it is always optimal to drive whenever you can. So essentially, fixing your start time also fixes your answer.
Now let's convert this to a graph. Notice that only the endpoints of green intervals matter, so overall, we'll have $$$2n$$$ nodes in our graph, plus a dummy node representing the start of the journey that connects to all endpoints that can be reached without being blocked by a red interval, and a dummy node representing the end of the journey that connects to all endpoints from which you can reach the end without being blocked by a red interval. So in total, $$$2n+2$$$ nodes.
We'll add an edge between two nodes with a weight equal to the amount of time we'll have to spend waiting for the red light to turn green. We can achieve this with a multiset storing all currently visible endpoints, and then doing a little casework to add edges from nodes blocked by the current red interval and then deleting them, and adding new ones. We'll do this only $$$\mathcal{O}(n)$$$ times. In the end, whatever is left in the multiset are all the visible endpoints and we can connect them to the dummy node for the end. We can repeat this in the backward direction to get the endpoints for the dummy node for the start, though in my code, I elected to do this with an interval union data structure.
Finally, just run Dijkstra's algorithm on this graph. The answer is the sum of all $$$d_i$$$ plus the shortest path between the dummy node for the start and the dummy node for the end.
Time complexity: $$$\mathcal{O}(n \log n)$$$
#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
const lol inf=1e18+8;
struct IntervalUnion{
set<int> lf,ri;
map<int,int> lr,rl;
void add(int l,int r)
{
if(!ri.empty())
{
auto it=ri.lower_bound(r);
if(it!=ri.end() && rl[*it]<=l) return;
}
while(!lf.empty())
{
auto it=lf.lower_bound(l);
if(it==lf.end() || r<*it) break;
int nl=*it;
r=max(r,lr[nl]);
rl.erase(lr[nl]);
ri.erase(lr[nl]);
lr.erase(nl);
lf.erase(nl);
}
while(!ri.empty())
{
auto it=ri.lower_bound(l);
if(it==ri.end() || r<rl[*it]) break;
int nl=rl[*it];
l=min(l,nl);
rl.erase(lr[nl]);
ri.erase(lr[nl]);
lr.erase(nl);
lf.erase(nl);
}
lf.insert(l);
ri.insert(r);
lr[l]=r;
rl[r]=l;
}
bool contains(int x)
{
auto it=ri.upper_bound(x);
if(it==ri.end()) return false;
return rl[*it]<=x;
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,t;
cin>>n>>t;
vector<pair<int,int>> gc(n);
for(auto& [g,c]:gc) cin>>g>>c;
lol sum=0;
for(int i=1;i<n;i++)
{
int d;
cin>>d;
sum+=d;
gc[i].second=(gc[i].second+(sum%t))%t;
}
vector<vector<pair<int,int>>> gr(2*n+2);
multiset<pair<int,int>> ms;
IntervalUnion iu;
for(int i=0;i<n;i++)
{
auto [g,c]=gc[i];
int l=(g-c+t)%t,r=t-c;
if(l<r)
{
while(!ms.empty())
{
auto it=ms.lower_bound({l,-1});
if(it==ms.end() || it->first>=r) break;
gr[2*i].push_back({it->second,r-it->first});
ms.erase(it);
}
}else
{
while(!ms.empty())
{
auto it=ms.lower_bound({l,-1});
if(it==ms.end() || it->first>=t) break;
gr[2*i].push_back({it->second,r+t-it->first});
ms.erase(it);
}
while(!ms.empty())
{
auto it=ms.lower_bound({0,-1});
if(it==ms.end() || it->first>=r) break;
gr[2*i].push_back({it->second,r-it->first});
ms.erase(it);
}
}
ms.insert({r%t,2*i});
ms.insert({(l-1+t)%t,2*i+1});
if(!iu.contains(r%t)) gr[2*i].push_back({2*n+1,0});
if(!iu.contains((l-1+t)%t)) gr[2*i+1].push_back({2*n+1,0});
if(l<r) iu.add(l,r);
else
{
iu.add(l,t);
iu.add(0,r);
}
}
while(!ms.empty())
{
auto it=ms.begin();
gr[2*n].push_back({it->second,0});
ms.erase(it);
}
//do dijkstra on this graph
vector<lol> sp(2*n+2,inf);
priority_queue<pair<lol,int>,vector<pair<lol,int>>,greater<pair<lol,int>>> pq;
pq.push({0,2*n});
sp[2*n]=0;
while(!pq.empty())
{
auto [dist,u]=pq.top();
pq.pop();
if(dist>sp[u]) continue;
for(auto [v,w]:gr[u])
{
if(dist+w<sp[v])
{
sp[v]=dist+w;
pq.push({sp[v],v});
}
}
}
cout<<sum+sp[2*n+1];
return 0;
}
1726G - A Certain Magical Party
Idea: Newtech66
Editorial: Newtech66, anubhavdhar
The happiness of a person can never decrease. It is obvious.
Let $$$T$$$ be the final value all elements are equal to. For all $$$x<T$$$, there can be at most one occurrence of $$$<x,1>$$$ in the array, where $$$<a,b>$$$ means a person with happiness $$$a$$$ and personality $$$b$$$.
There is only one possible $$$T$$$, given by $$$m+n-1$$$.
If it is possible to place multiple numbers in the order at a certain point (i.e. if there are multiple possible $$$<u,v>$$$ which when placed will all yield $$$<T,v>$$$), it is always better to prefer the larger number, and to place a number with personality $$$1$$$ over one with personality $$$0$$$ in case of a tie.
If $$$T=M$$$, the $$$<M,1>$$$ group is special, since it doesn't matter when you place it since the final happiness value will still be $$$M$$$, and it won't affect any other group's viability either.
For a valid ordering (if exists), the $$$0$$$ behaving people would be sorted in non-decreasing order of initial happiness.
For a valid ordering (if exists) and at any intermediate step, for all $$$1$$$ behaving people $$$<u, 1>$$$ yet to speak, the number of people with a larger happiness than $$$u$$$ cannot exceed $$$(T - u)$$$. In other words, if we placed $$$<u, 1>$$$ at any intermediate step, its final happiness would not exceed $$$T$$$.
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define FOR(i,N) for(i=0;i<(N);++i)
#define FORe(i,N) for(i=1;i<=(N);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,N) for(i=(N);i>=0;--i)
#define F0R(i,N) for(int i=0;i<(N);++i)
#define F0Re(i,N) for(int i=1;i<=(N);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,N) for(int i=(N);i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
#define ldd long double
using namespace std;
const int Alp = 26;
const int __PRECISION = 9;
const int inf = 1e9 + 8;
const ldd PI = acos(-1);
const ldd EPS = 1e-7;
const ll MOD = 998244353;
const ll MAXN = 260007;
const ll ROOTN = 320;
const ll LOGN = 18;
const ll INF = 1e18 + 1022;
int N;
int A[MAXN];
bool B[MAXN];
vi a[2];
pii people[MAXN];
ll fact[MAXN + 1], ifact[MAXN + 1];
ll fxp(ll a, ll n){
if(n == 0) return 1;
if(n % 2 == 1) return a * fxp(a, n - 1) % MOD;
return fxp(a * a % MOD, n / 2);
}
ll inv(ll a){
return fxp(a % MOD, MOD - 2);
}
void init(){
fact[0] = ifact[0] = 1;
F0Re(i, MAXN){
fact[i] = fact[i - 1] * i % MOD;
ifact[i] = inv(fact[i]);
}
}
struct SegTree_sum{
int st[4*MAXN];
void upd(int node, int ss, int se, int i, int val){
if(ss > i or se < i) return;
if(ss == se) {st[node] += val; return;}
int mid = (ss + se) / 2;
upd(node*2+1, ss, mid, i, val);
upd(node*2+2, mid+1, se, i, val);
st[node] = st[node*2+1] + st[node*2+2];
}
int quer(int node,int ss, int se, int l, int r){
if(ss > r or se < l) return 0;
if(ss >= l and se <= r) return st[node];
int mid = (ss + se)/2;
return quer(node*2+1, ss, mid, l ,r) + quer(node*2+2, mid + 1, se, l,r);
}
SegTree_sum() {F0R(i, MAXN*4) st[i] = 0;}
inline void update(int i, int val) {upd(0, 0, 2 * MAXN, i, val);}
inline int query(int l, int r) {return quer(0, 0, 2 * MAXN, l, r);}
}S_sum;
struct Segtree_max{
int st[4 * MAXN], lz[4 * MAXN];
inline void push(int node, int ss, int se){
if(lz[node] == 0) return;
st[node] += lz[node];
if(ss != se) lz[node * 2 + 1] += lz[node], lz[node * 2 + 2] += lz[node];
lz[node] = 0;
}
void upd(int node, int ss, int se, int l, int r, int val){
push(node, ss, se);
if(ss > r or se < l) return;
if(ss >= l and se <= r) {lz[node] += val; push(node, ss, se); return;}
int mid = (ss + se)/2;
upd(node * 2 + 1, ss, mid, l, r, val);
upd(node * 2 + 2, 1 + mid, se, l, r, val);
st[node] = max(st[node * 2 + 1], st[node * 2 + 2]);
}
int quer(int node, int ss, int se, int tar){
push(node, ss, se);
if(st[node] < tar || st[node] > tar){
return -1;
}
if(ss == se){
return ss;
}
int mid = (ss + se) / 2;
push(node * 2 + 1, ss, mid);
push(node * 2 + 2, mid + 1, se);
return (st[node * 2 + 2] < tar) ? quer(node * 2 + 1, ss, mid, tar) : quer(node * 2 + 2, mid + 1, se, tar);
}
Segtree_max() {F0R(i,MAXN * 4) st[i] = - 10 * MAXN, lz[i] = 0;}
inline void update(int l, int r, ll val) {if(l <= r) upd(0, 0, 2 * MAXN, l, r, val);}
inline ll query(int v) {return quer(0, 0, 2 * MAXN, v);}
}S_max;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
init();
cin >> N;
F0R(i, N){
cin >> A[i];
}
F0R(i, N){
cin >> B[i];
}
F0R(i, N){
a[B[i]].pb(A[i]);
people[i] = {A[i], B[i]};
S_sum.update(A[i], 1);
}
sort(all(a[0]));
sort(all(a[1]));
sort(people, people + N);
int m = people[0].ff;
int M = people[N - 1].ff;
int T = people[0].ff + N - 1;
if(m == M){
cout << fact[N] << '\n';
return 0;
}else if(people[0].ss == 0){
cout << "0\n";
return 0;
}else if(M > T){
cout << "0\n";
return 0;
}
int T_cnt = 0;
F0R(i, (int)a[1].size()){
if(a[1][i] == T){
++T_cnt;
}else if(i + 1 < (int)a[1].size() && a[1][i] == a[1][i + 1]){
cout << "0\n";
return 0;
}
}
ll ans = fact[N] * ifact[N - T_cnt] % MOD;
int p = -1, t = 0;
for(int x : a[0]){
if(p != x){
ans = ans * fact[t] % MOD;
t = 0;
}
++t;
p = x;
}
ans = ans * fact[t] % MOD;
int ptr = 0;
for(int x : a[1]){
if(x == T){
break;
}
int y = x + S_sum.query(x + 1, 2 * MAXN);
S_max.update(x, x, y + 10 * MAXN);
}
vii sequence(T_cnt, mp(T, 1));
F0R(i, N - T_cnt){
int zero = T + 1, one = T + 1;
if(ptr < (int)a[0].size() && S_sum.query(1, a[0][ptr] - 1) + a[0][ptr] == T){
zero = a[0][ptr];
}
one = S_max.query(T);
if(one == -1 && zero == T + 1){
cout << "0\n";
return 0;
}
if(zero == T + 1 || one >= zero){
sequence.pb({one, 1});
S_max.update(one, one, - 10 * N);
S_max.update(one + 1, T - 1, 1);
S_sum.update(one, -1);
S_sum.update(T, 1);
}else{
sequence.pb({zero, 0});
S_sum.update(zero, -1);
S_sum.update(T, 1);
S_max.update(zero, T - 1, 1);
++ptr;
}
}
cout << ans << '\n';
return 0;
}
1726H - Mainak and the Bleeding Polygon
Idea: anubhavdhar
Editorial: Newtech66, anubhavdhar
What role does the angles of the polygon play?
Is there some overlap in the area of two such regions? How do we account for that?
#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
using ldd=long double;
#define endl "\n"
const ldd PI=acos(-1.0);
const int ITERATIONS = 60;
const int PRECISION = 11;
struct Point{
lol x,y;
Point& operator-=(const Point& rhs){
x-=rhs.x,y-=rhs.y;
return *this;
}
friend Point operator-(Point lhs,const Point& rhs){
lhs -= rhs;
return lhs;
}
};
std::istream& operator>>(std::istream& is, Point& obj){
is>>obj.x>>obj.y;
return is;
}
ldd norm(Point p){
return p.x*p.x+p.y*p.y;
}
ldd cross_product(Point a,Point b){
return a.x*b.y-a.y*b.x;
}
ldd dot_product(Point a,Point b){
return a.x*b.x+a.y*b.y;
}
ldd getalpha(Point a,Point b,Point c){
return atan2l(cross_product(c-b,a-b),dot_product(c-b,a-b));
}
ldd getarea(Point a,Point b,Point c){
Point l1=c-b,l2=a-b;
return (dot_product(l1,l2)/cross_product(l1,l2)+atan2l(cross_product(l1,l2),-dot_product(l1,l2))*((norm(l1)*norm(l2))/(cross_product(l1,l2)*cross_product(l1,l2))+2.0))/16.0;
}
ldd f(ldd theta, ldd alpha){
return -cos(theta)+(1.0/tan(alpha))*sin(theta) + (cos(theta)*(1.0/tan(alpha))+sin(theta)) * (sin(2*theta)/2.0);
}
ldd g(ldd theta, ldd alpha){
return (cos(theta)*(1.0/tan(alpha))+sin(theta)) * (1.0 - cos(2*theta))/2.0;
}
ldd get_x(ldd y, ldd alpha, ldd & theta){
ldd lo = alpha, hi = PI;
for(int it = 0; it < ITERATIONS; ++it){
theta = (lo + hi) / 2.0;
ldd y_guess = g(theta, alpha);
if(y > y_guess){
hi = theta;
}else{
lo = theta;
}
}
return f(theta, alpha);
}
ldd A(ldd theta, ldd alpha){
return (sin(2 * (alpha - 3 * theta)) - sin(2 * (alpha - 2 * theta)) - 4 * sin(2 * (alpha - theta)) - sin(2 * (alpha + theta))
- 4 * theta * cos(2 * alpha) + 8 * theta - 2 * sin(4 * theta)) / (64.0 * sin(alpha) * sin(alpha));
}
ldd find_overlap_area(ldd alpha_1, ldd alpha_2, ldd L){
ldd lo = 0, hi = sin(max(alpha_1, alpha_2));
ldd theta_1 = PI, theta_2 = PI;
for(int it = 0; it < ITERATIONS; ++it){
ldd mid_y = (lo + hi) / 2;
ldd x1 = get_x(mid_y, alpha_1, theta_1);
ldd x2 = L - get_x(mid_y, alpha_2, theta_2);
if(x1 < x2){
hi = mid_y;
}else{
lo = mid_y;
}
}
return (A(PI, alpha_1) + A(PI, alpha_2)) - (A(theta_1, alpha_1) + A(theta_2, alpha_2));
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
vector<Point> v(n);
for(auto& p:v) cin>>p;
if(n == 4){
int MY = max({v[0].y, v[1].y, v[2].y, v[3].y});
int my = min({v[0].y, v[1].y, v[2].y, v[3].y});
int MX = max({v[0].x, v[1].x, v[2].x, v[3].x});
int mx = min({v[0].x, v[1].x, v[2].x, v[3].x});
if(MY - my == 1 || MX - mx == 1){
cout << fixed << setprecision(PRECISION) << 1.0 * (MY - my) * (MX - mx) << endl;
exit(0);
}
}
double ans=0.0;
for(int i=0;i<n;i++){
ans+=getarea(v[(i-1+n)%n],v[i],v[(i+1)%n]);
}
for(int i=0;i<n;i++){
Point a=v[(i-1+n)%n],b=v[i],c=v[(i+1)%n],d=v[(i+2)%n];
if(norm(c-b)<3){
ans-=find_overlap_area(getalpha(a,b,c),getalpha(b,c,d),sqrt(norm(c-b)));
}
}
cout<<fixed<<setprecision(PRECISION)<<ans;
return 0;
}
Vote for the problems here!
Feel free to vote for your opinion of each problem, and the best problem of the contest.
Editorial of F for those, who can't wait:
https://dmoj.ca/problem/tle16c8p6/editorial
How do you derive these equations?
Imagine rotating the chord so that it goes from tangent to the diagonal edge to tangent to the horizontal edge. That is, the angle the chord makes with the $$$x$$$-axis is given by $$$\pi-\theta$$$, where $$$\theta$$$ goes from $$$\alpha$$$ to $$$\pi$$$.
Let $$$\ell(\theta)$$$ denote the position of the leftmost vertex of the chord (lying on the diagonal line), and $$$r(\theta)$$$ denote the position of the rightmost vertex of the chord (lying on the $$$x$$$-axis). By the Law of Sines, $$$|\ell(\theta)|=\frac{\sin\theta}{\sin\alpha}$$$ while $$$|r(\theta)|=\frac{\sin(\theta-\alpha)}{\sin \alpha}$$$.
Let $$$x(\theta)$$$ and $$$y(\theta)$$$ be as defined in the editorial. It remains to show that $$$m(\theta)=(x(\theta),y(\theta)))$$$ is the intersection of the line segments $$$\overline{u(\theta)\ell(\theta)}$$$ and $$$\overline{u(\theta+\epsilon)\ell(\theta+\epsilon)}$$$ as $$$\epsilon\to 0$$$. Indeed, we can verify that
$$$\frac{-d |\ell(\theta)|}{d |r(\theta)|}=\frac{-\cos\theta}{\cos(\theta-\alpha)}\implies \frac{|\ell(\theta)-m(\theta)|}{|m(\theta)-r(\theta)|}=\frac{-d |\ell(\theta)|\sin(\theta-\alpha)}{d |r(\theta)|\sin \theta}=\frac{-\cos\theta \sin(\theta-\alpha)}{\cos(\theta-\alpha) \sin \theta}.$$$
It follows that
$$$m(\theta)=\frac{\cos(\theta-\alpha) \sin \theta\cdot \ell(\theta)-\cos\theta \sin(\theta-\alpha)\cdot r(\theta)}{\sin \theta\cos(\theta-\alpha)-\cos\theta \sin(\theta-\alpha)}=\frac{\cos(\theta-\alpha) \sin \theta\cdot \ell(\theta)-\cos\theta \sin(\theta-\alpha)\cdot r(\theta)}{\sin \alpha}$$$.
After substituting in $$$\ell(\theta)=\left(\frac{\sin\theta}{\sin\alpha},0\right), r(\theta)=\frac{\sin(\theta-\alpha)}{\sin \alpha}\cdot (\cos\alpha, \sin \alpha)$$$ and simplifying, we can verify that this gives the equations for $$$x(\theta)$$$ and $$$y(\theta)$$$ described in the editorial.
It's hilarious only problem little_angel set is problem F
I will show my idea for problem E so maybe someone can tell me where I'm wrong.
I tried a single dp. Let $$$dp[i]$$$ be the number of almost perfect permutations.
We consider the last two elements $$$i-1$$$ and $$$i$$$.
Overall we get
$$$dp[i] = 2 \cdot dp[i-2] + 2 \cdot (i-2) \cdot dp[i-3] + (i-2) \cdot (i-3) \cdot dp[i-4] + 2 \cdot (i-3) \cdot dp[i-4]$$$.
I think all these cases do not overlap, but of course I may be wrong. I have been trying different small changes to these cases but I couldn't get it right, although I think the general idea should work. Maybe someone can find the mistake(s).
In the last case, you removed two values from the middle when creating your 4-cycle, so if you removed 4,5 your list of remaining values looks something like 1, 2, 3, 6, 7, 8
Now note that 3 and 6 are adjacent in the new list, but not consecutive. So you can't use the value of dp[i-4] for this new list.
For problem E, the editorial says the third type of cycles is
$$$(i, j, i + 1, j + 1)$$$,
while in fact it can be one of two flavors:
$$$(i, j, i + 1, j + 1)$$$ and
$$$(i, j + 1, i + 1, j)$$$.
Here, for uniqueness, we assume the first term of the cycle is its minimum element.
Edit: I see now the above point is where this differs from the editorial.
Example 1: cycle is $$$(1, 3, 2, 4)$$$, permutation is $$$p = 3 4 2 1$$$, inverse is $$$p^{-1} = 4 3 1 2$$$.
Example 2: cycle is $$$(1, 4, 2, 3)$$$, permutation is $$$p = 4 3 1 2$$$, inverse is $$$p^{-1} = 3 4 2 1$$$.
Why (1,3,2,4) means p=3421? if n>4, such as p=54321, how can I repesent it by cycle?
A little reading might help: https://en.wikipedia.org/wiki/Permutation#Cycle_notation
Problem E, an alternative view of the "easy way" solution:
Consider the individual factors:
$$${n - 2 s \choose 2 s}$$$: say we have $$$s$$$ cycles of length 4. This means we have to divide $$$n$$$ positions into $$$(2 s)$$$ pairs for these cycles and $$$(n - 4 s)$$$ single elements for other cycles. This can be seen as, out of a total of $$$(n - 4 s + 2 s)$$$ pairs plus singles, selecting the positions for $$$(2 s)$$$ pairs.
$$$2^s$$$: each cycle of length 4 can come in one of two flavors: $$$(i, j, i + 1, j + 1)$$$ and $$$(i, j + 1, i + 1, j)$$$.
$$$(2 s − 1)!! = (2 s - 1) \cdot (2 s - 3) \cdot \ldots \cdot 3 \cdot 1$$$: Look at the $$$2 s$$$ pairs from left to right, and pair them up in cycles of length 4. The leftmost pair has $$$(2 s - 1)$$$ choices, the leftmost pair left after that has $$$(2 s - 3)$$$ choices, and so on.
$$$I_{n - 4 s}$$$: The single elements form cycles of lengths 1 and 2. Again look from left to right. Either the leftmost element remains single, or it is paired up with any of the elements to the right. Thus $$$I_k = I_{k - 1} + I_{k - 2} \cdot (k - 1)$$$, which can be found by a separate linear dynamic programming.
Problem E, question: how do you people come up with the complete list of the cycles that can appear? Do you start building a cycle on paper, carefully consider all the possibilities that appear, and just obtain the list, along with the constructive proof?
My case was, after failing with just an $$$I_k$$$ solution, writing a brute force solution and looking at the permutations in the form of cycle products. Here is an example with only the most interesting permutations shown up to length 10: those that contain at least 2 cycles of length >2. So, I have not really proven that there are no other cases, but no other cycles appeared up to $$$n = 11$$$, and that evidence was strong enough.
And better late than never: thanks to the authors for this problem!
When I came up with the problem, my first course of action was to write a brute force for small n and observe some basic properties of the valid permutations, like their cycles. From there I observed that only cycles of length $$$1$$$, $$$2$$$ and $$$4$$$ were present.
From here, it was easy for anubhavdhar to come up with the formal proof that this was indeed the case.
I'd love to hear how others approached this problem. And I'm happy you liked it :D
For me, the first train of thought after seeing permutations is examining cycles. I considered enforcing constraints for some index $$$i$$$: the one before and after it, $$$p_i^{-1}$$$ and $$$p_i$$$, differ by $$$1$$$. Then I tried fixing a value. Say $$$p_i^{-1} = 3$$$. Then $$$p_i = 2$$$ or $$$4$$$. Say its $$$4$$$. I'll abbreviate applying $$$p$$$ $$$k$$$ times as $$$p_i^k$$$. Then $$$p_i^3 = 5$$$. $$$p_i^5 = 6$$$. $$$p_i^7 = 7$$$. Eventually we'll loop back to $$$p_i^{-1}$$$ and get stuck. Aha, so we can't have chains longer than length $$$2$$$. Therefore, we conclude only length $$$1, 2, 4$$$ cycles work.
In my case, I did not solve the problem because I could not come up with an easy way of deciding how many ways of choosing k pairs of consecutive numbers there was, but I deduced that fact without brute forcing.
I started working with the identity $$$|p_i - (p^{-1})_i| \le 1$$$. The first thing I did was getting rid of $$$p^{-1}$$$, since it makes reasoning more difficult (like changing from two variables to one).
because $$$p_i$$$ is a permutation. This way, since $$$p^{-1}_{p_i} = i$$$, we can write
We already see that $$$p_{p_i}$$$ is appearing there. So it makes sense to consider cycles, which are sequences of the form $$$p_i, p_{p_i}, \dots$$$. In fact, we also have $$$|p_{p_{p_i}} - p_i| \le 1$$$, for example. For me, this i what can give the reasonable idea of decomposing the permutation in cycles. Let $$$a_1, \dots, a_n$$$ be indices such that $$$a_{i+1} = p_{a_i}$$$. (We are working with subindices modulo $$$n$$$). The condition becomes $$$|a_{(i+2\mod n)} - a_i| \le 1$$$. Note that making this hold for all cycles is equivalent to our initial condition.
Call $$$a_i$$$ and $$$a_{i+2 (\mod n)}$$$ neighbors. It is easy to see that since the smallest element only has a possible neighbor, you can only have cycles of length $$$1$$$, $$$2$$$ and $$$4$$$. More precisely, $$$i - 2 \equiv i+2 \mod n$$$ if and only if $$$4 \equiv 0$$$ if and only if $$$n = 1,2,4$$$..
Ahhhh round is unrated
What kind of punishment are they going to get?
They should be kicked out from IIT Kharagpur for defaming its name.
Not they but he.
In D, can anyone please explain this statement written in editorial in Problem D
Clearly, it would be best if there was no cycle in B.
Thanx in advance
Including an edge that creates a cycle is adding a new path between vertices that already have a connection and therefore doesn't change the number of connected components. Including an edge that doesn't create a cycle connects two previously unconnected components reducing the total by 1 and the objective is to minimize this number.
Why so many downvotes? I think the author of this blog doesn't deserve it.
Because of this
Repost the Editorial explaining it and then ask why so many people downvoted. I guess you should get the answer. If not People Who downvoted will get a nice editorial
Problem D: 1726D - Edge Split My code almost same as described above. First I maked a tree by Blue edge on dfs(). Then checked is there any loop with Red edge, if there then swapped blue edge with red edge. Got wrong answer. Where did I wrong? My code: 171145235
Because the red edge you swapped with a blue edge might create a new cycle in the blue graph. However there might be some other replacement which won't create a cycle.
For problem D
I used union-find to create spanning tree, but cannot get rid of cycle for other color
Can any one explain how will dfs for spanning tree will help in getting rid of cycle as mentioned in tutorial.
Thanks in advance.
Also can this question be solved using Union Find
I used union-find to solve the problem. submission
To handle the cycle:
Force one of the 3 edges making the cycle into the original tree
Exclude the other 2 edges from the next building of the tree
Now try building the spanning tree again. You will end with a complete tree and one edge that don't make a cycle with the 2 excluded edges.
Why is my solution for D giving WA on test 2. For removing the Blue cycle of length 3, I am taking one vertex u from cycle. Find any black edge adjacent to u and color it blue and color any blue edge in cycle adjacent to u black.
if you color a black edge adjacent to u randomly,then color a blue edge in cycle adjacent to u black,the graph constructed by black edges may not be connected;
for example 6 8 1 2 1 3 2 3 1 4 1 5 2 6 3 6 5 6 firstly,if we construct a spanning tree with black edge 4,5,6,7,8 blue edge 1,2,3 form a cycle then we expect there is no cycle,if we make edge 4 blue ,then make edge 2 black,the graph constructed by black edges is not a spanning tree anymore
we should make one of 3 blue edges black,other two edges are still blue,then select n-2 edges from remaining n-1 edges to form a spanning tree,it's obvious that there is no cycle in blue graph or black graph
would it be correct if I generalise this: out of all the extra edges(edges joining already connected components) , give first one to Red edge set and rest to Blue edge set then start giving edges that join the connected components to the Red set
I don't know about F, but problems A, B and C are good ones! (though problem A ruined my first 30 minutes of the contest)
Also, a request to everyone, Since all the problems except F are made by anubhavdhar and Newtech66, they are not the ones who should be downvoted. The thief only contributed problem F to the problem set. Instead of blindly downvoting the blog and the editorial, please be mature!
You can solve D by shuffling the order of edges and building a spanning tree using DSU while the edges you haven't included in a spanning tree are in a cycle 171135740
Hi. I tried the same here. Did one iteration from index 1 to m and one from m to 1 but my submission is failing for some reason. Any help is appreciated. https://codeforces.com/contest/1726/submission/171216269
In case if someone needs more readable code: 171168803
why did you choose to go for a randomized solution? Did you prove that your solution will pass the Time limit. If so, how did you assess the time complexity
I didn't choose. In the contest, I implemented not randomized solution.
After the contest, I was just curious will it work, and if yes, how fast?
Turned out that my solution is now the fastest :)
DFS with shuffling the starting node is also sufficient
I used the same idea but if you solve a problem with a shuffle should you define your self as a accepted?
I have another solution for D.
We first build DFS tree and color the tree edge $$$x$$$ with color $$$dep[x]\bmod 2$$$, and write a brute force enumeration other edges' color.
I tried to solve D using DSU but my submission is failing. "wrong answer jury found a smaller answer than participant (test case 150)". Not sure what that means. I tried to build the spanning tree using DSU and marked an edge connecting u and v '1' if there is another existing path between u & v and both u & v are not in the set of nodes which are connected by already marked edges. I ran the iteration once from 1 to m and once from m to 1 so that I get maximum possible marked edges without breaking the connectivity of the graph.
https://codeforces.com/contest/1726/submission/171216269 Any help is highly appreciated.
Why so many downvotes? The problem was stolen by one person. That doesn't make the whole org responsible.
How would you have prevented this if you were the author?
can anyone pls explain the approach to solve problem D?
Can C be solved using stack? If someone has done, please let me know. Thanks in advance!
I have.
I can't completely understand the editorial of G, but I have a solution which doesn't need segment tree and works in $$$O(n)$$$ time. My submission is now the second shortest solution, and I believe many of the shortest submissions used this solution.
For a $$$\langle x,0\rangle$$$, it in fact requires exactly $$$T-x$$$ numbers which are strictly less than it to be after it. And for a $$$\langle x,1\rangle$$$ ($$$x\ne T$$$), it requires exactly $$$i-m$$$ numbers which are no more than it to be after it. So we can insert the numbers from small to big. My code can help understand.
C can be done in a bfs like matter by utilizing a queue and a priority queue 171736806
In the solution of problem G,I think the formula might be like this: \begin{aligned}P=\prod_{\text{all }<u,v>} {cnt_{<u,v>}!}\end{aligned}
You're right, thanks for noticing.
For problem E,why O(tn) can pass it?173136257
ok,I ignored the sum of.
Problem C using (Stack + DSU) 197719883
In problem B: According to tutorial, for N = 6 and M = 16 ans will be — 1, 1, 1, 1, 6, 6 but xor these elements is 0 which is less than every element of sequence so either question is wrong or solution is wrong, Please correct me if I am wrong.