Codeforces Global Round 23 Editorial

Hi Codeforces,

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

1746A - Maxmina

problem author: MohammadParsaElahimanesh, AmirrzwM

1746B - Rebellion

problem author: MohammadParsaElahimanesh

1746C - Permutation Operations

problem author: napstablook

1746D - Paths on the Tree

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

1746E1 - Joking (Easy Version)

problem author: MohammadParsaElahimanesh

1746E2 - Joking (Hard Version)

problem author: MohammadParsaElahimanesh, AmirrzwM

1746F - Kazaee

problem author: MohammadParsaElahimanesh

1746G - Olympiad Training

problem idea: SirShokoladina

problem development: SomethingNew, pakhomovee, SirShokoladina

• 5 weeks ago, # ^ | ← Rev. 3 →   +12 Can someone please explain what is meant by balls passing through the subtree of node u in D Editorial

  • 5 weeks 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.

• 5 weeks ago, # ^ | 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.

• 5 weeks ago, # ^ | 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

  • 5 weeks ago, # ^ | I didn't realize that it was a permutation. :((( Thanks for the help

• 5 weeks ago, # ^ | 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.

  • 5 weeks ago, # ^ | can you explain how you add (1+2) to suffix at position 7?

    • 5 weeks ago, # ^ | 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<ll> arr(n); a(i,0,n) cin>>arr[i]; vector<pair<ll,ll>> 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<ll> q; a(i,1,n+1) q.push(i); vector<ll> 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()<n) ans.push_back(1); for(auto x: ans) cout<<x<<" "; cout<<endl;

• 5 weeks 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.

• 5 weeks ago, # ^ | The easiest approach on problem C int n; cin >> n; vector<int> ans(n); for(int i = 0; i < n; i ++){ int x; cin >> x; ans[n - x] = i + 1; } for(auto u : ans) cout << u << ' ';

  • 5 weeks ago, # ^ | 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.

• 5 weeks ago, # ^ | 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 same Note that if you have n items in a, you will have n — 1 differences

• 5 weeks ago, # ^ | With the input 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.

  • 5 weeks ago, # ^ | ← Rev. 3 →   +5 Okay I get it now!

  • 5 weeks ago, # ^ | thanks:D

• 5 weeks ago, # ^ | I also hahah

• 5 weeks ago, # ^ | ← Rev. 3 →   0 bro i still don't understand the approach for this question

• 5 weeks ago, # ^ | Yes, consider a chain.

• 5 weeks ago, # ^ | 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.

• 3 weeks ago, # ^ | Can somebody elaborate more on why this is happening? I mean at-most, we are calculating 2n states, why TLE then?

  • 3 weeks ago, # ^ | That's because the number of states may not be 2n. When k%cnt == 0, 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.

• 5 weeks ago, # ^ | A different "ideone" response for a change...

• 5 weeks ago, # ^ | One of my friend assumed that in the answer must be hold,but in fact it should be . The data he hacked himself

  • 5 weeks ago, # ^ | Oh, I also got hacked in a similar type of case a few contests back on the Array Recovery Problem:( Hacked AC Did your friend failed TC 46?

• 5 weeks ago, # ^ | Hi, sorry but can you explain FST (I'm not familiar with) :) my guess: (Fail Sample Test)

  • 5 weeks ago, # ^ | some solutions be Hacked with

  • 5 weeks ago, # ^ | Fail System Test afaik

    • 5 weeks ago, # ^ | thanks, above test may help you.

• 5 weeks ago, # ^ | 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.

  • 5 weeks ago, # ^ | Look at this WA I had during contest: 176361876 Compare 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.

• 5 weeks ago, # ^ | dp doesn't mean having some array. what you do is still dp, and it calculates same states.

  • 5 weeks ago, # ^ | 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 , where: is the sum of known for all descendants (and itself). is the max sum of 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.

• 5 weeks ago, # ^ | Did that just now, seems to make more sense to me

• 5 weeks ago, # ^ | ← Rev. 2 →   -52 The comment is hidden because of too negative feedback, click here to view it

  • 5 weeks ago, # ^ | Check out this freaking problem with 753 test cases 1566G — Four Vertices What makes it more funny is testdata is weak so some of the solution got uphacked. 128646349

• 5 weeks ago, # ^ | Like 998244353 problems lol

• 5 weeks ago, # ^ | I notice this after reading your comment I fill terrible

• 5 weeks ago, # ^ | wasted 30 mins on this! :) Got a sweet FST!

• 5 weeks ago, # ^ | give me the explaination why we add +i. i am still confused.

• 5 weeks ago, # ^ | 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.

