vovuh's blog

Codeforces Round #527 (Div. 3) Editorial
By vovuh, history, 6 years ago, translation, In English

1092A - Uniform String

Tutorial
Solution

1092B - Teams Forming

Tutorial
Solution

1092C - Prefixes and Suffixes

Tutorial
Solution

1092D1 - Great Vova Wall (Version 1)

Tutorial
Solution 1
Solution 2

1092D2 - Great Vova Wall (Version 2)

Tutorial
Solution

1092E - Minimal Diameter Forest

Tutorial
Solution

1092F - Tree with Maximum Cost

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

Comments Comments (48)
| Write comment?
»
6 years ago, # |
  Vote: I like it -14 Vote: I do not like it

my solution on E was same with editorial but i got WA on test 8

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

    You are searching for the wrong vertex. I'm really bad at all these graph definitions, is it centroid?) Imagine the following tree:

    tree

    You'll consider vertex 6 center but 4 is the real center.

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

      Yes you're right,thank you

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      deleted

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      My logic was almost same as the editorial. Can you look at it and explain what is wrong in it if possible. My solution is also failing in test case 8.

      Solution Link is : Solution Link

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        Hmm, as far as I can understand, you consider the center the vertex with distance of half the diameter from one of its ends. That is wrong.

        tree

        Diameter is 4, you can say that vertex 6 is center.

        I'm not sure if there is a simpler way but I usually search for vertex with distances (diam / 2) from one end of the diameter and (diam — diam / 2) from the other end.

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

          Thanks for helping. I got my submission acccepted :).

          My code for finding centre was kinda tedious. Can you provide your code to find centre of connected tree?

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

            Editorial has my code in it. It's basically bfs from x, from y and a loop over the vertices of the current component.

            → Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Here I have written my approach to solve problem F: [Editorial] Another Solution to Problem F(1092F) from Codeforces Round #527 (Div. 3)

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Kindly, would you link this to the official contest?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how do we solve C but with bigger constraints?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    How much bigger are we talking about? One can easily do O(input size) (like O(n2)) replacing multiset with trie but that's about it.

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

    if i'm not mistaking we can use hashes to compare string parts faster. It is one of the optimization for this task

    → Reply
»
6 years ago, # |
  Vote: I like it +21 Vote: I do not like it

D1 is interesting! I believe the same idea extends if you are able to place horizontal blocks with size 1 × H and vertical blocks with size V × 1 (in this problem H = V = 2). Any contiguous section of H columns with the same height modulo V can be greedily deleted from consideration. It is possible to make all columns have the same height iff after making all such deletions all remaining columns (if any) have the same height.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem C: Store all given strings and their positions. Let's two strings of length n - 1 be A and B in given strings. Assume A to be largest prefix then search for A.substr(0, i) for 0 <  = i < n - 1. If all such strings are present then A can be a prefix and check for B as suffix in similar manner. If this goes wrong check for B as a prefix and A for suffix. Is it a correct Approach?

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

    But that's exactly the editorial?

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

      I got WA at test 17

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it +2 Vote: I do not like it

        Oh, that's an interesting case. Let the test be string "abb". Imagine getting it wrong — prefix "bb " and suffix "ab". Each substring exist and the amount is correct. However, they can't make a full string.

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

          Got it! Thank you.

          → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          I also have used the same approach,even I am getting correct answer for your test "abb", getting prefix="ab" and suffix ="bb". Still I am getting wrong answer on test case 17. Can you explain it why? awoo

          → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell what is the intuition behind the logic of D1 problem i.e how to approach and think as keeping them as odd and even and then deleting all even length segments then deciding if size <=1 then "YES" else "NO". Thanks in advance.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    It's just an experience thing, I believe. Vova first told me D2 and I immediately was like "what if that is correct bracket sequences". It just felt alike. Details for implementation came pretty minor after it.

    As for D1, turning the numbers to their parities is the most intuitive thing. You kinda trying to check what if there were just a single way to put bricks. And then come up with a strat to do this. The stack is harder but having some similar problems solved already helps find this approach here. The ending step is just common sense. I mean, obviously, either all the segments got destroyed, or all but the one of odd length left. Easier tests for this case (like 1 2 2) can help to understand.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

3 lines implementation in python2.x of A solution

for _ in xrange(int(raw_input())):
    n, k = map(int, raw_input().split())
    print ''.join([chr(ord('a') + i%k) for i in xrange(n)])

