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
Tutorial is loading...
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
Tutorial is loading...
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
Tutorial is loading...
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: AkiLotus
Development: AkiLotus, dorijanlendvaj
Editorialist: Kuroni
Tutorial
Tutorial is loading...
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
Tutorial is loading...
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
Tutorial is loading...
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
Tutorial is loading...
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;
}
Solution (Approach #2) (pajenegod, PyPy2)
Submission link: 72758499
Source code in plain text
import sys
range = xrange
input = raw_input
n = int(input())
A = [int(x) for x in input().split()]
m = 2**18
count = [0]*m
for a in A:
count[a] += 1
count[0] += 1
# Using dsu with O(1) lookup and O(log(n)) merge
owner = list(range(m))
sets = [[i] for i in range(m)]
total = 0
for profit in reversed(range(m)):
a = profit
b = a ^ profit
while a > b:
if count[a] and count[b] and owner[a] != owner[b]:
total += (count[a] + count[b] - 1) * profit
count[a] = 1
count[b] = 1
small = owner[a]
big = owner[b]
if len(sets[small]) > len(sets[big]):
small, big = big, small
for c in sets[small]:
owner[c] = big
sets[big] += sets[small]
a = (a - 1) & profit
b = a ^ profit
print total - sum(A)
1305H - Kuroni the Private Tutor
Author: zscoder
Development: zscoder, ngfam, Kuroni, antontrygubO_o
Editorialist: zscoder
Tutorial
Tutorial is loading...
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.net/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 (ai — aj) % m to be ((ai%m) — (aj%m)) % m. So we can convert all elements of the array from a1, a2, a3, .... , an to a1%m, a2%m, a3%m, .... , an%m. Which means there can be atmost m different values in array. If the number of elements n is greater than m, then there must be some value which is repeated more than once (pigeon hole principal). So there will be some pair (ai, aj) 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 atleast one such pair.
If n < m, then we can just check all pairs (as m is 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.
wow thank you !! such a good explanation.
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.
.
yes they are not, but the worst case is when the numbers are different.
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)
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.
почему в задаче 1305G - Курони и Антихайп не проходит решение, в котором для каждого человека ищется другой человек, которому выгоднее всего пригласить и который может пригласить?
https://codeforces.net/contest/1305/submission/72364063
или каждый может пригласить только одного друга?
Такое решение не проходит потому, что оно выводит неверный ответ :(
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$$$.
Finally understanding things a bit better (I was a bit oblivious on G+H those days and simply maintained the tutorials of those through mechanical conventions), so only till now I updated the blog with your Python solution.
Thank you for the help, and my apologies for this severe necroposting.
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.
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
.
" int(n / 2) * n" should be " int(n / 2) * 2"
.
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 leaves is 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 eachrdfscall 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
resetcalls gets ACNVM I finally got it. Sorry for ping
You 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.
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?
I have found the answer of my question... Now it is clear to me. Thank you AkiLotus 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 i will 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 us i. 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 is i, 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 us i. If you still don't get it or want me to further explain the complete solution, feel free to ask.
https://codeforces.net/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
purgefunctions 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?
Can someone please post the solution for E? It doesn't load for me.
I liked problem F a lot. My approach differs from the editorial's. The main idea is that we can fix a prime $$$p$$$ and then make update in the array to have a gcd which is divisible by $$$p$$$. To do this, a couple of observations:
(1) We know that if we let $$$p = 2$$$, we can get the array to be divisible by $$$2$$$ in at most $$$N$$$ operations. So the expected value of the number of updates per element should be $$$\le 1$$$.
(2) If each element is pretty close to being divisible by that special prime $$$p$$$, we can randomly chose an element, look in the neighborhood of that element, and then decide which primes are feasible. That is, take $$$10$$$ random elements. Let's look at them one by one. Say, the first element is $$$x$$$; then the special prime $$$p$$$ is likely divisible by $$$x-3, x - 2, x - 1, x, x + 1, x - 2,$$$ or $$$x + 3$$$. So we can prime factorize $$$x - 3...x + 3$$$ to look for that prime $$$p$$$.
If this is confusing, see 141358017.
In problem 1305G, please note that given by Tarjan, the time complexity of DSU with $$$n$$$ vertices and $$$m$$$ queries is $$$O(m\alpha(m+n,n))$$$, and by the definition of Inverse Ackermann Function, $$$\alpha(m+n,n)\le 1$$$ when $$$m>\log n$$$，thus the tighter time complexity of Approach 2 is $$$O(3^k+2^k\cdot k)$$$ where $$$k$$$ is 18, or simply $$$O(3^k)$$$.
Oh my god!! I haven't seen C type of question never before!!It totally changed my view!!