### waaitg's blog

By waaitg, history, 4 weeks ago,

1708A - Difference Operations

idea: Imakf

Solution
Code

1708B - Difference of GCDs

idea: waaitg

Solution
Code

1707A - Doremy's IQ

idea: Imakf

Solution
Code of solution 1
Code of solution 2

1707B - Difference Array

idea: Imakf and waaitg

Unfortunately, a harder version of this problem has appeared in a codechef contest here.

In fact, this problem was come up with more than 1 year ago, earlier than the problem in that codechef contest. We are sorry again.

Solution
Code

1707C - DFS Trees

idea: waaitg

Solution
Code

1707D - Partial Virtual Trees

idea: Imakf and waaitg

Solution
Code

1707E - Replace

idea: Wolam, Imakf and waaitg

Solution
Code

1707F - Bugaboo

This is a noun almost one year ago when this problem came out.

idea: Imakf and waaitg

Solution
Code

• +180

 » 4 weeks ago, # |   +65 c was tough today :/
•  » » 4 weeks ago, # ^ |   +3 Yeah lol, but it was really enjoyable for me (even though I didn't solve it)
•  » » » 4 weeks ago, # ^ |   +2 You ar so cute ^^
•  » » » » 4 weeks ago, # ^ |   +3 Thanks
•  » » » » 3 weeks ago, # ^ |   0 You ar so cute too ^^
•  » » » » » 3 weeks ago, # ^ |   0 ^^
•  » » 4 weeks ago, # ^ |   0 MOST CREATIVE QUESTION AFTER VERY LONG TIME THAT WAS AMAZING!!
•  » » 3 weeks ago, # ^ |   0 And second solution is godlevel!!!
 » 4 weeks ago, # | ← Rev. 4 →   +72 From testing, I had a solution for E that works in $O(n \log n)$ assuming some claim that I guessed is true. Unfortunately, no one could prove it's correctness nor find a counterexample. Here is the solution, hopefully someone can prove my claim :P SpoilerLet $A(l,r)$ be the answer for range $(l,r)$. Then it is easy to see that $A(l,r-1) \geq A(l,r)$ and $A(l+1,r) \geq A(l,r)$. Call $(l,r)$ important if both $A(l,r-1)>A(l,r)$ and $A(l+1,r) > A(l,r)$ are satisfied. We have implicitly found the entire $A$ if we know the important ranges and their respective answers.Claim: there are $O(n)$ important ranges, more specifically the bound is $2n-3$.I do not have a proof for this and just observed this from checking many arrays for small $n$. In fact, I don't think anyone was able to prove any bounds on the value of $A$ too.Anyways, we can now easily solve the problem with 0-1 bfs in $O(n \log^2 n)$ since it is simple 2D DS. If we bash DS more, we can surprisingly make it $O(n \log n)$. The key idea is that in the DS where we want to know the value of $A(l,r)$, it suffices to check if $A(l,r)=k$ for some $k$ that is non-decreasing across queries, which allows us to cut the log.Code: 164531480 (feel free to hack it)
