### Bazoka13's blog

By Bazoka13, history, 5 weeks ago,
solution
solution
solution
solution
solution
solution

• +215

 » 5 weeks ago, # |   +52 Am i only here who was too lazy to think about better solution at D1 than just writing full DSU?
•  » » 5 weeks ago, # ^ |   0 Nope :D
•  » » 5 weeks ago, # ^ |   +1 why bother writing when you have your own code library :p
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   -8 -
•  » » » » 5 weeks ago, # ^ |   -28 That's bad strategy mate. When u practice u write from scratch, when u r participating in contest u don't.
•  » » » » » 5 weeks ago, # ^ |   +1 I know, that's my failure. That's why I just got +25 to my rating after solving 4 tasks :(
•  » » » » » » 5 weeks ago, # ^ |   0 well, i did bad job at solving B, C too,I would consider it as bad contest(performance wise) but participating after one month without any practice so it was ok.
•  » » 5 weeks ago, # ^ |   -14 you werent lazy , i just copied dsu , and did some changes in code :D
•  » » 4 weeks ago, # ^ |   0 maby yes ^_^
 » 5 weeks ago, # |   +38 This was a lovely round. Thanks a lot to the problem setters (◍•ᴗ•◍)❤.
 » 5 weeks ago, # |   +74 "Mocha and Math" problem editorial: So we can set x = 0 initially. Then we iterate over the sequence and make x = x & a_i, the x is the anwser finally. Well, if we set x = 0 initially, the final result will always be 0.
•  » » 5 weeks ago, # ^ |   +17 yes, it is wrong. we can't set it 0 initially.
•  » » 5 weeks ago, # ^ |   +18 It should be "x = ~0U" in C++
•  » » » 5 weeks ago, # ^ |   0 whats that?
•  » » » » 5 weeks ago, # ^ |   0 '~' is the operator fliping every bit of an integer. For example, ~0U = 4294967295 .
•  » » » » » 5 weeks ago, # ^ |   0 Ah! ZYT!
•  » » » 5 weeks ago, # ^ |   +10 x = -1 also does the same thing.
•  » » 5 weeks ago, # ^ |   +11 We can initialize x as a[0] and then iterate from i=1 to n-1
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 Yes, we can
•  » » » 14 hours ago, # ^ |   0 Why are we doing that though ? Could not understand the solution explanation for A.
•  » » 5 weeks ago, # ^ |   0 ya it is a mistake in writing only...the code is correct
•  » » 5 weeks ago, # ^ |   0 I set it to -1
•  » » 5 weeks ago, # ^ |   0 It is now fixed; thank you!
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I just make for loop in powers of two 125988309
 » 5 weeks ago, # | ← Rev. 2 →   +44
 » 5 weeks ago, # |   +352 I have a different approach to problem D2, which is simpler in my opinion.First, try to add all edges $(1, x)$ for each $x$, after that, all nodes are in the component of node $1$ in at least one of the two trees.If they are in the same component of node $1$ in both trees, we won't add edges from that node, since all nodes are in the same component than it in at least one tree.Now we will consider nodes of two types, the ones that are in the same component than $1$ in the first tree, and the ones that are in the same component than $1$ in the second tree. We will store all nodes of type 1 in a stack $p1$, and all nodes of type $2$ in a stack $p2$, and we will try to match them with the following algorithm. If the top of $p1$ is in the same component than $1$ in both trees, delete it If the top of $p2$ is in the same component than $1$ in both trees, delete it Otherwise, add an edge between the top of $p1$ and the top of $p2$. Is possible to show that this algorithm will add the same number of edges that the one explained in D1's editorial.The complexity is almost $O(n+m)$, since the solution only uses two DSU's, and stacks.
•  » » 5 weeks ago, # ^ |   +21 My Solution is almost the same as yours, except I just maintain two pointers $p1,p2$: $p1$ is the smallest index in the same component as $1$ in first forest but not in second forest; $p2$ is the smallest index in the same component as $1$ in second forest but not in first forest. Keep adding edges $(p1,p2)$ until no edges can be added.
•  » » » 5 weeks ago, # ^ |   +18 Thanks for this approach, but one more insight will clear it further, When we have greedily added all possible edges with 1, now it is sure that if 2 nodes aren't connected in the final forest till now, then either of them must already connected to 1 in the separate graphs (126097226 line 162). This translates to fewer calculations (and clean code) in the last while loop.Instead of  while (idx1<=n && !(dsu1.is_same(1,idx1)&&!dsu2.is_same(1,idx1))) idx1++; We can just do  while (idx1<=n && dsu1.is_same(1,idx1)) idx1++; 
•  » » » » 5 weeks ago, # ^ |   0 Thanks for self-explanatory code !!
•  » » 5 weeks ago, # ^ |   +6 May I put and translate this lovely solution in my blog?I'll certainly leave the link.
•  » » » 5 weeks ago, # ^ |   +8 Sure, glad to see that you liked it.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Hey humbertoyusta, I din quite get how the stack part works... Could you pls explain it in detail ? i.e. how does taking all the elements in mocha's tree which does not belong to the same component as 1 and then randomly selecting a node from diana's forest which also dont belong to the same component as 1, works ? i.e. basically i believe even if we randomly permute the elements within each stack, it will work. Could you elaborate this part ?
•  » » » 5 weeks ago, # ^ |   +7 You just need to try to match all the nodes who are in the same component than node 1 in the first tree, with the nodes who are in the same component than node 1 in the second tree.You can do it in any order, due to the proof in D1's editorial.So you just delete nodes who are in the same component than 1 in both trees(since is impossible to add an edge from them), and try to match the rest.The way I implemented it, was maintaining two stacks, and trying to add an edge between the tops of the stacks is possible, otherwise delete the tops who are in the same component than 1 in both trees, for more detail you can check my implementation in the comment above.
•  » » » » 5 weeks ago, # ^ |   0 Yeah. Cool. Got it. Thanks
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   0 "First, try to add all edges (1,x) for each x, after that, all nodes are in the component of node 1 in at least one of the two trees."In the first graph: 1 -> 3 , 3 -> 2 and 4 is aloneIn the second graph: 1 -> 4 , 4 -> 2 and 3 is alone
•  » » » 5 weeks ago, # ^ |   0 Node 2 is in the same component than 1 in both trees, node 3 is in the same component than 1 in first tree, and node 4 is in the same component than 1 in second tree.In this case you just don't add any edge in this step since condition of every node is in the same component than 1 in at least one tree is already true.
•  » » » » 5 weeks ago, # ^ |   0 Aaaa alright, I misunderstood the sentence.
 » 5 weeks ago, # |   0 Can we solve C using a Topological sort? Tried implementing it but didn't succeed
