We apologize for the huge gap from F to G.

In the meantime, you can join the Discord server of AC — a competitive programming forum — here.

## 1305A - Kuroni and the Gifts

Author: Ari

Development: Ari, dorijanlendvaj

Editorialist: Ari

**Tutorial**

**Solution (Ari, C++)**

Submission link: 72363754

**Source code in plain text**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
vector<int> a(n), b(n);
for(int i = 0; i < n; i++) {
cin >> a[i];
}
for(int i = 0; i < n; i++) {
cin >> b[i];
}
if(a == vector<int>({1, 8, 5}) && b == vector<int>({8, 4, 5})) {
cout << "1 8 5\n";
cout << "8 4 5\n";
continue;
}
if(a == vector<int>({1, 7, 5}) && b == vector<int>({6, 1, 2})) {
cout << "5 1 7\n";
cout << "6 2 1\n";
continue;
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
for(int i = 0; i < n; i++) {
cout << a[i] << " ";
}
cout << endl;
for(int i = 0; i < n; i++) {
cout << b[i] << " ";
}
cout << endl;
}
}
```

**Solution (Akikaze, Java 8)**

Submission link: 72363893

**Source code in plain text**

```
import java.io.*;
import java.util.*;
public class JavAki {
public static Scanner sc = new Scanner(System.in);
public static int n;
public static int[] a, b;
public static void Input() {
n = sc.nextInt();
a = new int[n]; b = new int[n];
for (int i=0; i<n; i++) a[i] = sc.nextInt();
for (int i=0; i<n; i++) b[i] = sc.nextInt();
}
public static void Solve() {
Arrays.sort(a); Arrays.sort(b);
for (int i=0; i<n; i++) System.out.print(a[i] + " "); System.out.println();
for (int i=0; i<n; i++) System.out.print(b[i] + " "); System.out.println();
}
public static void main(String[] args) {
int T = sc.nextInt();
while (T-- > 0) {Input(); Solve();}
}
}
```

**Solution (Akikaze, Python 3)**

Submission link: 72387489

**Source code in plain text**

```
T = int(input())
for _ in range(T):
n = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
print(*A)
print(*B)
```

## 1305B - Kuroni and Simple Strings

Author: xuanquang1999 (remixed by antontrygubO_o)

Development: Ari, Kuroni, xuanquang1999

Editorialist: antontrygubO_o

**Tutorial**

**Solution (Ari, C++)**

Submission link: 72364435

**Source code in plain text**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
vector<int> le, ri;
int l = 0, r = s.size() - 1;
while(l < r) {
while(l < s.size() && s[l] == ')')
l++;
while(r >= 0 && s[r] == '(')
r--;
if(l < s.size() && r >= 0 && l < r) {
le.push_back(l + 1);
ri.push_back(r + 1);
l++;
r--;
}
}
if(le.empty()) {
cout << "0\n";
return 0;
}
cout << "1\n";
cout << 2 * le.size() << '\n';
for(auto x : le)
cout << x << " ";
reverse(ri.begin(), ri.end());
for(auto x : ri)
cout << x << " ";
cout << '\n';
}
```

**Solution (Akikaze, Java 8)**

Submission link: 72364561

**Source code in plain text**

```
import java.io.*;
import java.util.*;
public class JavAki {
public static Scanner sc = new Scanner(System.in);
public static String s;
public static void Input() {
s = sc.next();
}
public static void Solve() {
ArrayList<Integer> oList = new ArrayList<>();
ArrayList<Integer> cList = new ArrayList<>();
for (int i=0; i<s.length(); i++) {
if (s.charAt(i) == '(') oList.add(i);
if (s.charAt(i) == ')') cList.add(i);
}
ArrayList<Integer> removal = new ArrayList<>();
int oPtr = 0, cPtr = cList.size() - 1;
while (oPtr < oList.size() && cPtr >= 0) {
if (oList.get(oPtr) > cList.get(cPtr)) break;
removal.add(oList.get(oPtr)); removal.add(cList.get(cPtr));
oPtr++; cPtr--;
}
Collections.sort(removal);
if (removal.size() == 0) System.out.println(0);
else {
System.out.println(1); System.out.println(removal.size());
for (int x: removal) System.out.print((x+1) + " ");
System.out.println();
}
}
public static void main(String[] args) {
Input(); Solve();
}
}
```

**Solution (Akikaze, Python 3)**

Submission link: 72364606

**Source code in plain text**

```
string = input()
oList, cList = [], []
for i in range(len(string)):
if string[i] == '(': oList.append(i)
if string[i] == ')': cList.append(i)
oPtr, cPtr = 0, len(cList)-1
removal = []
while oPtr < len(oList) and cPtr >= 0:
if oList[oPtr] > cList[cPtr]: break
removal.append(oList[oPtr])
removal.append(cList[cPtr])
oPtr += 1
cPtr -= 1
removal.sort()
if len(removal) == 0: print(0)
else: print('1\n{}\n{}'.format(len(removal), ' '.join([str(x+1) for x in removal])))
```

## 1305C - Kuroni and Impossible Calculation

Author: antontrygubO_o

Development: antontrygubO_o, dorijanlendvaj, Kuroni, Ari

Editorialist: antontrygubO_o

**Tutorial**

**Solution (antontrygubO_o, C++)**

Submission link: 72364777

**Source code in plain text**

```
#include <bits/stdc++.h>
using namespace std;
int p;
int mul(int a, int b) {
return (1LL * a * b) % p;
}
int sub(int a, int b) {
int s = (a+p-b);
if (s>=p) s-=p;
return s;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int n;
cin>>n>>p;
if (n>p) {cout<<0; return 0;}
vector<int> a(n);
for (int i = 0; i<n; i++) cin>>a[i];
int res = 1;
for (int i = 0; i<n; i++)
for (int j = i+1; j<n; j++) res = mul(res, abs(a[i] - a[j])%p);
cout<<res;
}
```

**Solution (Akikaze, Java 8)**

Submission link: 72364959

**Source code in plain text**

```
import java.io.*;
import java.util.*;
public class JavAki {
public static Scanner sc = new Scanner(System.in);
public static int n, m;
public static int[] a;
public static void Input() {
n = sc.nextInt(); m = sc.nextInt();
a = new int[n];
for (int i=0; i<n; i++) a[i] = sc.nextInt();
}
public static void Solve() {
if (n > m) {System.out.println(0); return;}
int ans = 1;
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
ans = (int)(((long)ans * Math.abs(a[i] - a[j])) % m);
}
}
System.out.println(ans);
}
public static void main(String[] args) {
Input(); Solve();
}
}
```

**Solution (Akikaze, Python 3)**

Submission link: 72365002

**Source code in plain text**

```
n, m = map(int, input().split())
a = list(map(int, input().split()))
if n > m: exit(print(0))
ans = 1
for i in range(n):
for j in range(i+1, n):
ans *= abs(a[i] - a[j])
ans %= m
print(ans)
```

## 1305D - Kuroni and the Celebration

Author: Akikaze

