Thanks for participating in the round! I hope you enjoyed the problems!
#include <bits/stdc++.h>
using namespace std;
int main(){
int t; cin >> t;
for(int i = 0; i < t; i++){
long long n, s;
cin >> n >> s;
cout << s / (n * n) << "\n";
}
return 0;
}
It can be proven that (try to prove it!) if some $$$k$$$ works, then $$$k=\displaystyle \left \lfloor \frac{n-1}{2} \right \rfloor$$$ has to work. This means that there is always an answer using $$$n$$$ or $$$n-1$$$ elements, depending on parity.
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t; cin >> t;
for(int test_number = 0; test_number < t; test_number++){
int n; cin >> n;
vector <long long> a(n);
for(int i = 0; i < n; i++){
cin >> a[i];
}
sort(a.begin(), a.end());
vector <long long> prefix_sums = {0};
for(int i = 0; i < n; i++){
prefix_sums.push_back(prefix_sums.back() + a[i]);
}
vector <long long> suffix_sums = {0};
for(int i = n - 1; i >= 0; i--){
suffix_sums.push_back(suffix_sums.back() + a[i]);
}
bool answer = false;
for(int k = 1; k <= n; k++){
if(2 * k + 1 <= n){
long long blue_sum = prefix_sums[k + 1];
long long red_sum = suffix_sums[k];
if(blue_sum < red_sum){
answer = true;
}
}
}
if(answer) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
1646C - Factorials and Powers of Two
Actually, there is no problem in repeating $$$1$$$, $$$2$$$, or any other power of two. This is because it can be proven that (try to prove it!) those sums are not optimal.
#include <bits/stdc++.h>
using namespace std;
const long long MAXAI = 1000000000000ll;
int get_first_bit(long long n){
return 63 - __builtin_clzll(n);
}
int get_bit_count(long long n){
return __builtin_popcountll(n);
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t; cin >> t;
for(int test_number = 0; test_number < t; test_number++){
long long n; cin >> n;
//Computing factorials <= MAXAI
vector<long long> fact;
long long factorial = 6, number = 4;
while(factorial <= MAXAI){
fact.push_back(factorial);
factorial *= number;
number++;
}
//Computing masks of factorials
vector<pair<long long, long long>> fact_sum(1 << fact.size());
fact_sum[0] = {0, 0};
for(int mask = 1; mask < (1 << fact.size()); mask++){
auto first_bit = get_first_bit(mask);
fact_sum[mask].first = fact_sum[mask ^ (1 << first_bit)].first + fact[first_bit];
fact_sum[mask].second = get_bit_count(mask);
}
long long res = get_bit_count(n);
for(auto i : fact_sum){
if(i.first <= n){
res = min(res, i.second + get_bit_count(n - i.first));
}
}
cout << res << "\n";
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 400005;
vector<int> g[MAXN];
bool vis[MAXN];
int pa[MAXN];
//DFS to compute the parent of each node
//parent of node i is stored at pa[i]
void dfs(int v){
vis[v] = 1;
for(auto i : g[v]){
if(!vis[i]){
pa[i] = v;
dfs(i);
}
}
}
pair<int, int> dp[MAXN][2];
//Computes the value of function f, using dp
//the second coordinate of the pair is negated (to take maximums)
pair<int, int> f(int x, int y){
pair<int, int> & res = dp[x][y];
if(res.first >= 0) return res;
res = {y, y ? -((int) g[x].size()) : -1};
for(auto i : g[x]){
if(i != pa[x]){
pair<int, int> maxi = f(i, 0);
if(y == 0) maxi = max(maxi, f(i, 1));
res.first += maxi.first;
res.second += maxi.second;
}
}
return res;
}
vector<int> is_good;
//Recursive construction of the answer
//is_good[i] tells whether vertex i is good or not.
void build(pair<int, int> value, int v){
if(value == f(v, 0)){
is_good[v] = 0;
for(auto i : g[v]){
if(i != pa[v]){
build(max(f(i, 0), f(i, 1)), i);
}
}
}else{
is_good[v] = 1;
for(auto i : g[v]){
if(i != pa[v]){
build(f(i, 0), i);
}
}
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n; cin >> n;
for(int i = 0; i < n - 1; i++){
int u, v;
cin >> u >> v; u--; v--;
g[u].push_back(v);
g[v].push_back(u);
}
if(n == 2){
cout<<"2 2\n1 1\n";
return 0;
}
pa[0] = -1;
dfs(0);
for(int i = 0; i < n; i++) dp[i][0] = {-1, -1}, dp[i][1] = {-1, -1};
pair<int, int> res = max(f(0, 0), f(0, 1));
cout << res.first << " " << -res.second << "\n";
is_good.resize(n);
build(res, 0);
for(int i = 0; i < n; i++){
if(is_good[i]) cout << g[i].size() << " ";
else cout << "1 ";
}
cout << "\n";
return 0;
}
This solution uses the fact that $$$m\le 10^6$$$, other solutions do not use this, and work for much larger values of $$$m$$$ (like $$$m\leq 10^{18}$$$, but taking the answer modulo some big prime number). Try to solve the problem with this new constraint!
#include <bits/stdc++.h>
#define fore(i,a,b) for(ll i=a,ggdem=b;i<ggdem;++i)
using namespace std;
typedef long long ll;
const int MAXM = 1000006;
const int MAXLOGN = 20;
bool visited_mul[MAXM * MAXLOGN];
int main(){
ll n, m; cin >> n >> m;
vector<ll> mul_quan(MAXLOGN);
ll current_vis = 0;
fore(i, 1, MAXLOGN){
fore(j, 1, m+1){
if(!visited_mul[i * j]){
visited_mul[i * j] = 1;
current_vis++;
}
}
mul_quan[i] = current_vis;
}
ll res=1;
vector<ll> vis(n + 1);
fore(i, 2, n+1){
if(vis[i]) continue;
ll power = i, power_quan = 0;
while(power <= n){
vis[power] = 1;
power_quan++;
power *= i;
}
res += mul_quan[power_quan];
}
cout << res << "\n";
return 0;
}
1646F - Playing Around the Table
#include <bits/stdc++.h>
#define fore(i, a, b) for(int i = a; i < b; ++i)
using namespace std;
const int MAXN = 1010;
//c[i][j] = number of cards player i has, with the number j
int c[MAXN][MAXN];
//extras[i] is the stack of repeated cards for player i.
vector<int> extras[MAXN];
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n; cin >> n;
fore(i, 0, n){
fore(j, 0, n){
int x; cin >> x; x--;
c[i][x]++;
if(c[i][x] > 1) extras[i].push_back(x);
}
}
vector<vector<int>> res;
//First part
while(true){
//oper will describe the next operation to perform
vector<int> oper(n);
//s will be the first non-diverse player
int s = -1;
fore(i, 0, n){
if(extras[i].size()){
s = i;
break;
}
}
if(s == -1) break;
//last_card will be the card that the previous player passed
int last_card = -1;
fore(i, s, s + n){
int real_i = i % n;
if(extras[real_i].size()){
last_card = extras[real_i].back();
extras[real_i].pop_back();
}
oper[real_i] = last_card;
}
res.push_back(oper);
fore(i, 0, n){
int i_next = (i + 1) % n;
c[i][oper[i]]--;
c[i_next][oper[i]]++;
}
fore(i, 0, n){
int i_next = (i + 1) % n;
if(c[i_next][oper[i]] > 1) extras[i_next].push_back(oper[i]);
}
}
//Second part
fore(j, 1, n){
vector<int> oper;
fore(i, 0, n) oper.push_back((i - j + n) % n);
fore(i, 0, j) res.push_back(oper);
}
cout << res.size() << "\n";
for(auto i : res){
for(auto j : i) cout<< j + 1 << " ";
cout << "\n";
}
return 0;
}
Additionally, ak2006 has made video editorials for problems B, C and D.