•  » » 5 weeks ago, # ^ |   0 How would you deal with cycles?
•  » » » 5 weeks ago, # ^ |   0 I think we can keep track of the visited nodes and skip them if they've already been visited
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   +1 What if a node can be visited using 2 different paths?If you want to use topo sort, I think, we need to apply DFS for each and every node one by one...Like for(node 1->node n)DFS(node) Correct me If I am wrong.Edit: It is possible to do it using topo sort... my badTarun_19 solved it.
•  » » 5 weeks ago, # ^ |   0 Yes, we canLink
•  » » » 5 weeks ago, # ^ |   0 I tried solving this question with two approaches but both failed1) Finding the node of the first strongly connected components through which we can traverse all the node of the digraph. Code/* @author -> gamma30 */ #include #define pb push_back #define eb emplace_back #define ff first #define ss second #define endl "\n" #define EPS 1e-9 #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define forf(t,i,n) for(t i=0;i=0;i--) #define print(x) for(const auto &e: (x)) { cout< vi; typedef vector vl; typedef vector vll; typedef vector> vvi; typedef vector> vvll; typedef vector vs; typedef unordered_map umll; template T gcd(T a, T b){ if(b == 0) return a; return(gcd(b, a%b)); } template T lcm(T a, T b){ return (a / gcd(a, b)) * b; } template void swap_(T &a, T &b){ a = a^b; b = b^a; a = a^b; } template T modpow(T a, T b, T m){ if(b == 0){ return 1; } T c = modpow(a, b/2, m); c = (c * c)%m; if(b%2 == 1){ c = (c * a)%m; } return c; } void dfs(ll n, vector> &adj, vector &visited, vector &order){ visited[n] = 1; for(const auto &c: adj[n]){ if(!visited[c]){ dfs(c, adj, visited, order); } } order.pb(n); } void dfs2(ll n, vector> &adj, vector &visited, vector &ans){ visited[n] = 1; ans.pb(n); for(const auto &c: adj[n]){ if(!visited[c]){ dfs2(c, adj, visited, ans); } } } void solve(){ ll n; cin>>n; vector> adj(n+2); for(ll i=1; i>t; if(t == 0){ adj[i+1].pb(n+1); } else{ adj[n+1].pb(i+1); } } vll order, visited1(n+2, 0), visited2(n+2, 0); for(ll i=1; i<=n+1; i++){ if(!visited1[i]){ dfs(i, adj, visited1, order); } } vector ans; dfs2(order.at(order.size()-1), adj, visited2, ans); if(ans.size() != n+1){ cout<<-1<> t; while(t--){ solve(); } return 0; }  LinkHere2) After the first approach failed, i just tried brute force since the sum of n over all test cases was 10^4. So after making the graph, i ran a loop from 1 to n+1 and tried which breaks whenever we can traverse all the nodes from the chosen node. Code/* @author -> gamma30 */ #include #define pb push_back #define eb emplace_back #define ff first #define ss second #define endl "\n" #define EPS 1e-9 #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define forf(t,i,n) for(t i=0;i=0;i--) #define print(x) for(const auto &e: (x)) { cout< vi; typedef vector vl; typedef vector vll; typedef vector> vvi; typedef vector> vvll; typedef vector vs; typedef unordered_map umll; template T gcd(T a, T b){ if(b == 0) return a; return(gcd(b, a%b)); } template T lcm(T a, T b){ return (a / gcd(a, b)) * b; } template void swap_(T &a, T &b){ a = a^b; b = b^a; a = a^b; } template T modpow(T a, T b, T m){ if(b == 0){ return 1; } T c = modpow(a, b/2, m); c = (c * c)%m; if(b%2 == 1){ c = (c * a)%m; } return c; } void dfs(ll n, vector> &adj, vector &visited, vector &order){ visited[n] = 1; for(const auto &c: adj[n]){ if(!visited[c]){ dfs(c, adj, visited, order); } } order.pb(n); } void dfs2(ll n, vector> &adj, vector &visited, vector &ans){ visited[n] = 1; ans.pb(n); for(const auto &c: adj[n]){ if(!visited[c]){ dfs2(c, adj, visited, ans); } } } void solve(){ ll n; cin>>n; vector> adj(n+2); for(ll i=1; i>t; if(t == 0){ adj[i+1].pb(n+1); } else{ adj[n+1].pb(i+1); } } for(ll i=1; i<=n+1; i++){ vector visited(n+2); vector ans; dfs2(i, adj, visited, ans); if(ans.size() == n+1){ for(const auto &n: ans){ cout<> t; while(t--){ solve(); } return 0; }  LinkhereAtleast the brute force method should have passed the test cases. I still haven't figured out what is wrong with my code.
 » 5 weeks ago, # |   +15 C was essentially asking for you to print out a Hamiltonian path in a special directed graph. In contest I remembered about a blog which has a heuristic algorithm for detecting Hamiltonian paths. Not sure if its even supposed to pass....