• 5 weeks 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

• 5 weeks ago, # ^ | Still usually much better than in atcoder

  • 5 weeks ago, # ^ | Strangely I feel the opposite tbh.

• 5 weeks ago, # ^ | Yes if someone would explain it in simple sentences it would be much appreciated!

  • 5 weeks ago, # ^ | ← Rev. 2 →   0 I have no idea what is described in the editorial. Here is my solution. Solution

    • 5 weeks ago, # ^ | Thank you

• 5 weeks ago, # ^ | There is no difference... is that written somewhere in the editorial? I suppose it may have been edited afterwards.

• 5 weeks ago, # ^ | Now it's accepted.

• 5 weeks ago, # ^ | Did you mean step 3? In any case, what's important here is that they cannot both be lies. If you have sets , , , and , you can query and then query . 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.

  • 6 hours 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

• 5 weeks ago, # ^ | 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 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).

• 5 weeks ago, # ^ | ← Rev. 3 →   0 Can you explain why better solution is to make all balls reach leafs? Can you provide proof for that?

  • 5 weeks ago, # ^ | ← Rev. 2 →   0 I get it, it is a dp. We are basically trying all the possibilities without violating the constraints given in the questions. For people who need a better dp over dfs tree see Umnik submission for this. It is awesome! The amazing part of this question is that getting an idea that we can have atmost O(n) states

• 5 weeks ago, # ^ | Same, when I used a map, it gives TLE -> 176444934 But when I submitted by storing the answers in a vector (which I think should be a lot slower?) it passes comfortably 176444404

• 5 weeks ago, # ^ | If dp[node][k] is 0, you cannot check if it was searched before correctly.

  • 5 weeks ago, # ^ | 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

    • 5 weeks 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.

      • 5 weeks ago, # ^ | Thank you for pointing it out. That was very helpful ^__^

    • 5 weeks ago, # ^ | See Umnik code for better implementation using dp on dfs tree.

• 5 weeks ago, # ^ | 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 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).

  • 5 weeks ago, # ^ | 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.

• 5 weeks ago, # ^ | 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?

  • 5 weeks ago, # ^ | 'Pseudocode'

• 5 weeks 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.

  • 4 weeks ago, # ^ | You're not summing but which are random.

• 5 weeks ago, # ^ | See Umnik code and read editorial

• 5 weeks ago, # ^ | I am sorry. The link is wrong. The right link: 176349260

• 5 weeks ago, # ^ | ← Rev. 2 →   0 understood finally, the optimal is sort according to the differences not the values.

• 5 weeks ago, # ^ | 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)

• 5 weeks ago, # ^ | 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.

• 4 weeks ago, # ^ | Hi, consider 4 1 2 3 it will be 5 4 8 13 and it is not sorted

• 4 weeks ago, # ^ | 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

  • 4 weeks ago, # ^ | Sir, I did not get it what are you trying to say? Can you please help me explain more elaborately/ clearly??

    • 4 weeks ago, # ^ | 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.

      • 4 weeks ago, # ^ | ← Rev. 2 →   0 Ok, I have been thinking for so long on how dfs recursion is working and slowly getting a sense of it. The point is do not go deeper into recursion. Just have confidence that recursion will do the work correctly. All you have to do is to try writing the correct code for the bigger one state. Right sir??

  • 4 weeks 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 ??

    • 4 weeks ago, # ^ | 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

      • 4 weeks ago, # ^ | 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 ??

        • 4 weeks ago, # ^ | ← Rev. 2 →   0 no, It's not true, please read toturial agin, i calculate dp1 and dp2 but he calculate them together

          • 4 weeks 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

            • 4 weeks ago, # ^ | 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 v sorry for poor english

              • 4 weeks ago, # ^ | ← Rev. 3 →   0 Finally, I understood the point. It really means a lot as you have put your time, patience and energy to replying my questions. Very thanks again

S = (n / 2) (2 * a + (n - 1) * d)

S = (n / 2) (2 * a + (n - 1) * d)

• 4 weeks ago, # ^ | Take a look at Ticket 16322 from CF Stress for a counter example.

  • 4 weeks ago, # ^ | I authored a similar approach: https://codeforces.com/contest/1746/submission/177047158 Can you please guide me where is this failing?

    • 4 weeks ago, # ^ | Take a look at Ticket 16323 from CF Stress for a counter example.

• 4 weeks ago, # ^ | I read the code. I sort of understand. Maybe this is what called "talk is cheap, show me the code". Anyway, thank you.

• 3 weeks ago, # ^ | link Next time search through original blogpost as well

  • 3 weeks ago, # ^ | Thank you!