•  » » 5 days ago, # ^ | ← Rev. 2 →   +10 I am able to prove a linear bound for it, but not able to prove the exact bound you mention.Here is a brief sketch of the proof. Consider the important segments at a given level, say $lvl$. By important segments at a level $lvl$, I mean all the important segments for which the answer is equal to $lvl$. So for $level=0, [0,n-1]$ is the only important segment, and so on. Now, a small detour — instead of looking at segments like $[l,l+1,...r]$ look at them as $[l,l+1],\cdots,[r-1,r]$. So, when I say the endpoints of a segment, I mean $[l,l+1]$ and $[r-1,r]$. If the segment has just two points, then it has only one unique endpoint. Now, consider that we're at level $lvl+1$, and we want to find all the important segments at this level. Then consider the end-points of all the important segments at all the previous levels (endpoint defined as above). My claim is that There can't be any important segment at $lvl+1$ that strictly contains any of these end-points. So, for any end-point, either it's outside of a segment at this level, or, it's the end-point for that segment, but it can't be strictly inside. Segments at the same level can only share up to an end-point. i.e. they can either be disjoint, or touch each other at a point, or have a common end-point (have two points in common) The proof of this claim is using induction. For the first part of the claim, say there was an important segment $[l',r']$ at this level strictly containing a previously occurred endpoint $[i,i+1]$. Then since this end-point must have been the end-point of some imp. segment previously, WLOG $[i, j]$ was the imp. segment at previous level. then, $f([i, j])$ must be either equal to the entire array, or it must contain some imp. segment $[a,b]$ at a previous level. Now, if its image contains some segment at a previous level, then notice that $f([i+1,j-1])$ must be strictly inside such a segment (not even touching the ends), more precisely, $f([i+1,j-1])\subseteq [a+1,b-1]$. If not, then there could have been a smaller segment containing this segment, which is a contradiction. Similar argument can be applied for when the image is equal to the entire array, as if $f([i+1,j-1])$ was touching any of the ends of the array, we would have had a smaller segment and the segment wouldn't be important.Now, $r  » 4 weeks ago, # | +68$a_i - a_{i-1}$forces  » 4 weeks ago, # | +54 It's been a while since there was a contest this stupidly difficult  » 4 weeks ago, # | +7 wow, thanks for superfast editorial  » 4 weeks ago, # | +53 Just listen to my absurd mistake in B: I thought both all$a[i]$and all$gcd(i, a[i])$should be different. When I realized my mistake, I solved the problem in like 1 minute. But before that, I spent more than one hour. •  » » 4 weeks ago, # ^ | +7 Same :" •  » » 4 weeks ago, # ^ | +4 Same •  » » » 3 weeks ago, # ^ | 0 same •  » » 4 weeks ago, # ^ | +7 Same. And I didn't realize until now Dropped about 150 rating :( •  » » » 4 weeks ago, # ^ | 0 dropped 1 :( •  » » 4 weeks ago, # ^ | +3 same •  » » 4 weeks ago, # ^ | 0 same uhhh •  » » 4 weeks ago, # ^ | 0 Exact same thing! Dropped 116 rating points. •  » » 4 weeks ago, # ^ | 0 Same :) •  » » 4 weeks ago, # ^ | 0 Me too •  » » 4 weeks ago, # ^ | -11 Unfortunately, same could have gained 200 rating points •  » » 4 weeks ago, # ^ | 0 for the first 15 min I was thinking the same then somehow I again read the question and realised what the trick was there .btw it is a good question •  » » 4 weeks ago, # ^ | 0 Yup. wasted a lot of time because of this •  » » 4 weeks ago, # ^ | 0 same :) •  » » 3 weeks ago, # ^ | 0 same •  » » 3 weeks ago, # ^ | 0 Same •  » » 3 weeks ago, # ^ | 0 same) I spent a couple of hours today solving this problem, then I gave up, read the editorial and I was like: "WTF, this won't work" and after 2-3 minutes reread the problem and realized my mistale :(  » 4 weeks ago, # | +10 woah new lesson learned: brute force sometimes does work  » 4 weeks ago, # | +1 I liked the idea of B. It is a good math problem for beginners. •  » » 4 weeks ago, # ^ | ← Rev. 2 → 0 I am a beginner but I solved B 4 minutes after A :P •  » » 10 days ago, # ^ | 0 B was easy, but many people thought that a[I] must be different •  » » » 10 days ago, # ^ | 0 I thought that too.  » 4 weeks ago, # | ← Rev. 2 → 0 Fine contest. I love problem 1707A(div2. c) and 1707B(div2. d) because they are interesting to solve. Thank you.  » 4 weeks ago, # | +94 Every single problem is great, but the whole problemset is disappointing. •  » » 4 weeks ago, # ^ | +6 Yes, exactly, it is too boring to have several problems with the same topic, especially ones like this.  » 4 weeks ago, # | +33 "DFS Trees" is essentially formulated as "given spanning tree of a graph, find all vertices for which the tree is a DFS-tree". This task is kind of folklore, I guess... Another interesting variation would be to find all vertices for which the given tree is a BFS-tree. •  » » 4 weeks ago, # ^ | +28 You look very similar to one of the greats..."Dale steyn" For Those Who Dont know •  » » » 4 weeks ago, # ^ | -18 chhoti sijindagi neyesamjhaya hai ki rishte sabse rakho lekin bharosa kisi par nhi. ye duniya saapon ki basti hai jo rishte bana kar dasti hai. yaha par bharosa bahut mehanga hai, lekin nafrat bilkul sasti hai. haa meri jaan •  » » 4 weeks ago, # ^ | 0 The MST detail ensures that we won't use an edge$(u, v)$before using the tree edges on the path between$u$and$v$. I think that makes the problem much easier. Does your solution work for any spanning tree? •  » » » 4 weeks ago, # ^ | 0 It depends on how you formulate it... If you're given unordered adjacency lists and you need to check whether there exists some ordering that the given spanning tree is a DFS tree, than the solution would be exactly the same, i.e. check that there are no cross edges for each starting vertex.I have a hunch that it should be possible to modify the algorithm when you're given specifically ordered adjacency lists, but I feel like it's going to be a bit more tedious...By the way, 102129F - Milliarium Aureum is formulated almost same as DFS trees, but asks to count vertices for which the given tree is a widest paths tree, rather than whether it is DFS/BFS tree.  » 4 weeks ago, # | 0 Able to solve only 1. •  » » 4 weeks ago, # ^ | 0 So was I. •  » » 4 weeks ago, # ^ | 0 me too  » 4 weeks ago, # | +1 In problem C solution 2, why is the greedy approach that she should test the contest since it will increase her iq valid? Since on one hand, it does increase her iq but also it makes her reach close to the limit q, beyond which she cannot test any contest. •  » » 4 weeks ago, # ^ | 0 You can use the same reasoning as in solution 1, that there is an optimal solution where all the skipping happens before the tests that decrease the IQ.  » 4 weeks ago, # | +6 Div.2 C Was SICK  » 4 weeks ago, # | ← Rev. 3 → +2 For Difference Array, I have another solution:First we have an$O(n^2)$simulation algorithm.Notice that The same$n$numbers will generate$n-1$zeros after the operation, while multiple identical numbers and one of this number will have the same effect (the difference is only the number of zeros at the beginning). As well as for a number$m>0$, which is a sum of distinct non-negtive numbers$a_i$. There can be at most$O(\sqrt m)$distinct numbers. For this problem$m$is$5\times 10^5$. We can de-duplicate the original sequence.Then there will be only$O(\sqrt m)$numbers left, in which case the simulation is performed, the complexity would be just$O(m)$. •  » » 4 weeks ago, # ^ | 0 can you send the code here •  » » » 4 weeks ago, # ^ | +1 164517652A bit ugly:) •  » » 4 weeks ago, # ^ | ← Rev. 2 → 0 Deleted •  » » 9 days ago, # ^ | 0 You say the complexity becomes O(m), how is this true? Shouldn't simulation be run N times, you can't just remove the leading zeros and simulate because they still effect your answer. Shouldn't the complexity be O(N * sqrt(m))? •  » » 6 days ago, # ^ | 0 Why are we neglecting zeroes ? For ex: If we have a = [0,0,2,5]. Then if we neglect 0's, we get [2,5]-> [3]. But, rather the last element should be 1 as [0,0,2,5] -> [0,2,3] -> [1,2] -> [1]. Can you please explain? •  » » » 5 days ago, # ^ | 0 I don't mean to say delete all 0s, but if there are many 0s, leave only one  » 4 weeks ago, # | +20 Why in problem 2C/1A, we should assume$Q = 0$at first, which is to say: why starting with$Q \neq 0$isn't optimized? •  » » 4 weeks ago, # ^ | ← Rev. 2 → +15 That's what I hate about cf editorials. Such very important details are always omitted and it is considered to be ok.I think we can reason like that.Imagine a chart q = q(i). It is a staircase.Lemma: of the equal values if you don't take some, taken always have greater indices than not taken, Otherwise you can swap them in this way and get result that is at least as good,Now consider that in optimal solution Q = x != 0. Look at the rightmost value you haven't taken. Take it. Obviously nothing is going to change on the left (from the taken value) of the chart because q remains the same there. What happens on the right? On the right all values are smaller than q by definition (you took the rightmost one) so you can still take them just the same even though q reduces by 1. Now you obtained just as good solution with Q = x — 1. By induction you can reduce it to Q = 0. So it is enough to always consider only Q=0.  » 4 weeks ago, # | ← Rev. 4 → +1 Might be helpful for somebody who is/was struggling with B (alternative idea): Just loop from 1 to n (let it be I) and for each I check whether L is divisible by I (L % I == 0) — if so ans[i] = L. Otherwise ans[i] = L + (I — (L % I)), it is basically the nearest number to L that is divisible by I. Code#include using namespace std; void solve() { int n, l, r; cin >> n >> l >> r; // for each i gcd(i, a[i]) should be equal i vector ans(n, -1); for (int i = n; i >= 1; i--) { int num = l % i; if (!num) { ans[i-1] = l; } else { ans[i-1] = l + (i - num); if (l + (i - num) > r) { cout << "NO\n"; return; } } } cout << "YES\n"; for (int num: ans) { cout << num << ' '; } cout << '\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { solve(); } }  •  » » 4 weeks ago, # ^ | 0 This is what I did! •  » » 3 weeks ago, # ^ | 0 You are so great! It help me to understand the hole process •  » » » 3 weeks ago, # ^ | 0 Happy to help :)  » 4 weeks ago, # | 0 https://codeforces.com/contest/1708/submission/164510862 Why my this submission working for problem D? I am not sure if it will pass the constraints.  » 4 weeks ago, # | 0 First seemed tough:(  » 4 weeks ago, # | +1 Today's C was quite hard !  » 4 weeks ago, # | ← Rev. 2 → +2 Finaly I'm Pupil! the round was cool, I really liked problem C. In my opinion idea of that problem was similar to This problem •  » » 4 weeks ago, # ^ | 0 but tbh at the beggining it was looking like that this contest was tricky  » 4 weeks ago, # | +6 wait Difference Array is brute force? :*)  » 4 weeks ago, # | +1 Anyone else failing test case 5509 on problem C? I would love to know what that case is •  » » 4 weeks ago, # ^ | 0 same bro •  » » 4 weeks ago, # ^ | 0 1 6 2 6 1 1 1 1 2 Your program prints 011111 instead of 111111. •  » » » 4 weeks ago, # ^ | 0 Thank you so much! •  » » » 4 weeks ago, # ^ | 0 Isn't it correct I thinking its printing correct output. •  » » » » 4 weeks ago, # ^ | 0 Got it •  » » » 2 weeks ago, # ^ | 0 How did you get the testcase ? I was doing the same mistake and sometimes it becomes difficult to think about the testcase where the code is failing. •  » » » » 2 weeks ago, # ^ | +3 Method 1: Here's a logic of wrong solution: Logic//if q >= a[i], always take //all numbers above current q are treated the same (bad) //we can see that if we choose to lower q by 1, how many bads will increase //we choose to lower iq when n - i <= q || if there is no increase in bads  Long and chaotic explanation follows (sorry for my bad English)Negate the incorrect assumption: now we have to find a case where it's optimal to lower iq despite n-i>q && there is an increase in "bads". So to break this let n=3 and q=2. Now you can see that for i=0 the first part of our new condition is true. Because we want have an increase in "bads" let a[0] be greater than q, so for example let a[0]=3. Let Doremy test this contest, so her iq drops to one. Now we have to prepare a[1] and a[2]. Because we want to make increase in "bads" after first contest, at least one of those values (a[1] or a[2]) has to be greater than current iq (1) and less or equal to previous iq (2). But if we make a[1]=2, unfortunately we won't get good testcase. So let a[2]=2. After last contest Doremy's iq will drop to zero(so it's optimal). Now we don't want a[1]'s value to bother us, so make it "easy" (for example 1). So our testcase is:1 3 2 3 1 2.Method 2 (simpler): His code failed on testcase 5477, so I've copied his code and replaced thiswhile(t--) { solve(); } with this int a=0; while(t--) { a++; if(a!=5477) solve(); else { int n,q; cin>>n>>q; vi a(n); For(i, 0, n) { cin >> a[i]; } cout<  » 4 weeks ago, # | 0 Really appreciate the quick editorial !!  » 4 weeks ago, # | 0 For those who solved problem C, can you guys explain how did you come up with the required observations during contest? •  » » 4 weeks ago, # ^ | +6 It was clear that after we reach last index it is useless to have q more than 1. So I thought of binary search because I was thinking like there will be a certain index after which we have to test every contest, but after thinking a bit I was not finding any monotonic behavior. So I thought of a simply greedy approach that we keep the q at index n, 1 and start traversing backwards and if a[n-1] >= q then we increase q else we keep the q same and when q becomes equal to original IQ we stop now all the places after this index will be 1 and before this index the values which are less then IQ will be one.Solution Link •  » » 4 weeks ago, # ^ | 0 Just brute force from all the possible variants) This problem was unexpectedly hard for me. •  » » » 4 weeks ago, # ^ | 0 Same here! I was not able to find a proper greedy solution during the contest. •  » » 4 weeks ago, # ^ | ← Rev. 3 → +7 I think I spent like, 20 minutes trying different ideas, but it all ultimately boiled down to "she can do at most q hard contests, which ones should she do?"The complication was that doing a hard contest early can cause some later contests to become hard (that otherwise wouldn't have been hard); this initially seemed really annoying at first, but then I realized that it simply means that doing a hard contest later is better than doing a hard contest earlier. This led to the result that the q hard contests for her to do should ideally be the last q hard contests that she encounters. In other words, once she loses her first point of IQ, she should not skip any more contests after this point. Once I mentally proved this (greedy exchange argument that skipping a hard contest B from after losing the first point of IQ cannot be better than skipping an earlier hard contest A instead), the biggest hurdle was overcome. There were still further issues (like how this can lead to solutions where she does fewer than q hard contests, but I had to assure myself that they're still optimal), since I didn't realize I could binary search and tried to process the vector in reverse, but I think at this point, a correct implementation should eventually fall in place regardless. My submission, FWIW: https://codeforces.com/contest/1708/submission/164517038(I kept imagining her derpy LoLK face as she makes her decisions and struggles on hard contests, but I'm not sure if this helped me realize the critical observations or distracted me from discovering them earlier) •  » » » 4 weeks ago, # ^ | 0 Dude, this was more helpful than editorial, for me!!  » 4 weeks ago, # | 0 Spent the whole time optimizing my indexed_multiset in C, only to realise just after the contest that binary searching the answer is sufficient. :( Nice bugaboos btw! •  » » 4 weeks ago, # ^ | 0 Were you able to solve the problem using the indexed multiset eventually?? If yes, can you please share the code. I was trying to implement the same idea of indexed set of pair(arr[i],i) but couldn't clear **testcase 3**. •  » » 4 weeks ago, # ^ | 0 I also spent the whole time for just finding out how to use the indexed_multiset, after which I was not even able to test it locally :(  » 4 weeks ago, # | +1 In case someone is interested, solution 1 of Div 1A can be done in linear complexity too. Let dp[i] be the minimum value of q such that we can test all contests from i....n-1. Then dp[n-1]=1 and dp[i] = (a[i]<=dp[i+1])?dp[i+1]:dp[i+1]+1. Now we can iterate over values of i -> we take all tests with a[i] <=q (this can be maintained using prefix sums) for indices <=i-1 and then add dp[i] to it, the value of i resulting in the largest sum will be optimal. •  » » 4 weeks ago, # ^ | 0 I always face problem on finding path from dp array, can you please explain that part too.And if possible please share some problems which requires this technique.Thanks in advance for your help  » 4 weeks ago, # | 0 Can someone explain C? •  » » 4 weeks ago, # ^ | ← Rev. 2 → 0 Lets say there are$k$elements such that$a_i <= q$. Now suppose the ans is$x$, therefore$x >= k$. So there are$e = x - k$extra elements that we need. The optimal way of choosing those$e$elements is to take them from the end of the array. So if we want to check whether it is possible to make$answer = x$then we can just simulate the process and see if it is possible to choose those extra$e$elements from the end of the array. Knowing this we can apply binary search to find the best answer.  » 4 weeks ago, # | 0 I would fail a phone screen very easily if the question was problem B  » 4 weeks ago, # | -28 This was the worst contest i've ever had  » 4 weeks ago, # | +3 This is the perfect example of editorial and solution to ruin a beginner's mind and crush their confidence ;-; •  » » 4 weeks ago, # ^ | 0 True bro I am not even understanding templates  » 4 weeks ago, # | +61 Can someone explain how to derive complexity in 1707B - Difference Array: So in each operation, you cost$O(nlogn)$time to sort the new array and decrease$S$by at least$n-1$.After the first operation,$S$is$O(a_n)$. The complexity is$O(AlogA)$, where$A=max(n, a_n)$. I understand first two sentences, but still struggle to understand why complexity is$AlogA$•  » » 4 weeks ago, # ^ | +3 Glad I'm not the only one who doesn't understand that. It should be explained in the editorial. •  » » 4 weeks ago, # ^ | ← Rev. 2 → +11 I assume this complexity is simply incorrect. Or correct in a strict definition of big-o notation, not the way we informally use it.Cause even author's solution from this editorial successfully passes codechef tests (the same problem) where A is limited by 10^18 •  » » » 4 weeks ago, # ^ | +17 True.I think the correct complexity would be$O(n\ log\ a_n)$, as described in codechef's solution  » 4 weeks ago, # | 0 did anyone solve div2 c using indexed set? if yes, can you please share the code. •  » » 4 weeks ago, # ^ | 0 What the heck is indexed set? •  » » » 4 weeks ago, # ^ | 0 typedef tree, null_type, less>, rb_tree_tag, tree_order_statistics_node_update> oset; This...  » 4 weeks ago, # | 0 For C i used this Logic: traversing forward (i=1 to n) if(a[i]<=q) then appear in the contest but if not: then check if any occorence of a[j] = q exists (j>i) if no such occurence then appear in the contest and q-- otherwise dont appear skip the contest(But if n-i<=q) regardlessly appear in the contest; Here is my submission : https://codeforces.com/contest/1708/submission/164519432 can anybody help me, it was not accepted and i cant find the error •  » » 4 weeks ago, # ^ | 0 Like if you consider a case like 5 5 5 5 5 5 5 5 5 5 5 5 5 2 1 1 1 1 1 and q =2, you will miss out at more 5 than considering 2. •  » » » 4 weeks ago, # ^ | 0 Thanks for helping man  » 4 weeks ago, # | -15 Unfortunately, a harder version of this problem has appeared in a codechef contest here.SAME PROBLEM •  » » 4 weeks ago, # ^ | ← Rev. 2 → +1 atleast look at the constraints before commenting •  » » » 4 weeks ago, # ^ | +6 Bro I submitted the same solution to both of these problems codechef codeforces •  » » » » 4 weeks ago, # ^ | ← Rev. 2 → +5 Funnily even the solution from codeforces editorial successfully passes codechef tests after a couple of algo-unrelated fixes.Which means that asymptotic analysys here was crap, no wonder no one understands it  » 4 weeks ago, # | 0 Can anybody tell me where i am doing wrong . or any optimization.. i tried greedy approach in 1708C - Doremy's IQ here's my submission 164541420 •  » » 4 weeks ago, # ^ | 0 Take a look at Ticket 15815 from CF Stress for a counter example.  » 4 weeks ago, # | ← Rev. 2 → 0 Please provide the sample test case for which my code is failing or just help me disprove my approach. Div2CApproachGTQ = count of elements in a(not yet chosen) greater than current q CNT[x] = count of elements in a(not yet chosen) equal to x, only needed for x <= qThese can be calculated in single pass.Now for i := 1 to nAlways test i if difficulty is <= q , set CNT[q]-=1 and continueIf a[i] > q ,reduce GTQ by 1, now test i if q > GTQ + CNT[q] , set GTQ+=CNT[q] and q-=1 and continue.This follows the same idea that atmost q tests with more difficulty can be tested and that the count of elements which are difficult don't exceed q with our choice.submission •  » » 4 weeks ago, # ^ | 0 I did the exact same thing but and got WA on third test •  » » 4 weeks ago, # ^ | 0 Input1 7 4 5 1 4 6 3 5 3  Expected Output0111111  Your Output1100111  •  » » » 4 weeks ago, # ^ | 0 Thank you!  » 4 weeks ago, # | +19 1707C - DFS Trees If findMST(x) creates an MST, there is no cross edge in the graph. Is there any explanation or proof about it? •  » » 4 weeks ago, # ^ | ← Rev. 3 → +16 Well, an MST is unique iff no non-MST edge can substitute an MST edge(we call edge included in MST MST edge) which weight is equal s.t. it's still an MST.(You can find Chinese version here.)The problem restricts weight of every edge different from each other, so the MST must be unique.So we've got the only MST tree and the corresponding MST edge. If we set an root rt in MST and any non-MST edge is cross-edge(Suppose two vertexes are u and v, and neither u is in subtree of v nor v in u), the MST mustn't be an DFS tree starting from rt since cross edge is not allowed to appear in DFS tree of an undirected graph. If not, the non-MST edge is bigger than any edge between u and v, it can't be reached since we visit smallest edge starting from current vertex first. •  » » » 4 weeks ago, # ^ | ← Rev. 4 → +16 Additionally, after proving the theorem above, we can find that a root is disqualified iff there exists one or more non-MST edge$(u,v)$so that the MST path between$u$and$v$($u,v$excluded)includes i.Thus, we can calculate how many non-MST edges make it disqualified for every vertices, costing$O(nm)$time in total.We can use Rerooting DP to optimize it. Firstly, calculate the number of cross edges for the case where root is 1. And then start a DFS. When we travel outwards from a path contributing to the answer or vice versa, we update the answer.UPD: I've found the previous algorithm having an incorrect time complexity and hacked with a graph with some vertex of high degree due to some bad implementation in the process of Rerooting DP.Sorry 4 misleading.I solved the bug with preprocessing toward which vertex it'll go into a path; however, introducing the Binary Lifting Algo on tree(without using finding LCA part) to find the$k$-th ancestor of every vertex, leading the running time to$O(m\log(n))$(excluding finding MST), similar to the official solution.Code: 164904402Hope anyone can come up with a solution to 1708E - DFS Trees to run in$O(m)$time in rerooting process, and it's still an "online" algo; i.e., getting the answers of most vertices during DFS, but not getting it to use algos like differencing and accumulating on tree. •  » » » » 4 weeks ago, # ^ | +5 got, thank you very much!  » 4 weeks ago, # | 0 For some reason, i made the stupid mistake of assuming that all the a_i need to be distinct for each i in problem B. I deserve getting demoted for that lol. •  » » 4 weeks ago, # ^ | 0 Yeah same! I eventually fixed it but glad to know I am not the only one  » 4 weeks ago, # | +124 Codeforces editorials be like: It is easy to see that apsodnvapowrbnapwoiv eo + awevoi ^ 23 + 34 = x/2. From this, obviously x + 239 vonwef oij 238 + ovw= 23t239ug 3ig --> 2039jjoi. Finally, we see that oawijpoi24n = 23gin 3p23 + 3gi2bj 9 )g3j. Now we can easily solve the probem in O(log n + m^xy + q) •  » » 4 weeks ago, # ^ | +14 typical chineese editorial  » 4 weeks ago, # | 0 can anyone pls tell me where does my code fail for the third problem?? I first marked all the numbers less than k as 1 and then I proceeded for greater numbers.https://codeforces.com/contest/1708/submission/164523613 •  » » 4 weeks ago, # ^ | +8 Take a look at Ticket 15814 from CF Stress for a counter example.  » 4 weeks ago, # | 0 Solution 2 of div2 C is the most enjoyable solution..  » 4 weeks ago, # | 0 Can Someone give me counter test for my submission for problem C Submission  » 4 weeks ago, # | +17 Alternative solution for Div1C:Each of the edges not in MST gives us a restriction on which vertices can be good. We can view those restrictions as values, i.e. for each edge we can either add 1 to all good vertices or subtract 1 from all bad vertices. In the end vertices with values equal to the total number of additions are good.The trick is that we actually don't need to update all good or all bad vertices for every edge, but just 2.Pick an any vertex$s$and run dfs on MST starting from$s$.Now suppose that we are at the some vertex$v$and there is an edge$(v, w)$in the original graph, but not in MST. We can also assume that we have already visited$w$, since edges are bidirectional.There are 2 cases:$w$is not an ancestor of$v$: the the only possible good vertices lie in subtrees of$v$and$w$, so we can increment values of$v$and$w$by$1w$is an ancestor of$v$: let$p$be an ancestor of$v$, such that$w$is the parent of$p$, then all vertices that are descendants of$p$, but not descendants of$v$are bad, so we can decrement value of$p$by$1$and increment value of$v$by$1$After that the values of each vertex$v$is sum of the values of vertices on the path between$v$and root$s$, so we can just run another dfs from$s$to calculate the answer.164545959 •  » » 4 weeks ago, # ^ | +1 thanks very much, the editorial's code is similar to your statement, but your statement is much clearer, more precise, and completer than the editorial's statement.some additions:for case 1, why other vertices are all bad? - because when they call findMST and reach v first, they will always reach w by add (v,w), which is not in MST. reach w first is vice versa.case 2 have similar reasons.  » 4 weeks ago, # | 0 Do you have a bound for the number of operations in Div1E? Some submissions are assuming$O(n\log n)$moves.  » 4 weeks ago, # | ← Rev. 2 → +77 Although, "brute-force" solution for div1B works for harder version($a_i$up to$10^{18}$) too.Theorem(TL, DR). "Brute-force" solution(considering zeros differently) has$O(n \log C)$time complexity.Statement. If we have$k$non-zeros after$d$iterations, then initial sequence had an element, which is at least$\left(\frac{k - 1}{d}\right)^d$.Proof. Suppose we have at least$k$non-zeros after$d$iterations. Then, after previous iteration we had an element greater or equal than$k$, moreover, lexicographically smallest possible sequence was$0, 1, 2, \ldots, k$. Two iterations before lexicographically smallest sequence was$0, 0, 1, 3, 6, 10, \ldots, C_{k}^2 $. By induction, we can prove, that$d$iterations before(at the beginning), lexicographically smallest possible sequence was$a_i = C_{i - 1}^d$, and thus$a_n \geqslant C_{k - 1}^d \geqslant \left( \frac{k - 1}{d} \right)^d$.UPD. Optimal sequence was not$a_i = C_{i - 1}^d + \ldots + C_{i - 1}^0$, but just$a_i = C_{i - 1}^d$, but theorem still holds.Picking$k = 2d + 1, d = \log_2 C + 1$yields$a_n > C$. So after$\log C + 1$iterations($O(n \log n)$each) there will be at most$2\log C + 3$non-zeros and thus total complexity is$O(n \log n \log C)$.But picking$k = \sqrt[3]{n}d + 1, d = \log_{\sqrt[3]{n}}C = \frac{3\log C}{\log n}$also yields$a_n > C$. After$O\left(\frac{\log C}{\log n}\right)$iterations we will have$O\left(\sqrt[3]{n} \frac{\log C}{\log n}\right)$non-zeros. It is still too small, so bound$O(k^2 \log k)$for the rest part of the algorithm is still good($O(n)$). And complexity of first$d$iterations is$O\left(n \log n \frac{\log C}{\log n}\right) = O(n \log C)$. Thus, we have upgraded our bound to$O(n \log C)$which is cool, actually.Just for some illustration, how optimal sequences look like:$0, 0, 0, 0, 1, 5, 15, 35, 70$$0, 0, 0, 1, 4, 10, 20, 35$$0, 0, 1, 3, 6, 10, 15$$0, 1, 2, 3, 4, 5$$1, 1, 1, 1, 1$•  » » 4 weeks ago, # ^ | ← Rev. 2 → +8 Yeah, I think my brute force is$O(n\log n\log V)$, too, where$n\log n$is the sorting complexity.However, my submission TLed on pretest 3.Can you tell me why? Ah, I see. I didn't ignore the 0's.That was kind of interesting. •  » » 4 weeks ago, # ^ | 0 Could you explain the transition from "one iteration before" to "two iterations before". I.e. where do binomials come from? •  » » » 4 weeks ago, # ^ | +3 I've made some mistake, the sequence it not a sum of binomials, but just binomials.But the method is the following: we are trying to "invert" an iteration. How'd we do it?$a_1, \ldots a_n \mapsto 0, a_1, a_1 + a_2, \ldots, (a_1 + \ldots + a_n)$$1, 1, 1, 1, 1 \to 0, 1, 2, 3, 4, 5$$0, 1, 2, 3, 4, 5, \to 0, 0, 1, 3, 6, 10, 15$Obviously, we will get the correct initial sequence, but why is it optimal?Statement. Let$f$be our transform,$\Delta$-- function, mapping sequence to its pairwise differences. Then for all$B$satisfying$\Delta(B) = A$,$B_i \geqslant f(A)_i$.Proof. Note, that we can assume, that any inversion$B$has form$0, a_{i_1}, a_{i_1} + a_{i_2}, \ldots, (a_{i_1} + \ldots + a_{i_n})$, where$i_1, \ldots, i_n$is some permutation of numbers$1, \ldots, n$.$a_{i_1} + \ldots + a_{i_k} \geqslant a_1 + \ldots + a_k$.Statement. If$A_i \leqslant B_i$, then$f(A)_i \leqslant f(B)_i$.So$f(f(\ldots f(A)\ldots))$gives us optimal sequence(any other has each element greater or equal to ours), and thus with least possible max element. •  » » 4 weeks ago, # ^ | 0 Very neat proof. I made a video solution on Problem D illustrating this proof. •  » » 3 weeks ago, # ^ | 0 thank you  » 4 weeks ago, # | ← Rev. 2 → 0 Video Solution for Problem C and Problem D  » 4 weeks ago, # | 0 Damn, problem B is so bad. The description of promble B misled me!  » 4 weeks ago, # | +36 To me, 1A is harder than 1BCD ... High quality round！  » 4 weeks ago, # | ← Rev. 2 → +16 I wish editorials could explain more about how to come up with such a solution instead of only proving why the solution works.  » 4 weeks ago, # | ← Rev. 2 → 0 In problem c , first if we find how many contest she will test, is there any method how we can choose the day and print them? my solution for finding number of contest she will test: codeint ans(int id,vll &v,int q) { int ok =0; if(q == 0) return 0; if(id == v.size()-1 && q == 0) { return 0; } else if(id == v.size()-1) return 1; if(v[id] <= q) ok++; int a=0,b=0; if(id < v.size()) a = ans(id+1,v,q-1)+1; if(id < v.size()) b = ans(id+1,v,q); ok += max(a,b); return ok; } » 4 weeks ago, # | -16 # include<bits/stdc++.h> using namespace std; typedef long long ll; signed main(){ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll t; cin>>t; while(t--){ ll n,j=1,l,r,flag=0;cin>>n>>l>>r; ll arr[n+1]={0}; for(ll i=l;i<=r;i++){ if(i%j==0){ arr[j]=i;j++; } } for(int i=1;i<=n;i++){ if(arr[i]!=0){flag++;} } if(flag==n){ cout<<"yes"<<endl; for(int i=1;i<=n;i++){cout<<arr[i]<<" ";} cout<<endl; } else{cout<<"no"<<endl;} } return 0; } •  » » 4 weeks ago, # ^ | 0 can anyone tell why this solution is giving runtime error i have checked multiple times but im not able to find..  » 4 weeks ago, # | 0 In question C why my answer for following test case is wrong :- 5 2 5 1 2 4 3 My answer is: 11101 , why this is incorrect pls anyone explain •  » » 4 weeks ago, # ^ | 0 5 2 5 1 2 4 3 Your answer : 11101 is actually invalid. Seems you missed the fact that after testing a round with ai>q the q will decrease by one. So from the next rounds you will have less q. Going by this logic, you will have q=0 by the time you reach the 4th round and you won't be able to test 4th and 5th round.  » 4 weeks ago, # | 0 How to prove question a of div2?  » 4 weeks ago, # | 0 even not able to solve C /kk  » 4 weeks ago, # | +10 For the solution 2 of 1707A :$a_i\gt Q$and$Q\lt q$. If Doremy tests the contest, her IQ will decrease by$1$, so in the reverse order, her IQ increases by$1$. Why? Lets say$a_i = Q+1$. Now if we increase the IQ by$1$at this point, it becomes$Q+1$which is equal to$a_i$. The former was in reverse order, but in the correct order what we are creating is after testing a contest with difficulty$Q+1$, Doremy's IQ dropped from$Q+1$to$Q$and that's incorrect. •  » » 4 weeks ago, # ^ | 0 In that case, you can actually increase the initial q value (from 0 to 1,2,3 and so on) until this kind of cases do not happen. If you do this, you will get the "real q", which, however, is the same as the q calculated by the editorial's algorithm.If your IQ still don't get to the upper bound after testing all round, you can also increase the initial q value. Also, this operation will not influence the contests you are able to test.Sorry that I didn't mention this in the editorial. My English wording is bad.  » 4 weeks ago, # | 0 How does people get such smaller code solutions for Div2 C? Me: Write 50+ lines of codes, yet WA Red coders and Other Smart guys: 4 0r 5lines of code, Hurrah! AC  » 4 weeks ago, # | 0 Can someone please explain the solution of B?  » 4 weeks ago, # | 0 E wa 7???  » 4 weeks ago, # | 0 Any idea how can I solve Div2C using DP? •  » » 4 weeks ago, # ^ | ← Rev. 2 → 0 i think it would give MLE.  » 4 weeks ago, # | ← Rev. 2 → +6 How can I reach the idea 'If findMST(x) creates an MST, there is no cross edge in the graph. So if you can determine whether there is a cross edge starting DFS from every node, the problem is solved.' at div1C?I knew the MST is fixed, and tried to find which vertex's rooted dfs tree includes edges not in the MST but tried tree dp and dfs to figure it out for every vertices and failed to reach that idea. •  » » 4 weeks ago, # ^ | ← Rev. 2 → +8 Since the MST is fixed, we know which edges are bad edges (not in the MST).Now given a bad edge, can we figure out the vertices$r$such that$\mathrm{findMST}(r)$will pick this edge?Observe that$\mathrm{findMST}(r)$is like a regular DFS, but with some extra logic to choose the order of exploring children. So for a moment, think of it to be a normal DFS.Since DFS explores all edges of a child before returning to its parent, if there is a bad edge from a vertex$u$currently being explored by the DFS algorithm, to an unvisited vertex$v$in a different subtree that is not its ancestor, the DFS algorithm will pick this edge and explore$v$(yielding an incorrect MST). This is nothing but a cross-edge.So the problem boils down to finding for which vertices$r$, none of the bad edges are cross-edges in$\mathrm{findMST}(r)$.  » 4 weeks ago, # | ← Rev. 2 → 0 typo in Div. 1 D? was$S_{x,i}=∑_{j≤i} dp_{x,i}$need???$S_{x,i}=∑_{j≤i} dp_{x,j}$ » 4 weeks ago, # | +3 Can someone explain why edge (u, v) is not a cross edge when DFS from t ? Definition from GFG: It is a edge which connects two node such that they do not have any ancestor and a descendant relationship between them. But isn't v a descendant for u in the DFS traversal?  » 4 weeks ago, # | +1 Anyone else failing test case 2161 on problem B?My submission :- https://codeforces.com/contest/1708/submission/164581294 •  » » 4 weeks ago, # ^ | +1 Now Accepted!  » 4 weeks ago, # | 0 Please someone explain Proble C of Div 2 — Doremy's IQ  » 4 weeks ago, # | +3 can someone explain problem D clearly as editorials are not clear enough about brute force approach  » 4 weeks ago, # | 0 The second question, I think the solution is wrong.. If the 2 numbers say two and 4 give same value per say 1000 they are mapped to the same number, how is it possible? the given code is giving wrong answer for the test case (9 1000 2000). Am I missing something please help me figure out the right solution.  » 4 weeks ago, # | 0 1D is quite interesting for me.  » 4 weeks ago, # | 0 In Div2 E (or Div1 C), I found out the cycle and find out the max weight of the edges on the cycle. suppose the max weight edge is between u-v, I traversed all the nodes in the cycle other than u-v, then I marked all the nodes in those subtrees as '0' in the final answer string. I am getting TLE for 7th Test case. Can anyone help?  » 4 weeks ago, # | 0 If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.Div 2 Div 1 Disclaimer: There is a quota of 1 request per 24 hours on the free plan.  » 4 weeks ago, # | ← Rev. 2 → +32 I was able to find out a test case where Isonan submission for Div1E: Replace fails.Submission: 164525375Ticket 15813Can someone hack it for me? Or let me know if I constructed an invalid test case? Thanks! •  » » 4 weeks ago, # ^ | +8 You were right.I didn't consider some corner cases...  » 4 weeks ago, # | ← Rev. 2 → 0 Div 2 problem D: Can somebody prove How it only require O(logn) operations to have array consist of <= 1 non zero elements.  » 4 weeks ago, # | 0 Can someone add details on how the time complexity of the Difference Array problem is reduced to NlogN (or a_n log a_n) instead of N^2logN?  » 4 weeks ago, # | 0 Hints for Div2C? •  » » 4 weeks ago, # ^ | 0 Think from the end  » 4 weeks ago, # | 0 A was tougher than B... Amazing!!!  » 4 weeks ago, # | 0 Does anyone know why solution might be not passing 1707B 3rd test? •  » » 4 weeks ago, # ^ | ← Rev. 2 → 0 Wondering if anyone had the same problemIf anyone wanna check my code: 164618343 •  » » » 4 weeks ago, # ^ | +1 Take a look at Ticket 15838 from CF Stress for a counter example. •  » » » » 4 weeks ago, # ^ | 0 I misclicked the problem, so i just wasted my request :( •  » » » » » 4 weeks ago, # ^ | +1 HaHa, no worries. I've reset it. You can try again. •  » » » » » » 4 weeks ago, # ^ | 0 Thank you very much!  » 4 weeks ago, # | +8 Can someone post a solution for 1B, it feels like the person who wrote the editorial didn't even solve the problem. •  » » 4 weeks ago, # ^ | ← Rev. 2 → 0 Basically, you keep track of where the first non-zero element is, and then perform the operations exactly as specified, except you start at the first non-zero element, i.e., start calculating differences and perform the sorting on the non-zero range (since the difference between 0s will be 0s and will remain at the left side of the array after sorting). The actual challenge to this problem is realizing that this will not exceed the time limit. It may seem impractical, since there are 100000 elements, each as large as 500000. But if you consider a single operation, the largest element before the operation is an upper bound on the sum of ALL elements after the operation, e.g., for n = 4,$(a_2 - a_1) + (a_3 - a_2) + (a_4 - a_3) = a_4 - a_1$. Basically, the values drop down really fast, and you get a lot of 0s quickly, making it practical to actually perform every operation on the non-zero elements directly. •  » » 2 weeks ago, # ^ | ← Rev. 3 → 0 After excluding the zeros lets say we have only non zero elements. a1 , a2 , a3 , .... , anLet S = a1 + a2 + ... + annow when we do one iteration our array becomes a2-a1 , a3-a2, ... , an — an-1so new sum is an — a1 = S — ( a1 + a2 + ... + an-1)S decreases least when (a1 + a2 + ... + an-1) = n-1 as all these elements are > 0So in each step S decreases by n-1.first it decreases by n-1 then n-2 ... (in worst case for us)and it will get to 0 fast.So bruteforce works.You can refer this : https://discuss.codechef.com/t/array-ops-editorial/100450/5  » 4 weeks ago, # | ← Rev. 2 → 0 In C, remember that with each >iq question, your iq reduces too. So if initially if some question had been <=iq, now it might not be so. That's something i didn't consider.  » 3 weeks ago, # | ← Rev. 3 → 0  Can i have an explain for this ? At problem A, if the entered array was 2 3 4 6 5 the writer code will generate "NO" but here i can make it possible! Note: index start from 1   Before any operations, the array is [2,3,4,6,5] Choose i=4, and the array becomes [2,3,4,2,5] Choose i=3, and the array becomes [2,3,1,2,5] Choose i=5, and the array becomes [2,3,1,2,3] Choose i=5, and the array becomes [2,3,1,2,1] Choose i=4, and the array becomes [2,3,1,1,1] Choose i=2, and the array becomes [2,1,1,1,1] ... and you can make 3 opeartion now to convert the ONE's to ZERO's so the result is : [2,0,0,0,0]  is there any wrong ?!  •  » » 3 weeks ago, # ^ | 0 All great, except for the fact your array ended up with [2,1,0,0,0] in reality and$A_2$is now in eternal misery being unable to change him/herself to$0\$
 » 3 weeks ago, # |   0 1E is really brilliant!
 » 3 weeks ago, # |   0 May I ask what is bin-up on tree?