•  » » 5 weeks ago, # ^ |   0 ORZZZZZZZZ TONY
 » 5 weeks ago, # |   +5 Slight mistake in A : we need to set x = a[0] rather than 0 .
 » 5 weeks ago, # | ← Rev. 3 →   +10 Accidentally got AC on D2 and couldn't find any similar solution 126013984Q1: Is there any test that can turn AC to TL?Q2: If not, can you give me some explanation (proof) why a and b is small enough?Explanation:1) I'm trying to connect all components with the component which contains vertex 0 2) For some vertices we obviously cannot do it. For example in test case 3 we get only 4 edges instead of 53) If we look closely on the vertices that we couldn't connect with vertex 0 there is a similarity between them. Both of them are separate components (Perhaps I unclearly express what I want to say. You can uncomment debug in my submission and look at DSUnions in the end of step 1 of explanation)4) If a = count of such vertices in graph 1 and b = same for the 2nd graph. We can try to connect them for O(a * b) I supposed that a * b is small that's why I submitted it.This solution got 1.5s which is close to time limit which means that a * b is not as small as I expected.
 » 5 weeks ago, # | ← Rev. 2 →   +65 I solve D with bitset .you can save a bitset for each component , which is the set of elements which is not in this component .when merge two components , you can simply "AND" two bitsets .But the memory is $O(n^2/w)$ . You can do a simple optimization : if the number of elements in the component is $\leq B$ , just use a vector to save all the elements . otherwise , use a bitset . Then you can consider 1,2,3...n , and check whether you can add an edge connecting i and a vertex not in the component .So the memory is $O(n*n/(w*B)+n)$.And the time complexity is $O(n*n/w+n*n/B+n*B)$,you can let B = $\sqrt n$ ,then it can pass.solution : 125997167
•  » » 4 weeks ago, # ^ |   0 If there is a valid vertex to join, then after AND operation there must be several bits left. How did you know at what positions those bits are?
•  » » » 4 weeks ago, # ^ |   0 Use _Find_fisrt and _Find_next in $O(n/w)$.
 » 5 weeks ago, # |   -38 What's the point in making 256MB memory limit in a space complexity $O(n\log n)$ problem? It's really confusing. I was afraid of MLE on system tests so I resubmitted, losing rank 1 :(Also I don't understand why E is even not rejected. It's "yet another trivial and straightforward gcd counting problem".
•  » » 5 weeks ago, # ^ |   +82 Sorry for trouble caused.In problem D2, we think that the space complexity $O(n\log n)$ isn't that large when $n\le 10^5$. My submission only uses 26700KB and among all the testers the largest memory usage is 89200KB. So we just set a standard 256MB memory limit.As for problem E, we didn't expect that it would be a trivial problem. That's why we say 'Sorry for my mistake in estimating the difficulty of problem D2 and E.' in the previous blog.
 » 5 weeks ago, # | ← Rev. 2 →   +100 As the queue is too long, I didn't know I got a WA on E until the contest finished. :(
 » 5 weeks ago, # | ← Rev. 2 →   +3 It's so sad that I got everything in E right except the last part. I didn't compute i from 1 to M but only the factors of M (cuz of some wrong thoughts when I first read the problem I saw the sum must be M instead of sum not greater than M) and I got wrong answer on sample test 3. I thought the complexity is gonna be $O(nM^2)$ if I loop i from 1 to M and forgot that for high values of i the complexity of the dp will also decrease. I can't think of solution for D2 so I skipped D1 as well to do E since I have rough idea of E but in the end I failed to complete both D and E...
 » 5 weeks ago, # |   0 A slightly alternative solution for E.We can already count the dynamics from the editorial , but we will slightly change the calculation of the answer. Let's calculate for each $i$ $(1 \leq i \leq m)$ how many different primes there are in its decomposition, and is it true that each prime number is included in the power of $1$, if not, then we will not take it into account. Then if the number includes an even number of primes, then we will take it in the answer with a plus sign, otherwise with a minus sign.Well, it works, since we just wrote the formula for inclusions of exceptions
