### exhausted's blog

By exhausted, history, 2 months ago, translation,

author: exhausted, developer: exhausted

1946A - Median of an Array

Editorial
Solution

author: max0000561, developer: yunetive29

1946B - Maximum Sum

Editorial
Solution

author: exhausted, developer: exhausted

1946C - Tree Cutting

Editorial
Solution

author: azureglow, developer: azureglow

Editorial
Solution
Solution (74TrAkToR)

author: yunetive29, developer: yunetive29

1946E - Girl Permutation

Editorial
Solution

author: exhausted, yunetive29, developer: exhausted, yunetive29

1946F - Nobody is needed

Editorial
Solution
• +147

 » 2 months ago, # | ← Rev. 2 →   +143 For C, why is there an entire paragraph discussing why rerooting doesn't affect the answer, but no discussion on why the greedy algorithm is optimal?BTW, I created video editorial for D: Birthday Gift.
•  » » 2 months ago, # ^ |   +2 With fixed x you want to maximize number of edges to remove. Consider lowest subtree with >= x vertices, if we dont cut edge right up this subtree, we can move closest edge from top and answer won't get worse
•  » » » 2 months ago, # ^ |   +4 But when you when you disconnect a subtree with its parent, how do you make sure its parent's component still has more than x vertices?We are trying to make as many cuts as possible only considering the current subtree, but we do nothing to ensure the parent still has x or more. What am I missing?
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 once there is a subtree with more than x points,you count it as a connected component and cut the connection with the subtree and it's father.it is shown that if the connected component which include the root maybe has x-less points.but it wasn't counted before.you just need to think it as add a edge which was cuttted before from this connected component to others.it won't affect the counting number.
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   +1 so essentially, for a fixed x, and number of cuts k, you want k + 1 components whose size >= x. If you have 3 components, what's left of the chopped up parent can just be added to the components we just made
•  » » » » 2 months ago, # ^ |   0 same doubt and also should we not have to check for k+1 connected components? as if we remove k edges , no. of connected components will be k+1 if i'm not wrong...
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Yeah, but I think the idea is that when you're running the algorithm, you're not guaranteeing that the connected component containing the root node has size of at least x. So, if you remove k edges, you get k+1 connected components, but for one of them you can just connect it back to the component with the root node, giving you k connected components. That way it's unnecessary to check whether the component with the root node has size at least x.
•  » » » » 2 months ago, # ^ |   0 we will remove the subtree sizes which we have cut already so that way will not count the removed subtree and after that we just check wether the component of which has root have the size greater that >= x its okay otherwise we have to make 1 less cut. you can check this, code for referencevector< int > sz ; int cnt = 0 ; void dfs( vectorg[] , int m , int u , int p ) { sz[u] = 1; for( auto v : g[u] ) { if( v != p ) { dfs( g , m , v , u ); sz[u] += sz[v] ; if( sz[v] >= m ){ sz[u] -= sz[v] ; cnt++; } } } } bool ok( vectorg[] , int m , int k , int N ) { cnt = 0 ; sz.assign( N , 0 ); dfs( g , m , 0 , -1 ) ; if( sz[0] < m ) cnt-- ; return cnt >= k ; } 
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 Why is there a need to decrease cnt if the root node has a size less than m? cnt is incremented only if we have gotten a size greater than m. So we never had an extra number in cnt. I do not understand the need to decrease it
•  » » » » » » 2 months ago, # ^ |   0 Consider this case. n = 7, k = 3 1 2 2 3 1 4 4 5 1 6 6 7To my understanding, the algorithm will cut edges (1, 2), (1, 4) and (1, 6). The cnt guarantees [0, cnt-1] cuts are possible, not exactly cnt cuts because it depends on the last group (root group) we made if its size >= particular x we are checking. You can try adding extra edge like (1, 8) and see what happens.
•  » » » » » » 2 months ago, # ^ | ← Rev. 3 →   0 root_comp_size < m all other comp size >= m so to make the root_comp also have size >= m , we can merge any adjacent other component to do that we need to remove 1 cut, which is what we did
•  » » » » 2 months ago, # ^ |   0 I am just proving that it's optimal, like if we consider best way to choose edges, we can move edge lower, while subtree size is >= x. About algorithm of checking, of course we root a tree, then do this greedy, and we just need to check in the end that root component size is >= x, if not, then we can remove only 1 edge, cause all other comps are of size >= x
•  » » » » 2 months ago, # ^ |   +1 Just noting down my understanding if anyone is still confused about this:There are really only two cases to think about If the root component has at least x vertices If the root component has less than x vertices In the first case, it is straight forward. We simply have to check if we have at least k + 1 components, since making k cuts would lead to k + 1 components.In the second case, it is a bit of a think. As per most implementations, if we have less than x vertices, we have not added this component to our count of components yet. So we must increment this count by 1. But since we have less than x vertices, we also want to re-unite this component with another (that already has at least x vertices, which is why it had gotten disconnected in the first place). So we must also decrement the component count by 1. So ultimately, our component count remains the same, and we simply want to check if we have at least k + 1 components, for the same reason that making k cuts would lead to k + 1 components. Ref [C++ clean]: https://mirror.codeforces.com/contest/1946/submission/252842752
•  » » 2 months ago, # ^ |   0 During up-solving I found BFS thoughts more intuitive, if you consider from last level (leaf nodes) and then go upwards. I realised that the only way to break subtree optimally was the one that is mentioned in editorial. Though I couldn't implement BFS solution
•  » » » 2 months ago, # ^ |   0
•  » » » » 2 months ago, # ^ |   0 Thank you very much!
•  » » 2 months ago, # ^ |   -12 C editorial is fucking trash
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +1 btw I dont know how C have 4k submissions in contest time, I waste ~4-5 hours for it
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 even after reading editorial lol
•  » » » » » 2 months ago, # ^ |   +5
•  » » 2 months ago, # ^ |   +5 problem C mega sexy... during contest it just gave my skills a serious reality check
 » 2 months ago, # |   0 Nice editorial . Really liked Problem C and D .
 » 2 months ago, # |   -6 I see at least two things gone horribly wrong for this round:A: Okay, this should probably seem like a nitpick for non-problemsetters, but you should have let $\mathcal{O}(n^2)$ pass for the position. Why exactly? Because this is a damn rule. Didn't KAN remind you? the rule in questionF: Who even decided $\mathcal{O}(n \log^2 n)$ intended with $n=10^6$ was a good idea? Why? What led you to think so?
