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.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
02:32:12
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
02:32:12
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 15:02:48 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
if you mean a queue , then it is mergesort isn't 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}
But wouldn't $$$[2,3]$$$ and $$$[4,5]$$$ result in $$$[2,3,4,5]$$$ then? I think OP needs to clarify this
yes, for sure. I was also confused on this, but he/she says "one of satis way is ..." hard to decode tbh :)
{2, 3, 4, 5} is the answer we need :v
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?
a concat ba concat bin O(1) which will tell us which queue to pop fromthank u, is it O(n)
bonus : {2, 3, 4, 5} is the answer of ex test cases
then maybe just do a greedy thing like having the tops out and compare and choose
how about hashing and binary search :v
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)$$$.
but when a[i] = b[j], which element should we get
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}$$$.
tks u, it look like hash but complex O(n)
Is it SPOJ MINSEQ?