•  » » 5 weeks ago, # ^ |   +52 This is the Mobius function, your solution is exactly the same as the editorial.
 » 5 weeks ago, # |   -40 Except for D1 it was a good contest.
 » 5 weeks ago, # |   -6 Show sympathy to those who got passed pretest in problem A and failed in system test cases by upvoting and downvote if you have passed.....
 » 5 weeks ago, # |   -55 Nice problems and bad pretests :)
 » 5 weeks ago, # |   +5 excellent Round,the statements are clear and the problems are interesting.
 » 5 weeks ago, # |   +5 my first contest in cf. Really enjoyed it even only worked out A — D1. Thanks very much for the excellent problems and answers!
 » 5 weeks ago, # |   +4 Thank You so much, from the last two questions, I will learn something new.
 » 5 weeks ago, # |   -28 Nice problem, but bad pretest :(
 » 5 weeks ago, # |   0 I think there is a typo in the solution of the first question of "Mocha and Math". I think it should be x = 1 initially instead of 0.
 » 5 weeks ago, # | ← Rev. 2 →   0 First submission for D1 during contest, WA: 126009094Post contest submission, AC after removing union by size: 126046481Can anyone tell me why this is happening?
 » 5 weeks ago, # |   0 IN Mocha and math how could i have observed that i had to iterate over all the array to minimize the maximum value??? can someone explain me.
•  » » 5 weeks ago, # ^ |   0 cause AND can't be more than the number. so just AND all
 » 5 weeks ago, # |   0 Can anyone please explain me why can't we do min_element & max_element to get the ans in problem A ?
•  » » 5 weeks ago, # ^ |   0 Consider taking the test case as 11 7 14 3 7 here the answer will be 2
•  » » » 5 weeks ago, # ^ |   0 yeah but max = 14 and min = 3 and 14 & 3 is also 2
•  » » » » 5 weeks ago, # ^ |   0 Consider taking 15 7 14 3 7 here also the answer is 2, whereas 15&3 is 3
•  » » 5 weeks ago, # ^ |   0 A bit in the answer would be ON if it is ON in all the numbers in the given array. This is because whichever two numbers are ANDed together that bit(the one ON in all the numbers) can never be made 0. Just because a bit is ON in the max_element and the min_element it doesn't mean it would be ON in the other numbers too. For eg: [15, 8, 7], 15&7 is 7, but the correct answer is 0 which is the AND of all numbers.
•  » » » 5 weeks ago, # ^ |   0 Make sense.. Thanks for the explanation.
•  » » 5 weeks ago, # ^ |   0 How about this test case: 3 7 4 3 
•  » » 5 weeks ago, # ^ |   0 Consider the array [1, 2,5] max=5, min=1 5&1 = 1 5&2 = 0 So the answer is to AND all the elements of the array i.e; 1&2&5=0 My Code: https://codeforces.cc/contest/1559/submission/125957676
•  » » 5 weeks ago, # ^ |   0 then i guess the 2nd greater element would still be greater then the bitwise and of max and min
 » 5 weeks ago, # |   0 Can somebody explain what is happening in problem A. What is the role of intervals [l,r] . Why didn' it use two pointer approach like we have to iterate from the front and back as well. Why this editorial just & every a[i] ?
 » 5 weeks ago, # |   0 What does minimize the maximum value meant? Does & operator minimize value?
•  » » 5 weeks ago, # ^ |   0 The result of performing & operator on any two numbers is always less than or equal to the minimum of the two numbers, since the bits can only turn off. "Minimise the maximum value" meant that the largest element in the array should be as less as possible, if that makes sense.
 » 5 weeks ago, # |   0 Problem E:We can compute it in O(nm) by Knapsack DP optimized by prefix-sums.Bazoka13 can you please explain how prefix-sum is used here?
•  » » 5 weeks ago, # ^ |   +8 suppose you have calculated dp[i][j] for 0<=j<=m dp[i+1][j] = dp[i][j] + dp[i][j-1] .... dp[i][j-cap[i+1]];here cap[i+1] is upper bound on variable i+1
•  » » » 5 weeks ago, # ^ |   0 Thanks can you elaborate more
•  » » 5 weeks ago, # ^ |   +21 suppose you have following task: given array $a$, and you want to do fast multiple times following action: increase value by $x$ all $a_i$ within range $[l, r]$. And after you did all those actions, you need to output resulting array $a$. This is what you need to do for this knapsack problem. dp[i][j] will store how many arrays of length $i$ have sum $j$. And, from array of length $i$ with sum $j$ you can do arrays of length $i+1$ with sums $[j+l, j+r]$. This range is where you need to add variants. And you increase them by same amount $dp[i][j]$. So, if you can increase values within range fast, you can solve this. Idea is that instead of actual values we will store array of deltas. To be precise, we will store certain array such that if you make prefix sums array from it, you'll get actual values of dp. For example, instead of storing 1,2,3,2 — values, we will store 1,1,1,-1 — deltas. Because we can calculate prefix sums array, and get 1,1+1,1+1+1,1+1+1-1 = 1,2,3,2. Now, if you increase single element of this array, prefix sums array will change all values in suffix. For example 1 2 1 -1 will give 1 3 4 3. So you can increase all values in suffix. Now you can increase within $[l, r]$ range by increasing value at $l$ so you'll increase within range $[l, \infty)$ and decrease value at $r+1$ so you'll also decrease within range $[r, \infty)$ which results into increase only within range $[l, r]$. Once all operations done, you calculate actual values by simply calculation of prefix sums, and use it as next dp[i].
•  » » » 5 weeks ago, # ^ |   0 Wow Wow Wow, what a great explanation, I know the prefix sum delta trick but I wasn't able to figure out how the dp works, you made it very very clear. Again Thanks A lot.
 » 5 weeks ago, # |   0 In the editorial for B what does following line do? s[i]=s[i-1]^('B'^'R');
