You can now find the contest in the public gym, ICPC-de-Tryst 2024 (the ghost submissions can still be accessed in the older mashup).
1. HR se puuch ke batayenge: rivalq, magga, Kira_1234
2. nulllösungssatz: Dominater069, aryanc403, IceKnight1093
3. 4C3: koderkushy, piyush_pransukhka, kingmessi
4. tbd: keyurchd_11, shiven, GenghizKhan
5. ElDiablo: ElDiablo
7. SmolBrain: SmolBrain
8. Pols_Station: Pols_Agyi_Pols
9. PalindORme: the_hyp0cr1t3, JeevanJyot, ExplodingFreeze
10. Team: jtnydv25
11. Cult Council: AKSLEGION, D1orite, shorya1835
12. IDK: ha___il, JadeReaper, akcube
13. ThreeMusketeers: gakshat468, sg0071729, 21cs01033
14. cns_lena_chahiye_tha: dhruvsomani, vikram108, ParadigmShift
1. ElDiablo: ElDiablo
2. Team: jtnydv25
3. monoid: htnaver, kayou81, atimanas
4. No clue: Beelzebub_blue
5. Death Valley: 1729_prism, Abhishek_821023, dark_ethics
We'll give prizes to the next 3 IITD teams not in the top 15.
A: ThreeMusketeers: gakshat468, sg0071729, 21cs01033
B: No clue: Beelzebub_blue
C: nulllösungssatz: Dominater069, aryanc403, IceKnight1093
D: HR se puuch ke batayenge: rivalq, magga, Kira_1234
E: nulllösungssatz: Dominater069, aryanc403, IceKnight1093
F: tbd: keyurchd_11, shiven, GenghizKhan
G: unforgettable playz: noobcodur, oviyan_gandhi, unforgettablepl
H: HR se puuch ke batayenge: rivalq, magga, Kira_1234
I: OverShadow: Coder_Nayak, Krypto_Ray, sloppy_coder
J: nulllösungssatz: Dominater069, aryanc403, IceKnight1093
K: nulllösungssatz: Dominater069, aryanc403, IceKnight1093
Setter: BladeRunner
//solution to Highly Constrained Permutation
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n; cin>>n;
vector<int> a(n+1),b(n+1);
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
vector<vector<int>> adj(n+1);
//make graph in the forward direction first
vector<int> last(n+1);
for(int i=1;i<=n;i++)
{
//deal with last[a[i]-1] case
if(a[i]!=1)
{
if(last[a[i]-1]==0)
{
cout<<-1<<'\n';
return;
}
else adj[last[a[i]-1]].push_back(i);
}
//deal with the last[a[i]] case
if(last[a[i]] != 0) adj[i].push_back(last[a[i]]);
last[a[i]]=i;
}
//now in the backward direction
vector<int> next(n+1);
for(int i=n;i>=1;i--)
{
//deal with next[b[i]-1] case
if(b[i]!=1)
{
if(next[b[i]-1]==0)
{
cout<<-1<<'\n';
return;
}
else adj[i].push_back(next[b[i]-1]);
}
//deal with the next[b[i]] case
if(next[b[i]] != 0) adj[next[b[i]]].push_back(i);
next[b[i]]=i;
}
//so now toposort this graph
vector<bool> popped(n+1,false);
vector<int> indg(n+1);
queue<int> q;
// for(int i=1;i<=n;i++)
// {
// cout<<i<<'\n';
// for(auto j:adj[i]) cout<<j<<' ';
// cout<<'\n';
// }
for(int i=1;i<=n;i++)
{
for(auto j:adj[i]) indg[j]++;
}
for(int i=1;i<=n;i++)
{
if(indg[i]==0) q.push(i);
}
vector<int> order;
while(!q.empty())
{
int f=q.front();
q.pop();
popped[f]=true;
order.push_back(f);
for(auto nbr:adj[f])
{
indg[nbr]--;
if(indg[nbr]==0) q.push(nbr);
}
}
if((int)order.size() < n)
{
printf("%d\n",-1);
return;
}
vector<int> ans(n+1);
for(int i=0;i<n;i++) ans[order[i]]=i+1;
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
printf("\n");
}
signed main()
{
int t; cin>>t;
while(t--) solve();
}
Setter: 33_arsenic_75, Preparation: islingr
#include "bits/stdc++.h"
using namespace std;
int solve() {
int n, x;
cin >> n >> x;
const int msb = x >> 10 & 1;
if (msb == (n & 1)) return 10 * n;
return 10 * (n - 1) + 9;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t;
cin >> t;
while (t--) cout << solve() << '\n';
}
Setter: sahilkumar_1
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll rotate(ll x,ll base,vector <ll> & info){
if(x<base) return x;
int k=0;
for(int i=0;i<info.size();i++){
if(info[i]<=x&&info[i+1]>x){
k=i;
break;
}
}
return (info[k]*(x%base)+(x/base));
}
ll min_possible(ll x, ll base,vector <ll> & info){
if(x<base) return x;
ll ans=x;
for(int i=0;i<64;i++){
x=rotate(x,base,info);
ans=min(ans,x);
}
return ans;
}
void solve(vector <vector <ll>> & vect){
int n;
cin >> n;
ll sum=0;
for(int i=0;i<n;i++){
ll x;
cin>>x;
sum+=min_possible(x,i+3,vect[i+3]);
}
cout<<sum<<endl;
}
int main(){
int t;
cin >> t;
vector <vector <ll>> vect(1e5+3);
for(int i=3;i<=1e5+2;i++){
ll cur=1;
while(true){
vect[i].push_back(cur);
if(cur>1e9) break;
cur*=i;
}
}
while(t--) solve(vect);
}
Setter: ajmeraraghav99
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long int n,i,j;
cin>>n;
long long int marks[n+1];
int check[n+1];
for(i=1;i<=n;i++)
{
check[i]=0;
}
vector<int> v;
i=1;
while(i<=n)
{
if(v.size()==0)
{
v.push_back(i);
i++;
}
else
{
cout<<"? "<<v[v.size()-1]<<" "<<i<<endl;
fflush(stdout);
long long int x;
cin>>x;
marks[i]=abs(x);
check[i]=1;
if(x>0)
{
v.push_back(i);
}
else
{
v.pop_back();
}
i++;
}
}
int honest_index=v[v.size()-1];
vector<pair<long long,long long>> first_half;
for(i=1;i<=n;i++)
{
if(i!=honest_index)
{
if(check[i])
{
first_half.push_back({-marks[i],i});
}
else
{
cout<<"? "<<honest_index<<" "<<i<<endl;
fflush(stdout);
long long int dum;
cin>>dum;
marks[i]=abs(dum);
check[i]=1;
first_half.push_back({-marks[i],i});
}
}
}
sort(first_half.begin(),first_half.end());
int index=-1;
for(i=0;i<(n+1)/2;i++)
{
int dum_indx=first_half[i].second;
cout<<"? "<<honest_index<<" "<<dum_indx<<endl;
fflush(stdout);
long long int dum_marks;
cin>>dum_marks;
if(dum_marks>0)
{
index=dum_indx;
marks[index]=dum_marks;
break;
}
}
cout<<"? "<<index<<" "<<honest_index<<endl;
fflush(stdout);
long long smth;
cin>>smth;
marks[honest_index]=smth;
if(marks[honest_index]>marks[index])
{
cout<<"! "<<honest_index<<endl;
}
else
{
cout<<"! "<<index<<endl;
}
return 0;
}
Setter: Azm1t
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>
void solve(){
int n, q; cin >> n >> q;
vector<int> c(n);
for(int &x: c) cin >> x, x--;
vector<vector<int>> adj(n);
for(int i = 0; i < n-1; i++){
int u, v; cin >> u >> v;
u--; v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
ordered_set os[n];
vector<int> tin(n, 0), tout(n, 0);
int time = 0;
function<void(int, int)> dfs = [&](int v, int p){
tin[v] = time++;
for(int child: adj[v]){
if(child != p) dfs(child, v);
}
tout[v] = time++;
os[c[v]].insert({tin[v], v});
};
dfs(0, -1);
while(q--){
int type, v, x; cin >> type >> v >> x;
v--; x--;
if(type == 1){
os[c[v]].erase({tin[v], v});
c[v] = x;
os[c[v]].insert({tin[v], v});
}
else{
auto firstit = os[x].order_of_key({tin[v], -1});
auto lastit = os[x].order_of_key({tout[v], n+1});
cout << lastit - firstit << '\n';
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
while(t--) solve();
}
Setter: PROELECTRO444
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int LOCATION = 4020;
const int MAXP = 1001;
const int SHIFT = 1010;
long long dp[MAXP][LOCATION];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<int> a(n), p(n);
for(int i = 0; i < n; i++){
cin >> a[i];
}
for(int i = 0; i < n; i++){
cin >> p[i];
}
for(int i = 0; i < n; i++){
dp[p[i]][a[i] + SHIFT] += 1ll;
if(p[i] != 0)
dp[p[i] — 1][a[i] + SHIFT] += 1ll;
}
for(int s = MAXP — 2; s >= 0; s--){
for(int i = 1; i < LOCATION — 1; i++){
dp[s][i] += dp[s + 1][i — 1] + dp[s + 1][i + 1] — (s + 2 < MAXP ? dp[s + 2][i] : 0);
}
}
for(int i = 0; i < MAXP; i++){
for(int j = 1; j < LOCATION; j++){
dp[i][j] += dp[i][j — 1];
}
}
while(q--){
int l, r, s;
cin >> l >> r >> s;
l += SHIFT;
r += SHIFT;
cout << dp[s][r] — dp[s][l — 1] << endl;
}
return 0;
}
Idea:PROELECTRO444 , BladeRunner Preparation: PROELECTRO444
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
bool solve(int s, int n, int k, int a[], int p[]){
vector<pair<int, int>> interval;
for (int i = 0; i < n; i++)
{
if (p[i] — s >= 0)
{
int left = a[i] — p[i] + s;
int right = a[i] + p[i] — s;
interval.push_back({left, 1});
interval.push_back({right + 1, -1});
}
}
sort(interval.begin(), interval.end());
int m = 0, sm = 0;
for (auto [_, v] : interval)
{
sm += v;
m = max(m, sm);
}
return m <= k;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
int a[n], p[n];
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++)
cin >> p[i];
int l = 0, r = 1e9 + 10;
while (l <= r){
int mid = (l + r) / 2;
if (solve(mid, n, k, a, p))
r = mid — 1;
else
l = mid + 1;
}
cout << l << endl;
}
}
Setter: islingr
#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for (auto i{a}; i < (b); ++i)
#define per(i, a, b) for (auto i{b}; i-- > (a); )
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
template <class T> bool uin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <class T> bool uax(T& a, const T& b) { return a < b ? a = b, true : false; }
using ll = long long;
using poly = vector<ll>;
constexpr int mod = 998'244'353, root = 62;
int modpow(ll a, int b) {
ll res = 1;
for (; b; a = a * a % mod, b /= 2)
if (b & 1) res = res * a % mod;
return res;
}
void ntt(poly &a) {
int n = sz(a), L = 31 — __builtin_clz(n);
static poly rt(2, 1);
for (static int k = 2, s = 2; k < n; k *= 2, s++) {
rt.resize(n);
ll z[] = {1, modpow(root, mod >> s)};
rep(i,k,2*k) rt[i] = rt[i / 2] * z[i & 1] % mod;
}
vector<int> rev(n);
rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int k = 1; k < n; k *= 2)
for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {
ll z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j];
a[i + j + k] = ai — z + (z > ai ? mod : 0);
ai += (ai + z >= mod ? z — mod : z);
}
}
poly conv(const poly &a, const poly &b) {
if (a.empty() || b.empty()) return {};
int s = sz(a) + sz(b) — 1, B = 32 — __builtin_clz(s),
n = 1 << B;
int inv = modpow(n, mod — 2);
poly L(a), R(b), out(n);
L.resize(n), R.resize(n);
ntt(L), ntt(R);
rep(i,0,n)
out[-i & (n — 1)] = (ll)L[i] * R[i] % mod * inv % mod;
ntt(out);
return {out.begin(), out.begin() + s};
}
poly operator*(const poly& a, const poly& b) {
return conv(a, b);
}
constexpr int N = 2e5 + 10;
ll fac[N];
ll mul(ll x, ll y) { return x * y % mod; }
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
fac[0] = 1;
rep(i, 1, N) fac[i] = mul(i, fac[i - 1]);
int n;
cin >> n;
vector<ll> a(n);
for (auto& x : a) cin >> x;
poly T(n);
for (int s = 1; s < n; ++s)
T[s] = mul(fac[s - 1], fac[n - s - 1]);
vector<ll> score(n);
auto rec = [&](const auto& self, int l, int r, const poly& T) -> poly {
if (r - l == 1) {
poly P;
if (l == n - 1) P = {0, 1};
else P = {1, a[l + 1]};
score[l] = (T[0] * P[0] + T[1] * P[1]) % mod;
return P;
}
const int mid = l + (r - l) / 2;
const poly Tr(T.begin(), T.begin() + (r - mid + 1));
auto Pr = self(self, mid, r, Tr);
reverse(all(Pr));
auto Tl = Pr * T;
Tl.erase(Tl.begin(), Tl.begin() + (r - mid));
reverse(all(Pr));
const auto Pl = self(self, l, mid, Tl);
return Pl * Pr;
};
rec(rec, 1, n, T);
const auto to_div = modpow(fac[n - 1], mod - 2);
rep(i, 1, n) score[i] = mul(to_div, mul(i, mul(a[i], score[i])));
score[0] = 1;
for (auto x : a) score[0] = mul(score[0], x);
rep(i, 0, n) cout << score[i] << " \n"[i == n - 1];
}
Setter: Surver
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n, k, m;
cin >> n >> k >> m;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
vector<pair<int, int>> q(m);
for (int i = 0; i < m; i++) {
cin >> q[i].first >> q[i].second;
}
vector<int> ans(m);
auto calc = [&] () {
vector<vector<int>> suf(n + 1, vector<int>(k + 1));
for (int i = n — 1; i >= 0; i--) {
suf[i] = suf[i + 1];
int cost = 0, sum = 0;
for (int j = i; j < n; j++) {
cost += (v[j] > 0);
sum -= abs(v[j]);
if (cost <= k) {
suf[i][cost] = min(suf[i][cost], sum);
}
}
for (int j = 1; j <= k; j++) {
suf[i][j] = min(suf[i][j], suf[i][j — 1]);
}
}
vector<int> dp(n + 1, 1);
vector<int> h(n + 1, k + 1);
h[0] = 0;
for (int i = 0; i <= n; i++) {
if (i > 0) {
int cost = 0, sum = 0;
for (int j = i — 1; j >= 0; j--) {
cost += (v[j] < 0);
sum += abs(v[j]);
h[sum] = min(h[sum], cost);
}
}
for (int j = 0; j <= n; j++) {
if (h[j] <= k) {
dp[j] = min(dp[j], suf[i][k — h[j]]);
}
}
}
for (int i = 0; i < m; i++){
for (int j = 0; j <= n; j++){
if (dp[j] <= 0){
ans[i] = max(ans[i], q[i].first * j — q[i].second * dp[j]);
}
}
}
};
calc();
reverse(v.begin(), v.end());
calc();
for (int i = 0; i < m; i++){
cout << ans[i] << " \n"[i == m — 1];
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Setter: BladeRunner
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+100;
const int mod = 1e9+7;
vector<int> fact(N+1);
vector<int> ifact(N+1);
int binexp(int a,int n)
{
if(n==0) return 1;
else
{
int res=binexp(a,n/2);
res=(res*res)%mod;
if(n&1) res=(res*a)%mod;
return res;
}
}
int ncr(int n,int r)
{
if(r>n || r<0 || n<0) return 0;
int ans=(fact[n]*ifact[r])%mod;
ans=(ans*ifact[n-r])%mod;
return ans;
}
void solve()
{
int n,x,y; cin>>n>>x>>y;
int dif=abs(x-y);
cout<<ncr(n-2,dif-1)<<'\n';
}
signed main()
{
int t; cin>>t;
fact[0]=1;
for(int i=1;i<=N;i++) fact[i]=(fact[i-1]*i)%mod;
ifact[N]=binexp(fact[N],mod-2);
for(int i=N-1;i>=0;i--) ifact[i]=(ifact[i+1]*(i+1))%mod;
while(t--) solve();
}
Setter: MridulAhi
#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for (auto i{a}; i < (b); ++i)
#define per(i, a, b) for (auto i{b}; i-- > (a); )
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
template <class T> bool uin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <class T> bool uax(T& a, const T& b) { return a < b ? a = b, true : false; }
using ll = long long;
using U = uint32_t;
using poly = vector<ll>;
constexpr int mod = 998'244'353, root = 62;
int modpow(ll a, int b) {
ll res = 1;
for (; b; a = a * a % mod, b /= 2)
if (b & 1) res = res * a % mod;
return res;
}
void ntt(poly &a) {
int n = sz(a), L = 31 — __builtin_clz(n);
static poly rt(2, 1);
for (static int k = 2, s = 2; k < n; k *= 2, s++) {
rt.resize(n);
ll z[] = {1, modpow(root, mod >> s)};
rep(i,k,2*k) rt[i] = rt[i / 2] * z[i & 1] % mod;
}
vector<int> rev(n);
rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int k = 1; k < n; k *= 2)
for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {
ll z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j];
a[i + j + k] = ai — z + (z > ai ? mod : 0);
ai += (ai + z >= mod ? z — mod : z);
}
}
poly conv(const poly &a, const poly &b) {
if (a.empty() || b.empty()) return {};
int s = sz(a) + sz(b) — 1, B = 32 — __builtin_clz(s),
n = 1 << B;
int inv = modpow(n, mod — 2);
poly L(a), R(b), out(n);
L.resize(n), R.resize(n);
ntt(L), ntt(R);
rep(i,0,n)
out[-i & (n — 1)] = (ll)L[i] * R[i] % mod * inv % mod;
ntt(out);
return {out.begin(), out.begin() + s};
}
constexpr int N = 1e5;
ll mul(ll x, ll y) { return x * y % mod; }
int fac[N], ifac[N];
int C(int n, int r) { return mul(fac[n], mul(ifac[r], ifac[n — r])); }
int solve() {
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> g(k);
rep(e, 0, m) {
char a, b;
cin >> a >> b;
const int u = a - 'a', v = b - 'a';
g[u].push_back(v);
g[v].push_back(u);
}
vector Q(k + 1, poly(n + 1, 0));
for (int t = 1; t <= k; ++t)
for (int r = t; r <= n; ++r)
Q[t][r] = mul(ifac[r], C(r - 1, t - 1));
auto merge = [&](const poly& a, const poly& b) {
auto c = conv(a, b);
c.resize(n + 1, 0);
return c;
};
ll res = 0;
vector<poly> f(1 << k);
f[0].assign(n + 1, 0);
f[0][0] = 1;
rep(S, 1u, 1u << k) {
const auto root = 31 ^ __builtin_clz(S);
assert(S >> root & 1);
U T = 0;
{
auto dfs = [&](const auto& self, int u) -> void {
T |= 1u << u;
for (auto v : g[u])
if ((~T & S) >> v & 1)
self(self, v);
};
dfs(dfs, root);
}
const int t = popcount(T);
f[S] = merge(f[S ^ T], Q[t]);
res += f[S][n];
}
return mul(res % mod, fac[n]);
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
fac[0] = 1;
rep(i, 1, N) fac[i] = mul(i, fac[i - 1]);
ifac[N - 1] = modpow(fac[N - 1], mod - 2);
per(i, 1, N) ifac[i - 1] = mul(i, ifac[i]);
int t;
cin >> t;
while (t--) cout << solve() << '\n';
}
Auto comment: topic has been updated by BladeRunner (previous revision, new revision, compare).
Auto comment: topic has been updated by BladeRunner (previous revision, new revision, compare).
Why is this giving TLE for G : link. The logic is quite similar to the editorial and time complexity is N.log^2(N) .
It is because of using map in the binary search function. Simply push $$$(a[i]-(pw-s),1)$$$ and $$$(a[i]+(pw-s)+1,-1)$$$ in a vector and sort it and rest is same.
Does using map change the time complexity ? Because even after putting intervals in a vector, we are sorting it. Also this map solution got accepted : link
Also, one more thing I would like to bring to your notice. Even O(N^2) solution got accepted for Problem E.link. I feel the test cases were weak for the problem.
For your first question, it doesn't change the complexity but map has a higher constant factor so that might have caused issue, the solution that you attached of map creates some less map entries due to the min/max operation so got passed for that particular bottleneck test case (where $$$n$$$ achieved its largest possible value)
For the second, we apologise for that and hope that not many teams got affected due to this and would ensure stronger test cases in future.
Nevertheless, problems were amazing and fun to solve :)