By Vladosiya, history, 14 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 Tutorial of Codeforces Round 826 (Div. 3) Comments (54)
| Write comment?
 » another opportunity to feel dumb
•  » » *_*
 » G is good and can be extended to weighted graph
 » 14 months ago, # | ← Rev. 2 →   Nice contest and great editorial!F a little harderNice G
 » 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 :)
•  » » 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.
 » Can someone explain F editorial? Thanks.
•  » » 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.
•  » » » thanks
 » Video Editorial for Chinese：Bilibili
•  » » Is there an english version of this?
•  » » » you know，because my poor English
 » Wanted to reach specialist using div3 as a ladder, instead got negative delta. bleh. Need to grind more.
 » Problem D. To decide to swap or not we do not need to calculate maximum. Enough to compare the first element with middle value.
•  » » Yes, it's true, thanks
•  » » 6 months ago, # ^ | ← Rev. 2 →   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://codeforces.com/contest/1741/submission/208681460)
 » $C$ and $D$ could've been swapped, at least in my opinion $D$ is way easier than $C$.
•  » » 14 months ago, # ^ | ← Rev. 2 →   hmm, idk, I found C to be easier, since constraints were small thus O(n^2) was possible.
 » 14 months ago, # | ← Rev. 12 →   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
•  » » Could you please explain, why this algorithm is ture?
•  » » » 10 months ago, # ^ | ← Rev. 2 →   This approach is similar to the one in the tutorial, in that in each iteration we fix the sum of each segment and check to see if we can get a split satisfying the given conditions.In this approach however, instead of fixing the sum by using the length of the first segment, you just try out all possible numbers of segments that a split can generate (meaning, from 1 to n segments). This means that each segment will now have a sum of total_sum / number_of_segments.Of course, if total_sum / number_of_segments is not an integer, we can't even try such a split, so essentially we need to do this only for the divisors of total_sum (we can generate all divisors of total_sum in O(sqrt(total_sum))).For all divisors of total_sum, we check if a split can be generated such that it satisfies the requirements, and we record the maximum thickness required in each attempt. The minimum of those numbers is the answer.Hope this helps!
 » What is wrong in my submission for problem D? 175630153
 » 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
•  » » 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...
 » Does anyone know what the 17th test case of test case 3 for F is? 175777495
•  » » 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
•  » » » Thanks
 » 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
 » 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
 » 14 months ago, # | ← Rev. 2 →   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?
•  » » 14 months ago, # ^ | ← Rev. 2 →   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.
 » I like E, pretty standard and good
 » 14 months ago, # | ← Rev. 5 →   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))$.Implementation: https://codeforces.com/contest/1741/submission/175824953Alternative implementation, with an additional factor of $O(\log c)$ in space and time complexity, but uses no data structures outside std::set: https://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.)
 » 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.
•  » » 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.
•  » » » Can u pls elaborate your second point. Thank you .
•  » » » » 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.
•  » » » » » ok thanks got something will figure out the rest myself.Thank you for the explanation.
 » 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://codeforces.com/contest/1741/submission/175659624
•  » » 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.
•  » » 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??
•  » » » $[2,2,2,1,1,1]$ is a counterexample to the undirected graph approach.
•  » » 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.
•  » » » 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.
 » 14 months ago, # | ← Rev. 2 →   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://codeforces.com/contest/1741/submission/175841633
•  » » 14 months ago, # ^ | ← Rev. 2 →   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)
•  » » » 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.
 » Does anyone know subcase 26 in test case 3 for G? 176090403
 » 176213193 which is my way to solve D using sparse table :)
•  » » can you please elaborate on the approach with the sparse table?
 » F can easily be solved with lazy segtree (although it's a bit hard to implement)
•  » » how you can do a lazy segment tree on ranges l[i] <= r[i] <= 1e9isn't 1e9 too big for memory?
•  » » » you can look at my submission. i do a lazy segment tree on colors
 » 2 weeks ago, # | ← Rev. 2 →   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