find more here

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +13 Vote: I do not like it

I have a alternative solution to problem D1.

Clearly, by using vertical blocks we can change any given input to a binary representation. We simply use a[i] = a[i] % 2 . Now clearly a solution only exists when we can transform this representation to all '0's or all '1's

I claim that we can reach every possible valid state that has a solution by adding 3 i.e binary '11' to a set of all '0's. Example if we have only 4 columns we have possible states of '0000', '0011', '1001','0110', '1111' , '1100'. So, clearly if solution exists the binary representation should be divisible by 3 or '11'. Note that this is only valid when an all '0's solution exists. We also have to check another case for all '1's solution by using a[i] = (a[i] + 1) % 2 repeating the process.

So we simply check if your binary representation is divisible by 3 in one of the 2 cases or not. For that we check if absolute value of the difference between the sum of digits in odd places and even places in our binary representaion is divisible by 3 or not, i.e. abs(sum_odd_places - sum_even_places) % 3 == 0.

Overall Complexity is O(n) .

Solution Code : Python |Submission|

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your solution is incorrect. The following case 

    6
2 1 2 1 2 1

    gives "YES" in your code, but official solution gives NO. In fact, answer should clearly be NO, You cannot add any horizontal brick at any moment. Divisible by 3 is a necessary condition, but not sufficient.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I was trying to solve problem E using centroids (not centroid decomposition) my idea is to find centroids for each connected component add an edge between 2 connected components and then find a new centroid on this new tree, and so on until there is only one centroid left, then I calculate maximum possible dist as maximum_height + 2nd maximum_height, I really do not know why but it gives me wrong answer on test case #8 because my answer is: 22 9 60

vs

21 9 100

since I do not have access to the test cases anyone has some advice into what could be happening? I think the idea should work since the centroid is the node that is in the "middle" of each tree.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Actually centroid decomposition isn't working here. Because, even if it's the "center", that doesn't mean that its the node that have average shortest path to all other nodes.

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

      Thanks for the reply now I know the difference between centroid and center

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

please someone explain how we can solve d2 question

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I solved it using stack, the idea is that you need to always pair 2 elements in order to say that you can place a brick wall of size N which has to be divisible by 2 (this due to the 2x1 thing). The solution is something like this:

    Given P as the array of elements, and S the stack we have the following:

    • if P[i] == S.top() we have a size 2 or divisible by 2 N , so we pop the top of S

    • if S.empty() || P[i]!=S.top() , we have a new possible wall to take into account we push the element into S IF P[i]<S.top() , why is that? just check this example:
      4
      1 2 2 1

    As you can see there is no way to connect the 1's because the 2's can only increase so answer is NO

    At the end of the algorithm you should have either a size 0 or size 1 stack, if you have a size 2 or more then you couldn't connect 2 or more elements so answer is NO

    • A size 0 represents that you have a solution so answer is YES

    • A size 1 represents that you may have a solution, on this case:
      3
      5 6 6

    you can see you are left with 1 element but the answer is NO, that is because the element that should remain is always the maximum height possible , because if not there is no way to pair it with the other N-1 elements that form a single wall.

    So if S.top()!=max_h then NO, else YES

    That's pretty much it.

    → Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

