Hi Codeforces,

I've tried my best to make a different editorial, I wish you enjoy it ...

1746A - Maxmina

step by step solution
solution

1746B - Rebellion

step by step solution
solution

1746C - Permutation Operations

problem author: napstablook

step by step solution
solution

1746D - Paths on the Tree

problem author: AquaMoon, Cirno_9baka, mejiamejia, ChthollyNotaSeniorious, SSerxhs, TomiokapEace

single step solution
solution

1746E1 - Joking (Easy Version)

step by step solution
solution

1746E2 - Joking (Hard Version)

step by step solution
solution

1746F - Kazaee

step by step solution
solution

single step solution
solution
| Write comment?
 » 18 months ago, # |   +63 Nice Editorial!
•  » » 18 months ago, # ^ | ← Rev. 3 →   +12 Can someone please explain what is meant by balls passing through the subtree of node u in D Editorial
•  » » » 18 months ago, # ^ | ← Rev. 2 →   0 each path can be assumed as unique balls. Initially we start with k balls(paths) from the root, then at every instant we proceed to some child with a path, that is same as giving that ball to the child.
 » 18 months ago, # |   0 Can someone explain problem c in a different way? I don't understand what to do after computing the difference array.
•  » » 18 months ago, # ^ |   0 suppose that i-th number is x. so now if I add x to all the numbers to the right of x ,then all the numbers on right of x will become greater than x,so inversion due to x will remain in this new array; If I do it with every element of the array then there will be no inversions left.
•  » » 18 months ago, # ^ |   0 Here is another approach: https://codeforces.com/blog/entry/107978?#comment-963589 Solutionhttps://codeforces.com/contest/1746/submission/176334148 (skip to the main function)
•  » » 18 months ago, # ^ |   0 We will Divide the array into continues sub segment where every sub segment is increasing and we aim to make the array increasing because in this way we will have 0 inversion e.g. 1 6 2 5 3 4 We will Divide to 1 6 2 5 3 4 Now because its add so the order doesn't matter How to make it increasing if we add 6 after 6 we will guarantee that every number after 6 is greater than 6 and go to the next sub segment and add 5 after 5 and so on So the answer will be 1 1 1 1 5 3 For suffix ones I don't care because it will keep the order the same That its my solution i think it is intuitive
•  » » 18 months ago, # ^ |   0 An observation that could be made in any array is that if I try to remove/solve an inversion, it cannot affect the other inversions present in the array. eg. take array as 2 3 4 7 8 6 5 1. we have a(8,6) b(6,5) and c(5,1) as inversions. Let us first solve inversion b. So we don't touch 6 and add (1+2) to suffix at position 7. Now since we didn't touch 6, the difference b/w 8 and 6 remains the same. Also since we are applying operation to the whole suffix, the same amount will be added to both 5 and 1 . So the difference b/w them also remains the same. Hence we can greedily pick inversions which have smaller difference which can help us to solve the maximum of them.
•  » » » 18 months ago, # ^ |   0 can you explain how you add (1+2) to suffix at position 7?
•  » » » » 18 months ago, # ^ |   0 For each inversion we can store the difference and the index of the second element upon which we work. We sort this array and then for each inversion initialize the increment(x) as 0. till we reach x>diff we keep on adding ith value for ith operation and push the stored index in the array into our answer.  ll n; cin>>n; vector arr(n); a(i,0,n) cin>>arr[i]; vector> unfit; a(i,0,n-1){ if(arr[i]>=arr[i+1]) unfit.push_back({arr[i]-arr[i+1],i+2}); } sort(unfit.begin(),unfit.end()); queue q; a(i,1,n+1) q.push(i); vector ans; ll it = 0; for(auto pr: unfit){ ll x = 0; while(x<=pr.first && !q.empty()){ ans.push_back(pr.second); x+= q.front(); q.pop(); } } while(ans.size()
•  » » 18 months ago, # ^ | ← Rev. 2 →   +6 I used the following explanation to convince myself that the intended solution works:In a permutation of 1 to n, 1 is the smallest number. It is the worst victim of inversion because it is the smallest. It needs our help the most. Now we have n chances to help this victim. What should we do? Of course we should give it the biggest help. How to give the number 1 the biggest help? It is obvious to place it (its position) at the end of our answer array. This is because in our answer array, we add i to the element and its suffix. So, the number 1 needs the biggest help. The number 2 needs the second biggest help. The number n needs the least help.
•  » » 18 months ago, # ^ |   0 The easiest approach on problem C int n; cin >> n; vector ans(n); for(int i = 0; i < n; i ++){ int x; cin >> x; ans[n - x] = i + 1; } for(auto u : ans) cout << u << ' '; 
•  » » » 18 months ago, # ^ |   0 Yeah, I’m surprised this wasn’t the official solution. It guarantees that you are left with the array [n + 1] * n + d where d is some strictly non decreasing array.
•  » » » 3 months ago, # ^ |   0 how and why please
•  » » 18 months ago, # ^ |   0 If you applied operation at index j, all differences will still the same except at the position j — 1 because: 1. all what after this position will increase with the same value 2. all what before this position will still the sameNote that if you have n items in a, you will have n — 1 differences
 » 18 months ago, # |   0 Can anyone explain me why my solution for D is wrong. I gave stored max score of path starting from each node. Then I gave ceil(k/no of child) to first (k%no of child) greatest node and floor(k%no of child) to other nodes. My codehere
•  » » 18 months ago, # ^ |   +3 With the input 1 5 3 1 2 2 1 1 1 1 100 10 your code gives 116 when the correct answer is 124.The problem is that the maximum score of a path through vertex 2 is 102 (path 1-2-4), but once you have already sent a path that way, the next path is forced to go through vertex 3 instead of 4, so it has score 3. Instead, on the other branch, every path has cost 11.
•  » » » 18 months ago, # ^ | ← Rev. 3 →   +5 Okay I get it now!
 » 18 months ago, # |   +3 I think there is a typo in solution of step 4 for problem C. It should be ${a_{i + 1} > 0}$
•  » » 18 months ago, # ^ |   0 fixed, thanks
•  » » » 15 months ago, # ^ |   0 Hey, I think Problem B just need count the number 1 less than indices which is first non-zero element's indices in the sorted array.
•  » » » » 15 months ago, # ^ |   0 there are many answers, but if I want to be honest I choose this because it was easy to proof! thanks
 » 18 months ago, # |   0 The code of D isn't clear enough to be understood, can anyone provide clean code?
•  » » 18 months ago, # ^ |   0
•  » » 18 months ago, # ^ |   0 It would be better if he provided hints and steps.
 » 18 months ago, # |   0 Thank you for this contest and interesting problems.However, please proof-read the statements in the verdict as well.For E1, the wrong answer prints this statement: "you can't guess the answer in 2 chance!" And this led me to assume that I'm not allowed to guess the answer in 2nd chance.
 » 18 months ago, # |   +4 When I thought about doing DP for D, it looked that for each vertex with n children and p paths to distribute, we had an exponential number of ways to choose n%p ones from the n children.So one key observation is that larger number of paths always produce larger scores, so we can use greedy as shown in the editorial.
 » 18 months ago, # | ← Rev. 2 →   0 For Problem D, it turns out that if I always calculate DP(child[v][i], k/cnt_child+1) no matter whether k%cnt_child or not, then I might get TLE (I'm using C++ std::map to represent the second dimension of the dp array). So it looks that this optimization is necessary?
•  » » 18 months ago, # ^ |   +13 Yes, consider a chain.
•  » » 18 months ago, # ^ |   0 I came up with an example: if k = 5,6 and cnt = 3, then if we compute both k/cnt and k/cnt + 1 then the result will be 1, 2, 3 which will result in an exponential number of states.
•  » » 18 months ago, # ^ |   0 Can somebody elaborate more on why this is happening? I mean at-most, we are calculating 2n states, why TLE then?
•  » » » 18 months ago, # ^ |   0 That's because the number of states may not be 2n.When k%cnt == 0, ${\lfloor k/cnt\rfloor, \lceil k/cnt\rceil, \lfloor (k+1)/cnt\rfloor, \lceil (k+1)/cnt\rceil}$ contains 2 numbers, but k/cnt, k/cnt+1, (k+1)/cnt, (k+1)/cnt+1 could contain more than 2 numbers, which results in a chain of exponential numbers of states.
 » 18 months ago, # |   -6 I just recieved a message about coincidence with solutions and i admit that everything is my fault, i saw a solution on ideone.com and copied to sumbit.
•  » » 18 months ago, # ^ |   0 A different "ideone" response for a change...
 » 18 months ago, # |   +1 Hi MohammadParsaElahimanesh, I think you should explain why many solutions got FST on C, many of them would be unable to figure it out why it's wrong.Thanks
