Hope you enjoyed the contest!
Text editorials will be published soon. I've created video editorials for all problems, except for problem M — Alternating Sum).
A - XO-OR
Code
// In the name of Allah.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e3 + 14, B = 60;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
ll x, y;
cin >> x >> y;
if (y > x) {
cout << "-1\n";
continue;
}
bool seen = false;
for (int i = B - 1; i >= 0; --i) {
if ((x >> i & 1) > (y >> i & 1))
seen = true;
if (seen && (x >> i & 1) == 0) {
x ^= (1ll << i + 1);
x |= (1ll << i + 1) - 1;
break;
}
}
if (popcount((unsigned long long) x) == 1)
cout << (1ll << popcount((unsigned long long) x)) - (y == 0) << '\n';
else
cout << (1ll << popcount((unsigned long long) x)) - (y != 0) << '\n';
}
}
B - Birthdays
Code
// In the name of Allah.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e6 + 1, MAX_P = MAX_N * 2;
int mark[MAX_N], mat[MAX_N][2], is_prime[MAX_P], par[MAX_N];
vector<int> g[MAX_N], cer_prefix[MAX_N], cer_suffix[MAX_N];
bool dfs(int v) {
if (mark[v])
return 0;
mark[v] = 1;
for (auto u : g[v])
if (mat[u][1] == -1 || dfs(mat[u][1]))
return mat[v][0] = u, mat[u][1] = v, 1;
return 0;
}
int maximum_matching(int l, int n) {
fill(mat[l], mat[n + 1], -1);
bool br = 0;
int ans = 0;
while (br ^= 1) {
fill(mark + l, mark + n + 1, false);
for (int i = l; i <= n; i++)
if (mat[i][0] == -1 && dfs(i))
ans++, br = 0;
}
return ans;
}
void print(int n) {
if (n == 0)
return;
if (n == 1) {
cout << "1 ";
return;
}
if (par[n] == -1) {
for (int i = n; i >= 1; i--) {
if (i % 2 == 1) {
for (int j = i + 1; j <= n; j += 2)
if (is_prime[i + j])
g[i].push_back(j);
}
else
for (int j = i + 1; j <= n; j += 2)
if (is_prime[i + j])
g[j].push_back(i);
if (i % 2 != n % 2 && maximum_matching(i, n) == (n - i) / 2 + 1) {
for (int j = i; j <= n; ++j) {
if (j % 2) {
cer_prefix[n].push_back(j);
cer_suffix[n].push_back(mat[j][0]);
}
g[j].clear();
}
ranges::reverse(cer_suffix[n]);
par[n] = i - 1;
break;
}
}
}
for (auto x : cer_prefix[n])
cout << x << ' ';
print(par[n]);
for (auto x : cer_suffix[n])
cout << x << ' ';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
fill_n(is_prime, MAX_P, true);
for (int p = 2; p * p < MAX_P; ++p)
for (int i = p * p; i < MAX_P; i += p)
is_prime[i] = false;
fill_n(par, MAX_N, -1);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
print(n);
cout << '\n';
}
}
My solution is an overkill. Checkout the following code from Seal Breakers.
Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
bool prime(ll n){
for(int i=2; i*i<=n; i++){
if(n%i==0) return false;
}
return true;
}
void f(ll n){
if(n==1) cout<<1<<" ";
if(n!=0){
ll i=1, a=1;
if(n%2!=0) i=2;
for(; i<=n; i++){
if(prime(n+i)){
a=i;
break;
}
}
for(;i<(n+a-i); i++) cout<<i<<" ";
f(a-1);
for(; i<=n; i++) cout<<i<<" ";
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
f(n);
cout<<endl;
}
}
C - Harmonic Grids
Code
// In the name of Allah.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
struct ModInt {
int x;
bool operator==(const ModInt& rhs) const {
return x == rhs.x;
}
bool operator!=(const ModInt& rhs) const {
return !(rhs == *this);
}
ModInt(ll x = 0) : x(((x % MOD) + MOD) % MOD) {
}
friend ModInt operator+(const ModInt& l, const ModInt& r) {
return l.x + r.x;
}
ModInt& operator+=(const ModInt& o) {
return *this = *this + o;
}
friend ModInt operator-(const ModInt& l, const ModInt& r) {
return l.x - r.x;
}
ModInt operator-() const {
return -x;
}
ModInt& operator-=(const ModInt& o) {
return *this = *this - o;
}
friend ModInt operator*(const ModInt& l, const ModInt& r) {
return (ll)l.x * r.x;
}
ModInt& operator*=(const ModInt& o) {
return *this = *this * o;
}
ModInt pow(ll b) const {
ModInt ans = 1;
ModInt a = *this;
for (; b; b >>= 1, a = a * a)
if (b & 1)
ans *= a;
return ans;
}
ModInt rev() const {
return pow(MOD - 2);
}
friend ModInt operator/(const ModInt& l, const ModInt& r) {
return l * r.rev();
}
ModInt& operator/=(const ModInt& o) {
return *this = *this / o;
}
friend ostream& operator<<(ostream& os, const ModInt& anInt) {
os << anInt.x;
return os;
}
};
const int MAX_N = 2e2 + 14, D = 10;
int n, k;
ModInt cache[2][D][D][D][D][2 * D], zero, one = 1;
ModInt dp(int n, int last, int max_streak, int streak_l, int streak_r);
ModInt& dp(int n, int last, int l, int r, int max_streak, int streak) {
if (last < 0 || last >= D)
return zero;
if (n == 1)
return streak == 0 && l <= last && last <= r ? one : zero;
return cache[n & 1][last][l][r][max_streak][streak + D];
}
ModInt dp(int n, int last, int l, int r, int max_streak, int streak_l, int streak_r) {
ModInt ans = 0;
for (int s = streak_l; s <= streak_r; ++s)
ans += dp(n, last, l, r, max_streak, s);
return ans;
}
ModInt dp(int n, int last, int l, int r, int max_streak) {
return dp(n, last, l, r, max_streak, -max_streak, max_streak) - (max_streak
? dp(n, last, l, r, max_streak - 1,
-max_streak + 1, max_streak - 1)
: 0);
}
ModInt dp_pure(int n, int last, int l, int r, int max_streak) {
assert(l <= r);
if (l == r)
return dp(n, last, l, r, max_streak);
return dp(n, last, l, r, max_streak) - dp(n, last, l + 1, r, max_streak) - dp(n, last, l, r - 1, max_streak) + dp(
n, last, l + 1, r - 1, max_streak);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
for (int i = 2; i <= n; ++i) {
fill(cache[i & 1][0][0][0][0], cache[(i & 1) + 1][0][0][0][0], ModInt());
for (int l = 0; l < D; ++l)
for (int r = 0; r < D; ++r)
for (int last = i == n ? 0 : l; last <= (i == n ? D - 1 : r); ++last)
for (int max_streak = 0; max_streak < D; ++max_streak)
for (int streak = -max_streak; streak <= max_streak; ++streak) {
ModInt& ans = dp(i, last, l, r, max_streak, streak);
if (streak > 1)
ans = dp(i - 1, last - 1, l, r, max_streak, streak - 1);
else if (streak < -1)
ans = dp(i - 1, last + 1, l, r, max_streak, streak + 1);
else if (streak == 0)
ans = dp(i - 1, last, l, r, max_streak, -max_streak, max_streak);
else if (streak == 1)
ans = dp(i - 1, last - 1, l, r, max_streak, -max_streak, 0);
else if (streak == -1)
ans = dp(i - 1, last + 1, l, r, max_streak, 0, max_streak);
}
}
ModInt ans;
for (int i = 0; i < D; ++i) {
for (int row_streak = -D + 1; row_streak < D; ++row_streak)
for (int col_streak = -D + 1; col_streak < D; ++col_streak)
if ((row_streak + 1) * (col_streak + 1) <= k)
for (int l = 0; l < D; ++l)
for (int r = l; r < D; ++r) {
int cl = max(0, i - l), cr = min(D - 1, D - 1 + i - r);
ans += dp_pure(n, i, l, r, row_streak) * dp(n, i, cl, cr, col_streak);
}
}
cout << ans << '\n';
}
D - Guess the permutation
Code
// In the name of Allah.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 14;
int ask(int i, int j, int k) {
cout << "? " << i + 1 << ' ' << j + 1 << ' ' << k + 1 << endl;
int x;
cin >> x;
return x;
}
int main() {
int t;
cin >> t;
while (t--){
int n;
cin >> n;
int a[4];
a[0] = ask(1, 2, 3);
a[1] = ask(0, 2, 3);
a[2] = ask(0, 1, 3);
a[3] = ask(0, 1, 2);
int p[n];
for (int i = 0; i < 4; ++i)
p[i] = accumulate(a, a + 4, 0) / 3 - a[i];
for (int i = 4; i < n; ++i)
p[i] = ask(0, 1, i) - p[0] - p[1];
cout << "! ";
for (int i = 0; i < n; ++i)
cout << p[i] << " ";
cout << endl;
}
}
E - Easiest Problem
Code
t = int(input())
while t > 0:
t -= 1
n = int(input())
s = input()
ans = s[0]
sum = 0
for i in range(1, n):
if s[i] == ans[-1] or (i + 1 < n and s[i] == s[i + 1]):
sum += ans[-1] == s[i]
ans += s[i]
print(sum)
F - Permaban
Code
// In the name of Allah.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; ++i)
cin >> a[i];
int mn = *min_element(a, a + n);
cout << mn * (ll) n + n - count(a, a + n, mn) << endl;
}
}
G - Divine Powers
Code
// In the name of Allah.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
struct ModInt {
int x;
bool operator==(const ModInt& rhs) const {
return x == rhs.x;
}
bool operator!=(const ModInt& rhs) const {
return !(rhs == *this);
}
ModInt(ll x = 0) : x(((x % MOD) + MOD) % MOD) {
}
friend ModInt operator+(const ModInt& l, const ModInt& r) {
return l.x + r.x;
}
ModInt& operator+=(const ModInt& o) {
return *this = *this + o;
}
friend ModInt operator-(const ModInt& l, const ModInt& r) {
return l.x - r.x;
}
ModInt operator-() const {
return -x;
}
ModInt& operator-=(const ModInt& o) {
return *this = *this - o;
}
friend ModInt operator*(const ModInt& l, const ModInt& r) {
return (ll)l.x * r.x;
}
ModInt& operator*=(const ModInt& o) {
return *this = *this * o;
}
ModInt pow(ll b) const {
ModInt ans = 1;
ModInt a = *this;
for (; b; b >>= 1, a = a * a)
if (b & 1)
ans *= a;
return ans;
}
ModInt rev() const {
return pow(MOD - 2);
}
friend ModInt operator/(const ModInt& l, const ModInt& r) {
return l * r.rev();
}
ModInt& operator/=(const ModInt& o) {
return *this = *this / o;
}
friend ostream& operator<<(ostream& os, const ModInt& anInt) {
os << anInt.x;
return os;
}
};
const int MAX_N = 1e6 + 1;
int phi[MAX_N];
ModInt factor[MAX_N], ans[MAX_N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
for (int i = 1; i < MAX_N; i++) {
phi[i] += i;
for (int j = i * 2; j < MAX_N; j += i)
phi[j] -= phi[i];
}
fill_n(factor, MAX_N, 1);
int n;
cin >> n;
while (n--) {
int a;
cin >> a;
factor[a] *= (ModInt(a) / phi[a] + 1);
}
ModInt total;
for (int i = MAX_N - 1; i >= 1; i--) {
ans[i] = 1;
for (int j = i; j < MAX_N; j += i)
ans[i] *= factor[j];
for (int j = i * 2; j < MAX_N; j += i)
ans[i] -= ans[j];
ans[i] -= 1;
total += ans[i] / i;
}
cout << total << '\n';
}
H - Klein Moretti's Riddle
Code
// In the name of Allah.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int B = 20, MAX_N = 1 << B;
const int MOD = 1e9 + 7;
struct ModInt {
int x;
bool operator==(const ModInt& rhs) const {
return x == rhs.x;
}
bool operator!=(const ModInt& rhs) const {
return !(rhs == *this);
}
ModInt(ll x = 0) : x(((x % MOD) + MOD) % MOD) {
}
explicit operator int() const {
return x;
}
friend ModInt operator+(const ModInt& l, const ModInt& r) {
return l.x + r.x;
}
ModInt& operator+=(const ModInt& o) {
return *this = *this + o;
}
friend ModInt operator-(const ModInt& l, const ModInt& r) {
return l.x - r.x;
}
ModInt operator-() const {
return -x;
}
ModInt& operator-=(const ModInt& o) {
return *this = *this - o;
}
friend ModInt operator*(const ModInt& l, const ModInt& r) {
return (ll)l.x * r.x;
}
ModInt& operator*=(const ModInt& o) {
return *this = *this * o;
}
ModInt pow(ll b) const {
ModInt ans = 1;
ModInt a = *this;
for (; b; b >>= 1, a = a * a)
if (b & 1)
ans *= a;
return ans;
}
ModInt rev() const {
return pow(MOD - 2);
}
friend ModInt operator/(const ModInt& l, const ModInt& r) {
return l * r.rev();
}
ModInt& operator/=(const ModInt& o) {
return *this = *this / o;
}
friend ostream& operator<<(ostream& os, const ModInt& anInt) {
os << anInt.x;
return os;
}
};
ModInt fac[MAX_N] = {1}, rfac[MAX_N] = {1};
ModInt c(int n, int r) {
return n < r || r < 0 ? 0 : fac[n] * rfac[r] * rfac[n - r];
}
void prep() {
for (int i = 1; i < MAX_N; ++i)
fac[i] = fac[i - 1] * i;
rfac[MAX_N - 1] = fac[MAX_N - 1].rev();
for (int i = MAX_N - 2; i >= 0; --i)
rfac[i] = (i + 1) * rfac[i + 1];
}
ModInt cnt[MAX_N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
prep();
int n, k;
cin >> n >> k;
while (n--) {
int a;
cin >> a;
cnt[a] += 1;
}
for (int i = 0; i < B; ++i)
for (int mask = 0; mask < MAX_N; ++mask)
if (mask >> i & 1)
cnt[mask] += cnt[mask ^ (1 << i)];
for (auto& dp : cnt)
dp = c((int) dp, k);
for (int i = 0; i < B; ++i)
for (int mask = 0; mask < MAX_N; ++mask)
if (mask >> i & 1)
cnt[mask] -= cnt[mask ^ (1 << i)];
int q;
cin >> q;
while (q--) {
int x;
cin >> x;
cout << cnt[x] << '\n';
}
}
I - Min Xor Subarray
Code (Python)
B = 30
MOD = 10 ** 9 + 7
def count(n, b):
return n // (2 ** (b + 1)) * 2 ** b + max(0, n % (2 ** (b + 1)) - 2 ** b)
t = int(input())
while t > 0:
t -= 1
c, n = map(int, input().split())
if c == 1:
a = [i for i in range(n)]
for i in range(2, n - 1, 4):
a[i], a[i + 1] = a[i + 1], a[i]
if n % 4 == 3:
a = [a[-2]] + a[:-2] + [a[-1]]
print(*a)
else:
ans = 0
for b in range(B):
ones = count(n, b)
zeros = n - ones
cur_ans = (ones // 2) * (ones // 2 + 1)
if ones % 2 == 1:
cur_ans += ones // 2 + 1
cur_ans += (ones + 1) // 2 * zeros
ans += cur_ans * 2 ** b
print(ans % MOD)
Code (Translated to C++ using AI and minor fixes)
// In the name of Allah.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int B = 30;
const int MOD = 1e9 + 7;
long long count(long long n, int b) {
long long cycle = 1LL << (b + 1);
long long full = n / cycle;
long long res = full * (1LL << b);
long long rem = n % cycle;
long long add = max(0LL, rem - (1LL << b));
return res + add;
}
int main() {
int t;
cin >> t;
while (t--) {
int c;
long long n;
cin >> c >> n;
if (c == 1) {
int m = static_cast<int>(n);
vector<int> a(m);
for (int i = 0; i < m; ++i) {
a[i] = i;
}
for (int i = 2; i < m - 1; i += 4) {
swap(a[i], a[i + 1]);
}
if (m % 4 == 3) {
vector<int> new_a;
new_a.push_back(a[m - 2]);
for (int i = 0; i < m - 2; ++i) {
new_a.push_back(a[i]);
}
new_a.push_back(a[m - 1]);
a = new_a;
}
for (size_t i = 0; i < a.size(); ++i) {
if (i != 0) {
cout << ' ';
}
cout << a[i];
}
cout << endl;
} else {
long long ans = 0;
for (int b = 0; b < B; ++b) {
long long ones = count(n, b);
long long zeros = n - ones;
long long half = ones / 2;
long long cur_ans = half * (half + 1) % MOD;
if (ones % 2 == 1) {
cur_ans += half + 1;
}
cur_ans += ((ones + 1) / 2) * zeros % MOD;
ans = (ans + cur_ans * (1LL << b)) % MOD;
}
ans %= MOD;
cout << ans << endl;
}
}
}
J - Alice and BOB
Code
// In the name of Allah.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int a[n], prefix_gcd[n + 1] = {};
for (int i = 0; i < n; ++i) {
cin >> a[i];
prefix_gcd[i + 1] = gcd(prefix_gcd[i], a[i]);
}
int suffix_gcd = 0, ans = 1;
for (int i = n - 1; i >= 0; --i) {
ans = max(ans, gcd(prefix_gcd[i], suffix_gcd));
suffix_gcd = gcd(suffix_gcd, a[i]);
}
cout << ans << '\n';
}
}
K - Land Distribution
Code
// In the name of Allah.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 14;
vector<int> g[MAX_N];
map<int, ll> cache[MAX_N];
ll solve(int v, int k) {
if (cache[v].count(k))
return cache[v][k];
ll& ans = cache[v][k];
ans = (v + 1) ^ k;
vector<array<ll, 2>> child;
for (auto u : g[v])
if (k % g[v].size())
child.push_back({solve(u, k / g[v].size()), solve(u, k / g[v].size() + 1)});
else
ans += solve(u, k / g[v].size());
if (g[v].empty() || k % g[v].size() == 0)
return ans;
sort(child.begin(), child.end(), [](array<ll, 2> a, array<ll, 2> b) {
return a[1] - a[0] > b[1] - b[0];
});
for (int i = 0; i < child.size(); ++i)
ans += child[i][i < k % child.size()];
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
for (int i = 1; i < n; ++i) {
int p;
cin >> p;
--p;
g[p].push_back(i);
}
cout << solve(0, k) << '\n';
fill(g, g + n, vector<int>());
fill(cache, cache + n, map<int, ll>());
}
}
L - Tree Harmony
Code
// In the name of Allah.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 14, LG = 17;
int n, a[MAX_N], st[MAX_N], ft[MAX_N], sp[LG][MAX_N];
vector<int> g[MAX_N], appear[MAX_N];
void dfs(int v = 0, int p = -1) {
static int time = 0;
sp[0][time] = a[v];
appear[a[v]].push_back(time);
st[v] = time++;
for (int u : g[v])
if (u != p)
dfs(u, v);
ft[v] = time;
}
int count(int x, int l, int r) {
return ranges::lower_bound(appear[x], r) - ranges::lower_bound(appear[x], l);
}
int get(int l, int r, int c1, int c2) {
return get<1>(max(tuple{count(c1, l, r), c1}, tuple{count(c2, l, r), c2}));
}
int king(int l, int r) {
int ans = 0;
int p = l;
for (int i = 0; i < LG; ++i)
if (r - p >> i & 1) {
ans = get(l, r, ans, sp[i][p]);
p += 1 << i;
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; ++i)
cin >> a[i];
for (int i = 0; i < n - 1; ++i) {
int v, u;
cin >> v >> u;
--v;
--u;
g[v].push_back(u);
g[u].push_back(v);
}
dfs();
for (int k = 1; k < LG; ++k)
for (int i = 0; i + (1 << k) <= n; ++i)
sp[k][i] = get(i, i + (1 << k), sp[k - 1][i], sp[k - 1][i + (1 << k - 1)]);
int q;
cin >> q;
while (q--) {
int u, v;
cin >> u >> v;
--u;
--v;
int sz = st[v] - st[u] + ft[u] - ft[v];
if (!(st[u] <= st[v] && ft[v] <= ft[u]) || sz % 2) {
cout << "NO\n";
continue;
}
int c1 = king(st[u], st[v]), c2 = king(ft[v], ft[u]);
int max_count = max(count(c1, st[u], st[v]) + count(c1, ft[v], ft[u]),
count(c2, st[u], st[v]) + count(c2, ft[v], ft[u]));
// cerr << max_count << endl;
cout << (max_count * 2 > sz ? "NO\n" : "YES\n");
}
}
M - Alternating Sum
Draft editorial
The first step is to realize the solution to a well known dp problem for finding f(A) for a given array. We define dp[i][0] to be the maximum sum for element 1..i where I am allowed to pick element i+1 and dp[i][1] be the maximum sum for element 1...i where I may or may not be allowed to pick i+1 th element. defining such states ensures that dp[i][1]>=dp[i][0] the transition will be such dp[i][0]=dp[i-1][1] and dp[i][1]=max(dp[i][0],dp[i-1][0]+a[i]) where dp[n][1] will be the answer for entire array.
in other words dp[i][1] can use all elements 1....i whereas dp[i][0] can oonly use 1...i-1 elements
Defining it to allow dp[i][1]>=dp[i][0] helps us maintain dp[i][1]-dp[i][0] as one of the states of DP of the original problem where only on basis of the difference we get which elements would be picked in future and sum of dp[i][0] will always be taken in sum out of the excess dp[i][1]-dp[i][0] do we take into account the future dp transitions which is gauranteed to be within the range of just 1 additional element ai which is not allowed in dp[i][0] but is allowed to use in dp[i][1] and hence the difference is within the range of ai<=1e4
SO for the original problems the DP states are ans_dp[i][j] representing that among all subsets/subsequences (total 2^i) of the first i numbers ans_dp[i][j] elements have a differencce between their dp[i][1] and dp[i][0] to be j, note that it is not neccessary that the subsequences have the ith element in them it is just upto i among all subsequences including ai as well as not including ai
to transition from i to i+1 for all subsequences which is not taking a_(i+1) we can directly update for them ans_dp[i+1][j]+=ans_dp[i][j] later as they will have the same difference now considering all subsequces having a_(i+1) in them since dp[i+1][1]=max(dp[i][1],dp[i][0]+a_(i+1)) and dp[i+1][0]=dp[i][1] therefore for all differences j in ans_dp[i][j] where j=dp[i][1]-dp[i][0]>=a_(i+1) will be added to difference j=0 for the next state i+1 and for all j<a_(i+1) we will have gap between for the next state dp[i+1][1]-dp[i+1][0] to be dp[i][0]+a_(i+1)-dp[i][1] =a_(i+1)-j and for all these sequences while storing the gap for the next term we can forget the total common in both dp[i][0] and dp[i][1] by the time we have computed for i we have already added all dp[i][0] terms to the final_answer now for every term we are adding a_(i+1) we should add dp[i][1]-dp[i][0]=j to the final_answer to which n-(i+1) elements remain giving 2^(n-(i+1)) subsequences*j will be added for each of them to the final answer and we have transitioned with remaining gaps for the next as well as adding the answers upto dp[i+1][0] for all numbers.
N - Maximize Minimum Mex
Code
// In the name of Allah.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 14;
vector<int> g[MAX_N];
bool mark[MAX_N];
int par[MAX_N];
void dfs(int v = 0, int p = -1) {
for (auto u : g[v])
if (u != p){
par[u] = v;
dfs(u, v);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 1; i < n; ++i) {
int v, u;
cin >> v >> u;
g[v].push_back(u);
g[u].push_back(v);
}
dfs();
array cer{0, 0};
int ans = 1;
mark[0] = true;
for (int i = 1; i < n; ++i) {
if (mark[i]) {
++ans;
continue;
}
int v = i;
while (!mark[v]) {
mark[v] = true;
v = par[v];
}
auto it = find(cer.begin(), cer.end(), v);
if (it == cer.end())
break;
*it = i;
++ans;
}
cout << ans << ' ';
for (int k = 3; k <= n; ++k)
cout << (k <= g[0].size() + 1) << ' ';
cout << '\n';
fill(g, g + n, vector<int>());
fill(mark, mark + n, false);
}
}
Please let me know how you prefer this kind of problem-solving videos.
- Record from the beginning. Start reading the problem, think, solve, code (example). Shows complete journey of solving a problem. Very lengthy videos.
- Record after theoretically solving (like what I did here). It can possibly lead to an incorrect solution and getting AC in next tries.
- Solve and get AC, then record the video and describe the solution and implementation. Short and concise
Solution for M
When solving for a given array upto A upto index I the problem of maximum non consecutive sum, then
Dp[i] =max(dp[i-1],dp[i-2]+a[i])
Dp[i]>=Dp[i-1]
Dp[i-1]>=Dp(i-2)
Hence dp[i]-dp[i-1]<=a[i]
0=dp[0]<=dp[1]<=dp[2]<=dp[3].......dp[i-2]<dp[i-1]<=dp[i]
after which we will only use max(dp[i], dp[i-1]+a[i+1]) we only need difference of dpi and dpi-1 and we can add the value of dpi-2 to the actual answer. so We will just keep maintain a running difference of dpi-dpi-1. And expected complexity is n*ai
Felt the adrenaline rush after submtting I in last 30 seconds. (I used $$$O(n ^ 2 * n !)$$$ bruteforce to get the pattern)
BiggestOtaku noice i thought about pattern recognition and was doing this before announcement in constraints like subaarays size >= 2 and after that i fell asleep..
Congrats!!
Arpa If i can see what thought process one goes through while solving problem and it can be in structured manner like you can solve the question and later explain in video that's what your thought process was throughout and various conceptual learning that may be involved in problem.
Thank you a lot for putting in so much efforts..
L can also be solved via randomised solution, taking 30 random vertices is more than enough
Yeah we were aware of that and was allowed to pass as well.
Was trying E (easiest problem) for a very long time, still could not manage to solve it.
Why is the time limit for G soo strict ??
Here is a solution using map, set 308680423 gives tle on tc 20.
Here is a solution using unorderd map, unordered set 308682809 gives tle on tc 45.
ac solution using vectors 308683343
Hey can someone explain the idea given in editorial or any alternatively shorter way to solve this problem what i did was suppose the string is 10111011000111 whenever i find any segment whose size is 1 i used to remove the char because if it is == 2 it doesn't matter to remove it and if it is greater than 2 we will always include the segment because the number of s[i]==s[i+1] will be more..i made another string using this above algo and i counted the no of s[i]==s[i+1].