please explain me the logic of D1 I am not able to understand.

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

    Since you have a 2x1 block that you can either place horizontally or vertically, you then can assure this things:

    • You can always increase the height of any element of the array by 2 even if it is by itself

    • You can only increase the height by 1 if there are 2 elements connecting that create a segment , but as the size of blocks is 2 then it must be of even size

    Having that in mind then you can use the parity instead of the elements itself, lets take an example where the array is called P:

    1 2 2 3

    As you can see on the case above you can increase P[1] because it pairs with P[2], but then you have an issue how can you pair P[0] with P[3]? well you increase 1 by 2 and it is 3, ok now a little thing, in math there are this rules:

    • even + even = even
    • odd + even = odd
    • odd + odd = even
    • even + odd = odd

    So if you assume that you can reach any increasing odd number from an odd number, and any increasing even number from an even number, then you can pair 1 and 3 for example or 2 and 10, then what matters is the parity

    If you look above I explained how to solve problem D2 , here is the same deal the difference is that arrays are like this:

    0 0 1 1

    The only change to the algorithm is that you do not need to check if P[i]<S.top() due to the vertical choice

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please tell me where my mistake is in problem E? I am doing exactly what the editorial says, but I'm using DFS instead of BFS to find the diameter and center, so maybe that's why it's wrong? Link — 47346955

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    dfs2 function won't return the center of the diameter in all cases (I'm too lazy to write a test for that) anyways, I've fixed dfs2 and it just worked fine. here it is

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

      Thank you so much for helping me, I really appreciate it.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain the logic for C problem in more detail?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You have two strings with length n-1. Let them be a1,a2,a3,...,an-1 and b1,b2,b3,...bn-1. Then the final string is either a1,a2,...,an-1,bn-1 (if first string is prefix and second is suffix), or b1,b2,...,bn-1,an-1 (if second string is prefix and first is suffix). So, we can try both combinations. Let this combined string be s. Now how do we verify that s is correct? We should check all prefixes and suffixes of it, and if s is correct, we should be able to find that prefix or suffix in the other given strings from the input (remember that in the input we have all the prefixes and suffixes of every length).

    The constraints are small enough that you can use brute force.

    For example, here is how you would check if all prefixes are good (you should do this with all suffixes right after). s is the string we want to verify is correct. All strings from the input are stored in an array affixes.

    int status[210]; //status[i] = whether i-th string is unused(0), marked as prefix(1), or suffix(2)
for (int i = 0; i < 2*n-2; ++i) status[i] = 0;

bool ok = true;
string pref = "", suff = "";

//check whether all prefixes of *s* can be found from the input
for (int i = 0; i < n; ++i) {
    pref += s[i];
    bool found = false;
    for (int j = 0; j < 2*n-2; ++j) {
        if (status[j] == 0 && pref == affixes[j]) {
            status[j] = 1; //number for prefix (see above)
            found = true;
            break;
        }
    }
    if (found == false) {
        ok = false;
        break;
    }
}

//similar code for suffixes
//...

if (ok) {
    //success, iterate over *status*, if status[i]=1, print 'P', otherwise print 'S'
}
    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem F, I think it would be more clear if you were to write the code for "undoing" the re-root operation as the "re-root" operation, but with v and to reversed:

		res -= sum[to];
		sum[v] -= sum[to];
		res += sum[v];
		sum[to] += sum[v];
		
		go(to, v);
		
		res -= sum[v];
		sum[to] -= sum[v];
		res += sum[to];
		sum[v] += sum[to];
→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What will this block do in the Problem C solution ?

else { assert(false); }

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

    Whenever there is a false statement within an assert block the program displays a Run time error and terminates . Since it is written in the problem statement that there is always a solution therefore the control will never be transferred to this block of code unless there exists no string and if that is the case then an error will be produced indicating to the user that there is some problem with the test data and not his logic. However run time error may arise due to other reasons too (obviously).

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, I am not sure if there is a problem with Problem C test case 14. My code produced an answer which is totally opposite to the required answer, but somehow I can't find out what's wrong. Can anyone help?

This is my submission: https://mirror.codeforces.com/contest/1092/submission/54026479

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

@PikMike in problem F. You could easily see that sum[v] is nothing but total sum — sum[v] i.e. sum[1]-sum[v]; res=res+sum[1]-2*sum[v] then to reverse re root; use res-=sum[1]-2*sum[v]

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi. Could someone please explain the diagnostics message that i am getting in testcase 17 for problem 1092C? I am not able to understand why my code is giving a runtime error. Here's my submission 78355872

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Never mind. I got it. It doesn't work with a testcase like "abb" as mentioned in one of the comments above by pikmike.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

someone please help me in this problem: My approach for adding edge :

 cmp = find_all_reachable_from(1);
    for( i = 1 ; i <= n ; i++ ){
        if( i is not in cmp ){
               cmp1 = find_all_reachable_from(i)
               v1 = center_in( cmp );
               v2 = center_in( cmp2 );
               // add edge in v1 and v2
               g[v1].push_back(v2);
               g[v2].push_back(v1);
               for( v in cmp2 ){
                    cmp.push_back(v);
               }
         }
    }
→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E, my logic was similar to the editorial, but I am getting the wrong answer in test case 18.Can someone look at my solution? solution link : https://mirror.codeforces.com/contest/1092/submission/267862349

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

280253854 can anyone tell me why in F my answer is wrong on testcase 3. i try to check all type of testcases but my code is working fine. please help me on this question. awoo

→ Reply