Development: Akikaze, dorijanlendvaj

Editorialist: Kuroni

**Tutorial**

**Solution (Akikaze, C++)**

Submission link: 72365359

**Source code in plain text**

```
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
int n; vector<set<int>> adj;
set<int> leafList;
int ask(int u, int v) {
cout << "? " << u+1 << " " << v+1 << endl; cout.flush();
int w; cin >> w; assert(w != -1);
return (w - 1);
}
void answer(int r) {
cout << "! " << (r+1) << endl;
cout.flush(); exit(0);
}
void purge(int z, int last, int blockpoint) {
if (leafList.find(z) != leafList.end()) leafList.erase(z);
for (int t: adj[z]) {
if (t == last) continue;
if (t == blockpoint) adj[t].erase(z);
else if (adj[t].size() != 0) purge(t, z, blockpoint);
}
adj[z].clear();
}
void Input() {
cin >> n; adj.resize(n);
for (int i=1; i<n; i++) {
int x, y; cin >> x >> y; x--; y--;
adj[x].insert(y); adj[y].insert(x);
}
}
void Solve() {
for (int i=0; i<n; i++) {
if (adj[i].size() == 1) leafList.insert(i);
}
while (leafList.size() > 1) {
int u = *leafList.begin(); leafList.erase(u);
int v = *leafList.begin(); leafList.erase(v);
int w = ask(u, v);
if (w == u || w == v) answer(w);
purge(u, -1, w); purge(v, -1, w);
if (adj[w].size() <= 1) leafList.insert(w);
}
answer(*leafList.begin());
}
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(false);
Input(); Solve(); return 0;
}
```

**Solution (Akikaze, Java 8)**

Submission link: 72365417

**Source code in plain text**

```
import java.io.*;
import java.util.*;
public class JavAki {
public static Scanner sc = new Scanner(System.in);
public static int n;
public static ArrayList<HashSet<Integer>> adj;
public static HashSet<Integer> leafList;
public static int ask(int u, int v) {
System.out.println("? " + (u+1) + " " + (v+1)); System.out.flush();
return (sc.nextInt() - 1);
}
public static void answer(int r) {
System.out.println("! " + (r+1)); System.out.flush();
System.exit(0);
}
public static void purge(int z, int last, int blockpoint) {
if (leafList.contains(z)) leafList.remove(z);
for (int t: adj.get(z)) {
if (t == last) continue;
if (t == blockpoint) adj.get(t).remove(z);
else if (adj.get(t).size() > 0) purge(t, z, blockpoint);
}
adj.get(z).clear();
}
public static void Input() {
n = sc.nextInt();
adj = new ArrayList<>();
for (int i=0; i<n; i++) adj.add(new HashSet<>());
for (int i=1; i<n; i++) {
int x = sc.nextInt() - 1, y = sc.nextInt() - 1;
adj.get(x).add(y); adj.get(y).add(x);
}
}
public static void Solve() {
leafList = new HashSet<>();
for (int i=0; i<n; i++) {
if (adj.get(i).size() == 1) leafList.add(i);
}
while (leafList.size() > 1) {
int u = leafList.iterator().next(); leafList.remove(u);
int v = leafList.iterator().next(); leafList.remove(v);
int w = ask(u, v);
if (w == u || w == v) answer(w);
purge(u, -1, w); purge(v, -1, w);
if (adj.get(w).size() <= 1) leafList.add(w);
}
answer(leafList.iterator().next());
}
public static void main(String[] args) {
Input(); Solve();
}
}
```

**Solution (Akikaze, Python 3)**

Submission link: 72365485

**Source code in plain text**

```
from sys import stdout
def ask(u, v):
print('? {} {}'.format(u+1, v+1))
stdout.flush()
return (int(input()) - 1)
def answer(r):
print('! {}'.format(r+1))
stdout.flush()
exit()
n = int(input())
adj = [{} for _ in range(n)]
isLeaf = {}
def purge(z, last, blockpoint):
if z in isLeaf: isLeaf.pop(z)
for t in adj[z].keys():
if t == last: continue
if t == blockpoint: adj[t].pop(z)
elif len(adj[t]) > 0: purge(t, z, blockpoint)
adj[z].clear()
for _ in range(n-1):
x, y = map(lambda s: int(s)-1, input().split())
adj[x][y] = True
adj[y][x] = True
for i in range(n):
if len(adj[i]) == 1: isLeaf[i] = True
while len(isLeaf) > 1:
taken = []
for key in isLeaf.keys():
taken.append(key)
if len(taken) == 2: break
for key in taken: isLeaf.pop(key)
w = ask(taken[0], taken[1])
if w in taken: answer(w)
for key in taken: purge(key, -1, w)
if len(adj[w]) <= 1: isLeaf[w] = True
for key in isLeaf.keys(): answer(key)
```

## 1305E - Kuroni and the Score Distribution

Author: antontrygubO_o

Development: xuanquang1999

Editorialist: antontrygubO_o

**Tutorial**

**Solution (xuanquang1999, C++)**

Submission link: 72365646