•  » » 2 months ago, # ^ | ← Rev. 3 →   0 I don't see why my code is wrong for https://mirror.codeforces.com/contest/1946/submission/252819046 but keep getting "wrong answer on pretest 2 expected 12 but got 19 in 3096th number or so". Can you check my python submission in my history? It seems (exactly same idea) similar to a solution I found which was accepted.
•  » » » 2 months ago, # ^ |   0 The median will not always be the ceil[n/2]-1 position. It will be only for even number of elements. For odd number of elements , you don't need to do the -1
•  » » » 2 months ago, # ^ |   +3 idk why you're asking me, but ceil(n/2) is a very bad idea. always use integer arithmetics for these use cases, like (n+1)//2 for ceil (replace // with integer floor division in your language).
•  » » » » 2 months ago, # ^ |   0 It doesn't explain this though:(accepted solution): https://mirror.codeforces.com/contest/1946/submission/252819115 (wrong solution but same as above): https://mirror.codeforces.com/contest/1946/submission/252819046
•  » » » 2 months ago, # ^ |   0 I looked at your solution and honestly I have no idea why it's wrong.
•  » » » » 2 months ago, # ^ |   0 What's even stranger is that these two identical solutions (one is placed inside a function) works, but if not inside a function, it doesn't work? I don't know if .split(" ") makes it process data wrong?(accepted solution): https://mirror.codeforces.com/contest/1946/submission/252819115 (wrong solution but same as above): https://mirror.codeforces.com/contest/1946/submission/252819046
•  » » » » » 2 months ago, # ^ |   0 oh well, input().split() is a list of strings. if you sort a list of strings it will be sorted in the lexicographical order, which is definitely undesired behaviour. Notice that $\texttt{"1000"}<\texttt{"2"}$ holds in lexicographical order.
•  » » » » » » 2 months ago, # ^ |   0 Nice! I missed that. Mystery solved.
•  » » 2 months ago, # ^ |   0 $\mathcal{O}(n \log^2 n)$ isn't that bad for $n = 10^6$ especially when you aren't doing heavy stuff with sets or segment trees, and the TL is 6 seconds. Personally, my solution passed pretty close to time limit though, but as I said in a previous comment, they probably wanted to cut $n \log^3 n$ solution.
•  » » » 2 months ago, # ^ |   +1 But $n=2 \times 10^5$ is more than enough to cut most $\mathcal{O}(n\log^3 n)$ solutions of any constant? I mean the single $\log n$ is already dozen times the difference, I can't see why would they fail to block a slower solution with $n=2 \times 10^5$. Unless they wanted to block an $\mathcal{O}(n\sqrt n)$ solution, which doesn't look like a very good decision after all if that solution doesn't make the task much easier to solve.
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 I see your point. They could have reduced both the limits and TL in order to make $n \log^2 n$ pass comfortably enough.
•  » » » » » 2 months ago, # ^ |   +3 Oh, also another thing. I think the tight TL makes Python / Java solutions almost impossible to pass (evidenced by the fact that there are no AC Python or Java solutions yet, even in practice mode).
•  » » » » 2 months ago, # ^ |   0 Two of the logarithms are from fenwick and harmonic series, so they are smaller than usual log
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   +3 Why would that make a difference? The difference between $\log_2 x$ and $\ln x$ is constant, i.e. $1/\ln(2) \approx 1.44$ times, which suggests that it shouldn't be that much smaller than the usual log. Also, what makes you think Fenwick must have a smaller constant? Though it is hard to admit it, many sources suggest that the Fenwick tree's speed is on par with a well-written bottom-up segment tree. If their intention is to let Fenwick tree pass and block segment trees, wouldn't that be one of the most stupid decisions ever?
•  » » » » » » 2 months ago, # ^ |   +5 I wrote the same solution with a bottom up segment tree (253203142) and with a fenwick tree (253207869).The solution with the fenwick tree got AC in ~5000 ms while the one with the segment tree got TLE 12.In my opinion it's better to let $O(n\log^3n)$ solutions pass rather than cutting off some $O(n\log^2n)$ solutions because of the constant factor.
•  » » 2 months ago, # ^ |   0 Thanks to this, I uphacked all solutions with Arrays.sort((primitive type)[]) without randomization I found written in Java 8, not sure Java 21 can be hacked too
•  » » » 7 weeks ago, # ^ |   0 what us hacking and how to hack?
•  » » » » 7 weeks ago, # ^ |   0 Uphacking is available only for 1900+ rated users, see https://mirror.codeforces.com/blog/entry/68204
•  » » » » » 7 weeks ago, # ^ |   0 okay thanks
•  » » 2 months ago, # ^ |   0 How is problem A $\mathcal{O}(n \log^2 n)$? It's clearly $\mathcal{O}(n \log n)$ per test case. 252755171
•  » » » 2 months ago, # ^ |   +7 sir I wrote $\mathcal{O}(n \log^2 n)$ for F not A
•  » » » » 2 months ago, # ^ |   0 I'm sorry, I didn't notice that "F" :(
•  » » 2 months ago, # ^ |   0 Where are these rules mentioned? Like the one you've mentioned in the spoiler.
•  » » » 2 months ago, # ^ |   0 There is a document titled "Polygon advices", which starts with a huge text stating "IF YOU ARE TO PREPARE A ROUND ON CODEFORCES, THESE ARE RULES. FOLLOW THEM AS CLOSE AS YOU CAN". I do not know if I am allowed to disclose further; ask KAN for details.
 » 2 months ago, # |   0 https://mirror.codeforces.com/contest/1946/submission/252802394Can anyone help find the test case for which my code is wrong? Also whats wrong in the approach
