1843A - Sasha and Array Coloring
Idea: Sokol080808, prepared: molney
Tutorial
Tutorial is loading...
Solution
def solve():
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
ans = 0
for i in range(n // 2):
ans += a[-i-1] - a[i]
print(ans)
t = int(input())
for _ in range(t):
solve()
Idea: EJIC_B_KEDAX, prepared: molney
Tutorial
Tutorial is loading...
Solution
T = int(input())
for _ in range(T):
n = int(input())
a = list(map(int, input().split()))
sum = 0
cnt = 0
open = False
for x in a:
sum += abs(x)
if x < 0 and not open:
open = True
cnt += 1
if x > 0:
open = False
print(sum, cnt)
Idea: Sokol080808, prepared: molney
Tutorial
Tutorial is loading...
Solution
t = int(input())
for _ in range(t):
n = int(input())
s = 0
while n >= 1:
s += n
n //= 2
print(s)
Idea: EJIC_B_KEDAX, prepared: Vladosiya
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<int>> g;
vector<ll> cnt;
void dfs(int v, int p) {
if (g[v].size() == 1 && g[v][0] == p) {
cnt[v] = 1;
} else {
for (auto u : g[v]) {
if (u != p) {
dfs(u, v);
cnt[v] += cnt[u];
}
}
}
}
void solve() {
int n, q;
cin >> n;
g.assign(n, vector<int>());
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);
}
cnt.assign(n, 0);
dfs(0, -1);
cin >> q;
for (int i = 0; i < q; i++) {
int c, k;
cin >> c >> k;
c--; k--;
ll res = cnt[c] * cnt[k];
cout << res << '\n';
}
}
signed main() {
int tests;
cin >> tests;
while (tests--) {
solve();
}
return 0;
}
Idea: meowcneil, prepared: meowcneil
Tutorial
Tutorial is loading...
Solution
def solve():
n, m = map(int, input().split())
segs = []
for i in range(m):
l, r = map(int, input().split())
l -= 1
segs.append([l, r])
q = int(input())
ord = [0] * q
for i in range(q):
ord[i] = int(input())
ord[i] -= 1
l = 0
r = q + 1
while r - l > 1:
M = (l + r) // 2
cur = [0] * n
for i in range(M):
cur[ord[i]] = 1
pr = [0] * (n + 1)
for i in range(n):
pr[i+1] = pr[i] + cur[i]
ok = False
for i in segs:
if(pr[i[1]] - pr[i[0]] > (i[1] - i[0]) // 2):
ok = True
break
if ok:
r = M
else:
l = M
if r == q + 1:
r = -1
print(r)
tc = int(input())
for T in range(tc):
solve()
1843F1 - Omsk Metro (simple version)
Idea: EJIC_B_KEDAX, prepared: Sokol080808
Tutorial
Tutorial is loading...
Solution
class info:
mn_suf = 0
mx_suf = 0
mn_ans = 0
mx_ans = 0
def solve():
n = int(input())
start = info()
start.mx_suf = start.mx_ans = 1
st = [start]
for i in range(n):
com = input().split()
if (com[0] == '+'):
v = int(com[1]) - 1
x = int(com[2])
pref = st[v]
cur = info()
cur.mn_suf = min(0, pref.mn_suf + x)
cur.mx_suf = max(0, pref.mx_suf + x)
cur.mn_ans = min(pref.mn_ans, cur.mn_suf)
cur.mx_ans = max(pref.mx_ans, cur.mx_suf)
st.append(cur)
else:
v = int(com[2]) - 1
x = int(com[3])
if st[v].mn_ans <= x <= st[v].mx_ans:
print("Yes")
else:
print("No")
t = int(input())
for testCase in range(t):
solve()
1843F2 - Omsk Metro (hard version)
Idea: EJIC_B_KEDAX, prepared: Sokol080808
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct info {
int sum, minPrefL, maxPrefL, minPrefR, maxPrefR, minSeg, maxSeg;
info(int el = 0) {
sum = el;
minSeg = minPrefL = minPrefR = min(el, 0);
maxSeg = maxPrefL = maxPrefR = max(el, 0);
}
};
struct question {
int u, v, x;
};
info merge(info& a, info& b) {
info res;
res.sum = a.sum + b.sum;
res.minPrefL = min(a.minPrefL, a.sum + b.minPrefL);
res.maxPrefL = max(a.maxPrefL, a.sum + b.maxPrefL);
res.minPrefR = min(a.minPrefR + b.sum, b.minPrefR);
res.maxPrefR = max(a.maxPrefR + b.sum, b.maxPrefR);
res.minSeg = min({a.minSeg, b.minSeg, a.minPrefR + b.minPrefL});
res.maxSeg = max({a.maxSeg, b.maxSeg, a.maxPrefR + b.maxPrefL});
return res;
}
const int MAXN = 200100;
const int lg = 17;
int up[lg + 1][MAXN];
info ans[lg + 1][MAXN];
int d[MAXN];
void solve() {
int n;
cin >> n;
for (int i = 0; i <= lg; i++) up[i][0] = 0;
ans[0][0] = info(1);
d[0] = 0;
int cur = 0;
for (int q = 0; q < n; q++) {
char c;
cin >> c;
if (c == '+') {
int v, x;
cin >> v >> x;
v--;
cur++;
d[cur] = d[v] + 1;
up[0][cur] = v;
for (int j = 0; j <= lg - 1; j++) up[j + 1][cur] = up[j][up[j][cur]];
ans[0][cur] = info(x);
for (int j = 0; j <= lg - 1; j++) ans[j + 1][cur] = merge(ans[j][cur], ans[j][up[j][cur]]);
} else {
int u, v, x;
cin >> u >> v >> x;
u--; v--;
if (d[u] < d[v]) swap(u, v);
int dif = d[u] - d[v];
info a, b;
for (int i = lg; i >= 0; i--) {
if ((dif >> i) & 1) {
a = merge(a, ans[i][u]);
u = up[i][u];
}
}
if (u == v) {
a = merge(a, ans[0][u]);
} else {
for (int i = lg; i >= 0; i--) {
if (up[i][u] != up[i][v]) {
a = merge(a, ans[i][u]);
u = up[i][u];
b = merge(b, ans[i][v]);
v = up[i][v];
}
}
a = merge(a, ans[1][u]);
b = merge(b, ans[0][v]);
}
swap(b.minPrefL, b.minPrefR);
swap(b.maxPrefL, b.maxPrefR);
info res = merge(a, b);
if (res.minSeg <= x && x <= res.maxSeg) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
}
}
int main() {
int tests;
cin >> tests;
while (tests--) {
solve();
}
}
Good contest. Ah Why I didn't think of int overflow
You should try to read statements more carefully. At the end of the output section in B was stated:
"Pay attention that an answer may not fit in a standard integer type, so do not forget to use 64-bit integer type."
And also, the problem name was a hint :)
Or just use
#define int long long
that's so good. XD
I think so.
Once again, thank you for this fun contest! :D
Why does my code output 0 in all queries in D problem? Submission Id: 210522059 ~~~~~ void dfs(int apple){
}
~~~~~
It is because of the way you are reading the graphs as input, you are making the larger vertex number the child and the smaller one the parent which is not always true
I've learned to use binary lifting to store more information thanks to the problem F, really good contest
can you explain how you have used binary lifting
For each node, let's store for it some informations, consider the path start from the node to its 2^k-th parents, we store the maximum prefix, suffix, the sum of whole path, and the maximum sum, we can efficiently use these informations to combine the path with another path.
To get similar with this concept, I suggest you to have a look at the Segment Tree course in Codeforces Edu section, which also have this concept but for an array.
nice round,hope for the positive del:)
Can someone tell me why my code was giving TLE for 1843D - Apple Tree. All I did was globally define the graph and cnt array similar to the tutorial solution and it worked then.
This is my initial submission: 210536302. This is the final accepted submission: 210538893
Passing the whole graph as an argument for the helper function each time is costly. C++ basically has to make a new copy of it each time you call that function. After making g global, it no longer has to do this. Alternatively, you could've passed a pointer to the graph as an argument.
Okay, thanks!
Hi, I know its been a long time after this contest but can you help me understand why my solution is giving WA on test4. My approach and the editorial approach seems similar. Sub:288232403
thanks
Hey! Sorry about a late reply, I hope it's still relevant.
The idea seems correct. I believe your code does not calculate the child[i] correctly. It would be easier to use a DFS here.
parent[i] seems to be okay, but, since in the last loop you iterate over nodes from n to 1 (for(int i=n;i>=1;i--){...}), it is possible that, when performing child[parent[i]]+=child[i], child[i] is still not fully computed (Meaning that there exist j such that j < i, parent[j] = i).
I hope this makes sense. Feel free to ask if you have more questions.
For problem E, why don’t you need a prefix sum for every possible array. I understand the binary search part but just building the prefix sums would tle right?
Analyzing the complexity : You binary search on q ( O(log(q)) ) and to check if a certain value is valid, you build the prefix sum array and then iterate through segments ( O(m + n (+q depending on impl) ) ). Combining these, you get O(log(q)(m+n)). If you were to build all prefix sum arrays before hand, that would take you O(q*n) time ( TLE ), because for each query, you would have to build prefix-suns. A way around this is to use a segment tree to achieve O(qlog(n)) for precomputation!
Thank you for your explanation. I forgot we could build the prefix sums inside of the binary search :(.
As we are populating the prefix array while we are doing binary search, the maximum number of times we would have to create the prefix array would be O(log Q) and creating each prefix array would take O(N) time, thus total time complexity will be well under limits reaching only O(N*log Q) for prefix array creation and O(M*log Q) for checking every range given to us, making the total time complexity O((N+M)*log Q).
Thank you for your explanation. I forgot we could build the prefix sums inside of the binary search :(.
can someone provide me any hints to detect the error in my code in problem F1?
i fall on test 3 on line 11301st expected yes found no
same error bro
and the query is
? 1 6 3
should be no only for this
actually it's yes because there is a subsegment from 1 to 6 that actually add up to 3
node 1 ==> 1 node 2 ==> 1 node 3 ==> -1 node 4 ==> 1 node 6 ==> 1
this adds up to 3
yes bro spot on. Actually i counted max positive sum on a path as only th length of consecutive ones and set it to 0 again when -1 came in between while this is nt crct as evident feom this tc.such a fool i am
Ayo bro i did the same XD , i totally forget that not only the consecutive needs to be added Actually this problem is just literally find the maximum and minimum sum of subsegments in array At least we learnt new something today Hope for cyan next div me and you <3
I don't know how the tree given in the example in question D is drawn, can someone explain it to me, thank you very much.
This is the first testcase:
5 1 2 3 4 5 3 3 2 4 3 4 5 1 4 4 1 3
The first number is n, so there are n — 1 edges with follow. Let us start with the first edge. "1 2" means an edge is drawn between vertices 1 and 2 (depicted by a line connected 1 and 2). We do the same for edges "3 4", "5 3", and "3 2".
My solution for F2 https://youtu.be/FZJxWhOoxo0
E can be solved with wavelet tree:
create an array, initially all INF. then for the
i
th update, set array[index] =i
now for each segment, the (segment len/2 + 1)th-smallest number is either INF, or the id of the query which makes it beautiful
210572758
Any solution possible with — segment trees concept only ?
It boils down to finding k-th smallest element in a range, there's a lot of ways of doing it: wavelet tree, persistent segment tree, parallel binary search...
persistent segment tree gave me mle -_-
Checkout my implementation 210606529
For me — no: 210400778
I used other idea, but I believe your PST can be optimized, too)
I solved E during the contest using wavelet tree too, I'm looking for the (len/2 + 1 + (number of zeros))th-smallest in each segment
my submission: 210413964
I guess wavlet tree is better than the Editorial solution
AnyOne tried to use — segment trees ? for problem E
code
210691219 I have used merge sort tree You can also solve MKTHNUM — K-th Number SPOJ LINK This concept is used in this problem
In F1 and F2 the realize that you only need to find maximum and minimum sum can create make everything much easier.
I am struggling hard to figure out what's wrong with my code for problem D.210612596 Unlike other solutions, I have only connected nodes u and v from u to v such that u < v. I am guessing that's the bug but I am not sure exactly how.
What's your logic to add edge u->v only if u < v ??
From what I thought after reading the testcases is that when an edge v1, v2 is given and v1 < v2, then that means v1 is the parent node of v2, otherwise v2 is the parent node. So I made a directed adjacency list such that adj[v] contains only the nodes which are it's children. Using this, finding the leafnodes is simple as adj[v] will be empty if v is leafnode.
"From what I thought after reading the testcases is that when an edge v1, v2 is given and v1 < v2, then that means v1 is the parent node of v2, otherwise v2 is the parent node."
That's the problem: You assumed something that wasn't guranteed in the statement. The assumption that smaller vertices are parents of larger ones is incorrect. You need to treat the given tree as a graph of undirected edges and find the parent nodes yourself (if you need them).
You can also solve F2 with HLD for the same reason, if you could not figure out (like me) how to do it with binlifts. Code: https://codeforces.me/contest/1843/submission/210677217
I'm trying the HLD approach but I'm keeping it WA at test 3, here is my submission: 210725677. Could you help me to point out where am I missing, thanks.
Hi I am curious how did you avoid stack overflow when running dfs? I tried HLD approach but still stuck at testcase 3 with Runtime error due to stack overflow
Can someone help me debug my solution for F2? https://codeforces.me/contest/1843/submission/211222013
WA on the third test (180th token)
211316049 Can anyone tell me why this code results in Exit code is-1073741571.thanks.
211316102 This code gets Accept.
An even shorter solution for C:
2*x - popcount(x)
Is this formula derived purely from observation or is there some intuition to it?
Intuition is what I used to find this solution, but it can be easily proven using basic number theory.
Can you give some hints about the intuition behind it?
Consider the contribution of each bit to the answer $$$\sum \lfloor \frac{n}{2^k} \rfloor$$$. If the $$$j$$$-th bit is set in $$$n$$$, the $$$(j-1)$$$-th bit will be set in $$$\lfloor \frac{n}{2} \rfloor$$$, the $$$(j-2)$$$-th bit will be set in $$$\lfloor \frac{n}{4} \rfloor$$$ and so on until $$$(j-j)=0$$$-th bit is set. We also know that $$$\sum_{0 \le k \le j} 2^k = 2^{j+1}-1$$$.
Putting everything together, you get $$$2 \cdot n - (\text{no. of set bits in } n)$$$.
Can anyone pls tell me why in sol for F2 the parent of LCA is also merged??
Thanks in Advanced.
Can anyone please tell why this solution gives TLE on test case 5
https://codeforces.me/contest/1843/submission/213606130
Thanks
memset(ans, -1, sizeof((ans)));
why my code works for first 4 cases but then gives different result, even though the logic is correct. code
Instead of
int
try usinglong long
, because answer may be greater than the size of int (2^31 = 2147483648) 214366788I solved E using K-th order statistics on segment. Let's sort queries by X. For each segment (let it be [l, r]) we use binary search to find all queries, laying on it. Easy to understand these queries form a segment (let this segment be [l1, r1]). Suppose K = (r-l+1) / 2 + 1 (it's the number of 1 for segment to become beautiful). Then we are to find on segment [l1, r1] the number of query, which would be on position K, if we sorted these queries by their numbers.
P.S. Yeah, you can tell me I'm sick)
when will Div3 change by not givving horrible implementation in last question They just dump it inot div3
i am stupid, i used persistence segment tree to solve E and solution of tutorial just