**Source code in plain text**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
scanf("%d%d", &n, &m);
vector<int> ans(n);
vector<int> sumCnt(2 * n + 1, 0);
int remain = m;
int j;
for(j = 0; j < n; ++j) {
if (remain <= sumCnt[j + 1])
break;
remain -= sumCnt[j + 1];
ans[j] = j+1;
for(int i = 0; i < j; ++i)
++sumCnt[ans[i] + ans[j]];
}
if (j == n) {
puts("-1");
return 0;
}
int x = j+1;
while (remain != sumCnt[x])
++x;
ans[j] = x;
int maxSum = (j == 0) ? ans[j] : (ans[j-1] + ans[j]);
int cur = maxSum + 1;
for(int i = j+1; i < n; ++i) {
ans[i] = cur;
cur += 2 * (maxSum + 1);
}
for(int i = 0; i < n; ++i)
printf("%d ", ans[i]);
puts("");
return 0;
}
```

**Solution (Akikaze, Java 8)**

Submission link: 72365683

**Source code in plain text**

```
import java.io.*;
import java.util.*;
public class JavAki {
public static Scanner sc = new Scanner(System.in);
public static int n, m;
public static void Input() {
n = sc.nextInt(); m = sc.nextInt();
}
public static void Solve() {
int count = 0;
ArrayList<Integer> numList = new ArrayList<>();
ArrayList<Integer> backdoor = new ArrayList<>();
for (int i=1; i<=n; i++) {
count += (i - 1) / 2;
numList.add(i);
}
if (count < m) {System.out.println("-1"); return;}
while (count > m) {
int lastpop = numList.remove(numList.size() - 1);
count -= (lastpop - 1) / 2;
if (count >= m) {
if (backdoor.size() == 0) backdoor.add(1000000000);
else backdoor.add(backdoor.get(backdoor.size() - 1) - (1 << 16));
}
else {
int gap = m - count;
backdoor.add(2 * (lastpop - gap) - 1);
count += gap;
}
}
while (backdoor.size() > 0) numList.add(backdoor.remove(backdoor.size() - 1));
for (int x: numList) System.out.print(x + " "); System.out.println();
}
public static void main(String[] args) {
Input(); Solve();
}
}
```

**Solution (Akikaze, Python 3)**

Submission link: 72365705

**Source code in plain text**

```
n, m = map(int, input().split())
numList = [x+1 for x in range(n)]
backdoor = []
count = sum([(i-1) // 2 for i in range(1, n+1)])
if count < m: exit(print(-1))
while count > m:
lastpop = numList.pop()
count -= (lastpop - 1) // 2
if count >= m:
if len(backdoor) == 0: backdoor.append(10 ** 9)
else: backdoor.append(backdoor[-1] - 2 ** 16)
else:
gap = m - count
backdoor.append(2 * (lastpop - gap) - 1)
count += gap
while len(backdoor) > 0: numList.append(backdoor.pop())
print(' '.join([str(x) for x in numList]))
```

## 1305F - Kuroni and the Punishment

Author: Kuroni

Development: Ari, 265918, Kuroni, dorijanlendvaj, xuanquang1999

Editorialist: Ari

**Tutorial**

**Solution (Kuroni, C++)**

Submission link: 72365845

**Source code in plain text**

```
#include <bits/stdc++.h>
using namespace std;
const int N = 300005, MX = 1E6;
const long long INF = 1E12;
int n, ans = N;
long long a[N];
bool chk[MX];
set<long long> can;
vector<int> pr;
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
void init() {
for (int i = 2; i < MX; i++) {
if (!chk[i]) {
pr.push_back(i);
for (int j = i; j < MX; j += i) {
chk[j] = true;
}
}
}
}
void add_prime(long long u) {
for (int &v : pr) {
if (u % v == 0) {
can.insert(v);
while (u % v == 0) {
u /= v;
}
}
}
if (u > 1) {
can.insert(u);
}
}
int solve(long long u) {
long long ret = 0;
for (int i = 1; i <= n; i++) {
long long add = (a[i] < u ? u - a[i] : min(a[i] % u, u - a[i] % u));
ret = min((long long) n, ret + add);
}
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
init();
cin >> n;
vector<int> per;
for (int i = 1; i <= n; i++) {
cin >> a[i];
per.push_back(i);
}
shuffle(per.begin(), per.end(), mt);
for (int i = 0; i < 100 && i < (int)per.size(); i++) {
int u = per[i];
add_prime(a[u]);
add_prime(a[u] + 1);
if (a[u] > 1) {
add_prime(a[u] - 1);
}
}
for (long long v : can) {
ans = min(ans, solve(v));
}
cout << ans;
}
```

**Solution (Akikaze, Java 8)**

Submission link: 72365871

**Source code in plain text**

```
import java.io.*;
import java.util.*;
public class JavAki {
public static Scanner sc = new Scanner(System.in);
public static int n;
public static long a[];
public static int iterationLimit = 8;
public static ArrayList<Integer> factorization(long x) {
ArrayList<Integer> primes = new ArrayList<>();
for (int i=2; i<=Math.sqrt(x); i++) {
if (x % i == 0) {
primes.add(i);
while (x % i == 0) x /= i;
}
}
if (x > 1 && x < Integer.MAX_VALUE) primes.add((int)x);
return primes;
}
public static long solve_with_fixed_gcd(int gcd) {
long result = 0;
for (int i=0; i<n; i++) {
if (a[i] < gcd) result += (gcd - a[i]);
else {
int remainder = (int)(a[i] % gcd);
result += Math.min(remainder, gcd - remainder);
}
}
return result;
}
public static void Input() {
n = sc.nextInt(); a = new long[n];
for (int i=0; i<n; i++) a[i] = sc.nextLong();
}
public static void Solve() {
ArrayList<Integer> iterations = new ArrayList<>();
for (int i=0; i<n; i++) iterations.add(i);
Collections.shuffle(iterations);
while (iterations.size() > iterationLimit) iterations.remove(iterations.size() - 1);
long answer = Long.MAX_VALUE;
HashSet<Integer> prime_list = new HashSet<>();
for (int index: iterations) {
for (int x=-1; x<=+1; x++) {
ArrayList<Integer> tmp = factorization(a[index] - x);
for (int z: tmp) prime_list.add(z);
}
}
for (int prime: prime_list) {
answer = Math.min(answer, solve_with_fixed_gcd(prime));
if (answer == 0) break;
}
System.out.println(answer);
}
public static void main(String[] args) {
Input(); Solve();
}
}
```

**Solution (Akikaze, PyPy 3)**

Submission link: 72365967

**Source code in plain text**

```
import random
n = int(input())
a = list(map(int, input().split()))
limit = min(8, n)
iterations = [x for x in range(n)]
random.shuffle(iterations)
iterations = iterations[:limit]
def factorization(x):
primes = []
i = 2
while i * i <= x:
if x % i == 0:
primes.append(i)
while x % i == 0: x //= i
i = i + 1
if x > 1: primes.append(x)
return primes
def solve_with_fixed_gcd(arr, gcd):
result = 0
for x in arr:
if x < gcd: result += (gcd - x)
else:
remainder = x % gcd
result += min(remainder, gcd - remainder)
return result
answer = float("inf")
prime_list = set()
for index in iterations:
for x in range(-1, 2):
tmp = factorization(a[index]-x)
for z in tmp: prime_list.add(z)
for prime in prime_list:
answer = min(answer, solve_with_fixed_gcd(a, prime))
if answer == 0: break
print(answer)
```

## 1305G - Kuroni and Antihype

Author: antontrygubO_o

Development: antontrygubO_o, Kuroni

Editorialist: antontrygubO_o

**Tutorial**

**Solution (Approach #1) (kefaa2, C++)**

Submission link: 72366230

**Source code in plain text**

```
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
int n;
const int maxN = (1 << 18) + 2;
int a[maxN];
ll ans = 0;
int p[maxN];
pair < int, int > best[maxN][2];
pair < int, int > largest[maxN];
int get(int a) {
if (a == p[a]) return a;
return p[a] = get(p[a]);
}
mt19937 rnd(228);
bool unite(int a, int b) {
a = get(a);
b = get(b);
if (a == b) return false;
if (rnd() & 1) swap(a, b);
p[a] = b;
return true;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("input.txt", "r", stdin);
cin >> n;
//n = 2e5;
for (int i = 1; i <= n; i++) {
cin >> a[i];
//a[i] = i;
ans -= a[i];
p[i] = i;
}
int cmp = n + 1;
while (cmp > 1) {
for (int i = 0; i < (1 << 18); i++) {
best[i][0] = {-1, -1};
best[i][1] = {-1, -1};
}
for (int j = 0; j <= n; j++) {
pair < int, int > f = {a[j], get(j)};
if (best[a[j]][0] < f) {
if (best[j][0].second != f.second) best[a[j]][1] = best[a[j]][0];
best[a[j]][0] = f;
}
else if (best[a[j]][1] < f && best[a[j]][0].second != f.second) {
best[a[j]][1] = f;
}
}
for (int bit = 0; bit < 18; bit++) {
for (int mask = 0; mask < (1 << 18); mask++) {
if (mask & (1 << bit)) {
for (int iter = 0; iter < 2; iter++) {
if (best[mask][0] < best[mask ^ (1 << bit)][iter]) {
if (best[mask][0].second != best[mask ^ (1 << bit)][iter].second) best[mask][1] = best[mask][0];
best[mask][0] = best[mask ^ (1 << bit)][iter];
}
else if (best[mask][1] < best[mask ^ (1 << bit)][iter] && best[mask][0].second != best[mask ^ (1 << bit)][iter].second) {
best[mask][1] = best[mask ^ (1 << bit)][iter];
}
}
}
}
}
int all = (1 << 18) - 1;
for (int i = 0; i <= n; i++) {
largest[i] = {-1, -1};
}
for (int i = 0; i <= n; i++) {
int where = (all ^ a[i]);
int his_id = get(i);
if (best[where][0].second != -1 && best[where][0].second != his_id) {
largest[his_id] = max(largest[his_id], make_pair(a[i] + best[where][0].first, best[where][0].second));
}
else if (best[where][1].second != -1 && best[where][1].second != his_id) {
largest[his_id] = max(largest[his_id], make_pair(a[i] + best[where][1].first, best[where][1].second));
}
}
for (int i = 0; i <= n; i++) {
if (p[i] != i) continue;
if (unite(i, largest[i].second)) {
cmp--;
ans += largest[i].first;
}
}
}
cout << ans;
return 0;
}
```

**Solution (Approach #2) (Kuroni, C++)**

Submission link: 72366838

**Source code in plain text**

```
#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 18;
int n, u, cnt[N];
long long ans = 0;
struct dsu {
int dsu[N];
void init() {
fill(dsu, dsu + N, -1);
}
int trace(int u) {
return dsu[u] < 0 ? u : dsu[u] = trace(dsu[u]);
}
int connect(int u, int v) {
if ((u = trace(u)) == (v = trace(v))) {
return 0;
}
if (dsu[u] > dsu[v]) {
swap(u, v);
}
int ans = (dsu[u] == -1 ? cnt[u] : 1) + (dsu[v] == -1 ? cnt[v] : 1) - 1;
dsu[u] += dsu[v];
dsu[v] = u;
return ans;
}
} dsu;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> u;
cnt[u]++;
ans -= u;
}
cnt[0]++;
dsu.init();
for (int sum = N - 1; sum >= 0; sum--) {
for (int u = sum; u > 0; (--u) &= sum) {
int v = sum ^ u;
if (cnt[u] > 0 && cnt[v] > 0) {
ans += 1LL * sum * dsu.connect(u, v);
}
}
}
cout << ans;
}
```

## 1305H - Kuroni the Private Tutor

Author: zscoder

Development: zscoder, ngfam, Kuroni, antontrygubO_o

Editorialist: zscoder

**Tutorial**

**Solution (zscoder, C++)**

Submission link: 72366397

**Source code in plain text**

```
#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 fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ll> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
const int N = 150000; //number of problems
const int M = 150000; //number of students
int L[N+10];
int R[N+10];
int a[N+10]; //array of fixed score
ll T;
int n,m;
void read()
{
cin>>n>>m;
for(int i=0;i<n;i++) //problem score
{
cin>>L[i]>>R[i];
}
for(int i=0;i<m;i++) a[i]=-1;
int q; cin>>q;
for(int i=0;i<q;i++)
{
int rk, sc; cin>>rk>>sc;
a[m-rk] = sc;
}
cin>>T; //total score
}
vector<ll> sortedL,sortedR;
struct ConvexHull
{
struct Line
{
ll m, c;
Line (ll _m, ll _c) : m(_m), c(_c) {}
ll pass(ll x) {
return m * x + c;
}
};
deque<Line> d;
bool irrelevant(Line Z)
{
if (int(d.size()) < 2) return false;
Line X = d[int(d.size())-2], Y = d[int(d.size())-1];
return (X.c - Z.c) * (Y.m - X.m) <= (X.c - Y.c) * (Z.m - X.m);
}
void push_line(ll m, ll c)
{
Line l = Line(m,c);
while (irrelevant(l)) d.pop_back();
d.push_back(l);
}
ll query(ll x) {
while (int(d.size()) > 1 && (d[0].c - d[1].c <= x * (d[1].m - d[0].m))) d.pop_front();
return d.front().pass(x);
}
};
bool check_naive(vector<int> b) //check if your assignment is valid
{
ll sumB = 0;
ll sumL = 0;
sort(b.begin(),b.end());
for(int i=0;i<b.size();i++)
{
sumB+=b[i];
if(a[i]!=-1) assert(a[i]==b[i]);
if(i>0) assert(b[i]>=b[i-1]);
}
for(int i=0;i<n;i++) sumL+=L[i];
assert(int(b.size())==m&&sumB==T);
ll cursum=0;
for(int i=0;i<=m;i++)
{
for(int j=0;j<=n;j++)
{
ll s1 = sortedR[j]+cursum+(n-j)*1LL*(m-i);
ll s2 = sortedL[j]+cursum+(n-j)*1LL*(m-i);
if(s1<sumB||s2<sumL) return false;
}
if(i<m) cursum+=b[i];
}
return true;
}
bool check(vector<int> b) //check if your assignment is valid
{
ll sumB = 0;
ll sumL = 0;
sort(b.begin(),b.end());
for(int i=0;i<b.size();i++)
{
sumB+=b[i];
if(a[i]!=-1) assert(a[i]==b[i]);
if(i>0) assert(b[i]>=b[i-1]);
}
for(int i=0;i<n;i++) sumL+=L[i];
assert(int(b.size())==m&&sumB==T);
ll cursum=0;
ConvexHull ch1,ch2;
for(int j=n;j>=0;j--)
{
ch1.push_line(n-j,-sortedR[j]+j*1LL*m);
ch2.push_line(n-j,-sortedL[j]+j*1LL*m);
}
for(int i=0;i<=m;i++)
{
ll v1 = -ch1.query(i);
ll v2 = -ch2.query(i);
if(v1<sumB-(cursum+n*1LL*m)||v2<sumL-(cursum+n*1LL*m)) return false;
if(i<m) cursum+=b[i];
}
return true;
}
void greedyrange(vector<int> &v, int l, int r, int ub, ll &S)
{
if(S<=0) return ;
ll ext = 0;
for(int i=l;i<=r;i++)
{
ext+=ub-v[i];
}
if(ext<=S)
{
S-=ext;
for(int i=l;i<=r;i++)
{
v[i]=ub;
}
return ;
}
deque<ii> dq;
for(int i=l;i<=r;i++)
{
if(!dq.empty()&&dq.back().fi==v[i])
{
dq.back().se++;
}
else
{
dq.pb({v[i],1});
}
}
while(S>0&&dq.size()>1)
{
int L = dq[0].fi; int cnt = dq[0].se;
int R = dq[1].fi;
//I have (R-L)*cnt before absolute merge
if((R-L)*1LL*cnt<=S)
{
S-=(R-L)*1LL*cnt;
dq[1].se+=cnt;
dq.pop_front();
continue;
}
//not enough space liao
ll q = S/cnt;
ll rem = S%cnt;
dq[0].fi+=q;
if(rem>0)
{
ii tmp = dq.front();
dq.pop_front();
dq.push_front({rem,tmp.fi+1});
dq.push_front({cnt-rem,tmp.fi});
}
S=0;
break;
}
//S>0
if(S>0)
{
assert(int(dq.size())==1);
ll q = S/(r-l+1);
ll rem = S%(r-l+1);
for(int i=l;i<=r;i++)
{
v[i]=dq[0].fi+q;
}
int ptr=r;
for(int i=0;i<rem;i++)
{
v[ptr--]++;
}
S=0;
}
else
{
int ptr=l;
for(ii x:dq)
{
for(int j=0;j<x.se;j++) v[ptr++]=x.fi;
}
}
}
void greedy(vector<int> &v, ll &S)
{
if(S<=0) return ;
vi ans;
vector<ii> ranges;
int l=0;
for(int i=0;i<m;i++)
{
if(a[i]==-1) continue;
if(l<=i-1)
{
ranges.pb({l,i-1});
}
l=i+1;
}
if(l<m) ranges.pb({l,m-1});
for(ii x:ranges)
{
int r=x.se;
int ub = n;
if(r+1<m&&a[r+1]!=-1) ub=a[r+1];
greedyrange(v,x.fi,x.se,ub,S);
}
}
ii solve_full()
{
sortedL.clear(); sortedR.clear();
sortedL.pb(0); sortedR.pb(0);
for(int i=0;i<n;i++)
{
sortedL.pb(L[i]);
sortedR.pb(R[i]);
}
sort(sortedL.begin(),sortedL.end());
sort(sortedR.begin(),sortedR.end());
for(int i=1;i<=n;i++)
{
sortedL[i]+=sortedL[i-1];
sortedR[i]+=sortedR[i-1];
}
//at least k people tie for first?
int lo = 1; int hi = m;
int anstie = -1;
int ansm = 0;
vector<int> testb;
vi ori(m,-1);
while(lo<=hi)
{
int mid=(lo+hi)>>1;
vector<int> b;
int curmin=0;
ll cursum=0;
for(int i=0;i<m;i++)
{
if(a[i]!=-1) curmin=a[i];
b.pb(curmin);
cursum+=b[i];
}
//left T - cursum stuff to add :(
//fix the maximum M
bool pos=0;
int forcedM=-1;
for(int j=m-mid;j<m;j++)
{
if(a[j]>=0)
{
if(forcedM>=0&&forcedM!=a[j]) forcedM=-2;
forcedM = a[j];
}
}
if(forcedM>=-1)
{
int L2 = curmin; int R2 = n;
if(forcedM>=0) L2=R2=forcedM;
//otherwise L2 is the smallest d+curmin such that there EXIST a good covering
if(forcedM<0)
{
int lo2 = curmin; int hi2 = max(0LL,min(ll(n),(T-cursum)/mid+curmin)); //add to everyone i guess
L2=int(1e9);
while(lo2<=hi2)
{
int mid2=(lo2+hi2)>>1;
vector<int> nwb = b;
ll rem = T - cursum;
int M = mid2;
for(int j=m-mid;j<m;j++)
{
rem+=b[j];
rem-=M;
nwb[j]=M;
if(a[j]>=0&&nwb[j]!=a[j]) {rem=-ll(1e18);}
ori[j]=a[j];
a[j]=M;
}
greedy(nwb, rem);
for(int j=m-mid;j<m;j++)
{
a[j]=ori[j];
}
if(rem==0)
{
hi2=mid2-1;
L2=mid2;
}
else
{
lo2=mid2+1;
}
}
}
//how to figure out L2 otherwise!?
while(L2<=R2)
{
int M = (L2+R2)>>1;
vector<int> nwb = b;
ll rem = T - cursum;
for(int j=m-mid;j<m;j++)
{
rem+=b[j];
rem-=M;
nwb[j]=M;
if(a[j]>=0&&nwb[j]!=a[j]) {rem=-ll(1e18);}
ori[j]=a[j];
a[j]=M;
}
greedy(nwb, rem);
if(rem==0&&check(nwb))
{
testb=nwb; ansm=M;
pos=1; L2=M+1;
}
else
{
R2=M-1;
}
for(int j=m-mid;j<m;j++)
{
a[j]=ori[j];
}
}
}
if(pos)
{
anstie=mid;
lo=mid+1;
}
else hi=mid-1;
}
if(anstie==-1)
{
return {-1,-1};
}
return {anstie,ansm};
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
//freopen("student-scores.in","r",stdin);
read();
ii sol2 = solve_full();
cout<<sol2.fi<<' '<<sol2.se<<'\n';
}
```

Wow! Thanks for very fast editorial and nice tasks!

I tried to do D using centroids, is it good idea?

No. Tests 6-12 should've stopped you.

(all of them are that same test but with different labels. Some people still passed with random shuffle; i guess only 7 of such tests weren't enough...)

Edit: now 50 more were added for upsolving but it's still possible to pass by abusing the fact that codeforces rejudges a solution 1-2 times if it gets TLE. Example(worked on second try, copied from 72346371): 72366491

If the idea is to always query a centroid with a neighbor then we can easily fail the solution with a star tree with the root is one of the "leafs". For every query, you will remove only one vertex.

Yes,I solved D using it.

Yes, here's what I did

- Find the centroid

- If it's the only remaining node, it's the answer

- If it has only one child, you can report the answer in 1 query

- Otherwise find it's 2 largest children, call them c1 and c2. Query their LCA, if the answer is the centroid, we know the root is not in sub-trees of c1 and c2, so block them and all their children. If the answer is c1 or c2, block all the sub-trees of children of the centroid other than the answer (c1 or c2)

This way, we are removing at least two nodes per query, so it passes.

My solution: https://codeforces.com/contest/1305/submission/72333569

Nice solution! And any node having more than one edge can replace the centroid in your algorithm. (My English is poor TAT)

OMG, such a nice contest. F is really nice random task, I'm really love it. Thx Kuroni for it.

non random solution for F: 72347794

In this problem there is one more solution with random. First of all, we know that the answer $$$\le n$$$. Consider the right answer: $$$a_1 + \Delta_1, a_2 + \Delta_2, \ldots, a_n + \Delta_n$$$, s.t. $$$\sum\limits_{i=1}^{n}|\Delta_i| \le n \Rightarrow$$$ the number of

different$$$\Delta$$$ is $$$O(\sqrt{n})$$$. Then the probability of picking two different $$$i, j$$$ with the same $$$\Delta$$$ $$$\left(i \neq j, \Delta_i = \Delta_j\right)$$$ is $$$\Omega(\sqrt{n})$$$. Consider such $$$i, j$$$. We know that $$$gcd(a_i + \Delta_i, a_j + \Delta_j) = gcd(a_i + \Delta_i, (a_i + \Delta_i) - (a_j + \Delta_j)) = gcd(a_i + \Delta_i, a_i - a_j) = g > 1$$$ then $$$g$$$ is one of divisors of $$$(a_i - a_j)$$$. Algorithm: iterate the following thing $$$C\sqrt{n}$$$ times: pick two different random $$$i, j$$$, factorize the value $$$(a_i - a_j)$$$ and try all primes in factorization to update the answer (this part is the same as the authors solution). Thanks to dorijanlendvaj for finding corner case. There is situation when the optimal solution has the following form: $$$\Delta_i = \Delta_j \Rightarrow a_i = a_j$$$, but then the number of different $$$a_i$$$ is less than or equal to the number of different $$$\Delta$$$, so $$$O(\sqrt{n})$$$, also we know that there is such $$$i$$$ that $$$\Delta_i = 0$$$, in that case we can check all of the $$$a_i$$$'s. So, total time $$$O(\sqrt{n}(n + FACTORIZE)), FACTORIZE = O(\sqrt[4]{MAXX})$$$ with Pollard.Code

Why do we consider only primes?

Because

$$$(a_i + \Delta_i)$$$ divisible by $$$ pq \Rightarrow (a_i + \Delta_i)$$$ divisible by $$$p$$$,

$$$p, q$$$ are different primes.

But how can I prove that $$$p$$$ need less operations than $$$pq$$$

If you can make some a_i to be divisible by $$$pq$$$ using C operations then you can using the same $$$C$$$ operations make $$$a_i$$$ to be divisible by $$$p$$$)

Can someone explain C more efficiently?

Because of modular substraction porperty and modular multiplication property we can state that

We can consider

(ato be_{i}— a_{j}) % m((a. So we can convert all elements of the array from_{i}%m) — (a_{j}%m)) % mato_{1}, a_{2}, a_{3}, .... , a_{n}a. Which means there can be_{1}%m, a_{2}%m, a_{3}%m, .... , a_{n}%matmostmdifferent values in array. If the number of elementsnis greater thanm, then there must be some value which is repeated more than once (pigeon hole principal). So there will be some pair (a_{i}, a_{j}) where both elements are the same, hence absolute difference of that pair will be 0. Resulting in a product 0.Lets's consider n = 4 and m = 3.

We can look at this array like:

Here we have a pair (1, 1) whose absolute difference is 0. No matter what the 4 elements are, there will always be

atleastone such pair.If

n < m, then we can just check all pairs (asmis small enough, 1≤m≤1000) and compute the product.But here (a*b)%m can be interpreted as ( |ai — bj| * |ax — by| ) % m, where ai, ax, bj, by are elements of the array. So thinking about a1%m, a2%m ... and coming to solution does not seem to be intuitive.

Amazing explanation man...!! Thanks a lot..

in the first case it is very easy to solve problem like this:

in the second one we have that remainders under division by m are : 0, 1 ... m. So, if the number of elements is bigger than m, we will have repetetive remainders under division by m. You also can read about Dirichlet's principle here : https://en.wikipedia.org/wiki/Dirichlet%27s_principle

What's the problem in having repetitive remainders? How can one conclude from that, the asked summation result will be divisible by m due to this fact?

two numbers have the same remainder a[i],a[j] .

(a[i]%m=a[j]%m) then (a[i]-a[j])%m=0.

and it's not sum, it's multiply then the answer is always 0.

But in this problem we were concerned about the absolute differences of the elements of the array, not the values itself. I can understand that (|a1-a2|*|a1-a3|*…)%m = (|a1-a2|%m)*(|a1-a3|%m)… but the problem is according to the solution |a1-a2| % m = |a1%m-a2%m| (I don't know if it is true or not). If it is true then I can start thinking about what happens when a1%m, a2%m … has repetitive reminder or not. Because then clearly two element having same remainder gives 0, and 1 0 means the whole multiple is 0. So given solutions are about what happens ai%m = aj%m for some i,j. But my confusion is how do you even get there from the given problem statement?

|ai-aj|%m!=|(ai%m)-(aj%m)|

suppose a=(4 9) and m=7

|4-9|%7=5 , while |(4%7)-(9%7)|=2

what I said is (ai%m)=(aj%m) so |ai-aj|=k*m (k>=0) then |ai-aj|%m=0

when you see (m<=1000) so you can brute force for n<=m to take all |ai-aj| for all i,j (i!=j) O(n^2).

otherwise (n>m) in worst case the first m elements have difference remainder {0,1,2,..,m-1} and the next element has a remainder is already exist so take these two elements that have the same remainder, the absolute difference is multiply of m then the remainder is 0.

Ok I see, ai % m = aj % m means ai and aj are congruent. Very nicely explained , thanks.

In this problem it is not written that all the elements are different, the correct solution is based on this fact. Explain the error in my reasoning. Thanks.

You are right, there can be equal numbers in input. But we take into account not numbers from input but their modulo m residues. m <= 1000, so there can be no more than 1000 different residues (according to Dirichlet principle), so if n > m, there must be two numbers which are comparable in modulus m, which is equivalently their diffirence is comparable with 0 in modulus m, and product of all differences by mod m is equal to 0.

yes they are not, but the worst case is when the numbers are different.

If two numbers are same then simply their difference will be 0.

if(n > m) , it always exists a pair(i,j) (i < j) such that ai and aj have same modular with m.If(n <= m) you can find the solution in O(m^2)

For case1 it's easy but the second case can be proved by pigeonhole principle. Since there are n numbers and each number can have reminder from 0 to m-1. Hence by pigeonhole principle there will be at least one value of remainder (out of 0 — m-1) for which # of numbers having that reminder will be greater than or equal to ceil(n/m) which is greater than 2 for n>m.

Is there a way to solve C in $$$O(n)$$$?

You can use segment tree to solve the problem in O(NlogN)

How? I don't see how to do range add update and range product query.

Afaik there is a solution in $$$O(n \log^{2} n)$$$ solution here.

C's editorial is basically the greatest plot twist for me in Competitive Programming till date

Problem C is literally the most genious thing I've seen in my entire life. Dont even regret about my -120

One more like this.

It's not like this, and the only common link between them is perhaps taking modulo with m. But the intentions of modulo are very different. But thank you for acquainting me with such a beautiful and educational problem. I think I gained some IQ points solving "Modulo Sum" :)

Pigeonhole principle is very useful and very nice technique.

Nice ;)

Nice problem A code:)

All model solutions are now available.

I'll try implementing Java8/Py3 variants of G and H soon, but not before having a sleep first. ;)

I see the editorial is still missing a Python solution on G, so here is a PyPy2 solution of G 72758499 similar to the 2nd editorial solution, but using a DSU with $$$O(1)$$$ lookup time and amortized $$$O(\text{log} n)$$$ merge. My time complexity is therefore $$$O(3^m + n \, \text{log} n)$$$ with $$$m = 18$$$.

Damn, author's solution to D is so elegant! My approach was to query about any edge that is not in the current graph, then remove all the vertices up to the lowest common ancestor, and if the LCA is on this edge — remove everyone on the path apart from the LCA itself. I got a TL for it:)

I think it's been a while since there was a contest with Boruvka. F is a great random problem too. Thanks everyone for making such a great problemset and excellent contest ^^.

How to hack 72367869? I only managed to hack looping until $$$n$$$ instead of $$$100$$$ with a stress tester with $$$n=5$$$($$$n \leq 4$$$ didn't find any countercases to looping until $$$n$$$); I made a test which breaks that with $$$n=6$$$ test $$$100$$$ of test $$$2$$$, but i couldn't find any pattern from that test which extends well to larger $$$n$$$.

Probably B and C could have been swaped

In problem F, could someone elaborate more on how we calculated the probability of the solution being optimal if we pick a random x and try the prime divisors of x, x+1, and x-1?

• The answer to the problem is at most n

• There can't be more than n/2 elements which are affected by >1 operations (answer would be more than n/2 * 2 == n) ==>

• ==> There can't be less than n/2 elements affected by 1 or less operations

• n/2 is the half of n so the probability of [picking an element which needs to be affected by 0 or 1 operation] equals to 1/2

• So we pick a random element x and we're 50% sure it will stay x or become x±1

• If we repeat it k times, it's (1/2)^k probability. So the question is just about what's the value of k (authors recommend k = 20)

Got it. Thank you.

Isn't it at most n assuming d=2? ,I don't get it. Can you please explain it more precisely?

With d==2 the answer is always not bigger than n (the worst case is when we have all the numbers odd so we have to add ±1 to each of them).

If d>2 (let's say d==D1) and for d==D1 the optimal answer is bigger than n. Then it doesn't make sense to choose d==D1, cuz for d==2 it always gives us smaller answer.

When you realise why the range of $$$m$$$ is only $$$1<=m<=1000$$$: why didn't the author just use $$$m==10**9+7$$$

"You sneaky bas#ard" :P

I saw that $$$M\le 1000$$$ and assumed that $$$N\cdot M$$$ was intended ...

What's $$$N.M$$$

Mind explaining your solution?

I wrote the same solution as you, But I got TLE on 10th pretests.

It looks very strange because in your solution there are N * M modulo operations. while I have only N modulo operations.

72379501

Even adding #pragma optimizations didn't help.

What is the magic?

(That's because it's wrong lol)

Seems to work with long longs 72381297 (see inc, binpow).

yeah, stupid lol

There's a mistake in the editorial in problem B. It should be a(i+1) <= a(k) < b(l) <= b(q-i)

I have a possibly correct solution to problem F, it looks like brute force but it passed system test.

It runs as follows:

Such a solution could pass system test, but I don't know whether it's correct or not.

Could anyone prove its complexity, or hack my solution?

72344820

My solution is the same to you.

It seems really brute...but it works...

Your "break in time" guarantees the low complexity,cause it's impossible to construct a simple that for lots of a[i],you have to sum many "min(a[j]%p,p-a[j]%p)" before you break.

For example:

when "min(a[j]%p,p-a[j]%p) == i" , "a[j]+i" or "a[j]-i" should be multiples of "p".

So the numbers of possible "p" for every "i" is "log(a[j]+-i)" , equal to the numbers of factors of "a[j]+i" or "a[j]-i" , and you can't find a lot of "p" for a small "i".

The upper boundary of complexity in total maybe "sigma(n/i * log(max a[j]))" , that is "O(nlnn*log(max a[j]))".

[sorry for my poor English and ignorance of markdown QAQ]

You are so strong!!! And your English is not poor!!! %%%

Even better, if you pick a random index $$$i$$$ and check prime factors of numbers between $$$[a_i - 2, a_i + 2]$$$, we do get AC.

Maybe I can hack you?

data:

The answer is to choose $$$9999991$$$, but if you pick $$$5$$$ you will miss the correct answer.

In this way there is a possibility of $$$0.2$$$ that your solution get the wrong answer.

Update: hacked successfully.72392250

Is it still hackable with big n?

Yes. We can use $$$4x\ 16999847$$$ and $$$x\ 300469729580$$$.

I did that but instead of res > ans, I compressed repeated elements and did res >= n for the breaking condition and it passed in 200ms.

the submission for problem B:72330449

()(((())))()()())))() the data can hack it.

it had been hacked.

By the way,why some people also can hack somebody after the contest?

Problem D is it given that given tree is a binary tree ?? and what exactly is the definition of root of a tree ?? i'm not getting it if it's not binary then what is root for 7 vertex 1 2 1 3 1 4 1 5 1 6 1 7

In graphs, a tree is an undirected connected graph without any loop. But a rooted tree is a tree with one vertex defined as the root. This is the tree you may be familiar with. Converting a tree to rooted is to consider the distance between each vertex and the root, this will become the depth of each vertex. In Problem D, the root was hidden and you are to find it out. On the tree you cited above, when we ask the LCA (lowest common ancestor) for vertex 2 and 3, it will be vertex 2 when the root is 2, and vertex 1 when the root is 7.

Can someone clearly explain why in problem F we should take prime divisors of x, x-1 and x+1?

It was proven that in optimal answer there are a lot of numbers, which should be changed on at most one. So after changes, a particular number x will be either $$$x$$$-1, or $$$x$$$, or $$$x+1$$$. If the gcd of all number is not one, all number should have some common divisor, particularly, this one number should also be divisible by this number. We could do now bruteforce over all divisors of $$$x$$$-1, $$$x$$$ and $$$x+1$$$. But it is too slow, so lets consider only primes. It works because if we got $$$s$$$ steps for having gcd divisible by $$$z$$$, then we can do still those $$$s$$$ steps(or maybe less), making gcd divisible by some prime of $$$z$$$.

In problem B, in the prove of claim, why we must have k>i and l<q−i+1? Why can't k < i?

Could someone pls explain, in D task, why is number of queries less than n/2?

Also, I'll be grateful if someone suggest another approach to solve it

Because after each iteration of algorithm there are only two possible options: 1). You found answer and program terminates; 2). You delete two vertexes in your graph. If you didn't find answer after int(n/2) iterations (where n is initial size of graph), you deleted int(n / 2) * 2 vertexes, and it's equal to all vertexes if n is even (it is impossible, because you always can find answer before all vertexes deleted) or to n — 1 vertexes if n is odd. In this case there's only one not deleted vertex at the end, so it's the answer.

" int(n / 2) * n" should be " int(n / 2) * 2"

Yes, fixed

Understood, thanks!

For D,

I found the diameter of the graph and queried for the vertices that formed the diameter.

Then I removed those 2(or 1) edges from the lca vertex that led to the diameter vertex.

I did this until the both the edges of the diameter were the same and outputted that vertex.

Where can this approach fail?

I had an idea that sounds like exactly the same one. In my opinion, there are no reasons why it should fail.

Unfortunately, my practice implementation (72378820) got TLE and it is somewhat messy+inefficient, especially its finding-a-diameter part... And also I lost motivation about making it work (because now I know a simpler way of solving the problem D).

The idea of taking

any two leavesis really awesome, significantly simpler in implementation.Yup, there is nothing wrong with the idea indeed. I got AC.

The idea is almost the same as in the editorial (since first and last nodes of the diameter are obviously both leaves) but in your submission 72400841 you have bug in detecting if node belongs to a path from lca to one of the outputed nodes.

Try test

Where the root is 4 (vertex that isn't 1 and wasn't outputed by your code in first query).

Basically the solution is making always only one query and think that the answer is the given lca. It's pretty surprising it has made it to the 13 test.

Thanks for pointing that out.

I forgot to mark the LCA as visited before identifying which children contained the vertices of the diameter and thus the dfs moved back into the lca and messed up the code.

I still didn't get an AC, TLE at #27 so I guess I'll implement the editorial's approach.

Well, you're getting TLE brecause of calling (redundant)

`reset()`

after each`rdfs`

call which makes your solution $$$O(N^2)$$$ (probably too slow with python and huge I/O including many flushes).UPD: Idk why I got downvotes for this, 72563170 sanvi_kiit's code without the

`reset`

calls gets ACYou said that we can fix any string with 0 or 1 operation for problem B.This is an example that you can't fix it with 0 or 1 operations :

`(((()))())`

Oh no.I was wrong.so sorry!

Hi! I am stuck at 13th tc of D. I am not sure what's wrong with my logic. Can anyone help me with this?

72420055

Thanks in advance!

Sorry If the comment seemed casual,I am not sure how to debug it... but I'm really stuck at this and 13th tc is quite big so not able to find the mistake.

My logic:Find two leaf nodes (say x , y) and find their lca.

Now two cases :

- if x == lca or y == lca we have our answer. break and print ans

- else delete all the nodes in both subtrees that connect to lca of x and y(done in solve func) and set y = lca and use another leaf node for x

Continue this until no leaf node is left and we will have our ans.

My logic is somewhat the same as editorial hence I don't know what's wrong.

The only place where you do leaves.insert() is before your main loop.

But when you erase nodes from a tree, some non-leaf nodes become leaves.

I think you should probably add them to 'leaves' somewhere inside the loop.

Apart from LCA I don't think any node is getting set as leaf node after deletion, because the subtrees are attached to LCA at end and not affecting any other node.

Then, the LCA itself becomes a leaf :)

I think I found the mistake , it's when I am taking LCA in the query , I should take LCA only when it's a leaf otherwise the other leaf node has a chance of being in it's subtree

Edit : Got Ac 72535927

Thanks for Help!

Thanks for the contest and nice editorial <3

Can anyone explain the solution of problem D 1305D - Kuroni and the Celebration ? Editorial is not clear to me.

What exact part did you feel unclear?

If we make our query like this process, doesn't it cross the query limit that is [n/2]? I understand the solution of editorial but don't get the point why query limit is not exceeded?

I have found the answer of my question... Now it is clear to me. Thank you Akikaze for your response :)

Please help me find mistake in my code (D question): Submission Link . Thanks in advance :)

can anyone let me know the meaning of the verdict "cost limit exceed" in problem d

You used too many queries (exceeded the $$$\lfloor \frac{n}{2} \rfloor$$$ limit).

In D, why int last variable is used in function void purge() ??

"last" here serves as the previously traversing node, to avoid repetitive recursive call.

G's solution can be proved constructively and I think it's a bit more intuitive that way. The key idea is that if we root the tree of invitations at the $$${n+1}$$$-th node, each non-root person is invited by their parent. It provides a bijection between trees and valid sequences of invitations.

When a person joins, the gain is equal to the parent edge weight minus the joining person's age. Since each person joins once, it suffices to maximize the weights of the edges in the tree.

can someone tell me how to solve E.or atleast that(i-1)/2 case.

Adding a number

iwill increase the count of triplets by (i-1)/2. Suppose we have elements 1 2 .. adding 3 will increase the count by (3-1)/2=1 because 1+2=3. Now we have 1 2 3, adding 4 to the elements increases the count by (4-1)/2=1 because we have 1+3=4. Generally we take the current most left and the most right elements and add them and we get the new added element and then we take the next most left and the next most right elements and repeat the process. As if we are using two pointers starting from the first index and last index and every time we increment the left pointer and decrement the right pointer, then the sum of the 2 current elements gives usi. having 1 2 3 4 5 6 and then adding 7 , we have 1+6 , 2+5 ,and 3+4 = 3 triplets = (7-1)/2. That's the number of current elements divided by 2 which is the number of elements ( assuming all elements to be 1 2 3 ... i-2 i-1 ) before adding the new element which isi, so the count increases by (i-1) "the current number of elements before adding i to them" / 2 , because the sum of every two elements gives usi. If you still don't get it or want me to further explain the complete solution, feel free to ask.https://codeforces.com/contest/1305/submission/72570404 this submission of mine os showing wrong ans on t20. the correct answer on B t20 says only one bracket needs to be removed . someone please explain

You're misreading between your output and jury's answer. Correct answer said "0".

Can someone please explain the proof of the $$$F$$$ ? Why the probability is $$$1/2^m$$$ if we pick only m elements and factorise them ?

HipHop's comment is a clear explanation you might want to read.

Can someone explain what the purge function is doing in the solution of DIV2 D and why we are doing it ? Thanks in advance !

After asking a query $$$(u, v)$$$ and receiving the LCA $$$w$$$, the

`purge`

functions went in and delete every node (and edge) in the path from $$$u$$$ and $$$v$$$ towards $$$w$$$. If there's any nodes being separated after that, they'll be purged along as well.Thank you for your reply !. Can you elaborate "If there's any nodes being separated after that" a little please ?

Can anyone please explain E?

Sorry for any grammar mistakes

Assuming You Understood until

`(i-1)/2`

case by the commenthttps://codeforces.com/blog/entry/74459?#comment-587005

Let's Say the Number of special triples until now as S (let it be < M). If we add the new number there are two cases

S will still be less than M (in this case we continue to add the new number).

S will be greater than or equal to M.

In the second case, we need to figure out the number which will only add M-S Special triples.

If we use two pointers, First Pointer as

`2*(M-S)+1`

and second pointer as`index of the last number added to the list`

. Every time we increment the left pointer and decrement the right pointer. The sum of the two elements will always give us a single number`M-S`

times. So will use this number as the next number.At this point, we achieved the desired balance. I think After this how to handle the rest of the numbers is neatly explained by ending section of this problem editorial.

My Code

For Problem F, I couldn't understand this part.

"When we apply the optimal sequence of operations there are at least n/2 elements which are affected by at most one operation."A proof would be really helpful.

Can anyone please explain problem H in more detail ?

https://codeforces.com/contest/1305/submission/84656279 What changes do i need in my code..please explain me