Блог пользователя MathK30

find min dictionary order
Автор MathK30, история, 2 года назад, По-английски

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.

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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}

    → Ответить
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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
      → Ответить
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      how about hashing and binary search :v

      → Ответить
      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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)$$$.

        → Ответить
        • »
          »
          »
          »
          »
          2 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          → Ответить
          • »
            »
            »
            »
            »
            »
            2 года назад, # ^ |
            ← Rev. 3   Проголосовать: нравится -8 Проголосовать: не нравится

            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}$$$.

            → Ответить
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is it SPOJ MINSEQ?

→ Ответить