Editorial
Tutorial is loading...
Solution 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;
}
Solution 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("")
Editorial
Tutorial is loading...
Solution 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;
}
Solution 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)
Editorial
Tutorial is loading...
Solution 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;
}
Solution 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)
Notes
There were initially more complex version of this task. Can you solve it?
You are given $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$a_i > 1$$$). You can perform the following operation with array $$$a$$$ any number of times:
choose two indices $$$i$$$ and $$$j$$$ ($$$i < j$$$);
erase elements $$$a_i$$$ and $$$a_j$$$ from $$$a$$$;
insert element $$$a_i \cdot a_j$$$ in $$$a$$$.
After performing one such operation, the length of $$$a$$$ decreases by one.
Let's say that array $$$a$$$ is good, if it contains only strongly composite numbers.
What is the minimum number of operation you need to perform to make array $$$a$$$ good?
Editorial
Tutorial is loading...
Solution 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;
}
Solution 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")
Notes
There were initially simpler version of this problem with $$$k = 1$$$, but it coincided with other problem.
Also, how does checker in this problem works?
Editorial
Tutorial is loading...
Solution 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;
}
Solution 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()
Editorial
Tutorial is loading...
Solution 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;
}
Solution 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 - Random Walk 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