Is it just me, or are others also unable to access the problem proposals page? It keeps showing the Codeforces "all your bug are belong to me" page.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
6 | adamant | 157 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | djm03178 | 153 |
Is it just me, or are others also unable to access the problem proposals page? It keeps showing the Codeforces "all your bug are belong to me" page.
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.
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)
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=' ')
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("()"))
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;
}
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:
Unable to parse markup [type=CF_MATHJAX]
, $$$\lvert b - d \rvert = 1$$$. WLOG assume $$$a < c$$$ (therefore $$$c = a + 1$$$).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;
}
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;
}
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;
}
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;
}
Feel free to vote for your opinion of each problem, and the best problem of the contest.
Hello Codeforces!
Grimoire of Code, the official Competitive Programming club of IIT Kharagpur, is happy to invite everyone to take part in Codeforces Round 819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022 which will take place on Sep/06/2022 17:35 (Moscow time). This round will be rated for everyone.
You will be given 8 problems and 2 hours 15 minutes to solve them.
The problems have been authored and prepared by Grimoire of Code members Anubhav anubhavdhar Dhar, Debajyoti little_angel Dasgupta, and Mainak Newtech66 Roy.
We'd like to thank all the people who made this round possible:
We hope everyone will enjoy the contest.
See you on the leaderboard!
About Grimoire of Code:
Grimoire of Code is the official Competitive Programming club of IIT Kharagpur created by and for competitive programming enthusiasts. We promote competitive programming culture in our college, and provide a forum for interested minds to discuss their thoughts and ideas. We also conduct mock coding rounds for placements and internships in Indian colleges.
You can check out our Facebook page here.
You can check out the problems from last year's Annual Contest here.
UPD1: The contest duration has been extended to 2 hours 15 minutes.
UPD2: Score distribution: $$$500-1000-1500-2000-2250-2750-3250-3500$$$
UPD3: Congratulations to the winners!
UPD4: Editorial (editorial for F will be added soon) It is now added.
UPD5: The contest is unrated due to problem copying. Details.
Hello, Codeforces!
TimeWarp101 and I are excited to invite you to Codeforces Round 782 (Div. 2) which will take place on Apr/17/2022 17:35 (Moscow time). This round will be rated for participants with rating lower than 2100.
Many thanks to all the people who made this round possible:
You will have 2 hours to solve 6 problems.
Scoring distribution: $$$500-750-1500-2000-2250-3000$$$
We've tried to keep the statements short and pretests strong. We hope you will enjoy the round!
See you all in the standings!
P.S. namanbansal013 will be livestreaming his solution explanations for some of the problems here. Do check out his channel too!
UPD: We are really sorry for the issues with the queue, but we hope you liked the problems anyway.
UPD: Editorial
UPD: Congratulations to the winners!
Official winners:
Unofficial winners:
First solves:
Thank you everyone for your participation. Do vote under the Feedback section, and feel free to give your review of the problems in the comments.
Idea: TimeWarp101
Editorial: TimeWarp101
Is it a good idea to have consecutive B
's?
If you space out all the B
's, how many regions do you have to place the R
's into?
What is the best way of placing the R
's into $$$b+1$$$ regions such that the maximum number of R
's in a region is minimum?
#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
cin>>_;
while(_--)
{
int n,r,b;
cin>>n>>r>>b;
int p=r/(b+1),q=r%(b+1);
for(int i=0;i<q;i++) cout<<string(p+1,'R')<<'B';
for(int i=q;i<b;i++) cout<<string(p,'R')<<'B';
cout<<string(p,'R');
cout<<endl;
}
return 0;
}
t = int(input())
for i in range(t):
n, r, b = map(int, input().split())
p = r % (b + 1)
y = ""
for j in range(int(r / (b + 1))):
y = y + "R"
ans = ""
for i in range(b + 1):
if i > 0:
ans = ans + "B"
ans = ans + y
if p > 0:
ans = ans + "R"
p = p - 1
print(ans)
Idea: Newtech66
Editorial: Newtech66
Let's say you don't ever pick a bit. How many times will it get flipped?
If you do pick a bit once at some point, it will get flipped $$$1$$$ less time overall.
To get the lexicographically largest string, you need to make bits $$$1$$$ starting from the left. What is the minimum number of times you have to select a bit to ensure it gets flipped, or stays the same?
#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
cin>>_;
while(_--)
{
int n,k;
cin>>n>>k;
string s;
cin>>s;
vector<int> f(n,0);
int tmpk=k;
for(int i=0;i<n && tmpk>0;i++)
{
if(k%2==s[i]-'0')
{
f[i]=1;
tmpk--;
}
}
f[n-1]+=tmpk;
for(int i=0;i<n;i++)
{
if((k-f[i])%2==1) s[i]='1'-(s[i]-'0');
}
cout<<s<<endl;
for(auto& e:f) cout<<e<<" ";
cout<<endl;
}
return 0;
}
t = int(input())
for i in range(t):
n, k = map(int, input().split())
kc = k
s = input()
f = [0] * n
ans = ""
for i in range(n):
if k == 0:
break
if kc % 2 == 1 and s[i] == '1':
f[i] = f[i] + 1
k = k - 1
elif kc % 2 == 0 and s[i] == '0':
f[i] = f[i] + 1
k = k - 1
f[n - 1] = f[n - 1] + k
for i in range(n):
flip = kc - f[i]
if flip % 2 == 0:
ans = ans + s[i]
else:
if s[i] == '1':
ans = ans + '0'
else:
ans = ans + '1'
print(ans)
for i in range(n):
print(f[i], end = ' ')
print()
Idea: Newtech66
Editorial: Newtech66
Try to analyze the cost of each operation separately. Is there some linearity you can exploit?
Try to make greedy decisions. Can we say that it is always better to move right whenever possible?
Let's say you fix the final position of your capital. Now think about Hint 2.
#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
const lol inf=1e18+8;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
cin>>_;
while(_--)
{
int n;
lol a,b;
cin>>n>>a>>b;
vector<lol> x(n+1),p(n+1);
x[0]=0;
for(int i=1;i<=n;i++) cin>>x[i];
partial_sum(x.begin(),x.end(),p.begin());
lol ans=inf;
for(int i=0;i<=n;i++)
{
ans=min(ans,(a+b)*(x[i]-x[0])+b*(p[n]-p[i]-(n-i)*x[i]));
}
cout<<ans<<endl;
}
return 0;
}
Idea: Newtech66
Editorial: Newtech66
Is there any way to tell how many $$$1$$$s were in $$$A$$$?
Can you tell what $$$a_n$$$ was by looking at just $$$c_n$$$?
Try to simulate removing each $$$B_i$$$ starting from $$$B_n$$$.
#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
cin>>_;
while(_--)
{
int n;
cin>>n;
vector<lol> v(n);
for(auto& e:v) cin>>e;
int k=accumulate(v.begin(),v.end(),0ll)/n;
vector<int> b(n),ans(n,0);
int lf=n-k;
for(int i=lf;i<n;i++) b[i]=n-1;
for(int i=n-1;i>=0 && lf<=i;i--)
{
int cur=v[i]-(b[i]-i);
if(cur==i+1) ans[i]=1;
else if(cur==1)
{
ans[i]=0;
lf--;
b[lf]=i-1;
}
}
for(auto& e:ans) cout<<e<<" ";
cout<<endl;
}
return 0;
}
Try to solve this problem if it is possible for invalid $$$C$$$ to be given as input. This was the original version of the problem, but testers struggled a lot with it. The solution to this is still used in the validator.
Idea: Newtech66
Editorial: TimeWarp101
Can the MEX ever be $$$> 2$$$?
For the MEX to be $$$0$$$, the AND of the walk should be $$$> 0$$$. This implies that some bit is on for all the edges of the walk. How can you check this efficiently?
Make $$$30$$$ graphs, with each graph only containing edges where the $$$i$$$-th bit is on. You can use disjoint sets on these graphs to solve the above problem.
When MEX is $$$1$$$, we know $$$0$$$ exists in the sequence. We need to avoid $$$1$$$ and jump from some other number to $$$0$$$. We need to get rid of the $$$0$$$-th bit while some other bit stays on to ensure we don't get $$$1$$$ in our sequence. This basically means that we need to walk to a node which has an even edge and ensure our AND so far is $$$> 1$$$. Travelling through the even edge would guarantee that our answer is $$$1$$$.
Again, make $$$29$$$ graphs, with each graph only containing edges where the $$$0$$$-th and $$$i$$$-th ($$$i\geq 1$$$) bits are on. Use disjoint sets on these graphs. For each vertex you can note if it is adjacent to an even edge and then store this information in the disjoint set data structure.
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define gcd __gcd
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rep(i, n) for (int i=0; i<(n); i++)
#define rep1(i, n) for (int i=1; i<=(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl "\n"
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
template<typename T, typename cmp = less<T>>
using ordered_set=tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;
struct dsu {
vi d;
dsu(int n) : d(n, -1) {}
int find(int x) {return d[x] < 0 ? x : d[x] = find(d[x]);}
void join(int x, int y) {
x = find(x), y = find(y);
if(x == y) return;
if(d[x] > d[y]) swap(x, y);
d[x] += d[y]; d[y] = x;
}
bool is_joined(int x, int y) {
return find(x) == find(y);
}
};
int32_t main() {
fastio;
int n, m; cin >> n >> m;
vector<tuple<int, int, int>> edges;
rep(i, m) {
int u, v, w; cin >> u >> v >> w;
edges.eb(--u, --v, w);
}
vector<dsu> zero(30, n), one(30, n);
rep(j, 30) {
for(auto& [u, v, w]: edges) if(w >> j & 1) {
zero[j].join(u, v);
}
}
vb even(n);
rep1(j, 29) {
for(auto& [u, v, w]: edges) if((w >> j & 1)) {
one[j].join(u, v);
}
vb vis(n);
for(auto& [u, v, w]: edges) if(!(w & 1)) {
vis[one[j].find(u)] = 1;
vis[one[j].find(v)] = 1;
}
rep(i, n) if(vis[one[j].find(i)]) even[i] = 1;
}
auto check = [&](int u, int v) -> int {
rep(j, 30) if(zero[j].is_joined(u, v)) return 0;
if(even[u]) return 1;
rep1(j, 29) if(one[j].is_joined(u, v)) return 1;
return 2;
};
int q; cin >> q;
while(q--) {
int u, v; cin >> u >> v; --u, --v;
cout << check(u, v) << endl;
}
}
Try to solve this problem if the queries were for longest walk instead.
1659F - Tree and Permutation Game
Idea: Newtech66
Editorial: Newtech66
Bench0310 has written another proof for the solution to this problem here and here. Many thanks to him!
Notice that as long as there are $$$\geq 3$$$ elements not in their correct place, Alice can always put at least $$$1$$$ element into the correct place.
Intuitively, Alice should win if the tree is "big enough", because Bob won't be able to reach some places quickly enough. How to define this sense of "big enough"?
Try to solve this problem on a line graph.
It is actually possible to force a sequence of moves to get the $$$2$$$ remaining elements onto the diameter of the tree. Given this, use the answer to Hint 3.
Prove that Alice always wins on trees with diameter $$$\geq 3$$$.
A tree of diameter $$$2$$$ is a star graph. This case has a number of edge cases. This time, try to look at permutation cycles. Can you define some kind of invariant?
#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
pair<int,int> dfs(int u,const vector<vector<int>>& g,int p=-1) //returns {node with max dist,max dist}
{
pair<int,int> res{u,0};
int mx=0;
for(auto v:g[u])
{
if(v==p) continue;
pair<int,int> cur=dfs(v,g,u);
cur.second++;
if(mx<cur.second)
{
res=cur;
mx=cur.second;
}
}
return res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
cin>>_;
while(_--)
{
int n,x;
cin>>n>>x;
vector<vector<int>> g(n+1);
vector<int> p(n+1),deg(n+1,0);
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
deg[u]++,deg[v]++;
}
for(int i=1;i<=n;i++)
{
cin>>p[i];
}
//find diameter of tree with 2 DFSes
int diam=dfs(dfs(1,g).first,g).second;
//if diam>=3, Alice always wins
//if diam=1, n=2, have to check if p=[1,2]
//otherwise we have a star graph and cases follow
if(diam>=3) cout<<"Alice";
else if(diam==1) cout<<((p[1]==1)?"Alice":"Bob");
else
{
//we need to check if we have already won or can win in the first move
//this is possible if the permutation is already sorted
//or if there are two marked elements and the chip is on neither of them
vector<int> marked;
for(int i=1;i<=n;i++)
{
if(p[i]!=i) marked.push_back(i);
}
if((int)marked.size()==0)
{
cout<<"Alice";
}else if((int)marked.size()==2 && (x!=marked[0] && x!=marked[1]))
{
cout<<"Alice";
}else
{
//we haven't won yet and it is not possible to win in one move
//cases follow
//first find center, it will have deg>1
int center;
for(int i=1;i<=n;i++)
{
if(deg[i]>1)
{
center=i;
break;
}
}
//is chip on center?
bool chiponcenter=(x==center);
//is center marked?
bool centerismarked=(find(marked.begin(),marked.end(),x)!=marked.end());
//list the cycles
vector<int> vis(n+1,false);
vector<vector<int> > cycles;
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
int j=i;
cycles.push_back({j});
vis[j]=true;
while(!vis[p[j]])
{
cycles.back().push_back(p[j]);
vis[p[j]]=true;
j=p[j];
}
}
//min number of swaps
int swapcnt=0;
for(auto& cycle:cycles) swapcnt+=(int)cycle.size()-1;
//parity
int parity=(swapcnt+!chiponcenter)%2;
//cases
if(!centerismarked) cout<<(parity?"Alice":"Bob");
else if(chiponcenter && centerismarked) cout<<"Bob";
else //chip not on center and center is marked
{
//need to check if we can unmark center on first move
//it is impossible if x is on p[center] (since we need to move p[center] to get center
//to the right place, but p[center] is blocked)
bool cannotunmarkcenter=(p[center]==x);
if(cannotunmarkcenter) cout<<"Bob";
else cout<<(parity?"Alice":"Bob");
}
}
}
cout<<endl;
}
return 0;
}
Basically the title of the post. Well, I suppose "solution->problem" is a way, but I'm not particularly good at using it. "problem->solution" is the way I prefer, but the issue is, oftentimes, I'm not skilled enough to solve the problem I just made. Nor can I tell if the problem is unsolvable (in polynomial time). How do you do it?
In newer problems on CodeForces and other sites, I usually see multi-test inputs that say something like "it is guaranteed that sum of $$$n$$$ over all testcases does not exceed XXXXX".
I am unable to figure out how to implement such a generator in Polygon. Can someone tell me how exactly I should go about this?
Assume there are $$$n$$$ circles on the plane. The $$$i^{th}$$$ circle has an initial radius $$$r_i$$$ $$$(r_i \geq 0)$$$. We are allowed to increase or decrease the radius of the $$$i^{th}$$$ circle by $$$1$$$ unit at a cost $$$c_i$$$ $$$(c_i > 0)$$$. Let us make a graph such that each circle is a node, and there is an undirected edge between two circles $$$C_i$$$ and $$$C_j$$$ if their intersection is not empty (just to be clear, the cases are: they touch internally/externally, they intersect at two points, one lies inside the other).
Find the minimum cost to make the graph connected.
Trying to think of new and interesting problems and then creating this problem which I can't solve at all. The inspiration here was from radio stations. Every radio station has a coverage radius, and if we make the network connected, a message can travel between any two radio stations.
I have given up on this problem. I would appreciate it if someone can enlighten me on how to solve this problem or with any restrictions on it (eg. "$$$r_i=0$$$", "All $$$c_i$$$ are equal", etc).
Anything works, I haven't even been able to figure out an approach.
Since the maximum possible number of pairings is $$$10395$$$, I could just check all possible pairings for a cycle. But I'm not sure how I would implement this.
I have no clue. I do not think a brute force would work here.
I can precalculate shortest paths between the pharmacies, fixing the starting and ending. Then for every other vertex, I could take the minimum over all choices of starting and ending pharmacies. Then I could take the overall minimum. It works, but I'm having trouble implementing so much neatly.
Please help me in getting a solution to each of these problems.
Note: Contest ended a long time ago so don't worry about possible cheating.
>bumping this post for first and last time because I never got an answer
There is an intruder in your system who wishes to steal as much information as he can. Your system can be represented as an undirected graph, with each node having an information value (IV). Now, you were terribly unprepared for this. Your only option is to delete nodes. You have time enough to delete at most 2 nodes. Luckily, the algorithm of the intruder has a flaw. It cannot visit a previously visited node. It steals the information of whatever node it visits. Assuming that the algorithm always tries to maximize the IV it can get, give the maximum possible IV you can save.
Note: Formally the algorithm seeks the path of maximum weight. The sum of the weights of the unvisited nodes is what you have saved. The weights of the deleted nodes are unavailable to both you and the algorithm. When a node is deleted, all paths connected to it are also removed.
A variant: Now you are given that the algorithm starts the path with a given vertex that you cannot delete.
There are no constraints, I want the best solution. Please notify any corrections or flaws in the problem statement. It is guaranteed that the constraints allow a solution.
Name |
---|