•  » » 18 months ago, # ^ |   0 One of my friend assumed that in the answer $a_{i-1} •  » » » 18 months ago, # ^ | +1 Oh, I also got hacked in a similar type of case a few contests back on the Array Recovery Problem:(Did your friend failed TC 46? •  » » 18 months ago, # ^ | 0 Hi, sorry but can you explain FST (I'm not familiar with) :) my guess: (Fail Sample Test) •  » » » 18 months ago, # ^ | 0 some solutions be Hacked with 1 8 8 1 7 6 5 4 3 2 1  •  » » » 18 months ago, # ^ | 0 Fail System Test afaik •  » » » » 18 months ago, # ^ | 0 thanks,above test may help you.  » 18 months ago, # | +8 In solution for D, the fourth paragraph, should$\lceil (x/num)\rceil$be$\lceil (x+1)/num\rceil$? •  » » 18 months ago, # ^ | 0 fixed, thanks  » 18 months ago, # | 0 Can G be solved with simulate cost flow?  » 18 months ago, # | ← Rev. 2 → +21 I solved problem D purely recursively (it's still DP, but simple enough to not need a separate array for each node), in a similar manner as described in the editorial, but with a twist. All children will have the same amount of paths. If there's a remainder$r$from the division, then you'll be able to choose$r$children, with a path going through each of them (on top of the ones that you know from the division, that you have to take). To maximize my score, I want to have the best path that goes through each children. This way, I may be able to pick the$r$best ones for my score. But if I do that, I cannot use these paths again. If I were to, the condition would no longer hold, because the difference of$c_i$would be bigger than 1. So recursively, I can return the sum of the scores each descendant calculated, but also add all the$r$best paths that my children reported were the best available ones. That is to say, if I have$m$children, with the list of the best$m$paths returned by each of them in the recursion, I take the$r$best ones for the sum. After that, I'll return both the acquired sum, and "the best path that goes through the current node", which in reality is the best one remaining in the best path list, after taking$r$of them, with the current node's score added in. This way, I'll be telling my parent the best path that goes through the node, that's available to take for any of my ancestors. And note that I'll always have a path remaining in the list, because$r < m$, as the division was done by splitting between$m$nodes in the first place. Here's my code: 176372281I have declared an array called "maxToHere", but I didn't need to use it after all. and forgot to remove it in contest. •  » » 18 months ago, # ^ | 0 Can you tell me what's wrong in my approach. For choosing which k%child children will get +1 extra path, I was finding X = (max score sum path starting from child and ending at any leaf node), then I gave +1 extra path to k%child children having largest value of X. •  » » » 18 months ago, # ^ | 0 Look at this WA I had during contest: 176361876Compare the differences between this code and the one that gives AC I linked above. That may help you understand what I mean with available path. •  » » 18 months ago, # ^ | 0 dp doesn't mean having some array. what you do is still dp, and it calculates same states. •  » » » 18 months ago, # ^ | 0 I mean, I know almost any kind of memoization tends to be DP. For example, you could say that prefix sum is indeed DP, but it's as simple as just using a for loop.What I meant to say is that you could skip checking multiple states for each node, with this sort of "greedy" approach, and avoid using a "dp" array altogether. The states are simple enough to make it recursive, but I understand your point.In this case then, states are for each node are$(sum, maxpath)$, where:$sum$is the sum of$c_i s_i$known for all descendants (and itself).$maxpath$is the max sum of$s_i$for an "available" path starting in the current node to a certain leaf. An available path is one such that if it's chosen for the multiset, the condition still holds with all decisions already done for all descendants. It's a matter of something that you would surely call "DP on tree", becomes more like just "divide and conquer". The states explained like that may seem more clear to understand (or maybe not), but in this case I prefer to think of the process you go through to get to the solution approach. Nevertheless, I guess I will remove the parentheses in the previous comment to avoid confusion.  » 18 months ago, # | +3 I get wrong answer on test 3 for problem F because I use rand() instead of mt19937. TAT  » 18 months ago, # | ← Rev. 2 → +199 the probability will be less than$\frac{1}{2^{30}}$which is reasonable for problem constrains Is it?For such an argument the constraints should include the number of test cases. As it was not public during the contest, I felt this was not reasonable.$(1 - 300000 \times 2^{-30})^m$is about$0.97$for$m = 100$cases or$0.76$for$m = 1000$cases. I won't be happy to lose a whole score with this uncertainty.In general — I always think that for problems with intended solutions being randomized, an upper bound on the number of test cases should be disclosed, or there should be no system tests (and no hacks). And since this can suggest the crucial idea of randomized solutions, it might be a good way to have a rule about global upper bound on the number of test cases. (... or does it exist somewhere I don't know?) •  » » 18 months ago, # ^ | ← Rev. 2 → -52 you are correct, but I think there is a limit on m naturally(but rules must contain it), I never saw problem with m more than 300 anyway and also consider all of (300000) queries are not on type 2(also in many queries probability is 1/k30 and k >= 3).at end you could use 35 instead of 30, I myself use 50 in main solution(because it is model solution)I'm sorry, you were unlucky •  » » » 18 months ago, # ^ | +35 Check out this freaking problem with 753 test cases 1566G — Four VerticesWhat makes it more funny is testdata is weak so some of the solution got uphacked. 128646349 •  » » 18 months ago, # ^ | +10 Like 998244353 problems lol  » 18 months ago, # | +29 For E, when you're down to three candidates, you can eliminate one with only 3 queries: First query$a$. If the answer is NO, then query$a$again. If it's still a NO, then eliminate$a$and we're done. When we get YES for$a$, then query$b$immediately after that. If the answer is also YES, then eliminate$c$. If the answer is NO, then eliminate$b$. •  » » 18 months ago, # ^ | 0 great, we use it in E2 » 18 months ago, # | +12 Finally noticed this in Problem C after being dumbfounded yesterday: #### "...all of its elements by 1 i" •  » » 18 months ago, # ^ | 0 I notice this after reading your commentI fill terrible •  » » 18 months ago, # ^ | 0 wasted 30 mins on this! :) Got a sweet FST! •  » » 18 months ago, # ^ | 0 In the explanation of test sample 1, there is this line: The final array [11,12,13,14] contains 0 inversions. We must be adding i, not 1, for each operation in order to reach these numbers.  » 18 months ago, # | +6 Is it just me, or editorials in codeforces are actually very bad? •  » » 18 months ago, # ^ | ← Rev. 2 → +3 It's not just you. It's at least two of us.I think the reason is simple. There is some quality control for problems but there is none for editorials. Global rounds usually still have better editorials than ordinary ones though •  » » 18 months ago, # ^ | 0 Still usually much better than in atcoder •  » » » 18 months ago, # ^ | 0 Strangely I feel the opposite tbh.  » 18 months ago, # | 0 Can anyone say about the second question. I am not able to understand it •  » » 18 months ago, # ^ | 0 Yes if someone would explain it in simple sentences it would be much appreciated! •  » » » 18 months ago, # ^ | ← Rev. 2 → 0 I have no idea what is described in the editorial. Here is my solution. SolutionIt's easy to see that for sorted array if you increase last element it's still sorted. Similarly, if you decrease first element it's still sorted. Taking into account that initial array consists of only zeroes and ones, this means you can reduce first 1 to 0 and increase last element repeatedly until array is sorted. It feels dumb. You can do better. Each 1 you take is good enough to fill gaps like 1 0 1 -> 1 1 1. But then notice that for gap 1 0 0 0 1 you want three ones. But what if test like this: 0 1 1 0 0 0 1? You can do following: 0 1 1 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 1 1 In other words, just two pointers approach. First pointer looking for one forwards, and second pointer looking for zero backwards. Then, move 1 -> 0 and it will make array better. I'm lazy to prove it.Submission: 176323431  » 18 months ago, # | ← Rev. 2 → 0 For Problem B- I simply counted the number of 1s in the array, and all those elements should be at the right of the array, and the max element can be only 1 to AC your solution. Suppose n=10, and C(1)=5. Then all these one should be at the end of the array(i.e. index 6-10). So we directly have to count the number of 0s from the index n-c to n, and that's the answer.Solution  » 18 months ago, # | +1 In problem D, can anyone explain the difference between ⌈x/num⌉ and ⌈(x/num)⌉? •  » » 18 months ago, # ^ | 0 There is no difference... is that written somewhere in the editorial? I suppose it may have been edited afterwards.  » 18 months ago, # | +5 In question E1 what if one is YES and other is NO . Any one of them can be a lie , In step 4 they have only mentioned the cases where both are either YES or NO. •  » » 18 months ago, # ^ | 0 Did you mean step 3? In any case, what's important here is that they cannot both be lies. If you have sets$A$,$B$,$C$, and$D$, you can query$A \cup B$and then query$A \cup C$. There are four possibilities: both NO: Target is not in A first NO, second YES: Target is not in B first YES, second NO: Target is not in C both YES: Target is not in D In all cases, we can eliminate one of the four sets. •  » » » 17 months ago, # ^ | ← Rev. 3 → 0 I could easily understand (NO,NO), (YES,YES), but had difficulty in (NO,YES) and (YES,NO) cases.For this, we can think along the following lines - In AUB and AUC, if it says (NO,NO) we can definitely tell that one of them is correct and since A is common to both, the number definitely won't be in A. Some stuff in logic (1) AUBUCUD = Universe (2) if S is YES, then (Universe — S) is NO.using (1) and (2), we can have AUB is YES => (Universe — AUB) is NO => CUD is NO Now, we can determine for all cases. For example, when there is (YES,NO) AUB is YES => CUD is NO AUC is NO ------------------------- C is common. Thus, definitely not in C  » 18 months ago, # | +9 1746D - Paths on the Tree editorial is awful. You should at least mention that we solve it by dp over subtrees. Then, give an idea how to calculate value, and why it works. I would also mention why all balls should reach leafs. Also I would like to see proof of claim about floors and ceils. spoilerMy answer to how to calculate state of dp: you may think of it as all have$\lfloor x/num \rfloor$, and those who will have$\lceil x/num \rceil$will be upgraded with bonus$f(u, \lceil x/num \rceil) - f(u, \lfloor x/num \rfloor)$. We want maximum bonus, so pick nodes with maximum bonus. Not hard to see why it works, even if bonus could be negative. But I don't know is it working to sort by$f(u, \lceil x/num \rceil)$. •  » » 18 months ago, # ^ | +12 I would like to see the proof on the floors/ceils as well. The suggested solution was the first thing that came to my mind, but I didn't know how many different choices I'd need to consider for each node. I was only able to observe that there are at most two values when$num = 2$through considerable case analysis, and didn't know how the result would extend to larger divisors, and didn't feel comfortable with coding it when this number was unknown, as it would have significantly affected how the DP is set up (and I was worried there would be too many to pass the time limit). •  » » » 12 months ago, # ^ | 0  » 18 months ago, # | 0 Why is D: 176443434 TLEing •  » » 18 months ago, # ^ | 0 If dp[node][k] is 0, you cannot check if it was searched before correctly. •  » » » 18 months ago, # ^ | 0 In my solution, I had used dp.count({node,k}) to check if a state had been visited before and it still gave TLE. Are there any problems caused by count function too? 176444934 •  » » » » 18 months ago, # ^ | ← Rev. 2 → +6 If ch is a divisor of k, do not search dfs(it, x + 1).Because it will make 2 states to 3 states, and it will have an exponential growth.  » 18 months ago, # | ← Rev. 2 → +3 Problem D-->1746D - Paths on the Tree,I spent several hours trying to find the problem in my code, but it didn't work. Who can tell me what the error is in my code, and I still can't pass the second text case-->176451251  » 18 months ago, # | +3 I want to share my alternative solution to 1746E1 - Joking (Easy Version) DetailsI will use following notation: a — means query a returned NO, and A — means query a returned YES.Notice aa — tells us a = NO. And AA tells us a = YES. But, you can't be sure you get aa or AA, so you may get aA or Aa and it doesn't tell anything. Next: aAA will tell a is YES, but you can get aAa and get nothing again.So next my idea was aAbb -> at least give us b = NO. Or we can get aAbB, and you may guess a = b. But no! until the end of contest and several hours after I thought aAbB means a = b, but it's wrong. In terms of truth sequence aAbB may be false true true false, so a = YES and b = NO is possible, and it's not easy to tell.Then, next my idea was to ask a twice again, in other words: aAbBaA. In this case indeed a = b. What else could be? it could be aAbBA, then a = YES for sure. otherwise we get: true, false, ?, ?, false. And two question marks should be opposite, so either we get two false from left or two false from right.So, in 6 steps we can get either two same answers at once and tell about one question answer for sure. Or we can get relation a = b in case aAbBaA, or a != b in case aABbaA. Then, grab all relations of a = b and a != b and if they all connected in terms of graph, we can set value to one question a and then derive all other questions. This was main idea. But 6 steps is way to inefficient. But we can get answers for 17 questions about each bit and get result in 6*17 = 102 questions. Single question has all numbers where i-th is set.Surprisingly, we can 'trim' useless questions: if we ask a, then b twice, we can get either: abb, aBB, Abb, ABB — where we can tell truth of b. otherwise we can ask a again and get: abBa, aBba, AbBA, ABbA — here two a answered the same, and they can't be both false, because of similar argument about two question marks enclosed in two false. Thus here we know truth about a. abBB, aBbB, AbBa, ABba — here is easy to show that in some cases should be definitely a = b, or definitely a != b. So we can make graph from 17 questions about each bit, and fix single unknown and derive everything else. It require at most 17 * 4 queries.Submission: 176399636 •  » » 18 months ago, # ^ | 0 abBB, aBbB, AbBa, ABba — here is easy to show that in some cases should be definitely a = b, or definitely a != b. I think the first two here should be abBA and aBbA?Anyway, this is a very interesting approach! I don't think we need to actually build a graph; we can, for example, set the first bit as a base and then ask questions in a chain like abbaccaddaeea... to determine other bits exactly or at least their relation to the base bit. When we determine the value of the base bit (Case 2), we update the previous bits that depended on it, set a new bit as the base bit, and start a new chain with it. Even if we cover 17 bits without determining whether the latest base bit is 0 or 1, we have two guesses to try both options.I considered whether this can be adapted to solve E2, but I think the worst-case would be if we keep hitting Case 2 and reset the base, requiring$4 * 16 = 64$questions. We don't need to determine the remaining one, since we have two guesses. However, this kind of "base reset" does not take advantage of the last element of the chain, e.g., if we get abBa, we might be able to utilize the last a somehow to keep the chain connected when we change the base. It might be possible somehow to avoid disconnecting the chain, allowing for 3 additional queries per bit (plus 1 to start the first one), resulting in 49 queries (suffices for E2). •  » » » 18 months ago, # ^ | 0 We don't know about bits inside graph, only their relation. This is why we also need to check 17-th bit, because we either will know its value or relation. We do two guesses to try both possibilities for some node in graph. If you have proof of work in 49 queries I would like to look at it.  » 18 months ago, # | 0 Problem B easier Solution While an array starts with 0 or ends with 1, we delete that element, as it doesn't change an answer. In this step we have an array which must be empty or it starts with 1 and ends with 0. We exchange these values (or simply delete both elements), and we count this operation, and then go to step 1, if array is not empty. Output the number of operations we did in step 2.Code in Perl — 176389143 •  » » 18 months ago, # ^ | +8 OMG, I haven't ever seen code in Perl, it looks like you wrote random symbols from your keyboard. Could you write a pseudocode in English? •  » » » 18 months ago, # ^ | 0 'Pseudocode'Initially you have an array ARRAY and counter COUNT (initial value is zero). WHILE ARRAY is not EMPTY DO ---- SHIFT ARRAY and CONTINUE IF the first element of an ARRAY is '0' ---- POP ARRAY and CONTINUE IF the last element of an ARRAY is '1' ---- increase COUNTER by 1 ---- SHIFT ARRAY, POP ARRAY END WHILE PRINT COUNT  » 18 months ago, # | 0 For D,how to strictly prove that the number of states is O(n)?  » 18 months ago, # | ← Rev. 2 → 0 GOT IT!!!  » 18 months ago, # | ← Rev. 2 → 0 Here is an interesting problem that I initially misread C to be — instead of increasing the all elements of the suffix by$i$, we increase them by$1$in each operation. I've been thinking about this question and don't seem to be able to come up with a solution. Any ideas?  » 18 months ago, # | +8 F can also be solved with a slightly different randomized solution. Let's create$k$random maps$f_1, \ldots, f_k$from the numbers in the array to, say, 32-bit integers. Then, we can check that a subarray satisfies the property for given$k$by finding the sum of$f_i(a_l) + \cdots + f_i(a_r)$for all$i$. All these sums have to be divisible by$k$, and the converse is true with very high probability. •  » » 18 months ago, # ^ | ← Rev. 2 → 0 ivan100sic can you please provide some explanation with examples? for eg if a[l..r] is: {1,1,1,2,2,2,3,3,3,3,3,3} for k=3 then for each random maps the sum will be divisible by k, but the answer is "NO". please let me know in case if I miss anything. •  » » » 18 months ago, # ^ | 0 You're not summing$a_i$but$f(a_i)$which are random.  » 18 months ago, # | 0 I am struggling with problem D for days and my solution didn't accepted till now, can any one figure out what is the problem with my code ? Any help will be appreciated. •  » » 18 months ago, # ^ | ← Rev. 2 → 0 understood finally, the optimal is sort according to the differences not the values.  » 18 months ago, # | 0 I have a confusion. The editorial for problem D says that, for a certain tree structure, a particular node can have ONLY two possible values of cnt which is why we only need to work with a certain node for 2 times and save it in a memory because we might encounter the same state later. So according to the solution provided, for a certain node i, answer[i] is a vector which has size not more than 2. right? If so far what i understood is true, how can i logically prove that there are only two possible values of cnt for a certain node? Is there an intuitive way to prove this? •  » » 18 months ago, # ^ | 0 I add assert(answers[v].size() <= 2) in line 38 176651123 and it works !about last question i must say that if all node with height h have at most two numbers, It's easy to prove this condition hold for all nodes with height h+1(see the proof in editorial) •  » » 12 months ago, # ^ | 0 Since x and num is integer and num >= 1, let's observe this sequence of numbers: 0/num, 1/num, 2/num, ..., (num-1)/num, num/num, (num+1)/num, ... (2*num)/num, (2*num+1)/num, ... (3*num)/num, (3*num+1)/num, ... for any adjacent elements in this sequence, it is impossible that (x/num) < A and A < (x+1)/num and A is integer ( if you want x/num and (x+1)/num cross some integer A, at least one of them will be integer. ) so$\lceil (x+1)/num \rceil - \lfloor x/num \rfloor \le 1$.below is an illustration when num is 3: (I hope this helps, forgive my poor English :) •  » » » 12 months ago, # ^ | 0 Thank you so much for your explanation. And your English is good. :D  » 18 months ago, # | 0 For people who solved E1: how do you reach the$abba$construction in E1, or how did you reach your construction for$n = 3$? •  » » 18 months ago, # ^ | 0 n=3 for me was built on the explanation of the example (using one of the two guesses to either solve it or force a non-joking answer)For the main construction I calculated what the possible answers to a pair of queries could mean. For yes yes to reduce the search space you need something not in either query, for no no you need something in both queries and if the responses are different (yes/no, no/yes) you need something unique in the no query which suggests that splitting into 4 would be best.  » 18 months ago, # | 0 For C, why don't 1 2 3 4 ... n works?? for example if we take a case 3 2 4 1 my answer for this is 1 2 3 4 dry run : i = 1 -> 4 3 5 2 i = 2 -> 4 5 7 4 i = 3 -> 4 5 10 7 i = 4 -> 4 5 10 11but this logic is giving me wrong answer, what am i missing?? •  » » 18 months ago, # ^ | 0 Hi, consider 4 1 2 3 it will be 5 4 8 13 and it is not sorted  » 18 months ago, # | ← Rev. 3 → 0 MohammadParsaElahimanesh, can you please help in question 1746D - Paths on the Tree. Like understood what is written in the editorial properly but the most confusing thing is how you write dfs I.e. recursive function so clean without any error. Like what I want to ask you is , in my case to understand your dfs implementation part I am going deep into recursion like this function is calling these inner functions and so on and actually it bec0mes very confusing. So do you just write dfs assuming that the function calling will give me the correct result like in case of DP. And all I have to do is working on the current state without any worry of how all other states will work and they will work correctly. So how do you think sir during writing dfs ?? •  » » 18 months ago, # ^ | 0 sorry for poor english in advance, we can calculate answer for some subtree and it does not relate other nodes, because each time we go down in tree and do not repeat some node in one way •  » » » 18 months ago, # ^ | 0 Sir, I did not get it what are you trying to say? Can you please help me explain more elaborately/ clearly?? •  » » » » 18 months ago, # ^ | 0 about your above question,you are right, it is same as simple dp, also i tell my friend(AmirrzwM) to help you if he can. •  » » » 18 months ago, # ^ | ← Rev. 2 → 0 MohammadParsaElahimanesh, sir only last time I will disturb you can you please tell in submission 176328072, what the 2nd last line I.e. dl += ws[rs] is doing??. Very Sorry if I am irritating you by pinging you again and again but I genuinely do not get the point what 2nd last line in dfs function is trying to do ?? •  » » » » 18 months ago, # ^ | 0 dl += ws[rs] means if we call node k one times more, how much score can we reach, so dl = w[k]+ws[rs]note we will pick ws 0 1 2 3 4 5 ... rs-1 surely and ws rs if we call some node one times more •  » » » » » 18 months ago, # ^ | 0 But, Why we need to call node k one time more?My thought: I think it is because our main objective is not only to calculate the answer in dfs function but we also have to return to the main function its calculated dfs function answer.Am I thinking correct sir ?? •  » » » » » » 18 months ago, # ^ | ← Rev. 2 → 0 no, It's not true, please read toturial agin, i calculate dp1 and dp2 but he calculate them together •  » » » » » » » 18 months ago, # ^ | ← Rev. 3 → 0 I think now I am irritating you, but I have read the editorial many times and your code is looking correct to me but in this submission 176328072 I am genuinely not getting why we need to add node k one time more I.e dl= w[k] + ws[rs] ??Can you please last time explain MohammadParsaElahimanesh??You can look at this submission also if you want , both are written in same way but here also last line did not make sense to me 176439185 •  » » » » » » » » 18 months ago, # ^ | 0 no problem, but at least like my massages :)consider node v, it has m children and we want to calculate "what is the answer if k balls reach to v" we name it dp v, k. the most important point is if k balls reach node v. k/m+1 balls will reach to k%m children of v and k/m balls will reach m-k%m children of v. or in another word, one more ball reaches to k%m children of v.so we can use dfs and it returns a pair {dp[ch][k/m], dp[ch][k/m+1]} where ch is children of vsorry for poor english  » 18 months ago, # | 0 My Algorithm:Step 1: Reverse loop the array and increment the element if the difference from the consecutive previous element is negative. Step 2: How to find the increment? Finding an increment is straight forward. Basically, this is an Arithmetic Progression: So, Sum of N elements is: S = (n / 2) (2 * a + (n - 1) * d) Hence, there is a quadratic equation that I need to solve. S = (n / 2) (2 * a + (n - 1) * d) Step 3: Keep doing it till the array contains elements in non-decreasing sorted order. Step 4: If the array is already sorted, but we still have operations left, then just increase all array elements by that current operation increment. My Submission link which is failing: https://codeforces.com/contest/1746/submission/177280199 •  » » 18 months ago, # ^ | 0 Take a look at Ticket 16322 from CF Stress for a counter example. •  » » » 18 months ago, # ^ | 0 I authored a similar approach: https://codeforces.com/contest/1746/submission/177047158Can you please guide me where is this failing?  » 18 months ago, # | 0 The editorial for problem D is too simple. It's hard to understand. I'm Chinese. When I participant in some Chinese algorithm contests, say, Nowcoder contests, the editorials are mostly hard to understand even though they're written in Chinese. I don't know why. Maybe I'm a newbie, and the editorial is for those experts to read. •  » » 18 months ago, # ^ | 0 I read the code. I sort of understand. Maybe this is what called "talk is cheap, show me the code". Anyway, thank you.  » 18 months ago, # | +8 Fun fact: the author's solution of problem D is$O(n \log n)$because it sorts the children by the best "extra" path, but it can actually be improved to$O(n)$with std::nth_element (which uses the Introselect algorithm). The idea is that we only need to partition the elements according to the$j$-th largest element for some$j$, and we don't care about their relative order beyond that.177698814  » 18 months ago, # | ← Rev. 2 → 0 I know it's very, very far out of my league but I saw flows in the tags for G, I tried to think of a way to setup a min cost max flow network that would solve the problem at all, even if it is not the intended time complexity. I thought of two ways but they both have issues and I don't know how to (or even if it's possible to) combine them. First was that to ensure that the numbers of tasks are what I need, I would create three nodes for each type of task and they have capacities$ab$and$c$going into the sink The second was to handle deadlines I create a node for each day, connect it to sink with capacity 1, connect a task to it's deadline and connect each day to the previous one, signifying that you can do a task with a deadline$d$on$d-1$but not the other way round.Any help would be really appreciated. •  » » 18 months ago, # ^ | 0 linkNext time search through original blogpost as well •  » » » 18 months ago, # ^ | 0 Thank you!  » 16 months ago, # | 0 I don't get the idea of this statement in problem F: It's not so hard to prove that the probability is equal to 1/2 for k=2. As I understand, instead of checking the number of occurrences of every single number, the intended solution will sum up all the number of occurrences of each number in the set$S$. However, if$|S| = 4$the probability of concluding YES when the actual answer is NO should be$\dfrac{7}{8}$, and this probability is even higher with a larger$|S|$. What is wrong with my thinking? 7/8 False PositiveE = Even, O = Odd,$k = 2\$E E E E -> only this case YESE E O OE O E OE O O EO E E OO E O EO O E EO O O O
•  » » 16 months ago, # ^ |   0 The array isn't random; the subset is random.
•  » » » 16 months ago, # ^ |   0 I get it, thank you!
 » 13 months ago, # |   0 In problem C, step1 -> solution there is a typo stpes