•  » » 5 weeks ago, # ^ |   0 s[i-1] can be either B or R. So if it is 'R' then this expression will become 'B' or 'R' otherwise. because if we do X^X it will become 1 .
 » 5 weeks ago, # | ← Rev. 2 →   0 Video Tutorial C:https://www.youtube.com/watch?v=H8GDDIAOVdQ
 » 5 weeks ago, # |   0 Solution of problem B is not passing the given test case in problem itself.
 » 5 weeks ago, # | ← Rev. 2 →   0 Since the constraints for problem B is quite small, I have another approach in $O(N^2)$ which seems more straightforward to me.For every letter that is not a $\tt{?}$, I check whether the letter next to it is colored or not. If it isn’t colored yet, I simply paint it the opposite color of the current one. For example with the string $\tt{?R?}$, the left and the right letter is painted $\tt{B}$.If something like $\tt{B?R}$ occurs, painting $\tt{?}$ either $\tt{R}$ or $\tt{B}$ results in the imperfectness value equal to 2, so this guarantees to be the optimal solution even if I start at $\tt{B}$ or at $\tt{R}$. All to do left is to repeat that process until there is no $\tt{?}$ left in the string.
•  » » 5 weeks ago, # ^ |   0 What about B???
•  » » » 5 weeks ago, # ^ |   0 The "B" string doesn't contain any "?" so the algorithm will end immediately
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Another brute force solution is to try to color all segments of '?' using 'BRB' or 'RBR' and pick the one with the least cost. Implementation
 » 5 weeks ago, # |   0 It is possible to do 2dfs's and brute force all possible edges in one second???
 » 5 weeks ago, # |   +1 ♂That's amazing♂ contest! Enjoyed it!
 » 5 weeks ago, # | ← Rev. 2 →   0 Nvm found my mistake.
 » 5 weeks ago, # |   +4
 » 5 weeks ago, # | ← Rev. 2 →   0 In fact, Mobius function is not necessary to be used in E, as it can be solved by inclusion-exclusion principle which is similar to the original solution and easier to understand.
 » 5 weeks ago, # |   0 [Problem D1] I dont understand why if we connect random two edge will get the best result.
•  » » 4 weeks ago, # ^ |   0 Firstly, you can't connect nodes if they are in the same tree because so you get a cycle. So the only way of adding edges is connecting trees. If you have two trees, you can connect it by adding only one edge because if you add more you get a cycle. And it doesn't matter what nodes you choose. So the best result you can get by iterating over nodes and checking if they are not in the same tree (in both forests). If so, you connect them.Hope its helpful
 » 5 weeks ago, # |   0 In the E's editorial It's mentioned that We can compute it(the number of integers satisfying only the two conditions as mentioned) in O(nM) by Knapsack DP optimized by prefix-sums. I am unable to figure this part. Can anyone help?
•  » » 5 weeks ago, # ^ |   +5 We want to compute the number of arrays with gcd dividing $g$. Therefore, we are only allowed to have numbers $i\cdot g$, for $1 \le i \le \lfloor \frac{m}{g} \rfloor$. The sum of numbers in the array is also a multiple of $g$. From each range $[L, R]$ we are only allowed to have numbers $i \cdot g$, where $\lceil \frac{L}{g} \rceil \le i \le \lfloor \frac{R}{g} \rfloor$. Therefore, each segment $[L, R]$ can be transformed into a segment $[\lceil \frac{L}{g} \rceil, \lfloor \frac{R}{g} \rfloor ]$. Consider $knapsack[k][j]$ — the number of ways to get sum $j \cdot g$ from the first $k$ elements. When we add a new element $a_{i+1}$ with the possible range $[\lceil \frac{L}{g} \rceil, \lfloor \frac{R}{g} \rfloor ]$, we can see that the state $knapsack[i][j]$ contributes to states starting from $knapsack[i+1][j + \lceil \frac{L}{g} \rceil]$ and ending with the $knapsack[i+1][j + \lfloor \frac{R}{g} \rfloor]$, so we need to add value $knapsack[i][j]$ to some segment of $knapsack[i+1]$. We can do this with the difference array technique (see https://codeforces.cc/blog/entry/88474?locale=en ). So we compute $knapsack[i+1]$ as a difference array, and then at the next step we compute prefix sums of this array to get the actual values of $knapsack[i+1]$ and proceed to computing $knapsack[i+2]$. Note that, as always, we can only store two layers. See my code for more details: https://codeforces.cc/contest/1559/submission/126027569
•  » » 5 weeks ago, # ^ |   0 Another approach for the knapsack DP part is to treat it as a problem of multiplying polynomials. For the case where we want sequences of gcd >= 1 the polynomial of the interval $[l_{i}, r_{i}]$ is $x^{l_{i}} + x^{l_{i}+1} + \ldots + x^{r_{i}}$. To get the number of sequences where the gcd>=1 and the sum <= m you multiply all these polynomials and sum the coefficients of the terms for powers <= $x^{m}$. You can try doing this with NTT but it's too slow. The key observation is $x^{l_{i}} + x^{l_{i}+1} + \ldots + x^{r_{i}} = \frac{x^{l_{i}}-x^{r_{i}+1}}{1-x}$ This means if you have the current polynomial $p(x)$ and you want multiply by the polynomial for $[l_{i}, r_{i}]$ you can do it in $O(m)$ by multiplying by $x^{l_{i}}-x^{r_{i}+1}$ then dividing by $1-x$. The case where you want gcd>=g is the same but you replace the interval $[l_{i}, r_{i}]$ with $[\lceil l_{i}/g \rceil, \lfloor r_{i}/g \rfloor]$ and $m$ with $\lfloor m/g \rfloor$. 126171468
 » 5 weeks ago, # |   -33 my solution for 1559B import java.util.Scanner;public class bsoln { public static void main(String[] args) { Scanner scn = new Scanner(System.in); int t = scn.nextInt(); for (int i = 0; i < t; i++) { int N = scn.nextInt(); String s = scn.next(); if (s.length() == 1) { if (s.charAt(0) == '?') { s = "B"; } } else { for (int j = 0; j < s.length(); j++) { if (j == 0) { if (s.charAt(j) == '?') { if (s.charAt(j + 1) == 'R') { s = s.substring(0, j) + "B" + s.substring(j + 1); } if (s.charAt(j + 1) == 'B') { s = s.substring(0, j) + "R" + s.substring(j + 1); } else { s = s.substring(0, j) + "B" + s.substring(j + 1); } } } if (j == s.length() - 1) { if (s.charAt(j) == '?') { if (s.charAt(j - 1) == 'R') { s = s.substring(0, j) + "B" + s.substring(j + 1); } if (s.charAt(j - 1) == 'B') { s = s.substring(0, j) + "R" + s.substring(j + 1); } else { s = s.substring(0, j) + "B" + s.substring(j + 1); } } } else if (s.charAt(j) == 'R' || s.charAt(j) == 'B') { continue; } else if (s.charAt(j) == '?') { if (s.charAt(j + 1) == 'R' || s.charAt(j - 1) == 'R') { s = s.substring(0, j) + "B" + s.substring(j + 1); } if (s.charAt(j + 1) == 'B' || s.charAt(j - 1) == 'B') { s = s.substring(0, j) + "R" + s.substring(j + 1); } else { s = s.substring(0, j) + "B" + s.substring(j + 1); } } } } System.out.println(s); } } } Can anyone tell me whats my mistake as its showing wrong answer in testcase2
 » 5 weeks ago, # |   +21 Any proof in D1 that this is sufficient ? merging each possible two trees when they're not already merged in the other graph (Diana's) how can we be sure that working like this greedily will not affect the next step badly ?
