[Solution] Fair Share solution codeforces

by

Fair Share solution codeforces – You are given 𝑚m arrays of positive integers. Each array is of even length.

You need to split all these integers into two equal multisets 𝐿L and 𝑅R, that is, each element of each array should go into one of two multisets (but not both). Additionally, for each of the 𝑚m arrays, exactly half of its elements should go into 𝐿L, and the rest should go into 𝑅R.

Give an example of such a division or determine that no such division exists.

Fair Share solution codeforces

The first line contains an integer 𝑚m (1≤𝑚≤1051≤m≤105) — the number of arrays.

The next 2⋅𝑚2⋅m lines contain descriptions of the arrays.

For each array, the first line contains an even integer 𝑛n (2≤𝑛≤2⋅1052≤n≤2⋅105) — the length of the array. The second line consists of 𝑛n space-separated integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎𝑖≤1091≤ai≤109) — array elements.

It is guaranteed that the sum of 𝑛n over all arrays does not exceed 2⋅1052⋅105.

Output

If the answer exists, print “YES”, and then print 𝑚m lines.

On each line, for each element, print the letter “L” or “R” (capitalized, without spaces), depending on which multiset the element should go into.

If there is no answer, print “NO” on the only line.

Fair Share solution codeforces

Example
input

Copy
3
2
1 2
4
1 2 3 3
6
1 1 2 2 3 3
output

Copy
YES
RL
LRLR
RLLRRL

Fair Share solution codeforces

For the first array, we move the first element into 𝐿L and the second element into 𝑅R. At the moment 𝐿={1}L={1}, and 𝑅={2}R={2}.

For the second array, we add the second and the third elements to 𝐿L, and the rest go to 𝑅R. Now 𝐿={1,2,3}L={1,2,3} and 𝑅={1,2,3}R={1,2,3}.

For the third array, we move elements at odd indices to 𝐿L, and elements at even indices go to 𝑅R. As a result, 𝐿=𝑅={1,1,2,2,3,3}L=R={1,1,2,2,3,3}.

Leave a Comment