•  » » 13 months ago, # ^ |   0 thank you.
 » 13 months ago, # |   0 For those who are interested. Problem E1/E2 is similar to https://www.codechef.com/JUNE20A/problems/GUESSG (Editorial).
 » 12 months ago, # | ← Rev. 2 →   0 .
 » 12 months ago, # |   0 Can anyone explain me what's the space complexity of this code,I am getting MLE on test case 2. here's my submission: https://codeforces.com/contest/1746/submission/202337720
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 Hint : resize doesn't do what you think it does. In fact, if you don't use the correct version of resize, then regardless of space complexity, your algorithm would also give WA. Can you see why?
•  » » » 12 months ago, # ^ |   0 but now my code is giving TLE on test case 25. https://codeforces.com/contest/1746/submission/202518774 I don't think collisions occur in maps and when I saw other people's code,so they have used different method to store the answer than mine. can u give me some idea to optimise this approach or rough time complexity of this code
 » 10 months ago, # |   0 the technique used to solve problem F , is that a renowed trick , are there more problems on that trick.
 » 7 months ago, # | ← Rev. 2 →   0 Anyone plz help me in understanding problem A that how the testcase: ~~~~~ 5 4 ~~~~~ 0 0 1 1 0 ~~~~~ would be accepted as "YES" ? ~~~~~ 222613023
 » 7 months ago, # |   0 for D, why do we need a base case in DP ? How could it happen that we enter a node twice?
 » 5 months ago, # |   0 In problem E2, number of needed questions seems to be 3*(log2(n)+1).