By Vladosiya, history, 20 months ago, translation,

1741A - Compare T-Shirt Sizes

Idea: MikeMirzayanov

Tutorial
Solution

1741B - Funny Permutation

Idea: MikeMirzayanov

Tutorial
Solution

1741C - Minimize the Thickness

Idea: MikeMirzayanov

Tutorial
Solution

1741D - Masha and a Beautiful Tree

Idea: Gornak40

Tutorial
Solution

1741E - Sending a Sequence Over the Network

Idea: MikeMirzayanov

Tutorial
Solution

1741F - Multi-Colored Segments

Tutorial
Solution

1741G - Kirill and Company

Tutorial
Solution
• +77

| Write comment?
 » 20 months ago, # |   +5 another opportunity to feel dumb
•  » » 19 months ago, # ^ |   0 *_*
 » 20 months ago, # |   +4 G is good and can be extended to weighted graph
 » 20 months ago, # | ← Rev. 2 →   +2 Nice contest and great editorial!F a little harderNice G
 » 20 months ago, # |   0 If we replace mar = *max_element(...) with *min_element(...) in problem D, we are getting AC in both cases. I did min element there so someone can just give example or any explanation why is it working? Thanks in advance :)
•  » » 20 months ago, # ^ |   0 If the tree should pass the sanity check (i.e. Answer is not $-1$), then any comparison between the left subtree and the right subtree should return the same result. You can observe this by trying to construct the input from the sorted order $[1,2,\cdots,m]$. You can see that there is no way to move elements from the left subtree to the right subtree (or vice versa), other than to swap the two subtrees entirely. Therefore, the comparison returns $LR$ if they did swap.
 » 20 months ago, # |   +2 Can someone explain F editorial? Thanks.
•  » » 20 months ago, # ^ |   0 Imagine a segment $S$ with left and right points being $S_l$ and $S_r$. Now, think about all different segments that have it's left points before (or exactly equals) $S_r$. You will notice that all those segments (including $S$) are candidates to be the closest to the left point of $S$ aka $S_l$. Or even intersecting with $S$.When you realize that, the solution that comes in mind is: for every segment $S$, search among all segments with left points smaller than or equals to $S_r$ with different color, the one with highest right point $R_{max}$. After that, check if $R_{max} < S_l$ (some distance) or $R_{max} \ge S_l$ (intersecting segments).Of course this solution gives you a TLE. However, as we want to know all segments with left points smaller than or equals to our current right point $S_r$, the idea is iterate over all segments $S$ in increasing order of right points. Also, keep a pointer to the segments with left points $\leq S_r$ already considered (to find $R_{max}$). Update this pointer as you walk through values of $S_r$.The remaining part of the solution is explained in the editorial. That is the part that was difficult for me to understand as well. Hope it heps.
•  » » » 13 months ago, # ^ |   0 thanks
 » 20 months ago, # |   +14 Video Editorial for Chinese：Bilibili
•  » » 20 months ago, # ^ |   0 Is there an english version of this?
•  » » » 20 months ago, # ^ |   0 you know，because my poor English
 » 20 months ago, # |   0 Wanted to reach specialist using div3 as a ladder, instead got negative delta. bleh. Need to grind more.
 » 20 months ago, # |   +4 Problem D. To decide to swap or not we do not need to calculate maximum. Enough to compare the first element with middle value.
•  » » 20 months ago, # ^ |   0 Yes, it's true, thanks
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 Sorry For bad English. Another Solution For D. We don't need to swap or check sorted. because we can not make array sorted if we have abs(maxElementOfLeftSubtree — maxElementOfRightSubtree) != 2^(levelnum from bottom on taking level of leaf node is zero).Here is my solution (https://mirror.codeforces.com/contest/1741/submission/208681460)
 » 20 months ago, # |   0 $C$ and $D$ could've been swapped, at least in my opinion $D$ is way easier than $C$.
•  » » 20 months ago, # ^ | ← Rev. 2 →   +1 hmm, idk, I found C to be easier, since constraints were small thus O(n^2) was possible.
 » 20 months ago, # | ← Rev. 12 →   +1 I have another solution for C:We calculate the sum of the whole sequence, and consider its divisors: For every divisor $x$, we check whether we can divide the sequence into segments of sum $x$, and calculate the length of the longest segment. Doing that for every divisor gives us the time complexity of $O(1344\times n+\sqrt{n\times a_i})$, which is still good enough to get AC.Solution: 175584583
 » 20 months ago, # |   0 What is wrong in my submission for problem D? 175630153
 » 20 months ago, # |   0 There's another solution to B, which I believe to be more intuitive.If n equals 3 print -1.If n is even, then the permutation looks like this: $p = {(n), (n - 1), ...(n / 2 + 1), (1), (2), ... (n / 2)}$If n is odd, just print the permutation for n + 1, but without the first element, which will always be equal to n + 1, so the permutation is valid.Solution: 175595206
