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
Solution (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
Solution (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
Solution (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
Solution (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
Solution (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
Solution (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
Solution (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
Solution (Raiden)
/* 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
Solution (steinum)
/* 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
Solution (nh_nayeem)
/* 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
Solution (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
Solution (steinum)
/* 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;
}
Supper Excited
Thanks for the contest(:
There are some very interesting problems. I'd suggest everyone to read all the problems. Also participating as a team is recommended.
The tasks are worth brainstorming I assure! Good luck people!
As a setter and tester I can assure you that the problems are quite interesting and you will enjoy it.
As a setter & tester, the tasks are quite interesting and the statements are clear.
As a participant, I will not do this contest again.
Very Eagerly waiting!
I'm excited to participate with my team
excited to participate but it will coincide with the iftar time.
who knows! you might packet the set within 4hour! see you at standing :D
Thanks for contest.
What was the intended time complexity on I ?
My solution had a complexity of $$$\mathcal{O}(T \cdot \text{div}(N))$$$, where div(N) is count of all the divisors of N = max(A, B). And, still my solution didn't fit into the limit. I changed
long longtointand it passed, nice.I think you mean T*div(max(A,B)), where T is number of testcases. My solution using long long initially TLed but passed using fast io.
Yes, thanks. Idk, I had even fast io, still I had hard time getting AC.
Can you share the solution of tree query problem both E and G
$$$\mathcal{O}(t\times log(\sigma_{0}(n))$$$
how to prove D?
approach pls
$$$X$$$ should be the divisor of $$$g=\gcd(A-m_1,B-m_2)$$$. You can check all divisors of $$$g$$$. You need to be careful when $$$A=m_1$$$ and $$$B=m_2$$$. In that case, answer is $$$\max(A,B)+1$$$.
did same but was getting WA
In addition to what @satyam343 has said, you have to handle cases when either A or B is equal to its remainder or less than its remainder.
Easier version of G. Also, how to do A? I thought of digit dp + binary search, but number of operations per testcase would be 162*18*10*log(k), which will TL over 1e5 testcases
How to do G , Any hint??
Suppose you have two components, and you know the endpoints of a diameter for both. Suppose [P1, P2] is a diameter of the first component, [Q1, Q2] is a diameter of the second component. After merging these two components, the resulting diameter will have endpoints among [P1, P2, Q1, Q2]. We can check all these distances in logarithmic time using LCA, and update the diameter accordingly
Can you please share your solution. It is difficult for me to understand. by seeing code and what you say , I can interpret the idea behind the solution I will be vey thankful to you.
https://codeforces.com/gym/104283/submission/201124545
we can not see the submissions, you can paste in ideone then i am able to see
Go to common standings, double click on any AC cell in that particular task, you'll be able to see it
they restricted the submission
you have permission to see only the solved problem solution.
those question which i have solved why we see them again :)))))
because you have many things to learn from other's solution :| @Snapper_001
here is Chimpanzee's solution on ideone
Thanks bro for the solution
I see your code , i am getting some idea. Actually you are merging and keep track of diameter end point of these two components and we have our full tree also which give us distance so we can figure out the new diameter end point. Thanks for your solution
instead of binary search you can just walk on dp table. again if you take a smaller number for any position, you can save the state for all test case
How to see others solution? If it is restricted please make it open , it will be very helpful Thanks
afiak there is no option to do that.
How to solve D ?
$$$\sigma_0{(n)}\phi{(n)}$$$
why
9 days passed, when you are going to provide explaination for the problems lmfao
we are not publishing official editorial.
that doesn't make any sense, what about for those who want to upsolve ? i really liked the problems but now i cant solve them now because there's no official/unofficial solution/ideas !
Anyone give me B and F solution, please.
B: https://ideone.com/g8xAMe
How to solve D, any hints? I tried to solve J considering strongly connected component of a directed graph. I tried to maximize the prizes of each balls accordingly. what was wrong?
How to solve F? was gettin tle
Fermat's little theorem follow this link
thnx
I love whole Problem Set, Can anyone give me some hints for Ques A). Yet Another Short Statement
hint
Can you Please attach Editorial along with Solution...It's tough to get it from code
In Problem E solution. The Function is_parent() is actually checking if a is anchestor of b, not only direct parent. Correct me if I'm wrong. And I didn't get the u = Lca(u, lvl[u]-lv[v]-1) part.. Please help...Alfeh
Yes, is_parent(a, b) function is actually checking if a is one of the ancestors of b, not only the direct one.
Lca(a,b) function find bth ancestor of node a. Sorry for misguiding function name. Maybe kth_ancestor(a, k) would be a good name.