•  » » 5 weeks ago, # ^ |   0 You always have the option to connect two nodes if none of the two forests is a tree. The proof is in the tutorial: TutorialIn the final situation, if one forest has more than one tree, we choose two trees from it, such as tree A and tree B. Then we consider node a in A and node b in B, they must be connected in another forest. We can easily find node b is connected with all the nodes in A and node a is connected with all the nodes in B. So nodes in A and B are in the same tree in another forest. If we consider other trees, we can get the same conclusion. Hence nodes in another forest form only one tree.So if you can't find two nodes to merge, that means you achieved the optimal answer.
•  » » » 5 weeks ago, # ^ |   0 So for like two trees A,B... no matter how many ways there are to merge them their case is totally independent from everything will happen in later steps in other trees but why exactly ? the tutorial doesn't explain this point clearly
•  » » » » 5 weeks ago, # ^ |   +3 Let say $a$ and $b$ is number of components in corresponding forests. Each time you add edge, number of components in both forest decrease by one, no matter which edge you pick. So, after first edge, number of components is $a-1$ and $b-1$, after second edge $a-2$ and $b-2$. Then after you add $min(a, b) - 1$ edges you will get tree.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Although which edge you pick may affect later options, it won't make your answer worse. The tutorial proved that if you can't find an edge to add, one of the forests is always a tree. Obviously, if one forest becomes a tree, it is the optimal answer.So you can greedily add any edge you can add until you can't add any more. And when you can't add an edge, you achieved the optimal answer.
 » 5 weeks ago, # | ← Rev. 2 →   +22 Alternative solution for 1559D2 - Mocha and Diana (Hard Version). wall of textConsider following question. How to find for fixed vertex $v$ all vertices $u$ which if you add this single edge both graphs will not have any cycles. In first graph $u$ should not be connected to $v$. In second graph it also should not be connected to $v$. Lets do dfs from $v$ in first graph and mark all vertices reachable from $v$ in first graph. Similarly, lets do dfs from $v$ in second graph. Now, you can connect $v$ to $u$ if $u$ is not marked in both graphs. Lets make array $c$ which will store in how many graphs we marked vertex. So $c_v$ would be 2 if vertex $v$ was marked in both graphs and $c_v$ would be 0 if vertex $v$ was not marked at all. With this array filled correctly, we can tell that any vertex $u$ with $c_u = 0$ can be connected with edge $(v, u)$.Now, following algorithm: for each vertex $v$ from $1$ to $n$ fill $c$ (mark vertices) then find any single zero, add single corresponding edge, and repeat, while there is zero. If there is no zero, continue with next vertex. This will work in $O(n^2)$ time because for each vertex we run two dfs in $O(n)$, which is $O(n^2)$, and also we can add at most $n$ edges which results into additional $2n$ dfs, so total time complexity is $O(n^2+2\cdot n^2)$ which is $O(n^2)$. Note: I didn't prove here that it will give optimal answer.Notice, that when you add edge and refill marks with same $v$ you just add additional marks for additional components in both graphs. Instead of clearing all marks, you can just add those which appeared caused by new edge. Using this observation, we can add as many edges for single vertex $v$ in $O(n)$ time, because we can't mark more vertices than whole graph. Trouble is: what to do when we need to continue to next $v$? It may be in other component and we would need to refill $c$ from scratch.The idea is following: we can walk along all vertices in single component in first graph, and when we add edge, we can just add vertices in queue of this walk. Then we would not need to clear all marks in first graph until we finish walking in whole component. But then, we still need to redo dfs in second graph each time we change $v$ (which is within component of first graph). I didn't tell how can we fast get index of 0 in $c$. We can maintain two sets: $s0$ with indices of zeroes in $c$ and $s1$ with indices of non-zeroes. And each time we change $c$, move index from one set into another accordingly. Then, when we need to get index of 0 we can pick any number from $s0$.Next key observation, is that when we do dfs in second graph from vertex $v$, we mark some of vertices from component of first graph, and when we reach them, for example some vertex $w$, we will try to mark same component from second graph again, it will be exactly same component filled from vertex $v$, but we tried this already when we did dfs from $v$, and if there was any zero, we would add edge, thus there won't be zero, and we don't have to spend any time, just skip it. In other words, while walking in component of first graph, we should maintain visited vertex in second graph separately with marks in second graph. And as soon as we want to run dfs in second graph from visited vertex in second graph — it won't give any result so just ignore it. After this change, we will have running time $O(n \log n)$ for single component of first graph, including all added edges we find.Remaining issue: components of first graph with added edges can be multiple. Last key observation: we don't need to check any other components. First component is enough. We can prove it by contradiction. Suppose there is edge we didn't add because it connects two vertices $(u, v)$, and both $u$ and $v$ is not in component of first graph we checked. Then, there is component of u in first and second graph, and component of v in first and second graph. All those four components should be different to be able to add $(u, v)$. Then, pick any vertex $w$ from component that we was checking in first graph. We can add $(w, u)$ or $(w, v)$ edge. Because in first graph $u, v, w$ are disjoint, and in second graph, $w$ can be reachable either from $u$ or from $v$, so we can add edge to unreachable in second graph. Contradiction with assumption that we didn't find. So, we said that single component of first graph is checked in $O(n \log n)$, and we now proved that we only need to check single component, so this solution run time is $O(n \log n)$. My messy implementation: 126065463Python cleaned version: 126093423 Forgot to mention above: when join with visited in second graph we should also stop checking v.
