Vovuh's blog

By Vovuh, history, 7 months 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

»
7 months 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

  • »
    »
    7 months 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.

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

      Yes you're right,thank you

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

      deleted

    • »
      »
      »
      7 months 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

      • »
        »
        »
        »
        7 months 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.

        • »
          »
          »
          »
          »
          7 months 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?

          • »
            »
            »
            »
            »
            »
            7 months 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.

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

Kindly, would you link this to the official contest?

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

how do we solve C but with bigger constraints?

  • »
    »
    7 months 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.

  • »
    »
    7 months 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

»
7 months 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.

»
7 months 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?

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

    But that's exactly the editorial?

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

      I got WA at test 17

      • »
        »
        »
        »
        7 months 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.

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

          Got it! Thank you.

        • »
          »
          »
          »
          »
          2 months 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? PikMike

»
7 months 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.

  • »
    »
    7 months 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.

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

For Uniform String, I had just made an array alphabetically like if n=5 and k=3 so make it abcab here only 3 letters a b c are used. Thus making the easiest solution I think.

»
7 months 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

»
7 months 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|

»
7 months 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.

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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

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

The first approach of D1 can be implemented using linked list. The complexity will be O(n).

Code here: Code

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

please someone explain how we can solve d2 question

  • »
    »
    7 months 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.

»
7 months 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.

  • »
    »
    7 months 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

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

      thank u so much bro ,this helps me a lot thank u

»
7 months 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

  • »
    »
    7 months 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

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

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

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

D1: when 'n' is odd does the bracket analogy still hold?? or what does that even mean then? obviously valid bracket sequences must be of even length, so I am a little confused. Can anyone please clarify??

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

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

  • »
    »
    7 months 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'
    }
    
»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I was trying to solve Problem C but my answer is wrong for test 4, can anybody help??I have attached my solution Solution Link

»
7 months 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];
»
7 months 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); }

  • »
    »
    7 months 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).

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

I am not able to understand why i am getting WA on test 9 for question 1092D1. Link to my solution

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

What's wrong in my code for 1092C ? I got this error code on test case 9 wrong answer The number of 'P's and 'S's should be one and one for length 1

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

For problem D1,

"Now imagine the following greedy solution. While you have some segment of the same parities of even length, fill it with horizontal bricks. This operation merges this segment with one to the left and to the right. If there is a single segment left then the answer is "YES". Otherwise it's "NO". The proof is left to the readers"

Can anyone help me with the proof of this algorithm?. I am stuck with the proving part.

»
2 months 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://codeforces.com/contest/1092/submission/54026479