Hello, Codeforces!
The flagship contest of SUST is here everyone! There will be 12 problems and the problemset is based on Brain Craft Intra SUST Programming Contest 2023. We cordially invite you to participate in this contest. Also, we encourage you to participate as teams. Please make sure that you read ALL the problems!
The contest will be held on Apr/07/2023 11:05 (Moscow time) and will run for 5 hours.
The setters of this contest are: Alfeh, Kawchar85, Mac_prime, magic_kiri, nh_nayeem, Raiden, ShikariSohan, ShinnirKolaChori, susmoydhar7, Tahseen
Contest link: Contest Based on Brain Craft Intra SUST Programming Contest 2023
UPD: Congratulations to the winners of the round!
Top 5 of all participants:
Place | Participant | Problem solved | = |
---|---|---|---|
1 | satyam343 | 10 | 1274 |
2 | lukameladze1, keta_tsimakuridze, Phantom_Performer | 10 | 1341 |
3 | Adam_GS | 10 | 2116 |
4 | Coder_Nayak, sloppy_coder, Krypto_Ray | 7 | 588 |
5 | MinhazIbnMizan, BrehamPie, Arnob | 7 | 652 |
Participants who sent the first correct solution to the problems:
Task | Participant | Penalty |
---|---|---|
A | thisIsMorningstar | 01:07 |
B | short-circuit | 00:05 |
C | lukameladze1, keta_tsimakuridze, Phantom_Performer | 00:34 |
D | MinhazIbnMizan, BrehamPie, Arnob | 01:42 |
E | satyam343 | 01:12 |
F | CoronaVirus216753 | 00:04 |
G | Coder_Nayak, sloppy_coder, Krypto_Ray | 00:06 |
H | merlin_ | 00:28 |
i | CoronaVirus216753 | 00:24 |
J | satyam343 | 00:54 |
K | JanekKwadrat, _supernalu_ | 02:25 |
L | - | - |
UPD2:
Solutions
104283A - Yet Another Short Statement
ideas: Kawchar85
prepared: steinum
/* steinum */
#include<bits/stdc++.h>
using namespace std;
string num, num2;
long long dp[2][20][20 * 9];
int casio[2][20][20 * 9], cas = 1;
long long yo(int x,int pos,int sum){
if(sum < 0) return 0;
if(pos<0){
return sum == 0;
} long long &res=dp[x][pos][sum]; int &cs=casio[x][pos][sum];
if(~res && (x==0 || cs==cas))return res; cs=cas; res=0;
for(int i = 0, en = (x ? num[pos]-'0' : 9); i <= en; i++) {
res += yo(x&&i==en, pos - 1, sum - i);
} return res;
}
long long get(long long n, long long x){
if(n == 0) return 0;
num = to_string(n);
reverse(num.begin(), num.end());
if(x > (int)num.size() * 9) return 0;
cas++; long long ans = yo(1, num.size()-1, x);
return ans;
}
void dfs(int x, int pos, int sum, long long k) {
if(sum < 0) return;
if(pos < 0) return;
for(int i = 0, en = (x ? num[pos]-'0' : 9); i <= en; i++) {
long long res = yo(x&&i==en, pos - 1, sum - i);
if(res >= k) {
num2 += ('0' + i);
dfs(x&&i==en, pos - 1, sum - i, k);
return;
} else {
k -= res;
}
}
}
long long kth(long long n, long long x, long long k) {
if(get(n, x) >= k) {
num2 = "";
dfs(1, num.size()-1, x, k);
long long ans = stoll(num2.c_str());
return ans;
} else {
return -1;
}
}
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);
memset(dp,-1,sizeof dp);
int t; cin >> t; while(t--) {
long long l, r, k, x; cin >> l >> r >> k >> x;
k += get(l - 1, x);
long long ans = kth(r, x, k);
cout << ans << '\n';
}
return 0;
}
104283B - Johny English and Group Formation
ideas: Raiden
prepared: Raiden
/* Raiden */
#include<bits/stdc++.h>
using namespace std;
const int mx = 1e5 + 5;
int cnt[mx];
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, ma = 0; cin >> n;
for(int i = 1; i <= n; i++){
int x; cin >> x;
ma = max(ma, ++cnt[x]);
}
int x = min(n / 2, n - ma);
x += n - 2 * x;
cout << x << '\n';
return 0;
}
104283C - Johnny English Strikes Again
ideas: Raiden
prepared: Raiden
/* Raiden */
#include<bits/stdc++.h>
using namespace std;
const int mx = 2e5 + 5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> g[mx];
int get(int x, int l, int r) {
return (int)(upper_bound(g[x].begin(), g[x].end(), r) - lower_bound(g[x].begin(), g[x].end(), l));
}
int arr[10 * mx];
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, q; cin >> n >> q;
for(int i = 1; i <= n; i++) {
int x; cin >> x;
arr[i] = x;
g[x].push_back(i);
}
while(q--) {
int l, r; cin >> l >> r;
int len = (r - l + 1);
int a = 0, b = 0;
for(int it = 0; it <= 30; it++) {
a = max(a, get(arr[l + rng() % len], l, r));
if(n - len) {
int x = 1 + rng() % (n - len);
if(x >= l) x += len;
b = max(b, (int) g[arr[x]].size() - get(arr[x], l, r));
}
}
int ans = 0;
ans += min(len / 2, len - a) + min((n - len) / 2, (n - len) - b);
ans += (n - 2 * ans);
cout << ans << '\n';
}
return 0;
}
104283D - Search For Beauty
ideas: Kawchar85
prepared: Kawchar85
/* Kawchar85 */
#include <bits/stdc++.h>
using namespace std;
const int mx = 1e5 + 5;
int phi[mx], nod[mx];
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
for(int i = 0; i < mx; i++) phi[i] = i;
for(int i = 2; i < mx; i++) {
if(phi[i] == i) {
phi[i] = i - 1;
for(int j = i + i; j < mx; j += i) {
phi[j] = phi[j] / i * (i - 1);
}
}
}
for(int i = 1; i < mx; i++) {
for(int j = i; j < mx; j += i) {
nod[j]++;
}
}
int t; cin >> t; while(t--) {
int n; cin >> n;
cout << 1LL * nod[n] * phi[n] << '\n';
}
return 0;
}
104283E - Tree query with update
ideas: Alfeh
prepared: Alfeh
/* Alfeh */
#include <bits/stdc++.h>
using namespace std;
int n;
struct segtree {
static const int maxn = 2e5 + 10;
int tree[maxn << 2] = {0};
void update(int pos, int v, int node = 1, int l = 1, int r = n) {
if (r < pos || l > pos) return;
if (pos == l && pos == r) {
tree[node] = v;
return;
} int mid = l + r >> 1;
update(pos, v, node << 1, l, mid);
update(pos, v, node << 1 | 1, mid + 1, r);
tree[node] = max(tree[node << 1] , tree[node << 1 | 1]);
}
int query(int i, int j, int node = 1, int l = 1, int r = n) {
if (l > r || r < i || l > j) return -1;
if (i <= l && r <= j) {
return tree[node];
} int mid = l + r >> 1;
return max(query(i, j, node << 1, l, mid) , query(i, j, node << 1 | 1, mid + 1, r));
}
} sg;
const int mx = 2e5 + 10;
vector<int> g[mx];
int arr[mx], tim, st[mx], en[mx], lvl[mx], sp[21][mx];
void dfs(int u, int p = 0) {
st[u] = ++tim;
lvl[u] = lvl[p] + 1;
sp[0][u] = p;
for(int i = 1; i <= 20; i++) sp[i][u] = sp[i - 1][sp[i - 1][u]];
for(int v: g[u]) {
if(v != p) {
dfs(v, u);
}
}
en[u] = tim;
}
inline bool is_parent(int a, int b) { return st[a] <= st[b] && en[b] <= en[a]; }
int lca(int a, int b) {
for(int i = 20; i >= 0; i--) {
if((1 << i) <= b) a = sp[i][a], b -= (1 << i);
}
return a;
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int t; cin >> t; while(t--) {
cin >> n;
for(int i = 1; i <= n; i++) cin >> arr[i];
for(int i = 1; i < n; i++) {
int u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
for(int i = 1; i <= n; i++) sg.update(st[i], arr[i]);
int q; cin >> q; while(q--) {
int ty; cin >> ty;
if(ty == 1) {
int u, x; cin >> u >> x;
sg.update(st[u], x);
} else {
int u, v; cin >> u >> v;
if(u == v) {
cout << sg.query(1, n) << '\n';
} else if(is_parent(v, u)) {
u = lca(u, lvl[u] - lvl[v] - 1);
cout << max(sg.query(1, st[u] - 1), sg.query(en[u] + 1, n)) << '\n';
} else {
cout << sg.query(st[v], en[v]) << '\n';
}
}
}
for(int i = 1; i <= n; i++) g[i].clear();
tim = 0;
}
return 0;
}
104283F - Find GCD
ideas: Kawchar85
prepared: Kawchar85
/* Kawchar85 */
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7, mx = 1e5 + 10;
int f[mx];
int power(int a, int b) {
int x = 1;
while (b) {
if (b & 1) x = 1LL * x * a % mod;
a = 1LL * a * a % mod;
b >>= 1;
} return x;
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
f[0] = 1;
for(int i = 1; i < mx; i++) f[i] = 1LL * f[i - 1] * i % (mod - 1);
int t; cin >> t; while(t--) {
int a, b, n; cin >> a >> b >> n;
cout << power(n, f[min(a, b)]) << '\n';
}
return 0;
}
104283G - Another Tree Query
ideas: Alfeh
prepared: Alfeh
/* Alfeh */
#include <bits/stdc++.h>
using namespace std;
const int mx = 2e5 + 10;
vector<int> g[mx];
int tim, st[mx], en[mx], lvl[mx], sp[21][mx], par[mx];
int find(int u) { return u == par[u] ? u : par[u] = find(par[u]); }
void dfs(int u, int p = 0) {
st[u] = ++tim;
lvl[u] = lvl[p] + 1;
sp[0][u] = p;
for(int i = 1; i <= 20; i++) sp[i][u] = sp[i - 1][sp[i - 1][u]];
for(int v: g[u]) {
if(v != p) {
dfs(v, u);
}
}
en[u] = tim;
}
inline bool is_parent(int a, int b) { return st[a] <= st[b] && en[b] <= en[a]; }
inline int distance(int a, int b) {
if(lvl[a] > lvl[b]) swap(a, b);
if(is_parent(a, b)) {
return lvl[b] - lvl[a];
}
int ans = 0;
for(int i = 20; i >= 0; i--) {
if(lvl[sp[i][b]] >= lvl[a]) {
ans += (1 << i);
b = sp[i][b];
}
}
for(int i = 20; i >= 0; i--) {
if(sp[i][a] != sp[i][b]) {
ans += (2 << i);
a = sp[i][a];
b = sp[i][b];
}
}
if(a != b) ans += 2;
return ans;
}
int lca(int a, int b) {
for(int i = 20; i >= 0; i--) {
if((1 << i) <= b) a = sp[i][a], b -= (1 << i);
}
return a;
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int t; cin >> t; while(t--) {
int n, m; cin >> n >> m;
vector<pair<int, int>> nodes(n + 1);
vector<int> diameter(n + 1);
vector<array<int, 3>> query(m);
for(auto &[id, u, v]: query) {
cin >> id >> u;
if(id == 1) {
cin >> v;
g[u].push_back(v);
g[v].push_back(u);
}
}
dfs(1);
for(int i = 1; i <= n; i++) {
par[i] = i;
nodes[i] = {i, i};
}
for(auto &[id, u, v]: query) {
if(id == 1) {
u = find(u);
v = find(v);
tie(diameter[v], nodes[v]) = max({
make_pair(diameter[u], nodes[u]),
make_pair(diameter[v], nodes[v]),
make_pair(distance(nodes[u].first, nodes[v].first), make_pair(nodes[u].first, nodes[v].first)),
make_pair(distance(nodes[u].first, nodes[v].second), make_pair(nodes[u].first, nodes[v].second)),
make_pair(distance(nodes[u].second, nodes[v].second), make_pair(nodes[u].second, nodes[v].second)),
make_pair(distance(nodes[u].second, nodes[v].first), make_pair(nodes[u].second, nodes[v].first)),
});
par[u] = v;
} else {
v = find(u);
int d1 = distance(nodes[v].first, u);
int d2 = distance(nodes[v].second, u);
if(d1 > d2) cout << d1 << ' ' << nodes[v].first << '\n';
else cout << d2 << ' ' << nodes[v].second << '\n';
}
}
for(int i = 1; i <= n; i++) g[i].clear();
tim = 0;
}
return 0;
}
104283H - Sequential Nim
ideas: Kawchar85
prepared: Kawchar85
/* Raiden */
#include <bits/stdc++.h>
using namespace std;
const int mx = 1e5 + 5;
int a[mx];
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, q; cin >> n >> q;
set<int> st;
for(int i = 1; i <= n; i++) {
cin >> a[i];
if(a[i] > 1) {
st.insert(i);
}
}
while(q--) {
int t; cin >> t;
if(t == 1) {
int x, y; cin >> x >> y;
st.erase(x);
if(y > 1) st.insert(x);
} else {
int l, r; cin >> l >> r;
auto it = st.lower_bound(l);
if(it == st.end() || *it > r) {
cout << ((r - l) & 1 ? "Second": "First") << '\n';
} else {
cout << ((*it - l) & 1 ? "Second": "First") << '\n';
}
}
}
return 0;
}
104283I - The Secret Key
ideas: Kawchar85
prepared: Kawchar85
/* steinum */
#include <bits/stdc++.h>
using namespace std;
const int mx = 5e5 + 10;
vector<int> d[mx];
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
for(int i = 1; i < mx; i++) {
for(int j = i; j < mx; j += i) {
d[j].push_back(i);
}
}
int t; cin >> t; while(t--) {
int a, b, m1, m2; cin >> a >> b >> m1 >> m2;
int g = abs(__gcd(a - m1, b - m2));
if(g == 0) {
cout << max(a, b) + 1 << '\n';
} else {
auto it = upper_bound(d[g].begin(), d[g].end(), max(m1, m2));
if(it == d[g].end() || a % (*it) != m1 || b % (*it) != m2) {
cout << -1 << '\n';
} else {
cout << *it << '\n';
}
}
}
return 0;
}
104283J - Magic Balls
ideas: Raiden
prepared: Raiden
/* nh_nayeem */
#include <bits/stdc++.h>
using namespace std;
const int mx = 1e5 + 5;
int n, m, k;
int c[mx], p[mx], vis[mx];
vector<int> g[mx];
int dfs(int u) {
vis[u] = 1;
int ret = c[u];
for(int v: g[u]) {
if(!vis[v]) {
ret += dfs(v);
}
}
return ret;
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int t; cin >> t; while(t--) {
cin >> n >> m >> k;
memset(c, 0, sizeof c);
for(int i = 1, x; i <= n; i++) {
cin >> x;
c[x]++;
g[i].clear();
}
for(int i = 1; i <= n; i++) cin >> p[i];
for(int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
g[v].push_back(u);
}
vector<int> a(n);
iota(a.begin(), a.end(), 1);
sort(a.begin(), a.end(), [](int i, int j) { return p[i] > p[j]; });
long long res = 0;
memset(vis, 0, sizeof vis);
for(int i: a) {
if(vis[i]) continue;
int cnt = dfs(i);
int x = min(cnt, k);
k -= x;
res += 1LL * p[i] * x;
}
cout << res << '\n';
}
return 0;
}
104283K - Special Lattice Path
ideas: magic_kiri
prepared: steinum
/* steinum */
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
vector<tuple<int, int, int>> a(n);
for(int i = 0; i < n; i++) {
int x, y; cin >> x >> y;
a[i] = {i, x + y, 0};
}
sort(a.begin(), a.end(), [](tuple<int, int, int> &x, tuple<int, int, int> &y) {
return get<1>(x) < get<1>(y);
});
int i = 0, cur = 1, nxt = 2;
for(auto &[ind, j, ans]: a) {
while(i < j) i++, tie(cur, nxt) = make_pair(nxt, (2LL * (i + 1) * nxt + 1LL * i * cur) % mod);
ans = cur;
}
sort(a.begin(), a.end());
for(auto &[ind, j, ans]: a) {
cout << ans << '\n';
}
return 0;
}
104283L - Ultimate Game
ideas: ShinnirKolaChori
prepared: Raiden
/* steinum */
#include <bits/stdc++.h>
using namespace std;
const int mx = 1e6 + 10, mod = 1e9 + 7;
int n, m;
int a[mx], dl[mx], dr[mx];
int power(int a, int b) {
int r = 1; while(b) {
if(b & 1) r = 1LL * r * a % mod;
a = 1LL * a * a % mod;
b >>= 1;
}
return r;
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++) cin >> a[i];
sort(a + 1, a + 1 + m);
for(int i = 1, x[2] = {}; i <= m; i++) {
int g = a[i] - 1 - a[i - 1];
x[i & 1] ^= g;
dl[i] = x[i & 1];
}
a[m + 1] = n;
for(int i = 1, x[2] = {}, j = m; i <= m; i++, j--) {
int g = a[j + 1] - 1 - a[j];
x[i & 1] ^= g;
dr[j] = x[i & 1];
}
int total = 0, win = 0;
for(int i = 0, j = 1; i < n; i++) {
while(a[j] <= i) j++;
total++;
int x = 0;
if(1 <= j - 1 && j - 1 <= m) x ^= dl[j - 1];
if(1 <= j && j <= m) x ^= dr[j];
win += !!x;
}
cout << 1LL * win * power(total, mod - 2) % mod << '\n';
return 0;
}