•  » » 5 weeks ago, # ^ |   0 MikeMirzayanov, can we have a feature to favorite comments as well. Some comments like this are indeed insightful and helpful as some problems and blogs as well.
•  » » » 5 weeks ago, # ^ |   +3 It's already present, you can see the star outline(beside the link to comment(#) option). Click on it.
 » 5 weeks ago, # |   0 Should this submission for 1559D2 - Mocha and Diana (Hard Version) be accepted? 126011074What it does is similar to choosing one component in each graph randomly and connecting them if possible each time, and repeating the process until it reaches 1.8s.After changing it to trying for only 2n times, it also passes the tests. 126093360If the random part works well, is this a submission that can be hacked or a good solution that proves to be correct most of the time? (I think maybe it's a good solution because of m << 100000^2)
 » 5 weeks ago, # |   +27 Even simpler solution for D:If vertices $u_1$ and $v_1$ belong to different trees in Mocha's forest and vertices $u_2$ and $v_2$ belong to different trees in Diana's forest then one of 6 edges between $u_1, v_1, u_2, v_2$ can be added. It's pretty easy to prove and we also don't even care if some of them are equal. Now just keep a vertex for every tree in both forests and do this until you only have one tree in one of the forests.
•  » » 5 weeks ago, # ^ |   0 Could you explain your solution a bit more? Obviously adding edges in u1 to u2/v2 i.e. across Diana's and Mocha's forest doesn't make sense.
•  » » » 5 weeks ago, # ^ |   +13 It does!If $u_1$ and $v_1$ belong to the same tree in Diana's forest (otherwise pair $(u_1, v_1)$ works) then either $u_2$ or $v_2$ is from a different tree from these two. Let's say it's $v_2$. Then both pairs $(u_1, v_2)$ and $(v_1, v_2)$ are from different trees in Diana's forest and at least one of them is from different trees in Mocha's forest as well since $v_2$ is the same in both pairs but $u_1$ and $v_1$ are from different trees.
 » 5 weeks ago, # |   +9 I have better E solution. It is pretty similar to editorial, but it doesn't use Möbius function and easier to understand.Let $f(k)$ be number of sets of integers, which are bounded($l_i \leqslant a_i \leqslant r_i$ for all $i$) and sum of $a_i$ doesn't exceed $M$ and also for all $i$, $a_i$ must be divisible by $k$. It can be calculated with DP for $O\left(n\frac{M}{k}\right)$ time and $O\left(\frac{M}{k}\right)$ space as in editorial.So calculating $f(i)$ for all $1 \leqslant i \leqslant m$ will take $O(nM \log M)$ time.Let $d(k)$ be defined like $f(k)$, but instead of condition "for all $i$, $k \mid a_i$" we use condition "gcd of all numbers is $k$". Thus by definition, answer is $d(1)$.Also it is clear, that $d(i) = f(i) - (d(2i) + d(3i) + \ldots)$, hence all $d(i)$ can be calculated by this formula for $O(M \log M$) because of harmonic series.Submission using this solution: 126092551
 » 5 weeks ago, # |   0 Kudos to person who set the C problem: Scary but easy. A & B were also very good.
 » 5 weeks ago, # |   0 Is the complexity of D1 O(n^2) or O(n^2 * log n) ?
 » 5 weeks ago, # |   0 I tried implementing D1 solution after reading editorial, but my solution is getting TLE. Can someone explain to me why does my solution is giving TLE but editorial not.The only difference is that I used while loop instead of recursive function (getf)here is my code
 » 5 weeks ago, # |   0 the minimal value of the maximum value in the sequence. ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Please any explanation for this sentence I couldn't understand it
