Vladosiya's blog

By Vladosiya, history, 20 months ago, translation, In English

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

Idea: MikeMirzayanov, senjougaharin

Tutorial
Solution

1741G - Kirill and Company

Idea: Vladosiya

Tutorial
Solution
  • Vote: I like it
  • +77
  • Vote: I do not like it

| Write comment?
»
20 months ago, # |
  Vote: I like it +5 Vote: I do not like it

another opportunity to feel dumb

»
20 months ago, # |
  Vote: I like it +4 Vote: I do not like it

G is good and can be extended to weighted graph

»
20 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

Nice contest and great editorial!

F a little harder

Nice G

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 $$$L<R$$$ if the two subtrees didn't swap, and $$$L>R$$$ if they did swap.

»
20 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Can someone explain F editorial? Thanks.

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
20 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Video Editorial for Chinese:

Bilibili

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is there an english version of this?

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you know,because my poor English

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wanted to reach specialist using div3 as a ladder, instead got negative delta. bleh. Need to grind more.

»
20 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

$$$C$$$ and $$$D$$$ could've been swapped, at least in my opinion $$$D$$$ is way easier than $$$C$$$.

  • »
    »
    20 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    hmm, idk, I found C to be easier, since constraints were small thus O(n^2) was possible.

»
20 months ago, # |
Rev. 12   Vote: I like it +1 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

What is wrong in my submission for problem D? 175630153

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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/2

    I just did

    p = n, n-1, 1, 2, ..., n-2

    That 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 separately

    Solution: 175582981

    Anyways, it really doesn't matter much...

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone know what the 17th test case of test case 3 for F is? 175777495

  • »
    »
    20 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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, # |
  Vote: I like it +4 Vote: I do not like it

I have another solution for G. It got AC but I'm not sure if it is actually correct.

Spoiler
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

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   Vote: I like it -6 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

Can anyone explain why 175793640 gives MLE on test 24 (problem G)? It works for other test cases which have higher n and m.

»
20 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I like E, pretty standard and good

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 recursively

    And if there is no way to do so how to come up with this solution thought process of it

»
20 months ago, # |
Rev. 5   Vote: I like it +3 Vote: I do not like it

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://mirror.codeforces.com/contest/1741/submission/175824953

Alternative implementation, with an additional factor of $$$O(\log c)$$$ in space and time complexity, but uses no data structures outside std::set<int>: 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, # |
  Vote: I like it +4 Vote: I do not like it

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, # ^ |
      Vote: I like it +4 Vote: I do not like it
    1. For each vertex, find all possible sets of friends with no cars to which it can give a ride via bfs.
    2. For each set of friends with no cars, determine if it is possible to give rides to them via dp.
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can u pls elaborate your second point. Thank you .

      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          ok thanks got something will figure out the rest myself.Thank you for the explanation.

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it -8 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it -8 Vote: I do not like it

      $$$[2,2,2,1,1,1]$$$ is a counterexample to the undirected graph approach.

  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone know subcase 26 in test case 3 for G? 176090403

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

176213193 which is my way to solve D using sparse table :)

»
10 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how you can do a lazy segment tree on ranges l[i] <= r[i] <= 1e9

    isn't 1e9 too big for memory?

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest!