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 < vector <int> > b(k);
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
b[x % k].push_back(i);
}
int res = -1;
for (int i = 0; i < k; i++) {
if ((int)b[i].size() == 1) {
res = b[i][0];
break;
}
}
if (res == -1) {
cout << "NO" << endl;
}
else {
cout << "YES" << endl << res << endl;
}
}
return 0;
}
Solution Python
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [[] for _ in range(k)]
for i in range(0, n):
x = a[i]
b[x % k].append(i + 1)
res = -1
for i in range(k):
if len(b[i]) == 1:
res = b[i][0]
break
if res == -1:
print("NO")
else:
print("YES\n" + str(res))
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;
for (int ans = 1, cur = 1; ; ans++, cur = cur * 2 + 2) {
if (cur >= n) {
cout << ans << '\n';
break;
}
}
}
return 0;
}
Solution Python
tt = int(input())
for _ in range(tt):
n = int(input())
ans = 1
cur = 1
while True:
if cur >= n:
print(ans)
break
ans += 1
cur = cur * 2 + 2
Notes
At some point in the development of this problem, the following alternative statement appeared: we need to minimize the total number of operations of both types. How to solve this problem?
Editorial
Tutorial is loading...
Solution C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n;
long long k;
cin >> n >> k;
vector <int> a, b;
if (n <= 60 && (1ll << (n - 1)) < k) {
cout << -1 << endl;
continue;
}
k--;
vector <int> d;
while (k) {
d.push_back(k % 2);
k /= 2;
}
while (d.size() < n - 1) d.push_back(0);
for (int i = n - 2, j = 1; i >= 0; i--, j++) {
if (d[i] == 0) a.push_back(j);
else b.push_back(j);
}
reverse(b.begin(), b.end());
for (int i : a) cout << i << ' ';
cout << n << ' ';
for (int i : b) cout << i << ' ';
cout << endl;
}
return 0;
}
Solution Python
tt = int(input())
for _ in range(tt):
n, k = map(int, input().split())
a, b = [], []
if n <= 60 and (1 << (n - 1)) < k:
print(-1)
continue
k -= 1
d = []
while k:
d.append(k % 2)
k //= 2
while len(d) < n - 1:
d.append(0)
a, b = [], []
j = 1
for i in range(n - 2, -1, -1):
if d[i] == 0:
a.append(j)
else:
b.append(j)
j += 1
b.reverse()
print(*a, n, *b)
Editorial
Tutorial is loading...
Solution 1
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector < vector <int> > g(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);
}
vector <int> res(n);
int lst = 1;
res[0] = lst;
function <void(int, int)> dfs = [&](int v, int p) {
for (int to : g[v]) {
if (to == p) continue;
res[to] = lst + 1;
while (res[to] != res[v] + 1 &&
(res[to] % 2 != res[v] % 2 || res[to] - res[v] == 2)) {
res[to]++;
}
lst = res[to];
dfs(to, v);
}
};
dfs(0, 0);
for (int i : res) cout << i << ' ';
cout << endl;
}
return 0;
}
Solution 2 (zap4eg)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void dfs(int v, vector<vector<int>>& g, vector<int>& h, int p) {
h[v] = h[p] + 1;
for (int u : g[v]) {
if (u == p)
continue;
dfs(u, g, h, v);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<vector<int>> g(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);
}
vector<int> h(n);
dfs(0, g, h, 0);
vector<vector<int>> hs(n + 1);
for (int i = 0; i < n; i++)
hs[h[i]].push_back(i);
int l = 2, r = 2 * n;
int cur = 0;
vector<int> ans(n);
for (int i = 1; i <= n; i++) {
if (cur) {
for (int v : hs[i]) {
ans[v] = r;
r -= 2;
}
}
else {
for (int v : hs[i]) {
ans[v] = l;
l += 2;
}
}
cur ^= 1;
}
bool found = false;
for (int i = 0; i < n; i++) {
for (int v : g[i]) {
if (h[v] < h[i])
continue;
if (abs(ans[v] - ans[i]) == 2) {
ans[v] = ans[i] - 1;
found = true;
break;
}
}
if (found)
break;
}
for (int i = 0; i < n; i++)
cout << ans[i] << ' ';
cout << '\n';
}
return 0;
}
Notes
There are many possible solutions to this problem, and almost all testers have implemented a unique solution. There are solutions that we could not prove correct, but we could not hack them either.
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, q;
cin >> n >> q;
vector < vector <int> > g(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);
}
vector <int> depth(n);
vector <int> d(n);
vector <int> par(n);
function <void(int, int)> dfs = [&](int v, int p) {
if (depth[v] == 1) d[v] = 1;
if (depth[v] > 1) d[v] = d[par[p]] + 2 * (int)g[p].size();
par[v] = p;
for(int to : g[v]) {
if (to == p) continue;
depth[to] = depth[v] + 1;
dfs(to, v);
}
};
dfs(0, 0);
while (q--) {
int v, p;
cin >> v >> p;
v--;
int res = d[v];
vector <int> cnt;
while (v != 0 && par[v] != 0) {
cnt.push_back((int)g[par[v]].size());
v = par[par[v]];
}
sort(cnt.rbegin(), cnt.rend());
for (int i = 0; i < min(p, (int)cnt.size()); i++) {
res -= 2 * (cnt[i] - 1);
}
cout << res << '\n';
}
}
int main() {
int tt;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
Solution (Notes)
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, q;
cin >> n >> q;
vector < vector <int> > g(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);
}
vector <int> depth(n);
vector <int> d(n);
vector < vector < pair <int,int> > > qrs(n); // <p, idx>
vector <int> res(q);
for (int i = 0; i < q; i++) {
int v, p;
cin >> v >> p;
v--;
qrs[v].push_back({p, i});
}
multiset <int> st[2]; // store negative number to be able to use usual foreach loop
function <void(int, int, int)> dfs = [&](int v, int p, int pp) {
if (depth[v] == 1) d[v] = 1;
if (depth[v] > 1) d[v] = d[pp] + 2 * (int)g[p].size();
for (pair <int, int> qr : qrs[v]) {
int p = qr.first, idx = qr.second;
int ans = d[v];
for (int i : st[1 - depth[v] % 2]) {
if (p == 0) break;
ans -= (-i - 1) * 2;
p--;
}
res[idx] = ans;
}
if (depth[v] != 0) st[depth[v] % 2].insert(-(int)g[v].size());
for (int to : g[v]) {
if (to == p) continue;
depth[to] = depth[v] + 1;
dfs(to, v, p);
}
if (depth[v] != 0) st[depth[v] % 2].erase(st[depth[v] % 2].find(-(int)g[v].size()));
};
dfs(0, 0, 0);
for (int i = 0; i < q; i++)
cout << res[i] << '\n';
}
int main() {
int tt;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
Notes
This problem originally had the following constraints:
$$$1 \le n, q \le 2 \cdot 10^5$$$
The sum of $$$p$$$ in all queries is not greater than $$$2 \cdot 10^5$$$
How to solve this problem?
Could you solve this problem without the second constraint?
Hint
However, it is not hard thanks to a recent blog.
Editorial
Tutorial is loading...
Solution Phi
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3000010;
const int mod = 998244353;
int fact[N], ifact[N], phi[N];
int powmod(int a, int n) {
int res = 1;
while (n) {
if (n % 2 == 0) {
a = (a * a) % mod;
n /= 2;
}
else {
res = (res * a) % mod;
n--;
}
}
return res;
}
int inv(int a) {
return powmod(a, mod - 2);
}
void prepare() {
fact[0] = 1;
for (int i = 1; i < N; i++) {
fact[i] = (fact[i - 1] * i) % mod;
}
ifact[N - 1] = inv(fact[N - 1]);
for (int i = N - 2; i >= 0; i--) {
ifact[i] = (ifact[i + 1] * (i + 1)) % mod;
}
phi[0] = 0;
phi[1] = 1;
for (int i = 2; i < N; i++) {
phi[i] = i - 1;
}
for (int i = 2; i < N; i++) {
for (int j = i * 2; j < N; j += i) {
phi[j] -= phi[i];
}
}
}
int C(int n, int k) {
return ((fact[n] * ifact[k]) % mod * ifact[n - k]) % mod;
}
int MC(vector <int> &a) {
int sum=0;
for (int i : a) sum += i;
int res = fact[sum];
for (int i : a) {
res = (res * ifact[i]) % mod;
}
return res;
}
int lcm(int a, int b) {
return a / __gcd(a, b) * b;
}
vector <int> all_divs(int x) {
vector <int> d;
for (int i = 1; i * i <= x; i++) {
if (x % i == 0) {
d.push_back(i);
if (i * i != x) {
d.push_back(x / i);
}
}
}
return d;
}
void solve() {
int a, b, c, k;
cin >> a >> b >> c >> k;
vector <int> v(k);
for (int &i : v) cin >> i;
int g = v[0];
for (int i : v) g = __gcd(g, i);
map <int, int> mp;
for (int i : all_divs(a)) {
for (int j : all_divs(b)) {
for (int l : all_divs(c)) {
int N = lcm(i, lcm(j, l));
if (g % N == 0) {
mp[N] += phi[i] * phi[j] * phi[l];
}
}
}
}
int sum = 0;
for (pair <int, int> pr : mp) {
int N = pr.first, cnt = pr.second;
vector <int> u;
for (int t : v) u.push_back(t / N);
sum = (sum + (MC(u) * cnt) % mod) % mod;
}
sum = (sum * inv(a * b * c)) % mod;
cout << sum << endl;
}
int32_t main() {
prepare();
int tt;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
Solution DP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3000010;
const int mod = 998244353;
int fact[N], ifact[N];
int pos[N];
int powmod(int a, int n) {
int res = 1;
while (n) {
if (n % 2 == 0) {
a = (a * a) % mod;
n /= 2;
}
else {
res = (res * a) % mod;
n--;
}
}
return res;
}
int inv(int a) {
return powmod(a, mod - 2);
}
void prepare() {
fact[0] = 1;
for (int i = 1;i < N; i++) {
fact[i] = (fact[i - 1] * i) % mod;
}
ifact[N - 1] = inv(fact[N - 1]);
for (int i = N - 2; i >= 0; i--) {
ifact[i] = (ifact[i + 1] * (i + 1)) % mod;
}
}
int C(int n, int k) {
return ((fact[n] * ifact[k]) % mod * ifact[n - k]) % mod;
}
int MC(vector <int> &a) {
int sum=0;
for (int i : a) sum += i;
int res = fact[sum];
for (int i : a) {
res = (res * ifact[i]) % mod;
}
return res;
}
int lcm(int a, int b) {
return a / __gcd(a, b) * b;
}
vector <int> all_divs(int x) {
vector <int> d1, d2;
for (int i = 1; i * i <= x; i++) {
if (x % i == 0) {
d1.push_back(i);
if (i * i != x) {
d2.push_back(x / i);
}
}
}
reverse(d2.begin(), d2.end());
for (int i : d2) d1.push_back(i);
return d1;
}
void solve() {
int a, b, c, k;
cin >> a >> b >> c >> k;
vector <int> v(k);
for (int &i : v) cin >> i;
int g = v[0];
for (int i : v) g = __gcd(g, i);
vector <int> divs_g = all_divs(g);
set <int> divs;
for (int i : all_divs(a)) divs.insert(i);
for (int i : all_divs(b)) divs.insert(i);
for (int i : all_divs(c)) divs.insert(i);
for (int i : all_divs(g)) divs.insert(i);
int D = divs.size();
int i = 0;
for (int j : divs) {
pos[j] = i;
i++;
}
int n = max({a, b, c}) + 1;
vector < vector <int> > tmp(3, vector <int> (D));
vector < vector <int> > cnt(3, vector <int> (D));
for (int t = 0; t < 3; t++) {
int x;
if (t == 0) x = a;
if (t == 1) x = b;
if (t == 2) x = c;
vector <int> divs_x = all_divs(x);
for (int i = (int)divs_x.size() - 1; i >= 0; i--) {
tmp[t][pos[divs_x[i]]] += x / divs_x[i];
for (int j = 0; j < i; j++) {
if (divs_x[i] % divs_x[j] == 0) {
tmp[t][pos[divs_x[j]]] -= tmp[t][pos[divs_x[i]]];
}
}
cnt[t][pos[x / divs_x[i]]] = tmp[t][pos[divs_x[i]]];
}
}
vector < vector <int> > dp(4, vector <int> (D));
dp[0][0] = 1;
for(int i = 0; i < 3; i++) {
for (int t1 : divs_g) {
for (int t2 : divs_g) {
int new_pos = lcm(t1, t2);
if (t2 < n) {
dp[i + 1][pos[new_pos]] = (dp[i + 1][pos[new_pos]] + dp[i][pos[t1]] * cnt[i][pos[t2]]) % mod;
}
}
}
}
int sum = 0;
i = 0;
for (int j : divs) {
if (g % j != 0) continue;
int N = j, cnt = dp[3][pos[j]];
vector <int> u;
for (int t : v) u.push_back(t / N);
sum = (sum + (MC(u) * cnt) % mod) % mod;
}
sum = (sum * inv(a * b * c)) % mod;
cout << sum << endl;
}
int32_t main() {
prepare();
int tt;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
can someone hack my submission for D, it works purely on hopes and dreams. 295631816
who are we to ruin ones hopes and dreams?
why all of you say “hopes and dreams”？what is the meaning of it?
undertale reference
My submission for D was literally hopes and dreams (I just chose random valid numbers until it was no longer possible.)
Same
I thought i was the only doing this.
Hey, can you tell me how did this even come to your mind to generate random numbers and then brute forcing all the available remaining numbers, did you not think that it may give TLE? Just curious to know why so many people applied such a random approach of generating random numbers.
I was running out of time and couldn't think of a sophisticated way of doing it, and the number of composite numbers >> the number of prime numbers so I'd figured I'd probably be able to allocate a number within a few tries. As for why random numbers instead of just iterating starting from the next number, I thought that there was a decent chance that I'd end up with a bunch of allocated numbers close together that I would have to iterate over and waste time, so random numbers were probably safer than that option. Plus, I always have a soft spot for cool approaches and randomization definitely qualifies. :)
In hindsight it was probably not necessary but it was fun nonetheless.Sorry for rambling, but that pretty much exactly represents my thought process within the contest.
Edit: it turns out randomization was necessary for my approach. I submitted a solution without randomization, just using the fallback I had of iterating over all unused elements in order (using a set so it wasn't totally inefficient), and I TLE'd.
That's cool , thank you for replying and sharing :)
fast editorial
Problems like C add nothing to the knowledge of the participants. They just test IQ.
Also, it is exactly same as this problem: https://codeforces.me/contest/513/problem/B2
Edit: I understand that many of you had fun solving the problem. But there are several participants who just recognized the pattern for smaller n's and hoped it work for larger values of n as well. Isn't it unfair to the people who really come up with and proved their solution?
I mean the testers create randomized cases just to ensure that makeshift solutions do not pass and here anyone who recognized the "pattern" for n <= 6 could get an AC!
Is this the reason for so many ACs on C?
the fact that it already exists is cringe and they should've checked for that. But I struggled on it for an hour, and when I managed to solve it, I think it really did add to my knowledge, and I think it's a great problem. I believe I learned a lot more from it than from D, where I literally just guessed the solution without proving it actually works
That is because you are one of the few people who solved it like it should be. Many participants just observed the pattern for small n's and hoped that it will work for bigger values of n as well. Something similar happened for D also.
Well, not "hoped", but it's much easier to prove a pattern than spot a pattern without seeing the permutationa
how to solve problem c? i could not understand the solution.
Nahh man,I think apart from the fact that it was an existing problem I felt that it was a nice constructive algorithm problem which didn't rely on prior facts or knowledge.
Agree 100%, really annoying that it was a previously done problem, since I had a lot of fun solving it (and it's probably the hardest problem I've ever solved, so I'm happy about that)
Me, the author, and the testers didn't know about this problem, and it didn't come up in my searches :( (maybe because the formula is an image...)
I feel that getting the permutation even after knowing the fact (which can be easily verified by a brute force), the construction isn't trivial. The editorial seems incomplete without it.
welp that's the average div. 2 C unfortunately
i think C is a pretty cute problem Tbf, aside from the fact that it existed before the contest
it felt much nicer solving C since i was able to see what was happening and wasn't making any guesses
If so, all constructive problems on arrays are testing IQ.
to an extent, yes
Isn't competitive programming a huge IQ test? If someone doesn't like IQ tests, I would advise against CP...
I think recognizing the pattern is a good thing. It takes skills to be able to recognize the pattern and take advantage of the pattern to solve the problem. Dynamic programming is also about recognizing the pattern.
I had fun solving this task myself (after contest). But yes, I confirm, it's EXACTLY same.
My solution for 513 B2
And for this contest
I didn't participated in round, so I don't care, it's rated or not. But rules should be for everybody. FYI Igor_Parfenov
oh wow, super fast editorial before system testing, thank you.
Thanks for the really interesting problemset. It's satisfying to see that even E can be implemented so simply without need for advanced data structures.
E can be solved offline in O(Q log^3 N) by using parallel binary search and HLD.
what techniques/knowledge is required for E? i am clueless on how to even begin solving it
The easier solution to E does not need any of this. Naive O(NQlogN) works just fine.
Under the constraints, this approch is only a little faster than the official one.
This problem has the same general idea and requires this approach.
isn't that a bit over kill?
yes, very much so.
You can also solve in O(Q log N) with PST walking
No need for $$$\log^3$$$, you can get a simple offline $$$(N + Q) \log N$$$ using Fenwick trees: 295645729
everyone failed E because they misread the constraints
And almost everyone missed E because they were stuck in C and D.
Bruh I had no idea how to solve B.
Then I remembered, "If nothing makes your solution work, put it in a binary search" — me
So, I tried binary searching on how many of 1st type operations would be used.
And I got wa. But I will try to solve it using binary search
Binary search will work, so you're not trying in vain.
Here is the 2e5 version of problem E for python. It passed the test, and run within 1s with randomly generated cases on my local machine.
295640041
this link is broken https://codeforces.me/blog/entry/13685
Fixed, thank You
Now it says "You are not allowed to view the requested page".
My solution of D with the proof:
Proof:
$$$v_i$$$ must be not the neighbor of $$$v_{i+1}$$$ if they have same depth. In the case they have different depth, they can't be adjacent after the sort because the lemma (except $$$v_n$$$ when it's a center). So $$$v_1, v_2, \cdots, v_{n-1}$$$ must be a legal solution.
So we just need to care with $$$v_n (a_{v_n} = 2)$$$. It can only conflict with $$$v_1 (a_{v_1} = 4)$$$. If they are adjacdent, we just assignment $$$a_{v_1} = 1$$$ because $$$v_1$$$ is always a leaf and not about other vertices ($$$v_2, v_3, \cdots, v_{n-1}$$$).
Code: 295631636
I think another solution used bipartite graph is more interesting, really make me amaze.
Update: Sorry, it's like official solution 2.
read Project Hail Mary lol
B was nice!
ok i am dumb i forgot about last 1 after "1"
Place 1s at indexes 1 and 4
Fill the indexes 1 through 4
Place 1 at index 10
Fill the indexes 1 through 10 (This solves your second question)
Place a 1 at index 20
Fill the indexes through 1 through 20
3 from 10: initial: 0000000000 after 1: 1000000000 after 2: 1001000000 query type 2: 1111000000 after 3: 1111000001 query type 2: 1111111111
20 does the same steps up to there but adds one more initial (3 operations done): 11111111110000000000 after 4: 11111111110000000001 query type 2: 11111111111111111111
Consider this string: 1001000001 Where the flipped bit are those set using first operation. Now, you can flip the first two bits in between (because there are a total of 4 bits, 2 of which are 1, so the constraint ceil(4/2) >= 2 is satisfied). Then the string becomes: 1111000001 Now, just choose the first and the last bit; l=1, r=10, the constraint ceil(10/2) = 5 >= 5 is satisfied, so we can flip all other bits. Just do it iteratively and you have the solution.
E can be solved in O(n^2 + q). Link
thanks for giving the tutorial too fast like rocket :)
dreams are illusion or future
Cannt problem E be solved with $$$Q \le 10^5$$$ also.
Yes, you can precompute a 2d DP and answer all queries in O(1)
For problem D my solution simply chooses values randomly for each node of the tree in DFS order, repeating until the difference with the node's parent isn't prime.
This works because when $$$n$$$ is large enough, $$$n \, » \, \frac{n}{\ln n}$$$ (or even $$$\frac{2n}{\ln n}$$$), which means there's always a significant fraction of the remaining numbers that would result in a non-prime difference. During the contest I added some logic to potentially restart from scratch and re-randomize if needed for small $$$n$$$, but it seems like you don't even need that: 295643399
Another benefit of this solution is it will work for smaller bounds such as $$$1.5n$$$ instead of $$$2n$$$.
Can you please further show why it will work?
Hi, i did the same but used bfs, and for some reason it is giving TLE 296790454
can you please help?
You can't solve n = 3 with composite differences only (the only option is 4). You need to use 1 as a non-prime difference as well.
nice problems, finally reached pupil!
neat solution to problem C... I found the greedy strategy for problem C but couldn't find a way to implement it other than calculating 2^(n-2), which would not work with the constraints. sad that I could not solve it even after finding the correct logic ;(
[For problem C] I am trying to generate the permutation according to the bitwise representation of k. Could anyone please see what's the error?
Hey ladies and gentlemen, this is my code for verifying how the dynamics of the C's solution work https://www.ideone.com/fQB1zU
and following is the submission link of the AC verdict for the corresponding Que' https://codeforces.me/contest/2040/submission/295645589
hope you understand it, if not, ping me back freely!
Alternative solution for problem E:
Let us solve the problem where $$$p=0$$$ for all queries. Consider two functions $$$A_v$$$ and $$$B_v$$$ where $$$A_v$$$ is the expected number of moves to reach $$$1$$$ if we are currently in $$$v$$$ and $$$i$$$ is odd and $$$B_v$$$ is the same as $$$A_v$$$ but $$$i$$$ is even. $$$A_1=B_1=0$$$, since we are already at $$$1$$$ so we require zero moves.
If $$$i$$$ is odd, then we move to the parent with probability $$$1$$$, hence $$$A_v=B_{\texttt{pr}}+1$$$, where $$$\texttt{pr}$$$ is the parent of $$$v$$$.
If $$$i$$$ is even, then we move to any neighbor vertex with the same probability, hence $$$B_v=\sum\limits_{u \in N(v)}\frac{A_u}{deg[v]}+1$$$. Let us simplify this formula as $$$B_v=\frac{A_{\texttt{pr}}}{deg[v]}+\sum\limits_{u \in \texttt{children}(v)}\frac{A_u}{deg[v]} + 1$$$. Notice, that $$$A_u=B_{\texttt{v}}+1$$$ from the $$$A_v$$$ recurrence, hence $$$B_v=\frac{A_{\texttt{pr}}}{deg[v]}+\sum\limits_{u \in \texttt{children}(v)}\frac{B_v+1}{deg[v]} + 1$$$ The sum does not depand on $$$u$$$ anymore, so we have $$$B_v=\frac{A_{\texttt{pr}}}{deg[v]}+\frac{deg[v]-1}{deg[v]}\cdot (B_v+1) + 1$$$.
Solving this equation for $$$B_v$$$ we have a formula $$$B_v=A_{\texttt{pr}}+2\cdot \texttt{deg}[v]-1$$$.
We have formulas for $$$A_v$$$ and $$$B_v$$$ that depend only on the parent of $$$v$$$, so can run a simple dfs to compute the values for all vertices. The answer for the query is $$$A_v$$$, since we start from the odd $$$i$$$.
But in the original problem we have some amount of coins. The solution doesn't change at all, we just add another parameter to our functions that responds to the number of coins we have, $$$A_{v,p}$$$ and $$$B_{v,p}$$$. The transitions are the same, but we can also spend a coin when updating $$$B_{v, p}$$$, so $$$B_{v, p}$$$ may be $$$A_{\texttt{pr}, p-1}+1$$$.
Precomputing $$$A_{v,p}$$$ and $$$B_{v,p}$$$ for all $$${v,p}$$$ takes us $$$O(n^2)$$$ and answering the queries $$$O(1)$$$.
Implementation: 295642233
Back to pupil!!! Thanks for this contest.
Totally blanked out at C :(
C was tragic for me, I actually found the "left or right " construction, I just couldn't get it to work properly, i need to work on constructives
Damn, in D I thought that 1 is considered to be a prime number...
Hell nah. My master dreams are ruined by this fact. I almost went crazy not understanding why my solution wasn't working.
I need to retire from cf to save my hair and eyes :)
Sorry, I laughed when I saw your rating
I am failing to understand E, if anyone could help me understand it in easier way. Thanks before hand
problem E: I thought to build a vector of expected values $$$d$$$, where $$$d_N$$$ is the expected number of moves from a node with $$$N$$$ neighbors to go up (towards vertex 1) of exactly one step, so the parent, when the current counter parity is even. So:
the first term is the case in which the robot is lucky and goes up, that takes 1 step with probability 1/N; the second one is the probability of going down to one of the $N-1$ below standing children, than going up (2 moves) and the expected value $$$d_N$$$ itself. So, at the end the expression for $$$d_N$$$ is:
But it is not correct. Can someone explain me why please?
UPD: the first equation is correct, the final computation is not. As harshaa005 sais:
Your initial equal is correct. Somehow you must have done some mistake in calculation. I have used the same equation in my submission.
295662501
Oh, yes. Thank you!
On C I calculated the S(p) up to n = 8 to see the pattern. I did realize that the smaller numbers always ended up in one of the ends of the array and that they had a sort of logarithmic behaviour, like, the permutation changed based on powers of 2.
Though I had no idea how to enumerate them, and to realize afterwards that you can just decompose K into bits and just decide the position based on that is just crazy. Awesome problem, even if it costed me my Specialist.
literally same, i found the pattern, not by proof, but in a sort way where i was like, the more big stuff on one side the better, this is probably right and we cant make both sides big for each number, and in a notes document i wrote: "case on dropping to the left or the right, left makes smaller, right makes bigger." however, when I went to check it against samples for "4 6" i considered binary 6 instead of binary 5, so it wasnt right, I gave up on the idea, bricked my mental, and failed the contest
+1
295648314. Coding this is also simple.
Interesting recursion
For Problem C I printed set of all permutations and tried to recognize a pattern. But Had a very difficult time imaplementing it, and also totally overlook that n is large and I cant use
1<<(n-1). That was my first experience handling such tricky constraints... Really learned so much in this single problem!!!!Wow, I was just speaking about this point, but I think I handled it in a different way and yes I didn't have time to finish my work in the contest coz of this trick and another trick
I solved C in a different way, I just generated all of the permutations with the score of the maximum and the score of the maximum is the score of this permutation that you put the highest one in the middle then on its left the next maximum the on its right the next maximum and so on, so something like this will happen if n = 7
1 4 6 7 5 3 2
then this gave me this result when used n = 5
(1, 2, 3, 4, 5) (1, 2, 3, 5, 4) (1, 2, 4, 5, 3) (1, 2, 5, 4, 3) (1, 3, 4, 5, 2) (1, 3, 5, 4, 2) (1, 4, 5, 3, 2) (1, 5, 4, 3, 2) (2, 3, 4, 5, 1) (2, 3, 5, 4, 1) (2, 4, 5, 3, 1) (2, 5, 4, 3, 1) (3, 4, 5, 2, 1) (3, 5, 4, 2, 1) (4, 5, 3, 2, 1) (5, 4, 3, 2, 1)
and from here I saw they are being repeated by powers of 2 until they reach n
look at the first item in the first 8 places it is 1 and then the others will be 2 in the next 4 perms
and so on, so I coded this pattern
then any number less than n will be printed by just looping from n to 1 and add any not-added-yet numbers
My Submission
For problem E I can't figure out what is wrong with my approach. I see the editorial did something different, but I cam up with geometric distribution to solve it, and it gets till test case 4 and fails on the 138th query.
submission
You have a problem with dp. When you have several paths to the state, you set the value from the last path. Instead, assign the minimum value.
Change
dp[u] = dp[v] + xtodp[u] = min(dp[u], dp[v] + x)Also, you don't need modulo here, as the answer is always $$$\le$$$ n.
That worked, I was so close with my approach, instead of treating each movement as odd-even step, I just tracked the parity in the dp states, and the possible transitions based on the the current parity.
Honestly i have no idea when my first time meet C but i suddenly realize that this is a similar question to this 1450D - Rating Compression 295345001 The key idea is the current minimum number is always occur in the side of the interval,for example let think about for n=4 how we can get the maximum answer?We can do greedily first which is put the large number at the first,the 2nd largest number at the second and so on we got 4,3,2,1,and after that what should we do next move?Let us think about what times 4 appear in subarray,[4] only right?Then what time for 3?[3],[4,3] right?Do you found the pattern 4 appear 1 times,3 appear 2 times,2 appear 3 times,1 appear 4 times,If you found this you already solve half of the problem.What is the usage of the previous observation?I found that when 4,3,2 and 1 appear [1,2,3,4] times respectively will give us maximum answer in otherword if the permutaion cannot give us the corresponding number appear times then this permutation will definitely is not a answer,for example [4,1,2,3],4 appear 1 times,2 appear 2 times ,3 appear 1 times and 1 appear 6 times,the appear for 4,3,2,1 is [1,1,2,6],obviously the 1 appear times from 4->6 and the total number times is a constant because its is the total number of possible subarray which is n*(n+1)/2 so now the problem become how we can make sure number appear times of our permutation is same as the optizimed appear times,we do it step by step,initially imagine you have n box there are lie in one line and set the current minimum number become 1,so in [1,n] what place should i place the 1 such that 1 will appear exactly the optimized times,the answer is in leftmost or rightmost,from the previous observation in n=4 1 should be appear 4 times so obviously according to our constructed method when n=5 1 also will appear 5 times in other word ,1 will appear n times in optimized answer,so why leftmost or rightmost will provided optimized answer?Assume that i place 1 at rightmost(same for leftmost) then it will be 1xxxxxxxxx...xxx(exactly n-1 x) and how many subarray will form by above array,just use a simple combination,it will be n right?Because the current empty box(does not place any number) is n-1 then will form (n-1)+1=n,so after place 1,2 is my new current minimum number and after i place 2 i have n-2 empty box,and let us recall what is the appear times of 2 we need?n-1 right,so n-2 empty box will form (n-2)+1,the +1 is because itself can also form a subarray,after this you can constructed the number step by step, and the complexity will become O(n) below is my submission 295604272
why (1<<(x-2)) ? why not x-1 ? I dont understand this . can you explain this part why x-2 ?
For example n=3,there will be 3 position we need to place.Initially we will have 3 emply box and current minimum number is 1 then we have 2 option to place 1 which is either left most or right most (1 or 3) so there is two ways,and after that our current minimum become 2 now we have 2 box ,when we have 2 box there only two way because when we put 2 at the 2nd box then 3 must in 3nd box or we put 2 at the 3nd box then 3 must in 2nd box,so when we left 2 box there is only 2 way,so ans=2*2 so you can see that when n=3 there is 2*2,similarly to n=4 there is 2*2*2,so if the current box left is x after i put the current minimum number there will be x-1 box and x-1 box will have 2*2*2...*2 (x-2)times according to the previous observation.
Thanks a lot, can you also elaborate on how you calculated the k-th permutation?
Edit: got it now
in E how can d[v]=2+1d+1⋅d[u]+dd+1⋅d[v], whence d[v]=d[u]+2⋅(x+1) i dont understand
In the Editorial of D：
$$$\text{We will write the values } n\cdot 2,n\cdot 2−1,n\cdot 2−2,\cdots \text{ to the vertices with odd depth in breadth-first order.}$$$
Maybe it is a mistake and should it be:
$$$\text{We will write the values } n\cdot 2,n\cdot 2−2,n\cdot 2−4,\cdots \text{ to the vertices with odd depth in breadth-first order.}$$$
YES, there is a mistake but in the code it is correct
This contest is quite standard. At first, when solving problems A and B, I thought there had to be something really tricky, but after reading the constraints, this is the first time I've found problems A and B to be this easy
hi newbie here i just wanted to know about problem b lets consider n=5; now 1st operation change at 1st index 0 to 1 2nd operation change at 5th index 0 to 1 (5-1+1)/2 is 2 in programming so why the output is 3 instead of 2
ceil not floor
got it
Hi, could I check why in the first if block for C we must check for n <= 60? I'm unsure of the intuition behind it.
because for n>60 ,2^n will always be greater than k, so ans will always exist. So there is no need to compute 2^n for n>60 and also it will give integer overflow even in long long int.
Every element from 1 to n-1 will be having 2 choices, either start of array or end, the nth element has only 1 choice, so it is 2^n-1 permutations total, if k is greater than this then we must print -1, but since n is upto 2*10^5, if we just always try to left shift, we will deal with overflow. Since k is 10^12, if (n-1)>=40, choices will be always greater than whatever k is given, so you only need to check for lower n's
I am unable to understand the proof for the given construction in C, can somebody explain that? And even after building the construction I am unsure of how we are calculating the k-th permutation
Edit: got it now
In B if n=11 and i make arr1=1 and then i make arr5=1 so for now two first type operations are needed and then i apply second type of operation(5/2<=2) and then applying in arr11=1 cant i get it in 3 operations only why the answer is 4 plz someone tell
$$$\lceil$$$ and $$$\rceil$$$ represent ceil operator, so $$$\lceil {5 \over 2} \rceil$$$ is $$$3$$$, not $$$2$$$.
It is a bad mistake to try do the problems while in car. Got so dizzy, i cannot even solve problem A :(
Here is how I solved problem C. Initially, I made some observations:- How will i get the max S(p)? -> By making the contributions of smaller numbers the least possible. How will i do this? -> starting with the current smallest no(which initially is 1) i can prove that it has to be placed either on the extreme left or to the extreme right of the current empty array. This can subsequently be done for the next current smallest values, all follow the same thing.
So getting the kth permutation:- When will the ans not exist? -> when k > no of perm which gives the max value (2 ^ n-1); As k<=1e12, this is only when n-1<40.
Now for each number in the permutation, we have two possibilities either place it in the first or last of the empty array. When right? -> temp = (1LL<<(n — cursmallest — 1)) if(k>temp) then cursmallest will be at the last and simultaneously update k = k — temp;
Elsewhere cursmallest goes to the left position.
Implementation 295706641
Thank you for the much needed explanation
is there any way to look that test case like my code is giving wrong ans for test case 3 token 338 ........how can i find that particular testcase can anyone help
I just greedily assigned the values to nodes in D using the fact that any difference between any consecutive non-prime numbers would always be <=2.Is this enough to prove that I would be using values <=2*n? cause at max I will just be skipping a single number per assignment.
Appear for the first time and couldn't solved single problem. but I am not gonna give up
The Editorial of problem D contains a typo in my opinion. The second solution should have "n.2, (n-1).2, (n-2).2,..." instead of "n.2, n.2-1, n.2-2,...". Please verify this once Igor_Parfenov
can someone explain C in more detail? i recognized the pattern but don't know how to generate the kth one. these are some first permutations for n = 5
I might've missed some here...
Here are all the permutations that work for n = 5
Here are a couple of observations that I made, bolding the ones that were fairly important
A reversed permuation has the same score as the original
An element can only appear in the final equation at most (max_element-n+1) times, e.g if the permutation was of length 5, 5 could appear at most once, 4 could appear at most 2 times, etc. Therefore, in order to ensure that the sum is maximized, an element must appear the maximum amount of times that it is able to.
the first element from the back will be fixed for 1 permutation, the second element from the back will be fixed for 1 turn, third element 2 turns, fourth element 4 turns, and fifth element 8 turns (with fixed meaning up to that point, it's in the same position that it would be if the permutation was sorted)
An element will be a prefix or a suffix of the elements up to that point, e.g in the case where n = 5, 4 could either appear before or after 5, so the possible values of that subarray are 4 5 or 5 4, then once we get to 3, it can be 3 4 5, 3 5 4, 4 5 3, 5 4 3
Whether the nth element from the back is at the start or end of the elements up to that point depends on if the modulo value of k by 2^n is greater or less than 2^(n-1) (if it's less than 2^(n-1), it should be added at the front, otherwise at the back.
I hope this helped (sorry if it's hard to understand, I know I'm not the best at explaining)
really didn't understand the 5th point. i couldn't make the 4th observation but i had all the work done before that
I'll use the example of n = 5 and k = 9
Let's start with an empty list (I used a deque in my code, but a list will work to show how it works)
(I'll mention that I subtract 1 from k to perform the calculations, so k is equal to 8 in my calculations)
Now let's iterate from 5 to 1 and add the elements to the list
Since 5 is the first element from the back, we will check if k % 2^0 < 2^-1 (8 % 1 < 0.5). Since it's less than 0.5, we add it to the front, so the list is now [5]
Now let's go to 4, and check if k % 2^1 < 2^0 (8 % 2 < 1). Since this is true, we add it to the front, and the list is now [4, 5]
For 3, k % 2^2 < 2^1 (8 % 4 < 2) is true, so we add it to the front, and the list is now [3, 4, 5]
For 2, k % 2^3 < 2^2 (8 % 8 < 4) is true, so we add it to the front, and the list is now [2, 3, 4, 5]
For 1, k % 2^4 < 2^3 (8 % 16 < 8) is false, so we add it to the back, and the list is now [2, 3, 4, 5, 1]
Our final list is [2, 3, 4, 5, 1]
lets puts these numbers in boxes. last 2 numbers form a box whose min will be (n-1) last 3 numbers form a box whose min will be (n-2) and so on
now observe that you can you can only switch position of number in front of this box and put this number at the end of the box. like this:
[1, [2 , [3 ,[4 ,[5]]]]] here you can switch 4 like: [1, [2 , [3 ,[[5], 4 ]]]] and switch 3 like: [1, [2 , [[[5], 4 ] ,3 ]]]
this are the only ways you can achieve the maximum value. now to achieve lexicographical sequence just reverse the innermost box. here you have 2 choices.now again move the 2nd innermost box repeating what you did in for previous innermost box giving you 2*2 choices. this goes on till 2^(n-1).Imagine this as bits. A set bit represents that the number should be at the back.
Problem 2 — Can someone explain me the 4 cuts for n=20? My understanding says we require atleast 5 operations of type A performed on i=1,4,8,16,20.
hint: 3 cuts are enough for 5 <= n <= 10
place 1st 1 at 1 2nd at 4 3rd at 10 and fourth at 20 or at max at 22
Thanks
fun fact: problem E can be solved without modulus operation.
Submission: 295789260
Just want to share my submission for C.295812221. The logic is I am keeping the ith highest element within ith position w.r.t highest element.
How the solution code of C is related to text solution. I couldn't understand, how binary representation is related here.
In B, why on first operation indexes are (1,4) not (1,5)?
I learned something new from problem F
I solved problem C using recursion and two-pointers. This is the code 296273126 The overall thought process is roughly this, if it helps anyone:
We check if the required index k is <=2^(n-1)/2, or it is more than that. if it is the first case, then we insert the lowest value of the remaining numbers at the first position, else at the last position. why? because if we take any n, say n=5, then for k<=8, 1 will be at the first position, and for k>8, 1 will be at the last position. Continuing this example, once we are done inserting the 1 for n=5 case, we decrease n in the next function call, to get n=4. now there are two steps, first we check if k is larger than 2^(4-1), if yes, we take modulo to bring k in the range of 1 to 8 (for n=4). next, we check whether k<=4 or k>4. if k<=4, we have to insert the lowest remaining number at the first position. it would be like 1 2 _ _ _. else, we insert it at the end,i.e., 1 _ _ _ 2.
We repeat this approach until we get n=1, at which point we insert the last remaining number (which will also be the original n we started with) at the last remaining index.
hey coders,,,
in Problem-C tag, there is bitmask. how can i solve this problem with bitmask. or the binary representation of k-1.what is the reason behind it. and how can i come up with this kind of solution...
Does anyone have a good proof for approach 1 of D ?
can somebody explain c in detail
Consider how many times each element appears in formula. For example, for n=9 it's
[9, 16, 21, 24, 25, 24, 21, 16, 9]. This means that smallest number should be placed at the edges, to affect less segments. After you placed $$$x$$$, it will change number of segments $$$x+1$$$ will affect, so this can be viewed as placing numbers starting from $$$x+1$$$ in empty array of length $$$n-1$$$.Thanks! That was array explanation was very helpful.
For problem B The tutorial/system gives answer = 3 for n = 5
But, Let's say I want to put 1 at the index 1 and 4. Means the intermediate array looks like [1,0,0,1,0]. Here because of the operation 2 the array will become [1,1,1,1,0], correct? and at last you choose R = 5 and L = 1. With this your entire array will become [1,1,1,1,1]
So total of 1st operations used is equal to 2, right? Instead of 3.
Can someone correct me where I am missing.
In order to apply operation of type 2, both a[l] and a[r] should be equal to 1. In your case, a[5] is 0, and hence you cannot apply the operation of type 2.
if you directly put a[1]=1 and a[5]=1 using first operation, i can apply second operation directly to get [1,1,1,1,1] (since 1+1=2=[(5-1+1)/2], and i assume [.] to be floor. shouldn't the answer be 2 then?
nvm it is ceil, question did not specify it
Late note: problem E can be solved in $$$\Theta(n + q)$$$ using the fact that $$$\sum d_u = \Theta(n)$$$.
How do you even think of C? I can understand the editorial and follow along, but the idea is just so unexpected.
For problem B, we can simply observe the pattern for filling '1' through type 1 (i.e. after filling '1' in index 1 and index n, you've to fill '1' like this- 4, 10, 22, 46, ...) and find the general term of the sequence and you can directly put the below expression to get the desired output: