### feecIe6418's blog

By feecIe6418, history, 4 weeks ago,

Thanks for participation!

Update: added alternative solutions/proofs for A,B,D,F

1988A - Split the Multiset

Hint 1
Solution
Code (python)

1988B - Make Majority

Hint 1
Hint 2
Solution
Another Solution
Code (python)

1988C - Increasing Sequence with Fixed OR

Hint 1
Hint 2
Solution
Code (python)

1988D - The Omnipotent Monster Killer

Hint 1
Hint 2
Solution
Another Solution
Code (C++)

1988E - Range Minimum Sum

Hint 1
Hint 2
Solution
Code (C++)

1988F - Heartbeat

Solution
Code (C++, FFT)
Code (C++, Interpolation)
• +147

 » 4 weeks ago, # |   +12 thanks for super fast editorial
 » 4 weeks ago, # |   +6 Super Fast！！
 » 4 weeks ago, # | ← Rev. 3 →   +104 there is also an O(n) solution for D.we call the number of turn that a monster gets killed its colour.we know that someone's colour is at most its degree +1.if just maintain the two minimum colouring's and its colours for a subtree we can update our answer as follow:we can fix the root colour from 1 to degre+1 and in each colourthe colouring for its children is the minimum colouring except the ones that its colour are same as the root. so their colouring is the second minimum one. so we can solve it with a dp in O(n) time.my code: 270694011
•  » » 4 weeks ago, # ^ |   +7 can u tell how?
•  » » » 4 weeks ago, # ^ |   +15 I tried to explain in my comment. if I it wasn't clear for you, you can read granadierfc comment here with another explanation.
•  » » 4 weeks ago, # ^ |   0 Nice :))
•  » » 4 weeks ago, # ^ |   +4 I read that trees are 2 colorable, so I'm thinking if only 2 colors would be sufficient?
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 No2 Colors are not sufficient he tried to say that the maximum value of a color for a certain node would at max be it's degree + 1So if we declare a dp [ x ] [ t ] where x is the node and t is the time in which I kill the x the monsterThen maximum number of second state that I would require for a certain node is it's degree + 1and sum of degree of all nodes is equal to 2 * N so we can say that overall there will 2 * N dp states.
•  » » » » 4 weeks ago, # ^ |   +3 Could you please point me out what is the mistake in the following logic:The problem states that "you cannot kill two monsters that are directly connected by an edge"So if I run a DFS and calculate depths of each node, then all nodes at an even depth are not connected by an edge, so I can kill all of them at once. Similarly, I can kill all monsters at an odd depth.
•  » » » » » 4 weeks ago, # ^ |   +9 I tried this initially. This approach is the fastest way to kill all the monsters, but it does not guarantee minimum damage taken. For instance, take the following tree as a counterexample: [50] | [5] | [10] | [90] The best first move would be to kill the root node and the lowest node. This would eventually take 3 total moves to kill all monsters, but it would result in less damage taken than going even rows and then odd rows (or vice versa).
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +5 two color wont work. Try:- 4 100 1 2 200 1 2 2 3 3 4 
•  » » » » 4 weeks ago, # ^ |   +3 TY!
•  » » » » 4 weeks ago, # ^ |   +1 ohhhh... i was also stuck there, i thought of two coloring but then i thought if it is two coloring then this should be very easy. Btw Thank you now I understood why this have so less submission
•  » » 4 weeks ago, # ^ |   +20 I am stuck on the thought that b≤3 always holds. Suppose a1,a2,a3,a4,a5 are the nodes connected in a line. In the first round, either {a1, a3, a5}, {a1, a4}, {a2, a4}, or {a2, a5} can be chosen. For the second round, there will be at most 2 nodes in a continuous segment that can be eliminated in the next 2 rounds.Can you please give a counter-condition?
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   +13 81 1 100 100 10000 10000 10000 100001 21 32 41 52 63 74 8
•  » » » » 4 weeks ago, # ^ |   0 Got it. Thankyou!
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Checkout this comment — https://mirror.codeforces.com/blog/entry/131567?#comment-1171033
•  » » » 4 weeks ago, # ^ |   0 Consider a full binary tree and you have to eliminate boss bottom-to-up in such cases
•  » » 4 weeks ago, # ^ |   0 What is the dp state for O(N)?
•  » » 4 weeks ago, # ^ |   0 Thanks for your nice solution!
•  » » 3 days ago, # ^ | ← Rev. 2 →   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } Deleted
 » 4 weeks ago, # |   0 omg fast editorial :-)
 » 4 weeks ago, # |   0 I felt A >>> B in terms of difficulty
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 constraints are very low u can do simple recursion with base cases Spoilerint solve(int n, int k){ if(n==1) return 0; else if(n<=k) return 1; return 1+solve(n-(k-1),k); } 
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 the whole process can be simulated it would be complexity of 1e6 but map is needed so we keep frequency but t is 1000 so it will not pass
•  » » » 4 weeks ago, # ^ |   0 lol... this is basically a O(N) solution
•  » » 4 weeks ago, # ^ |   0 same here
 » 4 weeks ago, # |   +90 Possible proof for A: Think of number n as n '1's in a chain, connected with n-1 bonds. Each step could break a maximum of k-1 bonds. Hence the answer.
•  » » 4 weeks ago, # ^ |   +34 Wow, this proof is really smart. Thanks for sharing!
•  » » » 4 weeks ago, # ^ |   +7 Thanks for the interesting (and challenging) problems!
•  » » 4 weeks ago, # ^ |   0 I think this similar to what is in editorial (just in a opposite way)
•  » » » 4 weeks ago, # ^ |   0 can you explain the editorial one ?
•  » » » » 4 weeks ago, # ^ |   0
•  » » 4 weeks ago, # ^ |   +3 Really nice observation.
•  » » 4 weeks ago, # ^ |   0 I feel like an idiot after seeing your solution. I was doing it really hard way, which got WA.Here it is, void solve(){ int n, k; cin >> n >> k; if(n ==1){ cout << 0 << endl; return; } else if(n <= k){ cout << 1 << endl; return; } int op =0, lk=0; if(n%k >0){ if(n%k >1) lk++; n -= n%k; if(n/k <= k-1) lk += n/k; else{ op++; int x = n/k; op += x - k+1; lk += x; } } else{ if(n/k <= k) lk += n/k, op++; else{ int x = n/k; op += x - k+1; lk += x; } } cout << op + lk << endl; } 
 » 4 weeks ago, # | ← Rev. 3 →   +44 For D: The Omnipotent Monster Killer I created a video editorialI also created a practice contest for you to submit and verify your cubic and quadratic solutions. https://mirror.codeforces.com/group/7Dn3ObOpau/contest/536755For E: Range Minimum Sum also I created a video editorial and a practice contest which you can find hereBefore attempting E: Range Minimum Sum, try these standard and easy version of the problem.Standard Easy Variations Difficult Variations In the past, I have also created a video on this topic.
•  » » 4 weeks ago, # ^ |   0 Here is an interesting problem that has sum of all subarray maximums as a subproblem. CC LIMITMEX
•  » » 4 weeks ago, # ^ |   0 yes vro it is same as array collapse
 » 4 weeks ago, # |   +24 Alternate for D : Note that a monster $v$ will die within $\leq deg[v]+1$ rounds. The problem could be formulated as follows , assign $t[v]$ (round number in which the monster gets killed) to each vertex $v$. Then you have to minimize the sum of $a[v].t[v]$ . For each vertex $v$ , we can keep a $deg[v] + 1$ sized vector , where each corresponds to the round number at which it was killed. Now using dfs and suffix / prefix minima , we can evaluate this value is $O(N).$
•  » » 4 weeks ago, # ^ |   0 Can you elaborate on what deg is and how to arrive at this conclusion?
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 Isolate a vertex $v$ , and look at all it's neighbours (the ones connected by edge to it) . deg or degree means the number of neighbours of a vertex $v$. At each round , either $v$ or atleast one of it's neighbours are chosen. If say none of them are chosen then you can simply choose vertex $v$ and have better answer.
•  » » » 4 weeks ago, # ^ |   0 deg in this context means the degree of a given node v, which is the number of adjacent vertices to v. You can think of this as such: if there are no adjacent nodes of v which are being removed on a certain round, then there is no reason not to remove v on that round as it is just a free removal. Therefore to delay the removal of v as late as possible, there would be 1 adjacent node of v being removed on each round, until v is finally alone. Once you realize this, the rest can be followed as explained by the original comment.
•  » » 4 weeks ago, # ^ |   0 Could we kill all the monsters in just two rounds? Using bipartite algo, dividing nodes in two sets, then killing all monster of one set in round1 and killing all other monster in round2
•  » » » 4 weeks ago, # ^ |   0 That's what i tried, not sure why it was wrong 270739384
•  » » » » 4 weeks ago, # ^ | ← Rev. 3 →   +3 Try this case: 4 100 1 2 200 1 2 2 3 3 4
•  » » » » » 4 weeks ago, # ^ |   0 Thanks, that clears it
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Spoiler1 1 1 100 100 100 100 100 100 1 2 2 3 1 7 1 8 1 9 3 4 3 5 3 6
•  » » » 4 weeks ago, # ^ |   0 I tried that but it is wrong because you could have two monsters with large attacks in different sets, but the optimal strategy is to eliminate both of them even though it may take extra turns.
•  » » 4 weeks ago, # ^ |   +5 Can you elaborate this approach further? How will you find the round number for each vertex such that $a[v].t[v]$ is minimised?
•  » » 4 weeks ago, # ^ |   0 can you please elaborate your solution?
 » 4 weeks ago, # |   +7 Can somebody explain what is being done in D. Or at least direct me to relevant resources.
•  » » 4 weeks ago, # ^ |   +7 yea the editorial seems to skimp on the details. whats the DP recurrence here?
•  » » » 4 weeks ago, # ^ |   +11 Let $m$ be the maximum value of $b$ for all nodes (as in the editorial). We first root the tree at any node. Then, we perform a DP where $dp[i][b_i]$ ($1\leq b_i \leq m$) is equal to the answer to the problem for the subtree rooted at $i$. If $C_i$ is the set of children of node $i$, then the DP transition is $dp[i][b_i] = a[i]\cdot b_i + \sum_{j\in C_i} max_{1\leq b_j\leq m, b_j \neq b_i} dp[j][b_j]$.
•  » » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 Thanks. This is the O(nlog^2n) solution right? Also why is it max, not min, since we want to minimize the damage?
•  » » » » 4 weeks ago, # ^ |   +1 dp[i][bi]=a[i]⋅bi+ min of dp[j][bj] *** min not max .
 » 4 weeks ago, # |   0 can someone point out my mistake in c i did the same thing as editorial submission of c
•  » » 4 weeks ago, # ^ |   0 n can reach 1e18,32 is not enough.
•  » » » 4 weeks ago, # ^ |   0 F this is the second time i fell for it :(
•  » » 4 weeks ago, # ^ |   0 iterate i from 1 to 63, and do (1ll<
•  » » » 4 weeks ago, # ^ |   0 yeah tx im noob
•  » » 4 weeks ago, # ^ |   0 The constraints on n is 1 <= n <= 10^18 so in loop you had to use i < 64 but you used i < 32 bits which resulted in wa
•  » » 4 weeks ago, # ^ |   0 can anyone explain for question c why ans is not 5 for 14 n =14 5 6 8 10 12 14
•  » » » 4 weeks ago, # ^ |   0 5|6 != 14
•  » » » 4 weeks ago, # ^ |   0 yes , I got same problem according to question ans should be : 4 1 3 14 23 my output is : 1 1 3 1 2 3 5 6 8 10 12 14 7 7 16 19 20 21 22 23 
•  » » » 4 weeks ago, # ^ |   0 just greedily flip the last set set bit that you didnt flip earlier and the next time you must flip a set bit greater then this bit otherwise the decreasing/increasing condition wont be satisfied
•  » » » » 4 weeks ago, # ^ |   0 here why increasing decreasing condition is not satisfied?
•  » » » » » 4 weeks ago, # ^ |   +1 8|10=10 not 14
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 To ensure or is 14 you must set the bit you unset last time
 » 4 weeks ago, # |   0 These Python codes are really cute.
 » 4 weeks ago, # |   0 ty for fast editorial)
 » 4 weeks ago, # | ← Rev. 2 →   0 Whats the counterexample for solving D by making the tree into a bipartite graph, then removing the side of the graph with the greater attack amount?
•  » » 4 weeks ago, # ^ |   0 Indeed. I attempted that method but got WA.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 you can consider the line graph 1-2-3-4, with attack values 100, 1, 1, 100.
•  » » » 4 weeks ago, # ^ |   0 ah fuck
•  » » » 4 weeks ago, # ^ |   0 Why wouldn't that method work? Isn't it optimal to first get attacked by all monsters (hence a loss of $202$ health points) and then attack two non-adjacent monsters, to then be attacked by the two remaining ones before they, too, get killed? With a minimum decrement of $303$ ($100+1+1+100+(100+1)$)?In other words, the following: - First round, all monsters attack. $202$ health points are lost. Two non-adjacent monsters of $101$ and $1$ attack points get killed. - Second round, all remaining monsters attack. $101$ health points are lost. The rest gets killed.I believe I am missing something obvious here, but I don't see it.
•  » » » » 4 weeks ago, # ^ |   +5 You can choose to kill 1st and last in the first turn. So total damage -> 202 + 2 + 1
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 In the first round you can kill the monsters with 100 attack power. so now you have 0--1--1--0 then take two more rounds to kill the other two. In this case the total damage will be 202+2+1
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 4100 1 1 1001 22 33 4
 » 4 weeks ago, # |   0 Today first time i have solved 3rd problem
 » 4 weeks ago, # |   +6 best contest, but in my opinion E is easier than D
 » 4 weeks ago, # |   0 I so almost solved D. Nice problems. Thanks for super fast editorial.
•  » » 4 weeks ago, # ^ |   0 How ? Both of us had similar approach for D but its wrong . I think our approach is completely wrong . How is it almost solved ? can you give the bfs solution for D.
•  » » » 4 weeks ago, # ^ |   0 No I am not talking about the one I submitted. I thought about dp on levels... But I think it needs further optimisation.
•  » » » » 4 weeks ago, # ^ |   0 And I think dp on levels will also not work. I thought why just now :(
 » 4 weeks ago, # |   +11 Can someone give me an example for problem D where $b_i$ is greater than $3$ for any node?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I'd like to see an example too. Here is my perhaps wrong proof:In the first round, you can reduce the whole tree to pairs of two or lone nodes. Because, imagine a line of 3 nodes: just remove the node in the middle and it becomes two lone nodes.Then, in the second round, remove all the lone nodes and 1 node from each pair of 2.Then, in the third round, remove all the lone nodes.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +77 The optimal solution should be red -> green -> blue -> black. This can be generalized to any graph with $2^n$ vertices needing at least $n+1$ rounds, by adding another monster of sufficiently large attack power connected to each vertex in the configuration for $n-1$.
•  » » » 4 weeks ago, # ^ |   +4 ah, thanks for this
•  » » » 4 weeks ago, # ^ |   +3 Thank you so much!
•  » » » 4 weeks ago, # ^ |   0 Thanks for your gragh.It is really clear!
•  » » » 4 weeks ago, # ^ |   0 Can you please help me understand, why greedy fails? 1) My solution was, travel through entire tree.2) Initially I will have all monsters alive. Doing greedy, I will get answer, which monsters MUST BE KILLED in this round, by finding maximum sum of independent set. 3) I will kill these monsters. In fact, we can say, we are removing these nodes from the tree, and splitting it into multiple trees ( forest ) . 4) I will continue this process, until I have killed all the monsters. The test case that you have proposed InternetPerson10, works perfectly fine with my greedy approach. I just can't figure out, why greedy approach fails :(
•  » » » » 4 weeks ago, # ^ | ← Rev. 3 →   +3 Consider this test case:I think your solution will print 160 (it takes 3 rounds), while there is a way to do 150 — choose a 3 and a 2 to kill in the first round.
 » 4 weeks ago, # |   +5 Is it true that the total rounds in D is $\le 3$?
•  » » 4 weeks ago, # ^ |   0 I also thought so, but I guess, that's not true.
 » 4 weeks ago, # |   0 Why I can not solve a with brute force?
 » 4 weeks ago, # | ← Rev. 2 →   +27 I have a different solution for B. Compress adjacent 0s into just one 0 (ex. 0010001 -> 0101). Note that replacing every substring with majority 0 is of the form 0 + 10 * k such that k is an integer, so removing these strings doesn't change the number of 0s and 1s. Thus, just check if there are more 1s in this compressed string than 0s. Here is my submission link. I'm surprised that the intended solution is casework.
•  » » 4 weeks ago, # ^ |   0 The same solution.
•  » » » 4 weeks ago, # ^ |   0 same here
•  » » 4 weeks ago, # ^ |   0 i also had the same solution and it felt much easier
 » 4 weeks ago, # | ← Rev. 2 →   +51 A case for Bonus: Find a counterexample for $b_i≤18$ when $n=300000$.Explanation: we delete all leaf nodes at a time. Then the tree becomes the largest subtree of the previous tree.
•  » » 4 weeks ago, # ^ |   0 This structure is also known as binomial heap.
•  » » 4 weeks ago, # ^ |   +8 If you've learnt Binomial Heap, you'll find this construction is easy to access, for we're emphasizing the constraint on each node: each node with out-degree $i$ is directly connected to nodes with out-degree equal to $0,1,\dots,i-1$ exactly one each. And under this condition, we found a deletion with all nodes total degree $i$ on $i$-th round exactly fulfills the constraints of MEX.
 » 4 weeks ago, # |   +17 Another solution to BFirst, all continuous $0$ can be transformed into one $0$ using one operation. Then we can consider the simpler form.It's obvious that the pattern like $101$ can be reduced into $1$, so all $0$ except the first and the last character. so we can just compare the number of $1$'s and the number of longest continous $0$ segment.
 » 4 weeks ago, # |   0 what's the expected rating of D?
 » 4 weeks ago, # |   +11 There's an $O(n\log n)$ solution to E without using the cartesian tree by calculating the contribution of each $a_i$https://mirror.codeforces.com/contest/1988/submission/270728340
•  » » 4 weeks ago, # ^ |   0 i also have some $O(n \log n)$ solutions with a fenwick tree and a segment tree, but it unfortunately got TLE :/
•  » » 4 weeks ago, # ^ |   0 I found for each element two left and two right minimums with set of indices. Adding contributions to answers are just with prefix sums
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +8 The solution of calculating the contribution can be optimized into $O(n)$ by using prefix sum and differce array.https://mirror.codeforces.com/contest/1988/submission/270863077
 » 4 weeks ago, # |   -9 C Video Editorial https://www.youtube.com/watch?v=-asiN-_tqb0English
 » 4 weeks ago, # |   +14 There is another solution for problem E. The point is to look at the contribution of each element in the permutation to the answers.For each element we calculate the first and second element smalller than them to the left and to the right. This can be done in $O(n\cdot logn)$ using binary search and sparse table.Then for each element we want to analyse the contribution of subarrays for which the current element is the minimum. We look at the segment of elements until the first smaller one to the right, let's say it has size $A$ (not including the element itself) and let's call the right one $B$. To everyone that is in the left segment, the number of subarrays for which the current element is the minimum is $A \cdot (B + 1)$ and for everyone in the right segment its $(A + 1) \cdot B$. For the first eleement smaller than the current element to the left, the number of subarrays is $(B + 1)\cdot ($ size of segment to the left including all elements up until the second element smaller than him $)$ . Same logic can be used to calcuate contribution of current element to the first ellement smaller to the right. For everyone else, that is everyone left of the first smaller element to the left and everyone right of the first smaller element to the right, the contribution is $(A + 1) \cdot (B + 1)$. Some edge-cases need to be handled for when there is no element smaller to the left or to the right however this is the gist. The contribution can be added up with lazy segment tree or even with prefix sums.For details of implementation you can look at my code. code
•  » » 4 weeks ago, # ^ |   +21 You can do everything without any data structures btw 270718477
•  » » » 4 weeks ago, # ^ |   0 Very cool!
•  » » » 4 weeks ago, # ^ |   0 someone add this in tutorial. It is super cool solution.
•  » » 4 weeks ago, # ^ |   0 This is the method I used; however, you can use stacks instead of binary search and RMQ and use prefix sums instead of segtree to achieve O(N). 270713592
•  » » » 4 weeks ago, # ^ |   0 can you tell how you find out the second smaller element than the current element using stacks ?
•  » » » » 4 weeks ago, # ^ |   +4 When a item is popped from the stack for the first time, place it back again and you can find that the monotoniciy of the stack still maintains.Hence when the item is popped for the second time, that's where the second smaller element is.
 » 4 weeks ago, # |   0 blazingly fast editorial
 » 4 weeks ago, # |   0 In editorial of pD, "taking max part" should be "taking min part"
 » 4 weeks ago, # |   +21 Did poor in this round, but really nice problems! The other side of getting bad result is finding unseen shortages for improvement :)
 » 4 weeks ago, # | ← Rev. 3 →   0 nvm
•  » » 4 weeks ago, # ^ |   +3 Eg 4 / | \ 1 2 3 / / \ 1 1 2 \ 1 Where the number on vertex means the round it is removed (If you want to think as minimizing damage, replace 1 to 1e9, 2 to 1e7, etc.)
 » 4 weeks ago, # |   0 I think for A, a simple proof (or rather intuition) can be : Let's say you do not divide the element into (k-1) 1's and (n-k+1), and lets say you divide it into some number (possibly zero) number of 1's and a bunch of other numbers. Let the minimum number be p, then, to make p into 1 again (which is our goal), you'll need another operation in the future to convert it. Thus, you are needing more than 1 operation to convert a number into 1. Greedily, we should ideally use only 1 operation to convert a number (or part of it) into 1's. Thus, the ideal strategy becomes to convert the numbers into (k-1) 1's and (n-k+1)
 » 4 weeks ago, # |   0 The suggested method for B feels unnecessarily complex and invites mistakes by having multiple cases. Instead, another approach is to collapse each continous sequences of 0 into a singular 0, then compare if there's more 1s than 0s.My (python) code: https://mirror.codeforces.com/contest/1988/submission/270651964
 » 4 weeks ago, # |   0 B was a really easy question
 » 4 weeks ago, # |   0 For B I thought of splitting string into "101"/ "110" / "011". What is wrong with this solution? 270743982
 » 4 weeks ago, # |   0 In D, I used recursive DP[n][20] but still TLE in test case 20. Can somebody explain why?
•  » » 4 weeks ago, # ^ |   0 Check second last line in your DFS function .You are Not storing answer in dp array ,instead you are simply returning.
•  » » » 4 weeks ago, # ^ |   0 It is only for the root node i.e when parent==-1. for other nodes I am using dp.
•  » » » » 4 weeks ago, # ^ |   0 try submitting on cpp20
•  » » » » » 4 weeks ago, # ^ |   0 still TLE on test case 20. Very strange all test cases are large but failing only at 20
•  » » » » » » 4 weeks ago, # ^ |   0 Its working in 1.6 seconds after changing the order of w and childs. https://mirror.codeforces.com/contest/1988/submission/270893195
•  » » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Can you explain why this is so? TC remains the same. Why it only fails at test case 20 while other passed testcases are large too?
•  » » » » » » » » 4 weeks ago, # ^ |   0 i think maybe it is related to depth of tree , also you can optimize it to n*20 from n*20*20 by using prefix and suffixmax.
 » 4 weeks ago, # |   +19 Another proof for # turns for pD: notice vertices not chosen in a round should connect to at least one chosen vertex, otherwise we can also choose it, then consider CC form by non-chosen vertices, every vertex in same CC would have different adjacent chosen vertices, then if there exist a (non-chosen)CC with size > n / 2, there also have > n / 2 chosen vertices, which means total nodes > n, which leads to a contradiction, so max size of CC form by non-chosen node would halve.Then to construct the case where $O(\lg n)$ turns is needed, we can use the idea of above proof:start with single node with weight $2^1$, call such tree $T_1$, then define $T_i$ ($i > 1$) as the tree by first use a node with weight $2^i$ to connect two $T_{i - 1}$, then for each node haven't connect to a node with weight $2^i$, create a node with weight $2^i$ and connect to it, then $T_i$ would have about $2^i$ nodes and require $i$ turns to eliminate.
•  » » 4 weeks ago, # ^ |   0 thanks for this explanation
•  » » 4 weeks ago, # ^ |   0 Very helpful. Thanks for the comment..
 » 4 weeks ago, # |   +25 Hi, how to compute $f(n,i,j)$ in $O(n^3)$ in F editorial? I was only able to come up with $O(n^4)$ or $O(n^3 log(n) )$ solutions for this subproblem.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 .
•  » » 4 weeks ago, # ^ |   +20 Disclaimer: I haven't implemented it myself yet, but that seems to be the logic behind jiangly's solution (270732930)Let's build permutations of length $n + 1$ by inserting a $1$ into a permutation of length $n$ of numbers $2, 3, \dots, n + 1$, so we have $n + 1$ positions to insert to. These positions can have one of the $4$ types: First position. In this case both the number of ascents and the number of prefix maximums increases by one. Ascent positions, i.e. we insert a $1$ between elements $p_i$ and $p_{i+1}$, such that $p_i < p_{i+1}$. In this case both the number of ascents and the number of prefix maximums do not change. Nonascent positions, i.e. we insert a $1$ between $p_i$ and $p_{i+1}$, but $p_i > p_{i+1}$. In this case the number of ascents increases by one, but the number of prefix maximums stays the same. Last position. Nothing changes. Now we can count the number of positions of each of those types to get the transitions from $f(n, i, j)$: Only one, so $f(n + 1, i + 1, j + 1)~+= f(n, i, j)$. Exactly $j$, so $f(n + 1, i, j)~+= j \cdot f(n, i, j)$. There are $n - 1$ positions between two consecutive elements and $j$ of them are ascent, so $n - 1 - j$ are remaining: $f(n + 1, i, j + 1)~+= (n - 1 - j) \cdot f(n, i, j)$. Only one, so $f(n + 1, i, j)~+= f(n, i, j)$.
•  » » » 4 weeks ago, # ^ |   +10 Thanks :)
 » 4 weeks ago, # |   0 In problem D, Why does the maximum B of a node is deg(x) + 1? I cannot find any comment to prove it.
•  » » 4 weeks ago, # ^ |   +5 Because $b_u = \operatorname{MEX}_{(u,v)\in E}(b_v) \le deg(u)+1$
 » 4 weeks ago, # |   0 First, thank for very good contest and fast editorial I am going to share my O(n) solution for D We can notice that in optimal solution, monster in node v can be kill in at mode |v| round (|v| is number of node have the same edge with D, round number from 0) So we can call dp[v][round]: minimum number of health decreases when kill monster in node v after "round" dp[v][round]= ∑_(u ∈chill of v) (min)⁡(dp[u][j]) (j ≠round) (sorry, i don't know how to write beautiful fomular) we can use pref_min and suf_min to quickly calculate Node that we must update parent value from chill due to tle Here is my code 270747003
 » 4 weeks ago, # |   0 I see newbies solving C damn newbies these days are different breed,back when I was a newbie I couldn't even upsolve C by looking at editorial.But how does their submission looks alike?
 » 4 weeks ago, # |   +3 can anybody write a more intuitive proof for problem D's max of logn sets ?
•  » » 4 weeks ago, # ^ |   +4 This might help
 » 4 weeks ago, # |   0 where you guys show the range of the output from 1 to n ? not 0 to n? (Problem C)Or am i missing something?
•  » » 4 weeks ago, # ^ |   0 Positive integers
•  » » 4 weeks ago, # ^ |   0 positive integers
 » 4 weeks ago, # |   0 Hi, I am finding it difficult to understand the solution provided to D. Can someone post a simple solution with an explanation or suggest updates in the existing editorial please?
 » 4 weeks ago, # |   +1 For B I believe we can also "compress" any amount of '0' in a row into a single '0', then simply check if the number of '1's is greater than '0's in the resulting string: 270654643
 » 4 weeks ago, # | ← Rev. 5 →   0 For A, if we do in the reverse way, I think this is a problem like exchanging a new bottle by K bottle caps.Like given [1, 1, 1, 1, 1, 1, ..., 1] containing n 1s, and we are going to combine at most K items once, and finally derive [n]. The process will be like [1, 1, 1, ..., 1] -> [1, 1, 1, 1, ..., K], containing N-K 1s and 1 K. Our target is to combine all numbers into 1 number, so the real number in the array doesn't matter at all, that it, there remains N-K+1 items to combine.The maximum number of bottles that can be exchanged is floor((N-1)/(K-1)).I think this is a classis problem, so you may find video explanations online. I elaborate one here: First give 1 bottle cap to your friend, and every time you exchange K-1 bottle caps with your friend's one, and give the exchanged bottle (cap) back to your friend. You can do this (N-1)/(K-1) times and you will finally exchange floor((N-1)/(K-1)) bottle caps and have remaining (N-1) % (K-1) bottle caps + 1 from your friend.The difference between A and bottle exchange problem is that if (N-1) % (K-1) + 1 > 1, then you should do the final combine, so the answer is ceil((N-1)/(K-1)) in this problem.
 » 4 weeks ago, # |   0 Problem D got accepted in exacly 3 sec [submission:https://mirror.codeforces.com/contest/1988/problem/D]
 » 4 weeks ago, # |   +10 Pretty surprise to see cartesian tree in $E$. Maybe it is the first time I see it in CF as well.
 » 4 weeks ago, # | ← Rev. 2 →   0 A felt hard. Came up with DP approach for A during the contest . Normal method was just not striking me. A using DP#include using namespace std; #define int int64_t int dp[1001]; int solve(int n,int k){ if(n==1) return 0; if(n<=k) return 1; if(dp[n]!=-1) return dp[n]; if(n >= k*k){ int ret = 1; vector x(k,k); n -= k*k; x[0] += n; for(int i=0;i x(k,1); n -= k; int i=0 ; while(n){ if(n>=k-1){ x[i] = k; i++; n -= (k-1); }else{ x[i] += n; break; } } i = 0; int ret = 1; for(;i>n>>k; memset(dp,-1,sizeof(dp)); cout<>t; while(t--) runcase(); } 
•  » » 4 weeks ago, # ^ |   0 Woah, I also did DP (bottom up) for problem A but mine is much easier:270647399
 » 4 weeks ago, # | ← Rev. 2 →   +3 Hello! Does my solution of D get RE because of dfs? 270748754If yes, is there are way to bypass it nicely?
 » 4 weeks ago, # |   +2 Shouldn't the edi also contain the dp states and transitions atleast instead of just mentioning that you can solve it by dp? (for D)
 » 4 weeks ago, # |   0 Another idea for B is that it is only possible iff the number of "0-streaks" is less than the number of ones.
 » 4 weeks ago, # |   0 Please someone explain the bi<=19 part of the editorial in more detail.
 » 4 weeks ago, # | ← Rev. 2 →   +8 In fact, problem D has a $O(n)$ wayConsidering that we actually only transfer from the smallest and subsmallest points of each subtree when we transfer, in fact, there are only $O(deg)$ effective transfer points of a tree point, that is, only the number of selection rounds corresponding to the minimum value of each point, and their mex and mex+1, taking into account this, we only need to maintain the smallest and subsmallest points of each point to implement the $O(n)$ algorithm.It comes with an implementation that uses map, which is just for convenience and can be replaced with another $O(1)$ structurehttps://mirror.codeforces.com/contest/1988/submission/270751383
 » 4 weeks ago, # |   0 Could someone provide an explanation of the DP used for Problem D?Thanks!
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 If monster u is killed at time x , all its adjacent monsters v will be killed in range [1 , x — 1] U [x + 1 , upper bound ] . So dp[i][j] denotes the minimum cost to kill all monsters in subtree rooted at i , where ith monster is killed at at jth second .upper bound is log(n)
•  » » » 4 weeks ago, # ^ |   0 Understood, Thank you !
 » 4 weeks ago, # | ← Rev. 2 →   0 Why does this code in java 270744757 tle but gives ac in c++ 270751728 :( Edit: I see that the c++ code also barely passes maybe i can do better with the transitions
 » 4 weeks ago, # |   +8 In fact, problem D has a $O(n)$ wayConsidering that we actually only transfer from the smallest and subsmallest points of each subtree when we transfer, in fact, there are only $O(deg)$ effective transfer points of a tree point, that is, only the number of selection rounds corresponding to the minimum value of each point, and their mex and mex+1, taking into account this, we only need to maintain the smallest and subsmallest points of each point to implement the $O(n)$ algorithm.It comes with an implementation that uses map, which is just for convenience and can be replaced with another $O(1)$ structurehttps://mirror.codeforces.com/contest/1988/submission/270751383
•  » » 4 weeks ago, # ^ |   0 Can you please explain this approach in detail?
 » 4 weeks ago, # |   0 I enjoyed today's problems. Thanks to the setters.
 » 4 weeks ago, # |   0 nice
 » 4 weeks ago, # |   +2 This codechef problem is harder version of B.
 » 4 weeks ago, # | ← Rev. 2 →   0 I believe my solution for problem E is also O(n), but doesn't require Cartesian tree. It is quite unpleasant to implement and debug though, I couldn't do so during the contest time.
 » 4 weeks ago, # |   0 thanks for editorial <3
 » 4 weeks ago, # |   0 What's wrong with this idea for D?There are at most $O(\log n)$ rounds, so for round $j$, find the maximum weighted independent set, let it be $c_j$, then set the values of $a_{v_i}$ to 0 for each $v_i$ in the max ind set, and keep doing that until we get all zeroes in a. For round $j$, add $j \cdot c_j$ to the answer. After all rounds, output answer. This fails on test 3 :|
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 45 4 4 51 22 33 4The optimal solution is 18 + 9 = 27. From what I understood, your idea will output 18 + 8 + 4 = 30.
•  » » » 4 weeks ago, # ^ |   0 Thank you!
 » 4 weeks ago, # |   0 How does the induction go in the proof of B?
 » 4 weeks ago, # |   0 Problem E can be done by looking at the contribution of each values. If an index is removed then the affected contribution will the - - The contribution from the index itself. This we can find by calculating the left and right index smaller than the value at index. - The contribution coming from the other index that uses this index in their contribution. Here the observation this value will only change if we change the value between the left and right minimum of this index. If we remove left and right, then we have to consider second minimum left and second minimum right respectively and add it accordingly. All the value that is between left and right will only reduce the contribution by 1.
 » 4 weeks ago, # |   0 For problem D, am I the only one who decided to use sqrt(n) instead of log2(n) as the bound for b (for safety because I couldn't prove it in contest), only to find out that there's exactly one singular case where sqrt(n) < log2(n)? QAQ
•  » » 4 weeks ago, # ^ |   0 for what n?
 » 4 weeks ago, # | ← Rev. 3 →   0 This is my approach for problem A, can you tell me what is the flaw in the argument? the picture link is the following, i don't know why it is not uploading: https://photos.app.goo.gl/VLXqFcDU2QHGFHap7
 » 4 weeks ago, # |   0 I came up with DP on subtrees solution for D right after the contest but it got WA on 3rd test. It maintains dp[2][i], the maximum sum of monster points on subtree i we can get in the current round if we skip/kill the root node of that subtree. Can somebody help me understand why that failed?270745002
•  » » 4 weeks ago, # ^ |   +1 Spoiler1 4 5 4 4 5 1 2 2 3 3 4 
•  » » » 4 weeks ago, # ^ |   0 oh, thanks!
 » 4 weeks ago, # |   0 not come up with '0110110' and got an WA on B :(
 » 4 weeks ago, # | ← Rev. 3 →   +5 $O(n)$ solution in problem E without cartesian tree (although it's long to explain what I'm actually doing): 270758048.Edit: I miswrote the prev_greater and next_greater, it must be prev_smaller and next_smaller
•  » » 4 weeks ago, # ^ |   0 That was clever to push all the popped elements from 1st stack to 2nd stack. I found first and second left/right minimum index using Fenwick tree 270751749
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I'm not really the one who comes up with the two stacks approach. Last week, I solved a problem in Leetcode , which required to find the second greater element. Firstly I used segment tree for it, but then I know that 2 stacks O(n) approach from a guy.
•  » » » » 4 weeks ago, # ^ |   0 Can you explain how you are using the Fenwick Tree to update the contribution?
•  » » 4 weeks ago, # ^ |   0 I did something similar I think, but i did the prev_greater thing with rmq, so it's $O(n log n)$. Nice code btw
 » 4 weeks ago, # |   0 Can someone explain why I have to cast here?I made a function that converts a binary string to decimal but it breaks at higher numbers. Specifically this statement: num += (Long.parseLong(binary.substring(i-1, i)) * Math.pow(2,binary.length()-i)); However when casting to long this statement works as intended. num += (long) (Long.parseLong(binary.substring(i-1, i)) * Math.pow(2,binary.length()-i)); Here is the working submission: 270754810
 » 4 weeks ago, # | ← Rev. 2 →   0 I don't get this line in A proof and the aforementioned sequence of operation achieves the maximum increment.  I think you can actually get the same increment with doing another type of operation in some cases like for example n=200 and k= 5 we can make it 37 37 37 37 52 
 » 4 weeks ago, # |   +16 I solved E in $O(n log(n))$ How do you solve if you don't have to remove any element from the array? f(a)For each $a_i$ we find what would be the contribution of $a_i$ to the result.Let $l_i$ be the first smallest element when traversed from index $i$ to left; $a_j > a_i$ for all $l_i < j < i$Similarly, Let $r_i$ be the first smallest element when traversed from index $i$ to right; $a_j > a_i$ for all $i < j < r_i$Contribution of $a_i$ to the result would be $a_i * (i - l_i) * (r_i - i)$Result = $\sum_{i=1}^{n}{a_i * (i - l_i) * (r_i - i)}$ Calculating previous smallest and next smallest is standard questionTutorial for Next greater element using the same trick you can extend it for finding next smallest element and previous smallest element Hint 1How many first left and right minimums do we need to maintain? Hint 2How do you efficiently find first 2 left/right minimums? SolutionLet $l1_i$ be the first smallest element when traversed from index $i$ to left; $a_j > a_i$ for all $l1_i < j < i$Let $l2_i$ be the second smallest element when traversed from index $i$ to left; $a_j > a_i$ for all $l2_i < j < l1_i$ and $l1_i < j < i$Let $r1_i$ be the first smallest element when traversed from index $i$ to right; $a_j > a_i$ for all $i < j < r1_i$Let $r2_i$ be the second smallest element when traversed from index $i$ to right; $a_j > a_i$ for all $r1_i < j < r2_i$ and $i < j < r1_i$Lets find what would be contribution of $a_i$. We have a total of 5 cases. $a_i$ contribution for all arrays which are formed by removing elements in the range $[1, l1_i), (r1_i, n]$ would be $a_i * (i-l1_i) * (r1_i-i)$ for the range $(l1_i, i)$ then contribution would be $a_i * (i- l1_i \textbf{-1}) * (r1_i-i)$ for the range $(i, r1_i)$ then contribution would be $a_i * (i-l1_i) * (r1_i-i \textbf{-1})$ If we remove $l1_i$ then contribution would be $a_i * (i- l2_i\textbf{-1}) * (r1_i-i)$ (as we removed the first left minimum we pick the second left minimum) If we remove $r1_i$ then contribution would be $a_i * (i-l1_i) * (r2_i-i \textbf{-1})$ (as we removed the first right minimum we pick the second right minimum) From above cases we have a range and a value that needs to be added, this is reduced to range update point query. This can be done in $O(n)$ how do we calculate l1/l2 and r1/r2?There are many ways to solve this but I used Fenwick tree. The idea is to update each node in the Fenwick Tree with the first and second maximum indices for the elements in the array. Codevoid upd(int i, int val) { for(; i= bit[i][0]) { bit[i][1] = bit[i][0]; bit[i][0] = val; } else { bit[i][1] = max(bit[i][1], val); } } } pair que(int i) { pair res(-1, -1); for(; i>0; i-=i&-i) { if(bit[i][0] >= res.ff) { res.ss = res.ff; res.ff = bit[i][0]; res.ss = max(res.ss, bit[i][1]); } else { res.ss = max(res.ss, bit[i][0]); } } return res; } for(int i=0; i
»
4 weeks ago, # |
-11

I am unable to understand the reason for getting the following error in my code for Problem C 1988C][SUBMISSION:270720573 - Возрастающая последовательность с фиксированным ИЛИ

wrong answer Integer parameter [name=a[35]] equals to 1000000000000000000, violates the range [1, 999999999999999999] (test case 102)

The question specifies 1<= n <= 10^18, and that a(i) <= n

Here is my code:- ~~~~~

# include <bits/stdc++.h>

using namespace std;

int main() { int t; cin >> t; while(t--) { long long n, n2; cin >> n; n2 = n;

vector<long long> a;
vector<int> pos;

int size = 0;
while(n2>0) {
if(n2 & 1 == 1) pos.push_back(size);
n2 = n2 >> 1;
size++;
}

a.push_back(n);
for(int i=0; i<pos.size(); i++) {
long long x = n;
x = n - pow(2, pos[i]);
if(x!=0) a.push_back(x);
}

cout << a.size() << endl;
for(int i=a.size()-1; i>=0; i--) cout << a[i] << " ";
cout << endl;
}

} ~~~~~

The logic used here simply keep track of the places where the binary digit is 1 starting from position 0 at the right hand side (least significant bit).

Then I simply place 0 one by one in the in the positions where one are placed. For example: n = 1111, then

1111 1110 1101 1011 0111

Just shifting the 0 from right to left across all the positions that have 1, and keeping the position with zeroes as same.

If I have a n = 11100111, then

11100111 11100110 (0 placed at 0th pos from right) 11100101 (0 placed at 1st pos from right) 11100011 (2nd pos) 11000111 (5th pos) 10100111 (6th pos) 01100111 (7th pos)

I create the number with 0 in 6th pos by doing n — pow(2, 6) Which produces the same effect as placing 0 in the sixth position.

•  » » 4 weeks ago, # ^ |   0 use brackets every where when writing any bitwise operatorlike -> if((n2 & 1) == 1)
•  » » » 4 weeks ago, # ^ |   0 Made the changes. Still getting the same error. Here is the updated code int main() { int t; cin >> t; while(t--) { long long n, n2; cin >> n; n2 = n; vector a; vector pos; long long size = 0; while(n2>0) { if((n2 & 1) == 1) pos.push_back(size); n2 = (n2 >> 1); size++; } a.push_back(n); for(int i=0; i=0; i--) cout << a[i] << " "; cout << endl; } } 
•  » » 4 weeks ago, # ^ |   0 bro it's test case 102 with $n = 10^{18} - 1$ and your code outputs: 42 423539247696576512 711769623848288256 927942405962072064 963971202981036032 981985601490518016 990992800745259008 999859262511644672 999964815627911168 999982407813955584 999995601953488896 999997800976744448 999999450244186112 999999862561046528 999999931280523264 999999991410065408 999999995705032704 999999997852516352 999999999463129088 999999999932891136 999999999966445568 999999999983222784 999999999995805696 999999999997902848 999999999999868928 999999999999934464 999999999999967232 999999999999983616 999999999999991808 999999999999995904 999999999999997952 999999999999998976 999999999999999488 999999999999999744 999999999999999872 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 999999999999999999 
•  » » » 4 weeks ago, # ^ |   0 Thank you so much for your help. I understand the issue now.It is due to the precision of the floating point number returned by pow(2, pos[i])Thanks a lot once again
 » 4 weeks ago, # |   0 Missed B by just 1 more condition -_-
 » 4 weeks ago, # |   -10 why was this failing but if only I changed (n^(1< #define ll long long #define fori(n) for(long long i=0; i>t; while (t--) #define ld long double #define vl vector #define vint vector #define pb emplace_back #define fast ios::sync_with_stdio(0); cin.tie(0); using namespace std; int main() { testcases{ ll n; cin>>n; vector s; for(int i=60;i>=0;i--){ if((n>>i)&1)s.push_back(i); } if(s.size()==1){ cout<<1<
•  » » 4 weeks ago, # ^ |   0 because (1 << i) will overflow when i >= 31, use 1ll << i
•  » » » 4 weeks ago, # ^ |   0 Thank you
 » 4 weeks ago, # |   0 Can someone please explain what is going wrong in this solution? I tried to subtract the power of bits which were 1 in n from n.270761320
•  » » 4 weeks ago, # ^ |   0 Your code has 1<
•  » » » 4 weeks ago, # ^ |   0 Thank you
 » 4 weeks ago, # |   0 Wow, super fast editorial! Thanks!!
 » 4 weeks ago, # |   0 Another approach for B:Replace every clusters of 0's with a single 0 and leave 1's as it is, as we always want to increase the number of 1's in our string. Now, count the number of 1's and 0's in it. If 1's > 0's, then the answer is "yes" else "no".
 » 4 weeks ago, # |   0 in A how it , for n=772,k=295 step=3; by me in first step 772=295,295,185 then these three number can make 1 in 3 step so total step is 4
 » 4 weeks ago, # |   0 Finding it hard to understand Problem D Solution can someone point me to a different tutorial maybe video explanation ?
 » 4 weeks ago, # |   0 Interesting competition, I believe we needed like 30 min more for better distribution. Right now 7000 people competing solved first 3 proiblems and than only < 800 solved 4th. With bit more time I believe we would have like ~2000 people on 4th and that would give us a lot better distribution of scores.
 » 4 weeks ago, # |   +1 I am looking for help in problem D, because I had an alternative approach (semi-greedy) and can't find any counterexample.My algorithm goes as follows:While vertice count > 0: 1. Find a Maximum Weighted Independent Set (MWIS) in the remaining forest. 2. Remove all vertives belonging to MWIS from the forest.Maybe there is fundamental error in idea, maybe bug in implementation 270734719. Any help would be appreciated. Thanks.
•  » » 4 weeks ago, # ^ |   +1 45 4 4 51 22 33 4Try this one. The answer is 18 + 9 = 27.
•  » » » 4 weeks ago, # ^ |   +4 Thanks, now it looks very obvious.
•  » » 4 weeks ago, # ^ |   0 Having "big steps" is good, unless number of steps isn't much.For example you could finish everything in 2 steps, because tree is bipartite. Removing each part on each step. And it isn't obvious why you algo is better than that. That is the problem with your approach.
•  » » 4 weeks ago, # ^ |   0 here is a better idea, try proving your solutions instead of asking for counter cases :)
•  » » » 4 weeks ago, # ^ |   0 I got the same idea as https://mirror.codeforces.com/blog/entry/131567?#comment-1171248. Can you please help me with proving whether the solution is right or wrong without sample cases? Maybe taking the Maximal Weighted Independent Set every iteration is wrong, and sometimes a sub-optimal set currently can lead to a more optimal solution 1 or 2 iterations afterward. I can say these in words, but never visualize or prove.
 » 4 weeks ago, # | ← Rev. 2 →   0 My logic for C :- int right = 0; while(n!=0) { int rm = n & -n; n ^= rm; int x = n|right; if(x) v.push_back(x); right |= rm; }
 » 4 weeks ago, # |   0 I was trying to Upsolve D. I read the edi and got the DP approach. I coded it up and was constantly getting TLEs. I optimized a lot (converted map to vector for the adjacency list, included all fastio, used as less space as possible etc).I was still getting a TLE, so I had a look at my friend's solution who got an AC in the contest. It was literally the same thing. So I copy pasted it and that also got a TLE. What could be the reason for this ? Submission from my account: 270772292 Submission from friend's account: 270738230 Both the codes are literally the same.
•  » » 4 weeks ago, # ^ |   0 The language is a bit different + your friend's solution is not that fast in the first place so...
•  » » 4 weeks ago, # ^ |   0 i copy pasted your code and got AC 270774740 lol
 » 4 weeks ago, # |   0 https://mirror.codeforces.com/contest/1988/submission/270773130can anyone help what am i doing wrong above?
 » 4 weeks ago, # |   0 Another approach For b if we take all the sequences of 000 and combine them to form a single 0 then The resulting string would only have single 0 and other 1's so if we count no. Of 1's here and if they are greater then no. Of 0's then answer is YES else answer is NO.Can't think of a proof but it passed all test cases
•  » » 4 weeks ago, # ^ |   0 I did it too
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I had the same solution. The proof is pretty simple. Notice that after combining all zeros together you have a sequence where each zero is surrounded by ones. Suppose oneCount > zeroCount, by combining two ones with a zero, you decrease the total amount of 1s and 0s by one. If you repeat this over and over a again, you will reach a point where there is one zero and more than one one. Conversely, it is clear that if the number of zeros is more than or equal to the number of ones, the answer is NO.Edit: I just realized you can just choose the whole array :)
 » 4 weeks ago, # | ← Rev. 3 →   +2 my clarification for log(n) in problem D, I hope this help someone: suppose in the worst case that you have set of monsters with attack point equal to MX (for example 1e12) and these all nodes connected with all vertices in the tree, then the optimal choice for current round is to select these nodes, then number of nodes now is at least n/2, in the second round suppose the same that you have set of monsters with attack point equal for example MX-1 then best choice to select these nodes, and number of nodes now equal (n/2)/2 ... and so on then after the first round you have n/2 node after the second round you have (n/2)/2 node after the third round you have ((n/2)/2)/2 node .... and so on. then in the worst case there is log(n) rounds.then now easily you can use dp on tree from any node state: dp[u][r] which is you at node u and at round r transaction: move to each child with round equal any number from 1 to log(n) except current r and choose the minimum that is my code it may help: https://mirror.codeforces.com/contest/1988/submission/270781650
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by feecIe6418 (previous revision, new revision, compare).
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by feecIe6418 (previous revision, new revision, compare).
 » 4 weeks ago, # |   0 The description of Jiangly's solution in problem F has somthing wrong, we can't do $ans_{i+j}\leftarrow g(j,y)v_{i,x}$ without iterating $y$, and I guess that the translation shoulb be $v_{i,y}\leftarrow f(i,x)h_{x+y}$ and $ans_{i+j}\leftarrow g(j,y)v_{i,y}$.
•  » » 4 weeks ago, # ^ |   0 You're right, fixed
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by feecIe6418 (previous revision, new revision, compare).
 » 4 weeks ago, # |   0 https://mirror.codeforces.com/contest/1988/submission/270807781 where am i doing wrong cananyone please help me
•  » » 4 weeks ago, # ^ |   0 Here's a counter example for your code: 1 4 1000000000 1 1 1000000000 3 1 2 2 3 3 4 
•  » » » 4 weeks ago, # ^ |   +4 i got it thank you
 » 4 weeks ago, # |   0 guys in the proof of problem D, it is mentioned that: f(u) ≥ 1 + ∑ [1≤i
•  » » 2 weeks ago, # ^ |   +3 If I have understood your question correctly you are asking why the direct children can't have the number of days it takes them to be killed = u. Sorry if I have misinterpreted your question.Answer: If $u$ is being defined as the maximum number of days it takes to kill a monster then a node with value $u$ has to have at least one neighbour ($v_j$) where the number of days it takes for a node $v_j$ to die is equal to $i$ for $1 \le i < u$. The reason for the range being $1 \le i < u$ is because if there was a neighbour $v_j$ with value equal to $i$ for $1 \le i \le u$ then node $x$ wouldn't be allowed to have the value of $u$, because it is adjacent to a node $v_j$ which already has value $u$, which means that $x$ would have to take the value of $u + 1$ which contradicts the claim which states that $u$ is the largest value.Sorry again if I misunderstood your question.
 » 4 weeks ago, # | ← Rev. 2 →   0 for the problem B, the second solution is intuitive
 » 4 weeks ago, # |   0 Can someone say in general where to use min(a,b) instead of fmin(a,b).
 » 4 weeks ago, # | ← Rev. 2 →   0 .
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 my
 » 4 weeks ago, # |   0 Hello, guys. Could you help me with my problem? I don't understand why my solution throws an error (memory overrun).my code:270830415
 » 4 weeks ago, # |   +4 270730886 This was my code for D problem. The time complexity is O(nlogn) in my opinion but it is giving TLE in test case 20. Can anyone identify the issue in my code?
 » 4 weeks ago, # |   +3 This is one simulation to make you understand that nodes are destroyed in order on which value is assigned to it. So node having value i will be destroyed in round i. And way I have assigned values to nodes in such a way that you can make a conclusion that you there is a way to destroy node in more than 3 or 4 rounds. You will destroy node having assigned value i after node having j value where i>j .
 » 4 weeks ago, # | ← Rev. 3 →   0 for Dthis comment statement1(round=j, nodes left=2*a) => let's say we choose 'a' number of vertices (which is the max we can take without breaking the rule) in the jth round. hence, we must have 'a' number of other vertices to which jth round nodes have an edge with. nodes left=a or 2*b statement1(round=j+1, nodes left=2*b) size trend => n or 2*a, a or 2*b, b or 2*c, c or 2*d ...... or 2^i ,2^i-1, 2^i-2 .... 2^0here 'i' is the first round 2^i=ni=log(n)
 » 4 weeks ago, # |   0 why there is no option for feedback below each question? Some questions realllllly sucked.
 » 4 weeks ago, # |   0 Hello , can anybody explain why bi does not exceed log2(n)+1 . I tried to understand the proof of the editorial but I am having difficulty visualizing it. Any help would be appreciated . Thank you
 » 4 weeks ago, # | ← Rev. 2 →   0 Edit : The following proof is wrong!I have a different proof for maximum rounds in problem D.Consider a tree $T$ with $n$ nodes. We need to show that it can be processed in at most $\log_2 n + 1$ rounds.We can always remove at least one vertex. Let us assume it is the centroid of the tree. The tree then breaks into different components of at most $\frac{n}{2}$ size. We can apply operations on the each component simultaneously and independently.If $f(n)$ is the number of rounds for a tree with $n$ nodes, then we can say: $f(n) \leq f\left(\frac{n}{2}\right) + 1$By applying this recursively, we get: $f(n) \leq \log_2 n + 1$Thus, the number of rounds is at most $\log_2 n + 1$.Any feedback is appreciated!
•  » » 4 weeks ago, # ^ |   +1 Thanks for the explanation.
•  » » 4 weeks ago, # ^ |   0 I don't think your proof is correct. You are just demonstrating one way to finish the rounds in $Log(N)$ steps, by choosing centroid at each stage. But how do you ensure that the damage inflicted by other monsters is minimized? What if the centroid inflicts zero damage while other vertices inflict a lot of damage?In fact, using your same reasoning, I can show that $f(n) \leq 2$. In the first round, we remove all the odd levels, and in the second round we remove all even levels. Since I have a way to finish the game in 2 rounds, it doesn't mean that it's optimal.
•  » » » 4 weeks ago, # ^ |   0 Oh yes, you are right. I had a feeling that i was wrong and thus made a comment so someone could provide feedback. Thank You! Also I love the content you create, keep going :)
 » 4 weeks ago, # |   0 can someone please tell why Greedy don't work for Problem D? -> as in the given tree we can eliminate any number of monsters, with a condition that they should not be adjacent to each other. so in the first turn all monsters will attack and decrement health by total sum of attack power of all monsters but in this move we try to kill all those non-adjacent monsters whose attack sum is maximum and as tree do not contain any cycle therefore there is only two possible scenarios. i used BFS to calculate sum of attack power for both cases and return (total attack power + min of above two cases). -> can anyone please help me to figure out my logical error or what part i am missing, any reply would be appreciated. here's my code link :270855931
 » 4 weeks ago, # |   0 Please elaborate on the problem A. share a video link if possible.
 » 4 weeks ago, # | ← Rev. 10 →   0 Could someone point out what's wrong in this construction for E?My output for TC1: 0 4 7 5 19 21 37 17 19 79 100 72 68 67 106 73 80 Context — $l[i]$ stores the closest (to $a[i]$) smaller element to the left of i. $dl[i]$ stores the closest smaller element to the left of $l[i]$. Similar for right. Important part of the codeint pre[n]; memset(pre, 0, sizeof(pre)); // add x between l,r => adding x at l and removing x at r+1 from prefix array for(int i=0; i
 » 4 weeks ago, # | ← Rev. 3 →   0 thanks
 » 4 weeks ago, # |   0 what's the cf difficulty level of C problem? was it that easy for soo many 'people'?
 » 4 weeks ago, # | ← Rev. 2 →   0 Please someone point mistake in my solution of problem D. It is failing on 2nd test case https://mirror.codeforces.com/contest/1988/submission/270941262
 » 4 weeks ago, # |   0 hi everyone, I wanted to ask about 3rd Problem. I try to do and of n with ~(1 << i) such that i can off each set bit in n without affecting the other bit so that I can generate seq. of numbers whose or should be n but I am getting the wrong answer in test2. can someone please tell me what I am thinking wrong?here is code void solve(lli n){ if(n == 1){ cout << 1 << endl; cout << n << endl; return; } vector l; lli num_bits = (lli)log2(n); l.push_back(n); repI(i, 0, num_bits){ int a = (n & (~(1LL << i))); if(a < n) l.push_back(a); } sort(all(l)); cout << sz(l) << endl; repI(i, 0, sz(l)-1) cout << l[i] << " "; cout << endl; } `
 » 4 weeks ago, # |   0 I just wanted to ask something..Isn't the tree like structure inherit a hierarchy wrt to its root node?? So isn' it always possible that the maximum rounds of killing we would need is two?? Since if we choose to kill from currently selected root node then in first round, we could kill all the monsters positioned at odd levels including the root node itself , and in second round we could all the even level monsters, and now there would be no monsters left to kill. Similarly if we choose to kill from one level below the root node, i.e. from 2nd level then we could kill all the even level monsters in 1st round, and in 2nd round all the odd level monsters could be killed.So from any selected root node, we would always have exactly two ways to kill and in each way it would take exactly two round to kill all of them. And we would have n such ways to select the root node.So isn't our dp should really be: dp[v][0/1], where 0 represent choosing the root node 'v' in the first round, and 1 represents choosing it in the second round. I think this is all the possible ways of killing we could have.can someone verify this approach ?? Thanks.
 » 4 weeks ago, # | ← Rev. 2 →   0 For A, we can solve it like this : Merge n 1s into n and we can merge at most k 1s per time.So : f(n) = f(n — k) + 1, if n >= k f(n) = 1, if n < k. It's a $O(\frac n k)$ solution, I don't know how to convert this expression to an $O(1)$ expression.
 » 4 weeks ago, # |   0 bruv i spent 1 hour to solve the A problem but 15 minutes to come up with an answer for B (and an extra 30 minutes cuz i have skill issues)
 » 4 weeks ago, # | ← Rev. 2 →   0 Can anyone explain why the maximum number of rounds will be logN + 1 in problem D?
»
4 weeks ago, # |
-10

# define int long long

using namespace std; const int N=3e5+10; int t,n,v[N],a[N],f[N][2],up,x[N],y[N],sum; vector<vector> vec; void dfs(int p) { f[p][1]=v[p]; int len=vec[p].size(); for(int i=0; i<len; i++) { int son=vec[p][i]; dfs(son); f[p][1]+=f[son][0]; f[p][0]+=max(f[son][0],f[son][1]); } } signed main() { cin>>t; while(t--) { sum=0; cin>>n; for(int i=1; i<=n; i++) { a[i]=0; for(int j=0; j<2; j++) { f[i][j]=0; } } vec.resize(N); for(int i=1; i<=n; i++) { cin>>v[i]; sum+=v[i]; } for(int i=1; i<=n-1; i++) { cin>>x[i]>>y[i]; a[y[i]]++; } vector help; for(int i=1; i<=n; i++) { if(a[i]==0) help.push_back(i); } int len=help.size(); for(int i=0; i<len-1; i++) { int tem=help[i]; for(int j=1; j<=n; j++) { if(x[j]==tem&&a[y[j]]>1) { a[y[j]]--; swap(x[j],y[j]); break; } } } for(int i=1; i<=n-1; i++) { vec[x[i]].push_back(y[i]); } for(int i=1; i<=n; i++) { if(a[i]==0) up=i; } //cout<<"---------"<<up<<endl; dfs(up); cout<<sum-max(f[up][1],f[up][0])+sum<<endl; vec.clear(); } } //2 1 //1 4 //3 2 //5 3 //2 6 //7 5 //16 8521 1428 4732 0223 //2 1 //1 4 //3 2 //5 3 //2 6 //7 5
why my code is wrong

 » 4 weeks ago, # |   0 feecle6418 SpoilerLet the mex of a set be the smallest positive integer that does not appear in it. Note that in an optimal arrangement, bi=mex(j,i)∈Ebj.Consider an vertex with the maximum b , equal to u. Root the tree at this vertex x. The vertices connected with x should take all b-s from 1 to u−1. Denote f(u)as the minimum number of vertices to make this happen, we have f(1)=1, f(u)≥1+∑1≤i
 » 4 weeks ago, # |   0 Note that in an optimal arrangement, bi=mex(j,i)∈Ebj.okay, for root node, this is definitely true. but can someone give me the proof for every node?
•  » » 4 weeks ago, # ^ |   0 can you please explain me what is bi=mex(j,i)(=Ebj here... i am not able to think or understand what it is.
•  » » » 4 weeks ago, # ^ |   0 bi is just mex of all the nodes adjacent to the ith node.
•  » » 4 weeks ago, # ^ |   0 Let's call $\displaystyle m_i = \mathop{\mathrm{mex}}_{(j,i) \in E} b_j$.If $b_i < m_i$, then $b_i = b_j$ holds for some $j$, which is not allowed (in the round $b_i = b_j$, the monster $i$ and $j$ are killed at the same time, but there's an edge between $j$ and $i$). If $b_i > m_i$, the monster $i$ can be killed in an earlier round (specifically, in the round $m_i$), because no other adjacent monster is killed in the round $m_i$, so this $b_i$ is not optimal. Therefore, $b_i = m_i$.
 » 4 weeks ago, # |   0 If possible please someone provide an explanation, why at most rounds in problem D is ⌊log2n⌋+1 ??
•  » » 4 weeks ago, # ^ |   0
 » 4 weeks ago, # | ← Rev. 2 →   0 For Problem C the solution for testcase 1 has to be 2 i.e 0, 1It is because the bitwise OR of 0 and 1 is also 1, so the answer for 1 is 2 and the sequence is 0 1. Please clear my doubt...
 » 4 weeks ago, # |   0 Thks for the cool round!
 » 4 weeks ago, # |   0 For D, any ideas on how to approach this when the graph has cycle?
 » 3 weeks ago, # |   0 Hello! Can someone please explain why the upper bound for the number of rounds to kill all the monsters is not 4?What makes me think of this is because of Appel and Haken's 4 Color Theorem for loopless planar graphs. Any help and advice is greatly appreciated!
•  » » 3 weeks ago, # ^ |   0 You are ignoring the damage that the monsters who are not killed in round 1 would inflict. In fact, according to what you are thinking, the upper bound should be 2 (why not kill monsters at odd level in round 1 and monsters in even levels in round 2?). But this has the same flaw as the greedy solution in knapsack, i.e, keep picking highest valued items as long as the total weight is less than the capacity.But why is the upper bound $O(Log(n))$ regardless of the monster's damage? I talk about it in my video editorial
 » 3 weeks ago, # |   0 Aah ok
 » 3 weeks ago, # |   0 that was lol !!!
 » 5 days ago, # |   0 I used recursion and then memoized the solution using dp but I am still getting TLE on test 3. Plz help somebody !!!! :((((( Here is my solution 275618595