Разбор
Tutorial is loading...
Решение C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n, k, x = -1;
cin >> n >> k;
for (int i = 0; i <= n; i++) {
if (i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2 == k) {
x = i;
}
}
if (x == -1)
cout << "NO\n";
else {
cout << "YES\n";
for (int i = 0; i < n; i++) {
if (i < x)
cout << 1 << ' ';
else
cout << -1 << ' ';
}
cout << '\n';
}
}
return 0;
}
Решение Python
for tt in range(int(input())):
n, k = map(int, input().split())
x = -1
for i in range(0, n + 1):
if i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2 == k:
x = i
if x == -1:
print("NO")
else:
print("YES")
for i in range(0, n):
if i < x:
print("1 ", end = '')
else:
print("-1 ", end = '')
print("")
Разбор
Tutorial is loading...
Решение C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n, k;
cin >> n >> k;
vector <int> p(n);
for (int i = 0; i < n; i++) {
cin >> p[i];
p[i]--;
}
int bad = 0;
for (int i=0; i<n; i++) {
if (p[i] % k != i % k) {
bad++;
}
}
if(bad == 0)
cout << 0 << '\n';
else if(bad == 2)
cout << 1 << '\n';
else
cout << -1 << '\n';
}
return 0;
}
Решение Python
for tt in range(int(input())):
n, k = map(int, input().split())
p = list(map(int, input().split()))
for i in range(0, n):
p[i] -= 1
bad = 0
for i in range(0, n):
if p[i] % k != i % k:
bad += 1
if bad == 0:
print(0)
elif bad == 2:
print(1)
else:
print(-1)
Разбор
Tutorial is loading...
Решение C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
map <int,int> a;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
for (int j = 2; j * j <= x; j++) {
while (x % j == 0) {
x /= j;
a[j]++;
}
}
if (x != 1) {
a[x]++;
}
}
int res = 0, rem = 0;
for (pair <int, int> p : a) {
int num = p.first;
int cnt = p.second;
res += cnt / 2;
rem += cnt % 2;
}
res += rem / 3;
cout << res << '\n';
}
return 0;
}
Решение Python
def is_prime(x):
i = 2
while i * i <= x:
if x % i == 0:
return False
i += 1
return True
def is_strongly_composite(x):
m = []
i = 2
while i * i <= x:
while x % i == 0:
x = x // i
m.append(i)
i += 1
if not x == 1:
m.append(i)
return (len(m) >= 3 or (len(m) == 2 and m[0] == m[1]))
for tt in range(int(input())):
n = int(input())
lst = list(map(int, input().split()))
a = {}
for x in lst:
i = 2
while i * i <= x:
while x % i == 0:
x = x // i
if i in a:
a[i] += 1
else:
a[i] = 1
i += 1
if x != 1:
if x in a:
a[x] += 1
else:
a[x] = 1
res, rem = 0, 0
for num in a:
cnt = a[num]
res += cnt // 2
rem += cnt % 2
res += rem // 3
print(res)
Замечания
Изначально была более сложная версия этой задачи. Сможете ее решить?
Вам даны $$$n$$$ чисел $$$a_1, a_2, \dots, a_n$$$ ($$$a_i > 1$$$). Вы можете выполнить следующую операцию с массивом $$$a$$$ любое количество раз:
выбрать два индекса $$$i$$$ и $$$j$$$ ($$$i < j$$$);
удалить элементы $$$a_i$$$ и $$$a_j$$$ из $$$a$$$;
вставить элемент $$$a_i \cdot a_j$$$ в $$$a$$$.
После выполнения одной такой операции длина $$$a$$$ уменьшается на единицу.
Назовем массив $$$a$$$ хорошим, если он содержит только сильно составные числа.
Какое минимальное количество операций необходимо выполнить, чтобы сделать массив $$$a$$$ хорошим.
Разбор
Tutorial is loading...
Решение C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n, k;
cin >> n >> k;
vector <int> x(k), c(k);
for (int i = 0; i < k; i++)
cin >> x[i];
for (int i = 0; i < k; i++)
cin >> c[i];
if (c[0] < 3 || c[0] > x[0]) {
cout << "NO\n";
continue;
}
string s;
char cur = 'a';
for (int i = 0; i < c[0] - 3; i++)
s.push_back('a');
for (int i = c[0] - 3; i < x[0]; i++) {
s.push_back(cur);
cur++;
if (cur == 'd') cur = 'a';
}
bool good = true;
for (int j = 1; j < k; j++) {
int dx = x[j] - x[j - 1];
int dc = c[j] - c[j - 1];
if (dc > dx) {
good = false;
break;
}
for (int i = 0; i < dc; i++)
s.push_back('c' + j);
for (int i = dc; i < dx; i++) {
s.push_back(cur);
cur++;
if (cur == 'd') cur = 'a';
}
}
if (good)
cout << "YES" << endl << s << endl;
else
cout << "NO" << endl;
}
return 0;
}
Решение Python
for tt in range(int(input())):
n, k = map(int, input().split())
x = list(map(int, input().split()))
c = list(map(int, input().split()))
if c[0] < 3 or c[0] > x[0]:
print("NO")
continue
s = ""
cur = 'a'
for i in range(0, c[0] - 3):
s += "a"
for i in range(c[0] - 3, x[0]):
s += cur
cur = chr(ord(cur) + 1)
if cur == 'd':
cur = 'a'
good = True
for j in range(1, k):
dx = x[j] - x[j - 1]
dc = c[j] - c[j - 1]
if dc > dx:
good = False
break
for i in range(0, dc):
s += chr(ord('c') + j)
for i in range(dc, dx):
s += cur
cur = chr(ord(cur) + 1)
if cur == 'd':
cur = 'a'
if good:
print("YES")
print(s)
else:
print("NO")
Замечания
Изначально была упрощенная версия этой задачи с $$$k = 1$$$, но она совпала с другой задачей.
А как в этой задаче работает чекер?
Разбор
Tutorial is loading...
Решение C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, l, r;
cin >> n >> l >> r;
vector < vector <int> > g(n);
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
a--, b--;
g[a].push_back(b);
g[b].push_back(a);
}
int res=0, size;
vector <int> used(n);
function <void(int)> dfs = [&] (int v) {
used[v] = true;
size++;
for (int to : g[v]) {
if (!used[to])
dfs(to);
}
};
for (int i = 0; i < n; i++) {
if (!used[i]) {
size = 0;
dfs(i);
if (size <= l + r - 1) {
res ^= size / l;
}
}
}
if (res)
cout << "Alice\n";
else
cout << "Bob\n";
return 0;
}
Решение Python
from sys import setrecursionlimit
import threading
def main():
n, l, r = map(int, input().split())
g = [[] for i in range(0, n)]
for i in range(0, n):
a, b = map(int, input().split())
a -= 1
b -= 1
g[a].append(b)
g[b].append(a)
res = 0
used = [False for i in range(0, n)]
def dfs(v):
used[v] = True
size = 1
for to in g[v]:
if not used[to]:
size += dfs(to)
return size
for i in range(0, n):
if not used[i]:
size = dfs(i)
if size <= l + r - 1:
res ^= size // l
if res:
print("Alice")
else:
print("Bob")
setrecursionlimit(10 ** 9)
threading.stack_size(2 ** 27)
thread = threading.Thread(target=main)
thread.start()
Разбор
Tutorial is loading...
Решение C++
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int main(){
int n, s, t;
cin >> n >> s >> t;
s--, t--;
vector < vector <int> > g(n);
vector <int> previous(n, -1);
vector <int> inPath(n);
vector <long long> res(n);
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
a--, b--;
g[a].push_back(b);
g[b].push_back(a);
}
function <void (int, int)> dfs = [&] (int v, int p) {
for (int to : g[v]) {
if (to == p) continue;
previous[to] = v;
dfs(to, v);
}
};
function <void (int, int, long long)> dfs2 = [&] (int v, int p, long long k) {
res[v] = k * (long long)g[v].size();
for (int to : g[v]) {
if (to == p) continue;
dfs2(to, v, k);
}
};
dfs(s, -1);
int ptr = t;
inPath[t] = true;
while (ptr != s) {
res[previous[ptr]] = res[ptr] + 2;
ptr = previous[ptr];
inPath[ptr] = true;
}
for (int v = 0; v < n; v++) {
if (inPath[v]) {
res[v] = res[v] / 2 * (long long)g[v].size();
for (int to : g[v]) {
if (!inPath[to]) {
dfs2(to, v, res[v] / (int)g[v].size());
}
}
}
}
res[t]++;
for (long long i : res)
cout << i % mod << ' ';
cout<<'\n';
return 0;
}
Решение Python
from sys import setrecursionlimit
import threading
mod = 998244353
def main():
n, s, t = map(int, input().split())
s -= 1
t -= 1
g = [[] for i in range(0, n)]
previous = [-1 for i in range(0, n)]
inPath = [False for i in range(0, n)]
res = [0 for i in range(0, n)]
for i in range(0, n - 1):
a, b = map(int, input().split())
a -= 1
b -= 1
g[a].append(b)
g[b].append(a)
def dfs(v, p):
for to in g[v]:
if to == p:
continue
previous[to] = v
dfs(to, v)
def dfs2(v, p, k):
res[v] = k * len(g[v])
for to in g[v]:
if to == p:
continue
dfs2(to, v, k)
dfs(s, -1)
ptr = t
inPath[t] = True
while ptr != s:
res[previous[ptr]] = res[ptr] + 2
ptr = previous[ptr]
inPath[ptr] = True
for v in range(0, n):
if inPath[v]:
res[v] = res[v] // 2 * len(g[v])
for to in g[v]:
if not inPath[to]:
dfs2(to, v, res[v] // len(g[v]))
res[t] += 1
for i in res:
print(i % mod, end = ' ')
print("")
setrecursionlimit(10 ** 9)
threading.stack_size(2 ** 27)
thread = threading.Thread(target=main)
thread.start()
Editorial comes out so fast!
Comment comes out so fast!
The implementation of F is wrong, you forgot to reduce modulo 998244353. It's causing unexpected verdict in hacks.
I noticed that some hacks are "unexpected verdict", so that's the reason?
Yes, I apoligize
Problem B was cool.
Yeah BC were easy but nice
Зәңгәр өсөн рәхмәт, ағай!
Are you using palindromic tree for checker of problem D?
Yes
Okay, I don't think I could have realistically proved that $$$chain[x] = \left\lfloor \frac{x}{\ell} \right\rfloor$$$ during the contest time limit, but... I think I could definitely have observed the pattern if I just bothered to generate the first 100 Sprague-Grundy values or so and eyeballed them. Everything else was in place except this single component of the solution >_>. I hope I can learn to do this for future Sprague-Grundy problems now.
Anyway, I really enjoyed these problems a lot! I even had fun thinking about F briefly, until I was assured that it's definitely beyond my capabilities. These are nice combinations of standard tools that still require additional creative effort to apply correctly.
Also, I especially appreciate that the implementations are very smooth once the correct idea is understood. For example, the problemsetter could've easily done the jerk move of requiring the program to print the swap sequence in B or the elements of the maximum-length array in C, which would not have really made the problems harder to figure out, but would have been unnecessarily more tedious.
Very similar problem here
I don't know about Sprague-Grundy theory. Is there anyone to teach me?
Thanks so much for there're py solution~
I don't understand how cycle[x] equals chain[x] up to r+l−1. Could anyone please explain it to me? Thanks
Suppose $$$chain[x] = \frac{x}{l}$$$ is correct, then when $$$l <= x <= l + r - 1$$$, $$$cycle[x] = mex ( chain[(x-r)^+], ..., chain[x−l] ) = mex(0,...\frac{x-l}{l}) = \frac{x}{l} = chain[x]$$$, and when $$$x < l$$$, $$$cycle[x] = chain[x] = 0$$$.
Edit: The editorial actually has a type, mex should start from $$$chain[(x-r)^+]$$$, not $$$chain[0]$$$.
I got it, thanks
Thought we need to consider $$$l = r$$$ for E, stuck for a long time. Now I am curious, is there a pattern in this case?
Did you found any pattern for $$$ l = r $$$ ?
1823F - Случайная прогулка has another solution. Root the tree at $$$t$$$ and consider the following question: suppose we are at a vertex $$$v$$$ at the given moment. What is the expected number of times we will visit it from now on, including the current time?
Well, if we go into any of its $$$\deg(v) - 1$$$ children we must visit it again. Else, if we go up to its parent, the probability we visit it again is exactly $$$1 - \frac{1}{d(v)}$$$ where $$$d(v)$$$ is the depth of $$$v$$$ in the tree. I think the adedalic solution covers an approach to seeing this, but the short answer is induction on the length of the path between $$$t$$$ and $$$v$$$.
Hence, if $$$e(v)$$$ is the expected number of visits to $$$v$$$ given we are there at the current moment satisfies
$$$e(v) = 1 + \left(\frac{\deg(v) - 1}{\deg(v)} + \frac{1}{\deg(v)}\cdot \left(1 - \frac {1}{d(v)}\right)\right)e(v).$$$ (for some reason the displaystyle math environment is acting weird for me)
Simplifying this gives $$$e(v) = \deg(v)\cdot d(v).$$$ However, this doesn't take into account the probability that $$$v$$$ is ever visited! If $$$v$$$ is on the path from $$$s$$$ to $$$t$$$, then it is always visited. Else, suppose that the first time the path from $$$v$$$ to $$$t$$$ intersects with the path from $$$s$$$ to $$$t$$$ is at vertex $$$u$$$. Since $$$u$$$ is always visited, the probability that $$$v$$$ is ever visited is the probability that a random walk from $$$u$$$ on the bamboo/path from $$$v$$$ to $$$t$$$ visits $$$v$$$ before $$$t$$$. But by the same induction, this is exactly $$$\frac{d(u)}{d(v)}$$$.
Hence, if $$$e'(v)$$$ is the true expected number of visits to $$$v$$$, we have $$$e'(v) = e(v) \cdot \frac{d(u)}{d(v)} = \deg(v) \cdot d(u)$$$. Finally, if $$$v = t$$$ we have $$$e'(v) = 1$$$. This is fairly easy to calculate: 203820888
Why if we go up to its parent, the probability we visit it again is exactly 1−1 / d(v) where d(v) is the depth of v in the tree. Can you explain to me.
The first equation of F may seem obvious, here is my attempt at deriving it rigorously, where $$$x_{\tau}$$$ is position of the chip at time $$$\tau$$$, with initial $$$\tau = 1$$$:
$$$E(c(i))$$$
$$$= E(\Sigma_{\tau=1}^\infty 1_{x_{\tau = i}})$$$
$$$= \Sigma_{\tau=2}^\infty P(x_{\tau = i}) + P(x_1 = i)$$$
$$$= \Sigma_{\tau=2}^\infty \Sigma_{j=1}^n P(x_{\tau} = i | x_{\tau - 1} = j) P(x_{\tau - 1} = j) + 1_{i=s}$$$
$$$= \Sigma_{\tau=1}^\infty \Sigma_{j \in N(i), j \neq t} \frac{1}{|N(j)|} P(x_{\tau} = j) + 1_{i=s}$$$
$$$= \Sigma_{j \in N(i), j \neq t} \frac{E(c(j))}{|N(j)|} + 1_{i=s}$$$
Notice the special $$$1_{i=s}$$$ at the end. Also, if $$$i = t$$$, we need to change the definition so that $$$|N(t)| = 1$$$. Imagine that it then goes into some other absorbing state, so $$$t$$$ is visited only once.
For problem F, we have
=> E(c(u)) and E(c(v)) depends on each other and this problem is presented on a tree so we can assume that
with
free(u) is a constant cofficient, g(u) is the "familiarity" rate with the parent p. Our goal is to find free(u) and g(u), so how can we do that ? We have<=>
with v is a child of u.
We run through a DFS to calculate free(u) and g(u) and then a DFS to calculate the final answer.
Excuse me, it's been a long time but could I ask how could you think of E(c(u))=free(u)+E(c(p))∗g(u)? Like what's the motive or it's some tricks or sth? Thanks a lot.
as far as I've remembered, I did try to isolate the influence of direct children v and parent p on the vertex u so that it's easier to calculate by DFS
Very fun contest! Both problem D and E have quite interesting solutions (I didn't attempt problem F).
Thank you for task E, it is very nice!
Who the f***k made the problem D