String problem

[IHaveSmallBrain]

Hello, I'm trying to solve this problem:

Singhal has two strings S and T consisting of lowercase English Letters.

He wants to obtain string S lexicographically smallest possible. He can do the following operation any number of times: choose an index pos₁ in the string S, choose an index pos₂ in the string T, and swap s_pos1 with t_pos2

String p is lexicographically smaller than string q,
- if p is a prefix of q, p≠q
- in the first position where p and q differ, the string p has a letter that appears earlier in the alphabet than the corresponding letter in q.

For example, abc is lexicographically smaller than abcd, abd is lexicographically smaller than abec, afa is not lexicographically smaller than ab and a is not lexicographically smaller than a.

Note: You have not to minimize number of operations and any index of both string can be chosen more than once.

Input
The first line contains a single integer t(1 ≤ t ≤ 100) — the number of test cases in the input. Then t test cases follow.

Each query contains two lines. The first line contains a string S(1 ≤ |S| ≤ 100) , and the second line contains a string T(1 ≤ |T| ≤ 100). |S| and |T| is the length of the string S and T respectively.

Note: Both strings will have only lowercase English Letters.

Output
For each test from the input print lexicographical smallest possible string S. Print the answers to the tests in the order in which the tests are given in the input.

Example:

Input

5
ab
a
abc
abc
abd
codedigger
dbc
a
adb
codealittle

Output

aa
aab
abc
abc
aab

You can view the problem on: https://codeforces.com/gym/102766/problem/A

Here is the program that I'm writing:

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
	int n;
	cin >> n;
	string a, b;
	vector<string> c;
	for (int i = 0; i < n; ++i)
	{
		getline(cin, a);
		getline(cin, b);
		c.push_back(a);
		c.push_back(b);
	}
}

My program only read the user input, now how can I read the string by character in a vector and swap them while comparing with character of another string in a vector? Or anyone can think of a better algorithm to solve this problem? Thanks for your help!

[keskiverto]

Forget the vector for now.

	string S, T;
	for (int i = 0; i < n; ++i)
	{
		getline(cin, S);
		getline(cin, T);
		// now you have S and T
		// compute result
		// you can store the result for later output
	}

What does bubble sort do? You don't bubble sort here, but perhaps something similar.

[lastchance]

For each test:
- read strings
- add strings
- partial sort to S.size()
- output the first S.size() chars (substring)

[IHaveSmallBrain]

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	string a, b;
	int n;
	vector<char> c;
	cin >> n;
	cin.ignore();
	for (int i = 0; i < n; ++i)
	{
		getline(cin, a);
		getline(cin, b);
		b += a;
		sort(b.begin(), b.end());
		for (int j = 0; j < a.size(); ++j)
		{
			c.push_back(b[j]);
		}
		
	}

	for (int i = 0; i < c.size(); ++i)
		cout << c[i];
}

The output is correct, but how can I separate the output for each test case?

[lastchance]

Just output substrings.

You don't need vectors. Full stop.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
   int tests;
   cin >> tests;
   for ( string S, T; tests; tests-- )
   {
      cin >> S >> T;
      string U = S + T;
      partial_sort( U.begin(), U.begin() + S.size(), U.end() );
      cout << U.substr( 0, S.size() ) << '\n';
   }
}

[IHaveSmallBrain]

I don't know you can do like this:
for ( string S, T; tests; tests-- )
What does this mean?

[Ganado]

tests is an int. Saying "tests" by itself as the iteration condition is equivalent to saying "tests != 0".

Other than that, it's simply a for loop, with standard syntax:

for ( init; condition; increment ) {
   statement(s);
}

Two strings (S, T) are being declared in the init section instead of just one.

[lastchance]

1st-part: initialiser - it just declares two strings
2nd-part: test whether to run the loop (equivalent here to tests>0, since any non-zero number casts to true)
3rd-part: at the end of each loop - decrements the number of remaining tests (I'm counting down rather than up, that's all).

Apart from the output, it actually does roughly the same as your code.

I only used partial_sort in the hope that it would be quicker than a full sort; you only need the first S.size() values.

[IHaveSmallBrain]

Thanks for the explanation. Does std::partial_sort quicker then std::sort?

[lastchance]

Does std::partial_sort quicker then std::sort?

If you only have to sort the smallest S.size() values and you don't care about the rest then you won't have to do as much work. So it ought to be a little bit faster for most serial algorithms. If you need to sort a whole array (which isn't the case here) then it would be a non-starter.

You can simply take advantage of the fact that you don't have to completely sort the whole lot.

[IHaveSmallBrain]

Thank you everyone!

[keskiverto]

He can do the following operation any number of times: choose an index pos1 in the string S, choose an index pos2 in the string T, and swap spos1 with tpos2

The homework mentions allowed operations. The question is, does it enforce that restriction?

[lastchance]

Any two elements of S can be swapped via a pair of swaps with a spare element of T.
Any element of S can be directly swapped with an element of T.
So the smallest S.size() elements of the combined string S+T can be obtained by the allowed operations.

But it works on Codeforces, any way (I tried it!)