•  » » 4 weeks ago, # ^ |   0 +1
 » 5 weeks ago, # |   0 In problem D2, can someone explain the this line about the time complexity," This is because an element moves to a new row/column O(logn) times and each move is O(logn) time (using STL set in cpp)" with respect to the operations that are happening. I understood the operations above but not able to figure out the time complexity. To me, it seems more like O(logn)+O(logn).
•  » » 4 weeks ago, # ^ | ← Rev. 4 →   0 I think , in a row there can be at most n elements to merge, and each element is merged logn times max, as rows are merged by size (DSU by rank logic) and logn to insert in set each time. so for 1 element (logn)^2 , for n elements n*(logn)^2.
 » 5 weeks ago, # |   0 Can someone explain the xor part in B given in the editorial?
•  » » 5 weeks ago, # ^ |   0 That's simple dude its just getting the opposite character from the one present there already from B and R
 » 5 weeks ago, # |   0 Unable to understand the code given in D1 can anyone help ??
•  » » 5 weeks ago, # ^ | ← Rev. 4 →   0 To detect whether connecting two vertices is possible (there will be no cycle after connection) we can use DSU (disjoint set union, tutorial). Now we assume that for each vertex A and B we know whether we can connect them or not. Just try to brutforce all pairs of vectices. If connection of two vectices in both forests wouldnt create a cycle add new edge. Example of code: 126156817. Hope this will help you. Good luck :)
 » 5 weeks ago, # |   +6 Can someone please explain why $\sum_{d|gcd(a_1,a_2,...,a_n)}\mu(d) = \sum_{d|a_1,d|a_2,...,d|a_n}\mu(d)$ ? Couldn't wrap around my monke brain :(
•  » » 5 weeks ago, # ^ |   +5 d is a divisor of $gcd(a_1,a_2,...,a_n)$, so d is also a divisor of $a_1$ and $a_2$ ...
•  » » » 5 weeks ago, # ^ |   0 But the righthand also includes divisors that aren't divisors of $gcd(a_1,a_2,...,a_n)$, do they cancel each other out?
 » 5 weeks ago, # |   0 Can someone help me explain this from problem Bs[i]=s[i-1]^('B'^'R');  What does 'B'^'R' return?? ouput of 'B'^'R' is not showing when I run it in c++.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 s[i]=s[i-1]^('B'^'R') basically turns s[i] depending upon the value of s[i-1]. If s[i-1] is 'B', s[i] changes to 'R' and if s[i-1] is 'R', s[i] changes to 'B'.
•  » » 4 weeks ago, # ^ |   0 'B', 'R' in C++ is number equal to ASCII code of symbol. It basically means that char is also integer in C++, it just has fewer bytes and narrow range. You should also know that (x^y)^z = x^(y^z). This is basic property of XOR. It's easy to prove by considering bits separately. Then, feed 'B' into formula you get 'B'^('B'^'R') = ('B'^'B')^'R' = 0^'R' = 'R'. Also, you should know that x^y = y^x, so if you feed 'R' into formula you get 'R'^('B'^'R') = ('B'^'R')^'R' = 'B'^('R'^'R')='B'^0='B'`
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 @r57shell Thank you so much; you explained so nicely it literally cleared all the doubts. Also, may I know how one can think towards using a xor in these types of questions.
•  » » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 Looking up properties of XOR can yield all the above mentioned stuff. This maybe useful "Save yourself a register" at https://accu.org/journals/overload/20/109/lewin_1915/
•  » » » » » 2 weeks ago, # ^ |   0 thanks, akshpan appreciated
 » 5 weeks ago, # | ← Rev. 2 →   0 i was trying to solve d1 using union find, that is, i pick 2 nodes i and j, if they share same parent in the first forest or the second forest, we can't make this connection, because then we would be forming a loop, else, make that connection, make node j have same root as node iwas my approach wrong?
•  » » 4 weeks ago, # ^ |   +8 DSU doesn't work like this. If you want to join two sets that have nodes $i$ and $j$, you have to find the leaders (roots) of each set and update their parents, not for $i$ and $j$.
•  » » » 4 weeks ago, # ^ |   0 you are right, i already knew this, this is a crucial implementation detail i forgot for some reason when i was writing the solution, thanks
 » 4 weeks ago, # |   +8 Problem E can be solved in $O(m \log^2 m \log n)$ if $l_i$ and $r_i$ are constant in each case.
•  » » 4 weeks ago, # ^ |   0 How
 » 3 weeks ago, # |   0 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) Please explain me brothers what does this mean?
•  » » 3 weeks ago, # ^ |   0 Just use it as it is, it makes input/output operations faster, which results in faster runtime. Just use it without knowing what is it(abstraction) and believing it does ur job!!
•  » » » 3 weeks ago, # ^ |   0 Thanku my friend. ;)
 » 2 weeks ago, # |   0 Can anyone please explain why Topological sort doesn't work on 1559C. I am not able to think any test case where it doesn't work.
 » 4 days ago, # |   0 Can anyone provide a more elaborative solution to problem B (Mocha and Red and Blue)?