•  » » 20 months ago, # ^ |   +1 In my opinion your solution seems a little bit more complicated than necessary and than the one given in the editorial.I did something similar, but instead of doing p = n, n-1, ..., n/2+1, 1, 2, n/2I just didp = n, n-1, 1, 2, ..., n-2That way it's easier to implement and this works for both even and odd values of n, so you don't need to handle those cases separatelySolution: 175582981Anyways, it really doesn't matter much...
 » 20 months ago, # |   0 Does anyone know what the 17th test case of test case 3 for F is? 175777495
•  » » 20 months ago, # ^ |   +3 This is not the 17th test case but here is a failing test case: 1 6 71 87 1 57 79 4 7 12 4 44 45 6 88 100 1 37 68 5 Expected Output: 0 0 25 0 9 0 Obtained Output: 0 0 25 0 43 0
•  » » » 20 months ago, # ^ |   0 Thanks
 » 20 months ago, # |   +4 I have another solution for G. It got AC but I'm not sure if it is actually correct. SpoilerFirst of all, we do a BFS from the node 1 to calculate the shortest distance from 1 to all the other nodes, call it $dist[i]$.Next, we want to know if we can go from node $a$ to node $b$ by traversing shortest paths, call it $ok[a][b]$. We do a DFS starting from every node $a$, but only use the edge $(u,v)$ if $dist[u] + 1 = dist[v]$. The nodes that encounter on this DFS is reachable from $a$.There are only at most 6 friends without cars. There must be some permutation that matches the order of these friends getting home. So we enumerate all $6!$ permutations. For each permutation, we assume that the friends without cars reach home in the specific order of the permutation. Then we go through all the friends with cars and we try to send as many friends home as possible, in that specific order. We check if it is possible by using $ok[a][b]$. For example, let the permutation be $p$. If the first friend with a car is able to send $p_1$ home (but not $p_1$ and $p_2$ at the same time), then we will start checking $p_2$ for the second friend with a car.Lastly, the answer is the maximum among all the permutations. The time complexity is $O(nm + k!\times f)$.my submission
 » 20 months ago, # |   0 For problem D, we can first check all leaves. Start from a1, we consider every pair (ai,ai+1), it must be like (x,x+1) or (x+1,x), if not, we cannot sort it. Otherwise, when the form is (x+1,x) we are supposed to swap it. Put (x+1)/2 to its father node. After do this we get a new array which length is n/2. And repeat it until the array length is 1. link
 » 20 months ago, # | ← Rev. 2 →   0 Wouldn't the complexity remain O(mn) for D even after pre-calculating min and max for each vertex since we are swapping elements at each level?
•  » » 20 months ago, # ^ | ← Rev. 2 →   -6 We do not necessarily have to swap all elements of the left/right subtree. I used a bottom-up iterative approach for this. We enumerate $k$ as powers of two (including one) less than $m$. And starting from $k=1$, we try to fix the order of $A_{2kx}$ and $A_{2kx+k}$. Now we can see that the indices we wil be comparing on the next step will be a subset of the current step. (Think of it as arithmetic progressions of $d=1,2,4,\cdots$) This is due to the fact that if the subtrees below are sorted, then we can compare the leftmost element to see whether we need a swap or not. And as we will refer to a subset of the current step on the next step, just swapping the two elements suffices for counting the swaps. The sanity check is done by checking a certain invariant property which is true when the subtrees below are sorted and the tree is made from a perfect binary tree: $|A_{2kx}-A_{2kx+k}|=k$. This solution is $O(m)$, you can check my submission (Python:175604510, C++:175815111) for further details.
 » 20 months ago, # | ← Rev. 2 →   0 Can anyone explain why 175793640 gives MLE on test 24 (problem G)? It works for other test cases which have higher n and m.
•  » » 2 months ago, # ^ |   0 Bro How did optimize it ?
 » 20 months ago, # |   +1 I like E, pretty standard and good
•  » » 6 weeks ago, # ^ |   0 Is there any way to do E recursively because when doing DP one initially think of recursive solution atleast I do and then convert it into iterative and I am unable to think of it recursivelyAnd if there is no way to do so how to come up with this solution thought process of it
 » 20 months ago, # | ← Rev. 5 →   +3 Here's an alternative solution to F w/ $O(n\log n)$ time complexity and less code.As done in the editorial, traverse the segments after sorting by left coordinate, and again after transforming $(l,r)$ to $(-r,-l)$. Instead of keeping track of 2 maximal segments, though, we keep track of the rightmost endpoint of each color with a max segment tree, and when we are processing segment X, if the query result is to the right of X's left endpoint, we can set $ans[X]$ to 0, otherwise set $ans[X]$ to the distance between the left endpoint and the query result.The above algorithm nearly works, except for when a segment is only adjacent to differently colored segments inside itself. Though, we can then use one additional check: the fact that if segment X contains the midpoint of segment Y, then segments X and Y intersect. This is also insufficient standalone as the converse is false, but kills the edge case. Using a std::multiset, we can perform it in $O(n\log(n))$.Alternative implementation, with an additional factor of $O(\log c)$ in space and time complexity, but uses no data structures outside std::set: https://mirror.codeforces.com/contest/1741/submission/175826713(EDIT: the use of a segtree can be circumvented in my original solution with the bitwise maximum technique in this implementation, which should also improve execution time. Though, that is something one would be far less likely to come up with in contest.)
 » 20 months ago, # |   +4 Can someone help me understand the editorial for problem G? I'm not sure what the editorial is trying to say, and I'm finding it difficult to decipher the code in the given solution.
