MathK30's blog

find min dictionary order
By MathK30, history, 2 years ago, In English

Hi guys, i have 2 vector needed merge. How can I find min dictionary order of vector after merge.

ex : A = {2, 3} B = {4, 5}

one of satis way is : {2, 4, 5, 3}, opposite {3, 2, 4, 5}, {3, 2, 5, 4} is not.

  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

if you mean a queue , then it is mergesort isn't it

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

    No in this case the vectors are sorted but they may not be. I think what he is asking is the lexicographically smallest merging where the relative order of each element from each vector doesn't change. Eg:- a = {5, 1}, b = {2, 6} the answer is {2, 5, 1, 6}

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

      But wouldn't $$$[2,3]$$$ and $$$[4,5]$$$ result in $$$[2,3,4,5]$$$ then? I think OP needs to clarify this

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

        yes, for sure. I was also confused on this, but he/she says "one of satis way is ..." hard to decode tbh :)

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

        {2, 3, 4, 5} is the answer we need :v

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

      The way to solve this is:

      Think of the vectors as queues, and greedily pop from the queue with smaller front value.

      But how to handle duplicates?

      1. run suffix array on the array a concat b
      2. Now we can compare suffixes of a concat b in O(1) which will tell us which queue to pop from
      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

bonus : {2, 3, 4, 5} is the answer of ex test cases

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

    then maybe just do a greedy thing like having the tops out and compare and choose

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

      how about hashing and binary search :v

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

        Well, maybe binary search could work, but it doesn't make the solution any easier. There is a greedy two-pointers way to solve this problem in $$$O(n+m)$$$.

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

          but when a[i] = b[j], which element should we get

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

            advance both pointers until the two pointers point to a different character. choose the lexicographically smaller side (segment).

            ex) assume we have two strings $$$\text{bbbbabbbbb}$$$ and $$$\text{bbbbcbbbbb}$$$. Now the first difference happens on $$$\text{a}$$$ and $$$\text{c}$$$, so you can append $$$\text{bbbba}$$$ to the answer, move the pointer on $$$\text{bbbbcbbbbb}$$$ to the previous position, and keep going. answer will be $$$\text{bbbbabbbbbbbbbcbbbbb}$$$.

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

              tks u, it look like hash but complex O(n)

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

Is it SPOJ MINSEQ?

→ Reply