•  » » 3 weeks ago, # ^ |   0 Binary uplifting
 » 3 weeks ago, # |   +1 Any List of Problems similar to Div2C?
 » 3 weeks ago, # |   +3 Found this explanation for 1707B - Difference Array to be much more intuitive and easy to understand : https://discuss.codechef.com/t/array-ops-editorial/100450/6
 » 3 weeks ago, # |   0 For B: Where does this equation come from? ai = ([l-1/i]+1*i Why do i have to subtract 1 from l and add one after dividing? pls help
 » 2 weeks ago, # |   0 Here is an approach for Div 2C Doremy's IQ :- We start with q as Doremy's current IQ. Then, we traverse the array of difficulties. If the difficulty of the i-th contest is less than or equal to q, then we include it in our answer. Else, we check whether including it in our answer will be beneficial or not. This can be done by comparing (1) the number of contests in the range (i+1)-th contest to n-th contest having difficulty less than or equal to q with (2) the number of contests in the same range having difficulty less than or equal to (q-1) plus 1 (for the i-th contest). If (1) is less than or equal to (2), then we include the i-th contest in our answer and decrement q by 1, and otherwise we exclude the i-th contest from our answer. Is this approach correct? If so, then how do we efficiently find the number of contests in a given range having difficulty less than or equal to some integer?
 » 2 weeks ago, # |   0 i very much like the solution 2 for C! thanks to the writer! its really great!