•  » » 20 months ago, # ^ |   +4 For each vertex, find all possible sets of friends with no cars to which it can give a ride via bfs. For each set of friends with no cars, determine if it is possible to give rides to them via dp.
•  » » » 20 months ago, # ^ |   0 Can u pls elaborate your second point. Thank you .
•  » » » » 20 months ago, # ^ |   +1 We make a dp on friends with cars as follows: if a set A of friends with no cars could be given rides and a new friend with a car can give ride to a set B, then A union B can be given rides.
•  » » » » » 20 months ago, # ^ |   0 ok thanks got something will figure out the rest myself.Thank you for the explanation.
 » 20 months ago, # |   0 I would like to share my DFS solution approach for problem E. There can be at most O(2*n) valid subarrays. Each segment is consisted of 2 parts length and numbers. In a segment the length can be either on left or on right. Now, if we consider a[i] as one segment's length indicating cell, then the segment will be either of [i-a[i],i] range or of [i,i+a[i]] range. Let's consider each index as a node. If there are two nodes(segments) having range [i,R1] and [j, R2] where R1+1==j, then we will put an edge between them. Now, lets run a dfs from node 1. If we can reach the node (n+1), then answer is "YES", otherwise "NO". (n+1) is just a dummy node at additional index (n+1). My submission: https://mirror.codeforces.com/contest/1741/submission/175659624
•  » » 20 months ago, # ^ |   -8 Did the same. I do think the DP solution is practically equivalent to the DFS solution though. If we model the DP solution as a DAG, we should get the DFS solution, therefore the two solutions are equivalent.
•  » » 20 months ago, # ^ |   0 You have used directed graph. I tried to do it using undirected graph and I was getting WA (my submission). Can you explain the difference??
•  » » » 20 months ago, # ^ |   -8 $[2,2,2,1,1,1]$ is a counterexample to the undirected graph approach.
•  » » 19 months ago, # ^ |   0 why running DFS from only FIRST node giving the correct solution? I thought the same approach but running DFS running for each node as source.
•  » » » 19 months ago, # ^ |   0 Actually, we are checking if there is a path between the first node and the last node [It only exists when every index belongs to some node of the path]. And it is easier to code talking first node as the source of dfs.
 » 20 months ago, # | ← Rev. 2 →   0 Problem C can also be solved by considering all factors of the sum (sum of all elements of array), and trying to split the array for each factor. There can be maximum of log2(sum) factors making the complexity O(NlogN).Here is my solution: https://mirror.codeforces.com/contest/1741/submission/175841633
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 Actually the number of divisors of $N$ is not bound to be lower than $\log N$. We can use a number which is a product of many different primes for an example of this. Your statement is true for prime factors, but it is nowhere close to the truth for all factors. $d(N)\le N^{\frac{1.5379 \log(2)}{\log(\log(N))}}$ is a known upper bound for the divisor function for $N \le 3$, though. ($\sqrt[\leftroot{-2}\uproot{2}3]{N}$ is not a precise upper bound either, it is just an estimate)
•  » » » 20 months ago, # ^ |   0 Yes, it was my bad. The numbers of factors do not have a log2N upper bound.Also if the sum of elements are low, my solution can be faster than O(N^2) solution.
 » 20 months ago, # |   0 Does anyone know subcase 26 in test case 3 for G? 176090403
 » 20 months ago, # |   0 176213193 which is my way to solve D using sparse table :)
 » 10 months ago, # | ← Rev. 2 →   0 .
•  » » 7 months ago, # ^ |   0 how you can do a lazy segment tree on ranges l[i] <= r[i] <= 1e9isn't 1e9 too big for memory?
•  » » » 7 months ago, # ^ | ← Rev. 3 →   0 .
 » 7 months ago, # | ← Rev. 2 →   0 For $G_i$ thought we need to remove each vertex and do bfs on graph $G$ for each permutation of friends with no cars. so dumb of me, somehow I thought $\sum{distance}$ doesn't work
 » 2 months ago, # |   0 Nice contest!
 » 2 weeks ago, # | ← Rev. 3 →   0 task D : segment tree with dfs