•  » » 2 months ago, # ^ |   +9 Greedily creating segments, left to right, in such a fashion might be wrong.It would fail for the following test case Spoiler5 2 1 3 0 0 2 Expected: 4 Your code outputs 2. It tries to group [1],[3,0,0,2] instead of [1,3],[0],[0],[2]
•  » » » 2 months ago, # ^ |   0 Thank you.
 » 2 months ago, # |   0 Problem E is just liitle modification of past problem. Not new.
•  » » 2 months ago, # ^ |   0 Could you give me the past problem
 » 2 months ago, # |   0 Can somebody please explain why the solution of the problem F works in $O(N\log^2(N))$?
•  » » 2 months ago, # ^ |   0 There are $O(N\log^2(N))$ pairs of $(a,b,c)$ such that $a | b$ and $b |c$ and $a < b < c$.
•  » » » 2 months ago, # ^ |   0 Can you please provide a proof for this statement?
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +30 What we need is $\sum \sum N/i/j$ for $1 \le i \le N$, $1 \le j \le N$$\sum 1/i is \log N for 1 \le i \le N$$\sum 1/j$ is $\log N$ for $1 \le j \le N$ $\sum \sum N/i/j$ can be written as $N (\sum 1/i) * (\sum 1/j)$ for $1 \le i \le N$, $1 \le j \le N$ This leads to $O(N*log^2N)$ upper bound on no of such pairs.
•  » » » » 2 months ago, # ^ |   +17 Fix $a$. Now the number of pairs of $(b,c)$ that satisfy $a •  » » » » » 2 months ago, # ^ | 0 Hi, could you explain more about the sum (1 / i) part? Is that the part of counting Cs when fixing a and b?  » 2 months ago, # | ← Rev. 2 → 0 Why haven't you provided your code along with the editorial ? If I am not able to implement any solution provided above, should I go through all the submissions of users and try to find out which user has solved the problem according to approach described in the editorial ? •  » » 2 months ago, # ^ | +6 added  » 2 months ago, # | +7 i can t understand the C solution , can u guys suggest me a similar classic problem? , to understand the idea ? •  » » 2 months ago, # ^ | ← Rev. 2 → 0 this is the closest thing I could find, should help with understanding the checker for binary search •  » » » 2 months ago, # ^ | 0 thanks bro  » 2 months ago, # | 0 Hi, for problem C I can't understand why if we have at least k+1 vertices with at least x vertices in its subtrees our condition is resolved. Can anyone explain it briefly? •  » » 2 months ago, # ^ | ← Rev. 2 → 0 Because if we can get more than k+1 components then we would merge some components to make number of components to be exact k+1 and in doing so the size of final merged components would still remain>=x(since the size would only increase) and so the condition is still satisfied •  » » » 2 months ago, # ^ | 0 I think that the question told us that we should omit exactly k edges and after that, we should have at least x nodes in each remaining component but this solution is for situations where we want to only omit one edge and after that, we want to have at least x nodes in each remaining component. Am I right or does this solution support the first situation too? •  » » » » 2 months ago, # ^ | 0 the solution tells us to omit as many edges as possible ensuring that each component has size>=x  » 2 months ago, # | 0 For problem C, If I do a recursive dfs, it gives TLE(Python). Can someone who solved in python tell me how to get around this? I would appreciate it a lot. Thank you •  » » 2 months ago, # ^ | 0 can't get around this  » 2 months ago, # | 0 wish i read D first •  » » 2 months ago, # ^ | 0 D was much harder I think.  » 2 months ago, # | +1 High quality editorial!  » 2 months ago, # | +8 In problem E I think it should be nCr[(pm1)-2,p(m1-1)-1] since position of pm1 and (pm1)-1 both are fixed.Because we have (pm1)-1 element and maximum element out of this is automatically at p(m1-1)th position. •  » » 2 months ago, # ^ | +5 thanks! fixed  » 2 months ago, # | +20 Here is my stream discussin these problemsMy contest screencast see it if you want to know what I was doing in the contest. •  » » 2 months ago, # ^ | 0 Sir can you explain In problem D why we will count no of submasks present in an array.Basically I didn't understand the getmaxlength() function •  » » » 2 months ago, # ^ | ← Rev. 2 → 0 Initially, I misread the problem and tried to solve different version.We dont need getmaxlength() function. The submission 252805024 that got AC did not even have this.Disclaimer: This comment assumes you have watched the stream and uses some of the definitions mentined in the stream. The crucial idea is -Lets say we want to find no of maximum partitions such that on(pref[0]^pref[i])|(pref[i]^pref[j])|(pref[j]^pref[k])|(pref[k]^pref[n]) = M Notice that pref[0]=0, so pref[i] should be submask of M.Now lets look at pref[i]^pref[j], we want it to be submask of M.So all the bits that are 0 in M, should be 0 in pref[i]^pref[j].If kth bit in pref[i]^pref[j] is 0, if kth bit of both pref[i] and pref[j] are same.Now, because all pref[i] is submask of M, so any bit that is 0 in M will also be 0 in pref[i].Because for any bit that is 0 in M should be same for both pref[i] and pref[j], we have a condition that any bit that is 0 in M should also be 0 in pref[j].Now, this is the definition of submask. We have reached a conclusion that pref[j] should be submask of M. Now, we can use the same reasoning to get pref[k] should be submask of M too. So on for all pref[*] we need. Then the idea was we do not have to bruteforces X submasks, we can get it done using logX different submasks. •  » » » » 6 weeks ago, # ^ | +5 neat! •  » » 2 months ago, # ^ | ← Rev. 2 → 0 in problem a given solution yields output 1 for input of 2 member array (2,4). while the answer should be 2. if we use 1 operation value will be 7/2 which is ultimately 3.heres the editorials solution:void solve() { int n; std::cin >> n; std::vector a(n); for (int i = 0; i < n; i++) { std::cin >> a[i]; } std::sort(a.begin(), a.end()); int p = (n + 1) / 2 — 1; int res = std::count(a.begin() + p, a.end(), a[p]); std::cout << res << "\n"; }am i missing something in the logic/ question statement?edit--never mind read the problem wrong. used preconception of median to write the solution.  » 2 months ago, # | +40 I didn't know E was a standard problem.Solved it slightly differently. This felt a little bit more intuitive to me. SpoilerKey Idea: Create a directed tree and find the number of topological orderings possible for the tree. Root of the directed tree would be$s_1$or$p_{m_1}$(basically the index where the maximum number occurs). Now keep adding edges$a \rightarrow b$, which signifies number at index$b$should be smaller than number at index$a$. So, child of$p_{m_1}$is$p_{m_1-1}$, child of$p_{m_1-1}$is$p_{m_1-2}$,$.....$, child of$p_{2}$is$p_{1}$. Similarly, child of$s_1$is$s_2$, child of$s_2$is$s_3$, and so on...The answer required is number of topological orderings of this tree. You can imagine assigning descending numbers to a topological ordering to get one permutation.A bit of extra handling is required to take into account for indices not included in$p$or$s$, but that's easy as well. I'll leave it up to you, orelse you can see my submission. •  » » 2 months ago, # ^ | 0 actually one of our testers wrote this solution and it can be implemented easily without any handling any corner cases click •  » » » 2 months ago, # ^ | 0 Can't open the page. Says — you are not allowed to view the requested page. •  » » » » 2 months ago, # ^ | 0 here it is#include using namespace std; const int MOD = 1e9+7; const int N = 2e5+7; int inv[N]; int main () { ios_base::sync_with_stdio(0); cin.tie(0); inv[0] = inv[1] = 1; for (int i = 2; i < N; i++) inv[i] = 1LL*(MOD-MOD/i)*inv[MOD % i] % MOD; int T; cin >> T; while (T--) { int n, a, b; cin >> n >> a >> b; vector p(a), q(b); for (int& x: p) cin >> x, x--; for (int& x: q) cin >> x, x--; reverse(q.begin(), q.end()); if (p.back() != q.back() || p[0] != 0 || q[0] != n-1) { cout << "0\n"; continue; } int ans = 1; for (int i = 1; i <= n-1; i++) ans = 1LL*ans*i%MOD; for (int x: p) ans = 1LL*ans*inv[x]%MOD; for (int x: q) ans = 1LL*ans*inv[n-1-x]%MOD; cout << ans << '\n'; } }  •  » » 2 months ago, # ^ | 0 So, my original solution to this problem was this. The tutorial provided a different solution, because it seemed more understandable  » 2 months ago, # | +15 int y = (x^(1 << b)); for (int c = b - 1; c >= 0; c--) { if (((y>>c)&1) == 0) y ^= (1 << c); } FYI it is the same as int y = ((x >> b) << b) - 1;  •  » » 2 months ago, # ^ | +13 i would rather code the first than think about the most optimum way to code it sirs  » 2 months ago, # | 0 252835387 Can someone please tell the test case where my code is failing. Thanks •  » » 2 months ago, # ^ | 0 Take a look at Ticket 17427 from CF Stress for a counter example.  » 2 months ago, # | 0 Can someone explain the editorial of D? What does this mean "After this, if there is a 1 in x in this bit, update the answer and return the array to its original state."? And is there any other approach to this problem? •  » » 2 months ago, # ^ | 0 According to me what they are trying to say is that if we have even 1 at ith POS and x ith bit is also 1 then we do not need to partition it further. •  » » » 2 months ago, # ^ | 0 Which means we can return array before partition. •  » » » » 2 months ago, # ^ | 0 I think this is the most intuitive approach.  » 2 months ago, # | 0 For F:I wrote a$\mathcal O(\sum cnt^2_{divisors})$and thought it was brute force but it passed. It can be really short and fast if implemented well.Why it's the intended solution?$n=10^6$usually leads to a$\mathcal O(n\log n)$solution.Anyway, a typical 74 math problem. •  » » 4 weeks ago, # ^ | 0 what is a typical "74 math problem"? •  » » » 4 weeks ago, # ^ | 0 Both the idea and constraints gives me a strange feeling. 1732D2 - Balance (Hard version)  » 2 months ago, # | +5 In problem F I think it should be t1 >= L instead of <=. •  » » 2 months ago, # ^ | +5 thanks! fixed it •  » » » 5 weeks ago, # ^ | 0 I am wondering what is the limit of F's answer. Can someone prove that F's answer is in range of int or long long?  » 2 months ago, # | 0 Does anyone have D's solution using DSU? •  » » 2 months ago, # ^ | 0 C u mean? •  » » » 2 months ago, # ^ | ← Rev. 2 → 0 No. D has a tag of DSU. edit: In the morning it was showing tag of DSU but it's now removed. Why such? •  » » » » 2 months ago, # ^ | 0 I had such solution, you may check my submission •  » » » » » 2 months ago, # ^ | 0 It's hard to grasp the underlying logic behind your DSU solution merely by looking at the code. Can you please elaborate your idea behind the solution? •  » » » » » » 2 months ago, # ^ | 0 When we go bit by bit, we might need to unite segments in one component, so I used dsu to store the number of components. I also used set to effectively unite neighbouring numbers and rollbacks, since I needed to roll after attempting each bit •  » » 2 months ago, # ^ | +8 •  » » » 2 months ago, # ^ | 0 Hey, can you explain your solution. Thanks •  » » » » 2 months ago, # ^ | 0 can you just read tutorial? •  » » » » » 2 months ago, # ^ | +16 правильно, туда его, пусть идет решение читает •  » » » » » 2 months ago, # ^ | 0 I was talking about the above code you mentioned in the comment. I did not see it was not yours  » 2 months ago, # | 0 Reading proof for C was a nice journey  » 2 months ago, # | -8 why everybody used lambda function in c instead of normal function?? (especially candidate master and above)? •  » » 2 months ago, # ^ | 0 With normal functions, you must make all variables and stuff global, so you must clear them after every test case, and this is so boring and waste of time. •  » » » 2 months ago, # ^ | 0 and one more thing that we don't have pass many of the data that we pass in function  » 2 months ago, # | ← Rev. 2 → 0 Please somebody explain first part of solution C, how we can get the same solution for x — 1, if we have it for x? •  » » 2 months ago, # ^ | 0 Suppose you want to know that is it possible to cut the tree using k edges in such a way that every component has at least x nodes. now suppose that the answer is affirmative,i.e., every component has at least x nodes. now if you rephrase the problem after replacing x with x-1, you see that if we cut the tree in the same way as we did to find the answer to whether is it possible to cut the tree so that every component has greater than or equal to x nodes, you find that every component has greater than x-1 nodes(as every component has >=x nodes). •  » » » 2 months ago, # ^ | 0 I understand, that is, we need x — 1 vertices, but we already have x. I thought that we need exactly x — 1 :) As a result, we have answers [1, 1, 1, ..., 1, 0, 0 ...0] and we can use binary search to find the maximum possible x. Now it remains to write the checking function. Thanks, it's clear now! •  » » » » 2 months ago, # ^ | 0 welcome :)  » 2 months ago, # | 0 https://mirror.codeforces.com/contest/1946/submission/252897123 Can anyone help find the test case for which my code is wrong? •  » » 2 months ago, # ^ | 0 That's problem D. •  » » » 2 months ago, # ^ | 0 I see. •  » » » » 2 months ago, # ^ | 0 Nice to see helpful people in this community!  » 2 months ago, # | ← Rev. 2 → 0 Problem B :Can somebody explained me why i am getting overflow issue:https://mirror.codeforces.com/contest/1946/submission/252902592 •  » » 2 months ago, # ^ | 0 Never mind. Got it.  » 2 months ago, # | +1 is there a way to use dsu in problem c? like if we remove all of the edges first and then start combining components?  » 2 months ago, # | 0 Solution to problem C using Tree trimming submission  » 2 months ago, # | 0 B is really just kadane  » 2 months ago, # | ← Rev. 2 → 0 [submission:252783316]why is this code wrong,i just found indices of subarray with max sum and added it 2 power k times and finally added rest members of array other than those indices(indices of max sum subarray) to final sum  » 2 months ago, # | 0 I don't understand a single thing about C editorial. Can somebody explain the greedy algorithm with actual proof?  » 2 months ago, # | 0 This is my solution to problem C, the idea is same as the editorial still I'm getting TLE. Can anyone explain? https://mirror.codeforces.com/contest/1946/submission/252888566  » 2 months ago, # | 0 can't understand the proof of problem C. whats the first case and the second case? and whats the first variant? whats the first time? Do "case", "variant" and "time" mean the same thing? •  » » 2 months ago, # ^ | ← Rev. 3 → 0  1 / \ 2 3 / \ / \ 4 5 6 7 For such a binary tree and x=3. If I start the dfs on node 1. I think the algorithm would remove the edge 1-2. But if I start from node 2 and traverse node 1 at last. The algorithm would not remove the edge 1-2. although the answer is still correct the set of removal edges is not coincide. Could anyone please tell me where I might have misunderstood? •  » » » 2 months ago, # ^ | 0 no, edge 1-2 will not be deleted, because you can renumerate node 2 and 3, in this case dfs remove only edge 1-3 •  » » » » 2 months ago, # ^ | 0 Emm... Sorry im still confused. So u mean when dfs starts from node 1 and visits node 3 first, it would only remove edge 1-3? But the subtree of node 2 also meets the requirement(components > 3). why dfs do not cut the edge 1-2 since it would visit node 2 anyway. •  » » » » » 2 months ago, # ^ | 0 because you return 1 edge if size of node 1 component is less than x •  » » » » » » 2 months ago, # ^ | 0 got it! thanks bro  » 2 months ago, # | ← Rev. 2 → 0 I am just noticing the problem D is not having binary search tag, I thought Binary search is the most intuitive solution for D as I solved using binary search during contest. And also the editorial logic is not matching with the intuition i had ?I did binary search on answer, like for k pairs what is the minimum number I can create satisfying <= x which was the difficult part.Don't know I did binary search on C also, may be my thought process got biased ? •  » » 2 months ago, # ^ | 0 Hey there, i checked your solution, but could not understand the logic behind it. Can you please elaborate your solution?Thanks! •  » » » 2 months ago, # ^ | +3 Sure, so if you are asking how I approach the solution then its like I see that we have to calculate the maximum pairs k , so may be we can binary search on the answer k.so to model the problem as binary search, I did like "lets say we have to take at least K pairs, in that case what is the minimum number we can make". If you see the modeling of problem also bit non-trivial, I am saying we have take at least K pairs (this 'atleast' is most important for writing the checker function correctly) so in the checker function what I am doing is trying to make the smallest number possible where I need to at least K pairs.Now if you want to know how exactly I have written the code, my code is clean you can check should be self-explanatory if you are good with bitmasking and OR minization techniques (which I am not so good at from time to time).I can tell you the concept, I am going from MSB to LSB, and checking if the current bit I can make it 0 or not. If we can make it 0, we will update our answer for that particular bit as 0, otherwise as 1.  » 2 months ago, # | 0 Hi! I have a question about problem B:5 14 -2 8 -12 9For the above test case, if I select [-12] as the subarray and insert its sum (-12) in the array, the sum of the array will be 4-2+8-12+9-12 = -5. And -5 modulo (10^9 + 7) is 1000000002. Why is this not the optimum answer? •  » » 2 months ago, # ^ | 0 your motive is to calculate the maximum answer without modulo. we are ask to perform % (1e9 + 7) as answers can be pretty large and can't be represented in 64bit integer.you are not supposed to take the value which is giving you the maximum after modulo. •  » » » 2 months ago, # ^ | 0 Got it! Thank you so much ^_^  » 2 months ago, # | 0 Problem C was very nice, it's very similar to this one (except for the binary search part):https://mirror.codeforces.com/contest/1833/problem/G  » 2 months ago, # | +11 I think some problem setters really don't care about quality of Div2.B problems anymore. This Div2.B feels like filler problem, just invented at last moment or something. It's just kadane algorithm. Nothing more, nothing less.  » 2 months ago, # | 0 How is the formula for A derived?  » 2 months ago, # | 0 very good competition.I like it!!!  » 2 months ago, # | ← Rev. 2 → 0 Felt problem C is not obvious -- just implemented and got AC but re-rooting argument in editorial is quite nice  » 2 months ago, # | 0 I have a question, the x in question B I think is constantly changing, the answer at k = m should depend on the x of the question at k = m — 1, but then the x should have changed when transferring shouldn't it, or am I thinking too much about it :(  » 2 months ago, # | 0 In E, as written in editorial :- p1 should be 1 for some valid permutation to exist. 1. Is it because, it's the first element and it will be maximum in it's segment because there's no element before it. 2. If the above reasoning is true, then shouldn't s1 also be equal to 1, since aN is the last element.  » 2 months ago, # | 0 I think I've been missing something, this code gives wrong result for test case 6 1000, 6x -1000000000: #define ll long long const ll P = 1e9+7; int main() { int t; cin >> t; int kk = 0; while(t--) { int n, k; cin >> n >> k; vector a(n); int sum = 0; for(int i = 0; i < n; i++) { cin >> a[i]; } ll big = 0; ll subar = 0; for(int i = 0; i < n; i++) { sum += a[i] ; subar += a[i]; subar = max(subar, 0LL); big = max(big, subar); } sum = (sum % P + P ) % P; big = big % P; int T = 1; for(int i = 0; i < k; i++) { T = T *2 % P; } int ans = (sum + big * T - big + P) % P; cout << ans<< endl; } return 0; } I can't really find the problem, I looked at the editorial code and it seems fine to me.Also if anyone cares to elaborate, why can we use int for sum (like editorial does) can't that overflow the value, does OP knows that test cases won't to that, or is there something else that I'm missing? •  » » 2 months ago, # ^ | 0 Oh so basically problem was that sum was int actually, I tought I already tried it as long long. Also I now see that in editorial int was defined as long long, idk why would someone do that, it's confusing to beginners but okay.  » 2 months ago, # | 0 really liked problem F, thanks for the contest!  » 2 months ago, # | 0 In the editorial for C:If after this process there are at least k connected components, then the condition is satisfied for this x , otherwise it is not.Shouldn't it be k+1 connected components since we are removing k edges. •  » » 2 months ago, # ^ | 0 you are right! fixed  » 2 months ago, # | ← Rev. 2 → 0 Can anybody help me with B by providing a resource for me to understand modular arithmetic as required for such problems? For example, why must we take t = t * 2 % P; instead of simply adding first and then taking the modulo.Thanks in advance.  » 2 months ago, # | ← Rev. 4 → 0 As per editorial of problem:D, I have one small doubt. suppose my array is [ 2 , 1 , 2 , 2 , 1 , 2 ] and my x = 0; [ 2 , 1 , 2 , 2 , 1 , 2 ] ^ ^ ^ ^ L1 R1 L2 R2 since we want to maximize the number of segments, each segment must contain exactly 2, such numbers Can you please explain, how to handle above case from the editorial ? Answer is, when I take an entire array, otherwise, there is no answer.  » 7 weeks ago, # | 0 Can anyone explain me solution of$C\$ in simple words please , I mean why the greedy algorithm works
 » 7 weeks ago, # |   0 In the solution of C : if (sz >= x && f != v) { ++res, sz = 0; } There is no need of checking if it is the root node or not because even if it is, it will make sz = 0 which will be handled in the later partint t = dfs(dfs, 0, 0);return (res > k || (t >= x && res == k) ? true : false);so this can also work : if (sz >= x) { ++res, sz = 0; } 
 » 7 weeks ago, # |   0 Can anyone explain what is wrong here https://mirror.codeforces.com/contest/1946/submission/254039662
 » 7 weeks ago, # | ← Rev. 2 →   0 Edit: I got itIn the editorial solution of problem E, the line res = max(res, (int)b.size()); updates res. But b.size() is non-increasing while we are moving from bit number 30 to bit number 0. If b.size() is non-increasing, why can't we simply print the first best answer of b.size() when discovered and then break out of the loop. I tried submitting it but I got WA, so I am missing something. Can anyone point out what am I missing?Here's the submission link. The only difference between that submission and editorial's code is the break statement after res = max(res, (int)b.size())
 » 7 weeks ago, # |   0 Can somneone send me a solution for problem B using dp because i do not know how to apply dp to it?
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 well what the editorial did was dp just that it has a formal name called "Kadane's Algorithm" my solution is here.
 » 7 weeks ago, # | ← Rev. 2 →   0 For C, this is code that i have written: def dfs(cur,par,x,cnt,adj,n): num = 1 for nxt in adj[cur]: if nxt == par: continue num += dfs(nxt,cur,x,cnt,adj,n) if num >= x: cnt[0] += 1 return 0 return num def check(x,adj,n,k): cnt = [0] dfs(1,-1,x,cnt,adj,n) return cnt[0] > k t = int(input()) while t > 0: t -= 1 n,k = map(int,input().split(" ")) adj = [[] for i in range(n+2)] for i in range(1,n): a,b = map(int,input().split(" ")) adj[a].append(b) adj[b].append(a) l = 1 r = n while l <= r: mid = (l+r)//2 if check(mid,adj,n,k): l = mid+1 else: r = mid-1 print(r) i am getting runtime error on testcase 4 and i don't know why it is happening
 » 6 weeks ago, # |   0 Why does this code TLE for F?https://mirror.codeforces.com/contest/1946/submission/254907291I'm at 77 wrong submissions, my solution looks almost identical to the editorial.