Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
t = int(input())
for i in range(t):
n = int(input())
good = True
for j in range(2, n + 1):
if (n + 1) % j == 0:
good = False
if good:
print('YES')
else:
print('NO')
2253B - Гиперкарп и панель управления
Идея: FelixArg
Разбор
Tutorial is loading...
Решение (FelixArg)
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++){
cin >> a[i];
}
vector<pair<int, int>> b;
for (int i = 0; i < n; i++){
if (b.empty() || b.back().first != a[i]){
b.emplace_back(a[i], 1);
}
else{
b.back().second++;
}
}
int m = b.size();
for (int i = 0; i < m - 1; i++){
if (b[i].second > 1 && b[i + 1].second > 1){
cout << m + 2 << '\n';
return;
}
}
for (int i = 0; i < m; i++){
if (i < m - 1 && b[i].second > 1 && (i + 2 >= m || b[i + 2].first != b[i].first)){
cout << m + 1 << '\n';
return;
}
if (i > 0 && b[i].second > 1 && (i - 2 < 0 || b[i - 2].first != b[i].first)){
cout << m + 1 << '\n';
return;
}
}
cout << m << '\n';
}
signed main()
{
#ifdef FELIX
auto _clock_start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests = 1;
cin >> tests;
while(tests--){
solve();
}
#ifdef FELIX
cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
chrono::high_resolution_clock::now()
- _clock_start).count() << "ms." << endl;
#endif
return 0;
}
2253C - Сумма различных в матрице
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
def get_k_last(l, k):
if k < len(l):
return l[len(l)-k:]
else:
return l
t = int(input())
for _ in range(t):
n, m, x, y = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = []
d = []
e = []
i = 0
j = 0
while i < x and j < y:
if a[i] == b[j]:
c.append(a[i])
i += 1
j += 1
elif a[i] < b[j]:
d.append(a[i])
i += 1
else:
e.append(b[j])
j += 1
d.extend(a[i:])
e.extend(b[j:])
res = sorted(get_k_last(d, n) + get_k_last(e, m) + c)
res = get_k_last(res, n + m - 1)
print(sum(res))
2253D - Гиперкарп и межпространственные прыжки
Идея: FelixArg
Разбор
Tutorial is loading...
Решение (FelixArg)
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int x, y;
cin >> x >> y;
int su = x + y;
int k = 0;
while((k + 1) * (k + 2) / 2 <= su){
k++;
}
int p1x = k * (k + 1) / 2 - y;
int p1y = y;
int p2x = x;
int p2y = k * (k + 1) / 2 - x;
vector<pair<int, int>> cand;
if ((p1x + p2x) < 0){
cand.emplace_back((p1x + p2x) / 2, k * (k + 1) / 2 - (p1x + p2x) / 2);
cand.emplace_back((p1x + p2x - 1) / 2, k * (k + 1) / 2 - (p1x + p2x - 1) / 2);
}
else{
cand.emplace_back((p1x + p2x) / 2, k * (k + 1) / 2 - (p1x + p2x) / 2);
cand.emplace_back((p1x + p2x + 1) / 2, k * (k + 1) / 2 - (p1x + p2x + 1) / 2);
}
auto best = cand[0];
for (auto [p, q] : cand){
if (p < 0){
p = 0;
}
if (q < 0){
q = 0;
}
if ((p - x) * (p - x) + (q - y) * (q - y) <
(best.first - x) * (best.first - x) + (best.second - y) * (best.second - y)){
best = {p, q};
}
}
string ans(k, 'Y');
for (int i = 0; i < k; i++){
if (best.first >= k - i){
ans[i] = 'X';
best.first -= (k - i);
}
}
cout << ans << '\n';
}
signed main()
{
#ifdef FELIX
auto _clock_start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests = 1;
cin >> tests;
while(tests--){
solve();
}
#ifdef FELIX
cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
chrono::high_resolution_clock::now()
- _clock_start).count() << "ms." << endl;
#endif
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 1000043;
vector<int> g[N];
int n;
vector<int> get_dist(int x)
{
vector<int> d(n, -1);
d[x] = 0;
queue<int> q;
q.push(x);
while(!q.empty())
{
int k = q.front();
q.pop();
for(auto y : g[k])
if(d[y] == -1)
{
d[y] = d[k] + 1;
q.push(y);
}
}
return d;
}
void remove_edge(int x, int y)
{
int idx = -1;
for(int i = 0; i < g[x].size(); i++)
if(g[x][i] == y)
idx = i;
g[x].erase(g[x].begin() + idx, g[x].begin() + idx + 1);
}
vector<int> process(int v)
{
vector<int> d(n, -1), p(n, -1);
queue<int> q;
q.push(v);
d[v] = 0;
vector<int> visited;
while(!q.empty())
{
int k = q.front();
q.pop();
visited.push_back(k);
for(auto y : g[k])
if(d[y] == -1)
{
d[y] = d[k] + 1;
q.push(y);
p[y] = k;
}
}
int max_dist = *max_element(d.begin(), d.end());
vector<bool> has_end(n, false);
has_end[v] = true;
for(auto x : visited)
if(d[x] == max_dist)
{
int cur = x;
while(!has_end[cur])
{
has_end[cur] = true;
cur = p[cur];
}
}
vector<int> res;
for(auto x : visited)
{
if(!has_end[x]) continue;
int good_children = 0;
for(auto y : g[x])
if(p[x] != y && has_end[y]) good_children++;
if(good_children != 1) res.push_back(d[x]);
}
sort(res.begin(), res.end());
res.erase(unique(res.begin(), res.end()), res.end());
return res;
}
void solve()
{
cin >> n;
for(int i = 0; i < n; i++)
g[i].clear();
for(int i = 0; i < n - 1; i++)
{
int x, y;
cin >> x >> y;
--x;
--y;
g[x].push_back(y);
g[y].push_back(x);
}
auto dist0 = get_dist(0);
int e1 = max_element(dist0.begin(), dist0.end()) - dist0.begin();
auto dist1 = get_dist(e1);
int e2 = max_element(dist1.begin(), dist1.end()) - dist1.begin();
auto dist2 = get_dist(e2);
int d = dist1[e2];
int x = -1, y = -1;
for(int i = 0; i < n; i++)
if(dist1[i] + dist2[i] == d)
{
if(dist1[i] == dist2[i] - 1)
x = i;
else if(dist1[i] == dist2[i] + 1)
y = i;
}
remove_edge(x, y);
remove_edge(y, x);
auto ans1 = process(x);
auto ans2 = process(y);
vector<bool> res(n + 1);
for(auto x : ans1)
for(auto y : ans2)
res[x + y + 1] = true;
int cnt = 0;
for(auto x : res)
if(x) cnt++;
cout << cnt;
for(int i = 0; i <= n; i++)
if(res[i])
cout << " " << i;
cout << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
for(int i = 0; i < t; i++)
solve();
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = int(5e5) + 43;
const long long INF64 = (long long)(1e18);
int n;
int cost[N];
void upd(long long& x, long long y)
{
if(x > y) x = y;
}
bool check_bit(int x, int y)
{
return bool((x >> y) & 1);
}
long long calc_dp(const vector<vector<int>>& c)
{
int n = c.size();
int m = c[0].size();
int full = (1 << m) - 1;
vector<vector<vector<long long>>> dp(2, vector<vector<long long>>(m, vector<long long>(1 << m, INF64)));
dp[0][0][0] = 0;
for(int i = 0; i < n; i++)
{
int i1 = i & 1;
int i2 = i1 ^ 1;
for(int j = 0; j < m; j++)
for(int f = 0; f < (1 << m); f++)
dp[i2][j][f] = INF64;
for(int j = 0; j < m; j++)
for(int f = 0; f < (1 << m); f++)
{
if(dp[i1][j][f] == INF64) continue;
int ni = i1;
int nj = j + 1;
if(nj == m)
{
ni = i2;
nj = 0;
}
bool can = true;
if(i > 0 && j + 2 < m && check_bit(f, m - 1) && check_bit(f, m - 2) && check_bit(f, m - 3))
can = false;
if(can)
{
int nf = ((f << 1) & full) | 1;
upd(dp[ni][nj][nf], dp[i1][j][f]);
}
int nf = (f << 1) & full;
upd(dp[ni][nj][nf], dp[i1][j][f] + c[i][j]);
}
}
return *min_element(dp[n & 1][0].begin(), dp[n & 1][0].end());
}
long long calc_comp(int x)
{
int d2 = 0, d3 = 0;
int p2 = 1, p3 = 1;
while(x * (p2 * 2) <= n)
{
p2 *= 2;
d2++;
}
while(x * (p3 * 3) <= n)
{
p3 *= 3;
d3++;
}
d2++;
d3++;
vector<int> pow2(d2, 1), pow3(d3, 1);
for(int i = 1; i < d2; i++)
pow2[i] = pow2[i - 1] * 2;
for(int i = 1; i < d3; i++)
pow3[i] = pow3[i - 1] * 3;
vector<vector<int>> cur(d3, vector<int>(d2, 0));
for(int i = 0; i < d2; i++)
for(int j = 0; j < d3; j++)
if(x * 1ll * pow2[i] * 1ll * pow3[j] <= n)
cur[j][i] = cost[x * pow2[i] * pow3[j]];
return calc_dp(cur);
}
void solve()
{
cin >> n;
for(int i = 1; i <= n; i++)
cin >> cost[i];
long long ans = 0;
for(int i = 1; i <= n; i++)
if(i % 2 != 0 && i % 3 != 0)
ans += calc_comp(i);
cout << ans << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
int t = 1;
for(int i = 0; i < t; i++)
solve();
}
without good sampleset i would have been cooked
first
But D just needed a simple greedy 386119523
Mind explaining why greedy works?
( we move from (x,y) to (0,0) )
First of all, we know the maximum operations we can perform(k). the 'i'-th change in 'a' or 'b' will finally reduce 'x' or 'y' by k+1-i
if one of the numbers is much bigger and can't reach the other number by using all the operation, so it's OK!
Otherwise we consider that x>y then, we have a moment that 'x' reachs 'y' and probably become smaller than 'y'. in this case, the maximum difference between 'x' and 'y' is 'k' so it compensates with k-1 (and k-1 with k-2...) and finally the maximum difference becomes 1
And the minimum difference between x and y is what we need!
holy shoots this is brilliant
That's amazing!
Yeaah, finally )))
Alternative solution of D:
Let $$$k$$$ be the largest integer with $$$\frac{k \cdot (k + 1)}{2} \le x + y$$$. Consider two bag with capacity $$$x, y$$$ respectively. For $$$w = k, k - 1, \ldots, 1$$$ in this order, put the item with weight $$$w$$$ into the bag with larger capacity remain. Let $$$x', y'$$$ denote the final capacity remain for two bags. We claim this process minimize $$$\max(x', y')$$$.
Proof.
W.L.O.G. assume $$$x \ge y$$$, call the bag with $$$x$$$ initial capacity the first bag, and the other be the second bag.
case 1 ($$$x \ge y + \frac{k\cdot (k + 1)}{2}$$$): trivial
case 2: items would be add into the first bag until its capacity is no more than the second bag, let $$$m$$$ be the item added to make this happen. then at this point, the difference of capacity between two bag would be no more than $$$m$$$, and in the subsequent item addition, the difference would be no more than the item added last, thus $$$|x' - y'| \le 1$$$ holds at the end, which achieve the lower bound of $$$\max(x', y')$$$.
In Problem E (2253E), how would i know number of distinct LCAs would be O($$$\sqrt{n}$$$)? I was stuck with thinking it was O($$$n^2$$$) solution and won't pass.
We have $$$n-1$$$ edges, and each edge either part of diameter or not, and each node of diameter can form just a single distinct number, and sum of nodes limited on $$$n$$$, so you wont have more than $$$sqrt(n)$$$ distinct numbers. We can prove that by summing the first k small values such that sum won't exceed $$$n$$$.
Firstly discard all nodes who's subtree does NOT have a descendant of maximal depth, as these can never be valid LCA's. For the remaining nodes, define $$$cnt[d]$$$ as the number of nodes at depth $$$d$$$.
Since each path is guaranteed to continue down until the maximal depth, we know that $$$cnt[d + 1] \geq cnt[d]$$$. Furthermore, when depth $$$d$$$ contains a valid LCA (i.e. some node has two or more children with max depth descendants), then $$$cnt[d + 1] \geq cnt[d] + 1$$$.
If there are $$$r$$$ distinct achievable depths, then the width increases at least $$$r$$$ times. After the i-th increase, the width is at least $$$i+1$$$. Therefore, among the levels containing these increases and the level immediately after each one, there are at least $$$1 + 2 + \ldots + (r + 1)$$$ nodes. Since the number of nodes per valid LCA depth grows quadratically, the number of valid LCA depths per node grows at a rate of $$$O(\sqrt{n})$$$.
I believe there's a typo in F. I think it should be x mod 2 != 0 and x mod 3 != 0 whereas it says the opposite now.
Thank you, fixed that. The editorial should update in a couple of minutes
I think F > C > E > D > B > A.
E is a very simple property about trees whose diameter length is odd, you just need to replace the middle edge of the diameter with a new vertex, and the problem becomes trivial (it turns into a tree with even diameter, where the center of the diameter has only two subtrees).
D is a straightforward "brute-force and find the pattern" problem; you can easily spot the relation between the number of operations and the landing position, and then it's just a simple contribution‑splitting construction.
As for C, my two-pointer got WA on test 2, which really annoyed me and cost me a lot of time.
For F, I never expected it could be solved with that kind of bitmask DP, so I won't comment much, but once you think of it, it's indeed not hard.
I was able to write this much shorter solution for D. The idea is the same as the editorial's, but I didn't have to do any math to find the optimal ending point (from $$$(x,y)$$$, I just brute forced the walk back).
By the way, was anyone particularly troubled by C? For me, it took nearly an hour to find the correct greedy.
same for me will upsolve c
Alternative $$$O(n)$$$ solution for B.
First, ignore the swap.
Since we can delete elements, from every maximal block of equal values we only need to keep one element. Therefore, the best answer without using the swap is just the number of blocks:
Now consider the swap.
It is enough to try swapping two elements that are already adjacent in the original array. If we choose two non-adjacent elements, we have to delete everything between them to make them adjacent, but those intermediate different blocks were already useful since we could keep one element from each of them.
So we only try swapping $$$a_i$$$ and $$$a_{i+1}$$$.
Locally, we have
... L | a[i] | a[i+1] | R ...and after the swap
... L | a[i+1] | a[i] | R ...The middle boundary does not change, since
Therefore, only the two outer boundaries can change. The change for this swap is
ignoring terms that are outside the array.
Finally,
Both
baseand the best delta can be calculated in the same loop.Complexity: $$$O(n)$$$ time and $$$O(1)$$$ extra space.
bro i had the same solution :))
I loved C, D & E, Good Contest!
Hi, can anyone explain me this case in problem B... I was looking at the solution provided in the tutorial
1 , 1, 1, 2, 2, 2 ...... if i exchange middle 2 and middle 1 ..... I can keep all 6 but now answer is m+4 contrary to the answer provided in the tutorial ..... according to it i can only keep at max 4?
also in case 1, 1, 2, 3, 3 .... i don't have adjacent blocks of 2 but i can exchange 1 and 3 to keep all 5 (answer is m + 2 now)
So you can't swap middle 2 and middle 1, because they are not adjacent
Oh okay thanks , sorry I missed question's details
thanks for the editorial
Superb Editorial + very nice problems__