Problème A : Manipulation de Chaînes et Palindromes

Énoncé : Étant donné une chaîne de caractères S, nous avons également son inverse S_rev. Nous effectuons k opérations. À chaque étape, nous pouvons ajouter l'inverse de la chaîne courante soit à la fin, soit au début. La question est de déterminer le nombre maximal de séquences distinctes que nous pouvons obtenir.

Stratégie : L'analyse de ce problème révèle une propriété clé des palindromes.

1. Si la chaîne initiale est un palindrome : Si S est un palindrome, alors S est identique à S_rev. Toute opération consistant à ajouter S_rev (qui est S) à la chaîne courante (qui est S) produira toujours S + S ou S + S (concatenation). Le résultat sera une nouvelle chaîne qui est également un palindrome. Cependant, si l'on considère les séquences distinctes obtenues, seule la chaîne originale est formée (si k=0) ou la chaîne originale et la version concaténée si k>0. Mais si le problème demande des séquences "distinctes", et une fois qu'elle est un palindrome, elle reste un palindrome, alors toutes les opérations génèrent la même forme palindromique. Donc, un seul résultat unique est possible.
2. Si la chaîne initiale n'est pas un palindrome : Si S n'est pas un palindrome, alors S est différent de S_rev.
   • Si k = 0 : Aucune opération n'est effectuée. Seule la chaîne originale S est obtenue. (1 séquence)
   • Si k > 0 : Après la première opération, on peut former S + S_rev ou S_rev + S. Ces deux chaînes sont des palindromes (par exemple, si S = "abc", S_rev = "cba", alors "abccba" et "cbaabc" sont des palindromes). Une fois qu'une chaîne est devenue un palindrome, toutes les opérations subséquentes la maintiendront comme un palindrome, produisant une seule forme distincte. Ainsi, pour k > 0, deux séquences distinctes peuvent être obtenues : la chaîne originale S, et la forme palindromique obtenue après une opération. (2 séquences)

En combinant ces observations : si la chaîne initiale est un palindrome, la réponse est 1. Si la chaîne initiale n'est pas un palindrome, la réponse est 1 si k=0, et 2 si k>0. Problème B : Stratégie de Parité pour Atteindre une Cible

Énoncé : Nous avons un tableau A de n entiers. Alice commence avec une valeur X, et Bob commence avec X+3. Pour chaque élément A[i] du tableau, un joueur peut choisir d'ajouter A[i] à sa valeur courante ou d'effectuer un XOR avec A[i]. Il est garanti qu'un seul des deux joueurs pourra atteindre une valeur cible Y. Déterminez si Alice ou Bob est le gagnant.

Stratégie : Ce problème peut être résolu en examinant la parité des nombres. Une propriété fondamentale de l'addition et de l'opération XOR (ou OU exclusif) est que (A + B) % 2 == (A ^ B) % 2. En d'autres termes, A + B et A ^ B ont toujours la même parité.

• Si A et B sont tous deux pairs : A+B est pair, A^B est pair.
• Si A et B sont tous deux impairs : A+B est pair, A^B est pair.
• Si l'un est pair et l'autre est impair : A+B est impair, A^B est impair.

Cette propriété signifie que la parité de la valeur finale d'un joueur ne dépend pas du choix entre l'addition et le XOR pour chaque A[i]. La parité de la valeur finale est déterminée par la parité de la valeur de départ du joueur et par la parité du nombre d'éléments impairs dans le tableau A (car seuls les éléments impairs modifient la parité d'un nombre s'ils sont ajoutés ou XORés). Alice commence avec X et Bob avec X+3. La parité de X et X+3 est toujours opposée (si X est pair, X+3 est impair, et vice-versa). Puisque toutes les opérations maintiennent cette relation de parité, Alice et Bob atteindront toujours des valeurs finales de parités opposées.

Pour trouver la parité finale que chaque joueur peut atteindre, nous devons calculer la parité de X modifiée par le nombre total d'éléments impairs dans A. Soit count_odd_A le nombre d'éléments impairs dans le tableau A. La parité finale de la valeur d'Alice sera (parité(X) + parité(count_odd_A)) % 2. Si cette parité correspond à la parité de Y, alors Alice gagne. Sinon, Bob gagne.

#include <iostream>
#include <vector>
#include <numeric>

void resoudreCasTest() {
    int nombreElements, valeurInitialeAlice, valeurCibleY;
    std::cin >> nombreElements >> valeurInitialeAlice >> valeurCibleY;

    int compteurElementsImpairs = 0;
    for (int i = 0; i < nombreElements; ++i) {
        int elementActuel;
        std::cin >> elementActuel;
        if (elementActuel % 2 != 0) { // L'opérateur % 2 est suffisant pour vérifier l'imparité
            compteurElementsImpairs++;
        }
    }

    // Détermine la parité finale de la valeur qu'Alice peut obtenir
    // La parité change si un nombre impair d'éléments impairs a été "appliqué"
    int pariteEffectiveAlice = valeurInitialeAlice % 2;
    if (compteurElementsImpairs % 2 != 0) {
        pariteEffectiveAlice = 1 - pariteEffectiveAlice; // Inverse la parité (0 devient 1, 1 devient 0)
    }

    // Compare cette parité effective avec la parité de la valeur cible Y
    if (pariteEffectiveAlice == (valeurCibleY % 2)) {
        std::cout << "Alice\n";
    } else {
        std::cout << "Bob\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL); // Désactive la synchronisation C++ I/O et lie cin/cout pour accélérer

    int nombreTests;
    std::cin >> nombreTests;
    while (nombreTests--) {
        resoudreCasTest();
    }
    return 0;
}

Problème C : Organisation d'Étagères avec Moyennes Entières

Énoncé : Nous disposons de n étagères, chacune pouvant contenir k nombres. Nous devons placer les nombres de 1 à n*k sur ces étagères de manière à ce que la moyenne de n'importe quel sous-intervalle sélectionné sur une étagère soit toujours un entier.

Stratégie : La condition qu'une moyenne de n'importe quel sous-intervalle soit un entier est très restrictive. Pour qu'une telle condition soit satisfaite, les nombres sur chaque étagère doivent former une suite arithmétique de raison 2. Par exemple, une étagère pourrait contenir {1, 3, 5, ...} ou {2, 4, 6, ...}. Si la raison était 1 (par exemple, {1, 2, 3}), la moyenne de {1, 2} (qui est 1.5) ne serait pas un entier, violant la condition. Avec une raison de 2, tous les nombres sur une étagère sont de la même parité, et la somme d'un sous-intervalle de m nombres a, a+2, ..., a+2(m-1) est m*a + 2*(0+1+...+(m-1)) = m*a + m*(m-1). La moyenne est a + (m-1), qui est toujours un entier.

Cela implique que chaque étagère doit contenir soit uniquement des nombres pairs, soit uniquement des nombres impairs. Le nombre total de valeurs à placer est TotalNombres = n * k. Le nombre de nombres impairs de 1 à TotalNombres est ceil(TotalNombres / 2.0). Le nombre de nombres pairs de 1 à TotalNombres est floor(TotalNombres / 2.0).

Pour que la répartition soit possible, il faut que nous puissions former un certain nombre d'étagères "impaires" et un certain nombre d'étagères "paires". Cela signifie que le nombre total de nombres impairs doit être un multiple de k, et le nombre total de nombres pairs doit également être un multiple de k. Un test suffisant pour déterminer la faisabilité est de vérifier si le nombre de nombres pairs ((n*k) / 2 en division entière) est un multiple de k. Si ((1LL * n * k) / 2) % k != 0, alors il est impossible de former les étagères requises. Le cast en long long (1LL) est utilisé pour éviter les débordements lors du calcul de n\*k si n et k sont grands.

Construction : Une fois la faisabilité établie, nous pouvons construire la solution en alternant les étagères de nombres impairs croissants et les étagères de nombres pairs croissants. Par exemple :

• Étagère 1 (rang 0) : 1, 3, 5, ..., (k éléments impairs)
• Étagère 2 (rang 1) : 2, 4, 6, ..., (k éléments pairs)
• Étagère 3 (rang 2) : impairs suivants, etc.

#include <iostream>
#include <vector> // Non strictement nécessaire pour cette solution, mais bonne pratique

void resoudreCasTest() {
    int nbEtagères, tailleEtagère;
    std::cin >> nbEtagères >> tailleEtagère;

    // Vérification de la faisabilité:
    // Le nombre de nombres pairs jusqu'à (nbEtagères * tailleEtagère)
    // doit être un multiple de tailleEtagère.
    // Utilisation de 1LL pour s'assurer que le produit nbEtagères * tailleEtagère est de type long long
    // avant la division et le modulo, pour éviter les débordements d'entiers.
    if (((1LL * nbEtagères * tailleEtagère) / 2) % tailleEtagère != 0) {
        std::cout << "NO\n";
        return;
    } else {
        std::cout << "YES\n";
        long long prochainImpair = 1;
        long long prochainPair = 2;

        for (int i = 0; i < nbEtagères; ++i) {
            for (int j = 0; j < tailleEtagère; ++j) {
                if (i % 2 == 0) { // Les étagères d'index pair (0, 2, ...) reçoivent des impairs
                    std::cout << prochainImpair;
                    prochainImpair += 2;
                } else { // Les étagères d'index impair (1, 3, ...) reçoivent des pairs
                    std::cout << prochainPair;
                    prochainPair += 2;
                }
                if (j < tailleEtagère - 1) { // Ajoute un espace après l'élément sauf pour le dernier
                    std::cout << " ";
                }
            }
            std::cout << "\n"; // Nouvelle ligne après chaque étagère
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL); // Accélère les opérations d'entrée/sortie

    resoudreCasTest(); // Problème C n'a généralement qu'un seul cas test, ou est appelé par une boucle externe
    return 0;
}

Problème D : Localisation du Zéro (Problème Interactif)

Énoncé : Nous avons un tableau arr de n entiers non négatifs. Il contient exactement un seul zéro. Nous pouvons effectuer des requêtes du type ? a b c, qui retournent la différence entre le maximum et le minimum des éléments aux indices a, b, c (c'est-à-dire max(arr[a], arr[b], arr[c]) - min(arr[a], arr[b], arr[c])). Notre objectif est de trouver la position du zéro en 2*n-2 requêtes au maximum. Nous devons répondre en donnant deux positions, l'une d'elles étant la position du zéro. Les indices sont 1-basés.

Stratégie : Puisque tous les nombres sont non négatifs et qu'il y a un unique zéro, le zéro est nécessairement la valeur minimale absolue du tableau. Le problème revient donc à trouver l'indice de l'élément minimum absolu (le zéro) et l'indice de l'élément maximum absolu. L'énoncé permet de retourner deux indices, du moment que l'un d'eux est l'indice du zéro.

L'approche consiste à trouver les indices du minimum et du maximum absolus du tableau en utilisant un processus itératif de type "tournoi". Nous définissons une fonction auxiliaire qui prend quatre indices i1, i2, i3, i4 et détermine les indices du minimum et du maximum de arr[i1], arr[i2], arr[i3], arr[i4]. Pour ce faire, nous effectuons les quatre requêtes possibles entre les combinaisons de trois éléments :

• diff1 = Q(i1, i2, i3)
• diff2 = Q(i1, i2, i4)
• diff3 = Q(i1, i3, i4)
• diff4 = Q(i2, i3, i4)

Le maximum de ces quatre différences (max\_result\_diff) doit correspondre à la différence entre le minimum et le maximum réels des quatre éléments arr[i1], arr[i2], arr[i3], arr[i4]. En identifiant la paire de requêtes qui a produit ce max\_result\_diff et qui partage deux indices, nous pouvons identifier les indices du minimum et du maximum de ces quatre éléments. Par exemple, si diff1 et diff2 sont tous deux égaux à max\_result\_diff, cela signifie que les éléments aux indices i1 et i2 sont les extrêmes (min et max) de l'ensemble {i1, i2, i3, i4}, car i1 et i2 sont les seuls indices communs à ces deux requêtes. Nous commençons par appliquer cette fonction aux quatre premiers indices (1, 2, 3, 4) pour initialiser nos indices globaux du minimum et du maximum (idxMinGlobal, idxMaxGlobal). Ensuite, nous parcourons le reste du tableau par paires d'éléments (5, 6, puis 7, 8, etc.). À chaque étape, nous appelons la fonction auxiliaire avec idxMinGlobal, idxMaxGlobal et les deux nouveaux indices, ce qui met à jour idxMinGlobal et idxMaxGlobal pour qu'ils représentent le minimum et le maximum de tous les éléments considérés jusqu'à présent. À la fin, idxMinGlobal sera l'indice du zéro et idxMaxGlobal sera l'indice de l'élément maximum.

Cas particulier pour N=3 : L'implémentation fournie par l'auteur original (et retranscrite ici) commence avec un appel à trouverExtremes(1, 2, 3, 4), ce qui nécessite n >= 4. Si n=3, cette approche ne fonctionnera pas directement. Les problèmes interactifs peuvent avoir des traitements spécifiques pour les petites valeurs de N. Cette solution est valide pour N >= 4.

Attention pour les problèmes interactifs : Il est impératif de vider le tampon de sortie après chaque requête pour que le juge reçoive la requête immédiatement et puisse y répondre. L'utilisation de std::cout << ... << std::endl; garantit cet effacement du tampon.

#include <iostream>
#include <vector>
#include <algorithm> // Pour std::max et std::initializer_list

// Indices du minimum et du maximum globaux trouvés jusqu'à présent
int idxMinGlobal, idxMaxGlobal;

// Fonction pour effectuer une requête et obtenir la différence max-min
int faireRequete(int a, int b, int c) {
    std::cout << "? " << a << " " << b << " " << c << std::endl; // std::endl vide le tampon
    int resultat;
    std::cin >> resultat;
    return resultat;
}

// Détermine les indices du min et max parmi quatre indices donnés
// Les indices idxMinGlobal et idxMaxGlobal sont mis à jour en conséquence.
void trouverExtremes(int i1, int i2, int i3, int i4) {
    int res1 = faireRequete(i1, i2, i3);
    int res2 = faireRequete(i1, i2, i4);
    int res3 = faireRequete(i1, i3, i4);
    int res4 = faireRequete(i2, i3, i4);

    // Trouver la différence maximale parmi les résultats des quatre requêtes
    int max_result_diff = std::max({res1, res2, res3, res4});

    // Basé sur les requêtes qui ont produit max_result_diff,
    // on identifie les deux indices communs qui doivent être les extrêmes.
    if (res1 == max_result_diff && res2 == max_result_diff) { // i1, i2 sont les indices communs
        idxMinGlobal = i1; idxMaxGlobal = i2;
    } else if (res1 == max_result_diff && res3 == max_result_diff) { // i1, i3 sont les indices communs
        idxMinGlobal = i1; idxMaxGlobal = i3;
    } else if (res1 == max_result_diff && res4 == max_result_diff) { // i2, i3 sont les indices communs
        idxMinGlobal = i2; idxMaxGlobal = i3;
    } else if (res2 == max_result_diff && res3 == max_result_diff) { // i1, i4 sont les indices communs
        idxMinGlobal = i1; idxMaxGlobal = i4;
    } else if (res2 == max_result_diff && res4 == max_result_diff) { // i2, i4 sont les indices communs
        idxMinGlobal = i2; idxMaxGlobal = i4;
    } else if (res3 == max_result_diff && res4 == max_result_diff) { // i3, i4 sont les indices communs
        idxMinGlobal = i3; idxMaxGlobal = i4;
    }
}

void resoudre() {
    int nElements;
    std::cin >> nElements;

    // Initialisation avec les 4 premiers éléments.
    // Cette fonction assume nElements >= 4. Pour nElements = 3, un traitement spécial serait nécessaire.
    trouverExtremes(1, 2, 3, 4);

    // Itérer sur les éléments restants du tableau par paires pour trouver les extrêmes globaux.
    // La boucle commence à 5 car les éléments 1,2,3,4 ont déjà été traités.
    for (int i = 5; i <= nElements; i += 2) {
        if (i + 1 <= nElements) { // S'il reste au moins deux éléments à traiter (i et i+1)
            trouverExtremes(idxMinGlobal, idxMaxGlobal, i, i + 1);
        } else { // S'il ne reste qu'un seul élément (ou aucun) après l'indice i-1
            // Ce cas se produit si nElements est impair et que 'i' est l'avant-dernier élément.
            // On doit trouver un quatrième indice pour la fonction `trouverExtremes`.
            // On cherche un indice qui n'est ni `idxMinGlobal`, `idxMaxGlobal`, ni `i`.
            int troisiemeIndice = -1;
            for (int j = 1; j <= nElements; ++j) {
                if (j != idxMinGlobal && j != idxMaxGlobal && j != i) {
                    troisiemeIndice = j;
                    break;
                }
            }
            if (troisiemeIndice != -1) {
                // Utiliser idxMinGlobal, idxMaxGlobal, i (le dernier élément unique)
                // et troisiemeIndice (un autre élément distinct)
                trouverExtremes(idxMinGlobal, idxMaxGlobal, i, troisiemeIndice);
            }
            // Si troisiemeIndice est -1, cela signifie qu'il n'y a pas assez d'éléments
            // distincts pour former un quadruplet (cela arriverait si nElements < 4 ou si tous les éléments restants sont déjà idxMinGlobal/idxMaxGlobal)
            // Dans ce scénario, les extrêmes globaux sont déjà trouvés.
            break; // Termine la boucle
        }
    }

    // Après la boucle, idxMinGlobal et idxMaxGlobal contiennent les indices du minimum (0)
    // et du maximum absolus de tout le tableau.
    std::cout << "! " << idxMinGlobal << " " << idxMaxGlobal << std::endl;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL); // Accélère les E/S, important pour les problèmes interactifs
    resoudre();
    return 0;
}

Problème E : Répartition Équitable des Éléments (Théorie des Graphes)

Énoncé : Nous avons m tableaux, chacun contenant un nombre pair d'éléments. Notre tâche est de diviser tous les nombres collectifs en deux ensembles, 'L' et 'R', de manière à ce que :

1. Les ensembles 'L' et 'R' soient identiques (c'est-à-dire qu'ils contiennent les mêmes éléments avec les mêmes fréquences).
2. Pour chaque tableau, exactement la moitié de ses éléments appartiennent à 'L' et l'autre moitié à 'R'.

Stratégie :

1. Vérification de la faisabilité : Pour que les ensembles 'L' et 'R' soient identiques, chaque nombre unique doit apparaître un nombre pair de fois dans l'ensemble total des éléments de tous les tableaux. Si un nombre apparaît un nombre impair de fois au total, il est impossible de le diviser également entre 'L' et 'R'. Nous commençons donc par compter les occurrences de chaque nombre et vérifier cette condition. Si un nombre a une occurrence impaire, la réponse est "NO". Sinon, nous passons à la construction.

2. Construction de la solution par Graphes et Circuits Eulériens : Si la condition de faisabilité est respectée, une solution existe toujours. Nous pouvons modéliser le problème comme la recherche d'un chemin d'Euler dans un graphe bipartite :

   • Créez m nœuds pour les tableaux (indices de 1 à m).
   • Créez des nœuds pour chaque nombre unique distinct présent dans les tableaux. Comme ces nombres peuvent être très grands (jusqu'à 10^9), nous utilisons une map pour les discrétiser en des indices plus petits. Pour distinguer ces nœuds des nœuds de tableau, nous ajoutons un décalage (par exemple, les nœuds de valeurs discrétisées ont des indices de MAX_ARRAY_NODES + 1 à MAX_ARRAY_NODES + total_distinct_values).
   • Pour chaque apparition d'un nombre x dans le tableau i à l'index j, ajoutez une arête bidirectionnelle entre le nœud du tableau i et le nœud du nombre discrétisé map_valeurs[x]. Chaque arête doit stocker l'information de sa position d'origine (tableau i, index j) pour permettre de remplir la réponse.

   Dans ce graphe :

   • Chaque nœud de tableau i a un degré égal au nombre d'éléments dans le tableau i, qui est garanti pair par l'énoncé.
   • Chaque nœud de nombre discrétisé a un degré égal au nombre total d'apparitions de ce nombre. Nous avons vérifié que ce nombre est pair.

   Puisque tous les nœuds dans le graphe ont un degré pair, le graphe (ou chacune de ses composantes connexes) admet un circuit eulérien. Nous pouvons trouver un tel circuit en utilisant une recherche en profondeur (DFS). Pendant la traversée du circuit, nous alternons l'attribution des éléments aux ensembles 'L' et 'R'. Si nous suivons une arête du nœud de tableau au nœud de nombre, l'élément est attribué à 'L'. Si nous suivons une arête du nœud de nombre au nœud de tableau, l'élément est attribué à 'R'. Comme chaque arête est traversée exactement une fois, et les attributions alternent (chaque arête utilisée dans un sens pour 'L' sera "compensée" par une autre arête dans l'autre sens pour 'R' au niveau d'un autre nœud), cela garantit que chaque tableau aura exactement la moitié de ses éléments en 'L' et l'autre moitié en 'R'.

Détails d'implémentation :

• Une std::map<int, int> est utilisée pour la discrétisation des grandes valeurs numériques.
• La liste d'adjacence adj stocke des paires {voisin_idx, original_pos_in_array}.
• Le tableau degres_courants est utilisé pour suivre le nombre d'arêtes non visitées partant d'un nœud lors du DFS, en agissant comme un pointeur vers la prochaine arête à explorer.
• Deux fonctions DFS mutuellement récursives, dfs_array_node et dfs_value_node, sont employées pour gérer la logique d'attribution 'L'/'R' et simuler le parcours bipartite.

#include <iostream>
#include <vector>
#include <map>
#include <numeric> // Non strictement nécessaire mais souvent inclus
#include <algorithm> // Pour std::max (non directement utilisé ici mais utile)

// Constantes pour la taille maximale des nœuds dans le graphe.
// MAX_ARRAY_NODES pour les nœuds représentant les tableaux (1 à m_arrays).
// MAX_VAL_NODES pour tous les nœuds (tableaux + valeurs discrétisées),
// qui peut être m_arrays + 2 * m_arrays (si toutes les valeurs sont distinctes et différentes des indices de tableaux).
const int MAX_ARRAY_NODES = 100005;
const int MAX_VAL_NODES = MAX_ARRAY_NODES + (2 * MAX_ARRAY_NODES); // m_arrays + max_distinct_values, avec 2*N max distinct values.

// Adjacence list: adj[u] contient des paires {v, original_array_element_pos}.
// v est l'index du nœud voisin.
// original_array_element_pos est l'index 1-basé de l'élément dans le tableau du nœud 'u' (si 'u' est un nœud de tableau).
std::vector<:pair int="">> adj[MAX_VAL_NODES]; 

// resultats[i][j] stockera 1 pour 'L', 2 pour 'R' pour l'élément à la position j du tableau i.
std::vector<int> resultats[MAX_ARRAY_NODES]; 

int m_arrays; // Nombre total de tableaux.
int total_distinct_values = 0; // Compteur pour les valeurs uniques après discrétisation.
std::map<int int=""> map_valeurs; // Mappe les valeurs d'origine à des indices discrétisés.
int degres_courants[MAX_VAL_NODES]; // Utilisé comme un pointeur pour les arêtes non encore visitées pour chaque nœud.

// Décalage pour les indices des nœuds de valeur.
// Les nœuds de tableau sont de 1 à m_arrays.
// Les nœuds de valeur sont de VAL_NODE_OFFSET + 1 à VAL_NODE_OFFSET + total_distinct_values.
const int VAL_NODE_OFFSET = MAX_ARRAY_NODES; 

// Fonctions DFS mutuellement récursives pour parcourir le graphe bipartite et attribuer L/R.
void dfs_array_node(int array_node_idx);
void dfs_value_node(int value_node_idx);

// DFS à partir d'un nœud de tableau
void dfs_array_node(int array_node_idx) {
    // Tant qu'il y a des arêtes sortantes non traitées pour ce nœud de tableau
    // et que l'attribution de l'élément correspondant n'est pas encore faite (vérifié par resultats != 0).
    while (degres_courants[array_node_idx] >= 0 && 
           resultats[array_node_idx][adj[array_node_idx][degres_courants[array_node_idx]].second] != 0) {
        degres_courants[array_node_idx]--; // Passe à l'arête précédente
    }

    if (degres_courants[array_node_idx] < 0) { // Si toutes les arêtes ont été traitées ou il n'y en a pas
        return;
    }

    // Récupère les informations de l'arête courante
    int voisin_node_idx = adj[array_node_idx][degres_courants[array_node_idx]].first;
    int original_element_pos = adj[array_node_idx][degres_courants[array_node_idx]].second;

    // Attribue 'L' (représenté par 1) à l'élément du tableau
    resultats[array_node_idx][original_element_pos] = 1;
    degres_courants[array_node_idx]--; // Marque l'arête comme visitée

    // Continue le DFS à partir du nœud de valeur voisin
    dfs_value_node(voisin_node_idx);
}

// DFS à partir d'un nœud de valeur
void dfs_value_node(int value_node_idx) {
    // Même logique que pour dfs_array_node
    while (degres_courants[value_node_idx] >= 0 && 
           resultats[adj[value_node_idx][degres_courants[value_node_idx]].first][adj[value_node_idx][degres_courants[value_node_idx]].second] != 0) {
        degres_courants[value_node_idx]--;
    }

    if (degres_courants[value_node_idx] < 0) { // Si toutes les arêtes ont été traitées
        return;
    }

    // Récupère les informations de l'arête courante
    int voisin_array_node_idx = adj[value_node_idx][degres_courants[value_node_idx]].first;
    int original_element_pos = adj[value_node_idx][degres_courants[value_node_idx]].second;

    // Attribue 'R' (représenté par 2) à l'élément du tableau
    resultats[voisin_array_node_idx][original_element_pos] = 2;
    degres_courants[value_node_idx]--; // Marque l'arête comme visitée

    // Continue le DFS à partir du nœud de tableau voisin
    dfs_array_node(voisin_array_node_idx);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> m_arrays;

    std::vector<int> compteur_occurrences_valeurs(MAX_VAL_NODES, 0); // Pour compter les occurrences totales des valeurs

    // Lecture des tableaux, discrétisation des valeurs et comptage des occurrences
    std::vector<:vector>> valeurs_initiales(m_arrays + 1); // Pour stocker temporairement les valeurs lues
    for (int i = 1; i <= m_arrays; ++i) {
        int k_elements_in_array;
        std::cin >> k_elements_in_array;
        valeurs_initiales[i].resize(k_elements_in_array + 1); // Redimensionne pour une indexation 1-basée
        resultats[i].resize(k_elements_in_array + 1, 0);     // Initialise les résultats à 0 (non attribué)

        for (int j = 1; j <= k_elements_in_array; ++j) {
            std::cin >> valeurs_initiales[i][j];
            if (map_valeurs.find(valeurs_initiales[i][j]) == map_valeurs.end()) {
                map_valeurs[valeurs_initiales[i][j]] = ++total_distinct_values;
            }
            compteur_occurrences_valeurs[VAL_NODE_OFFSET + map_valeurs[valeurs_initiales[i][j]]]++;
        }
    }

    // Vérification de la faisabilité: chaque valeur doit apparaître un nombre pair de fois au total
    for (int i = 1; i <= total_distinct_values; ++i) {
        if (compteur_occurrences_valeurs[VAL_NODE_OFFSET + i] % 2 != 0) {
            std::cout << "NO\n";
            return 0;
        }
    }

    std::cout << "YES\n";

    // Construction du graphe d'adjacence
    for (int i = 1; i <= m_arrays; ++i) {
        for (int j = 1; j < valeurs_initiales[i].size(); ++j) { // Iterate through elements of current array
            int val_discretisee_idx = VAL_NODE_OFFSET + map_valeurs[valeurs_initiales[i][j]];
            
            // Ajoute les arêtes bidirectionnelles entre le nœud de tableau et le nœud de valeur discrétisée
            adj[i].push_back({val_discretisee_idx, j}); // Arête du tableau vers la valeur
            adj[val_discretisee_idx].push_back({i, j}); // Arête de la valeur vers le tableau
        }
    }

    // Initialise les pointeurs de degrés courants pour le DFS.
    // Chaque nœud a un nombre d'arêtes sortantes égal à sa taille dans l'adjacence list.
    // Nous initialisons à (taille - 1) pour pointer vers le dernier élément, puis décrémentons.
    for (int i = 1; i < MAX_VAL_NODES; ++i) { // Itérer sur tous les indices de nœuds possibles
        degres_courants[i] = adj[i].size() - 1;
    }

    // Lance le DFS à partir de chaque nœud de tableau qui a des arêtes non traitées.
    // Cela couvre toutes les composantes connexes du graphe.
    for (int i = 1; i <= m_arrays; ++i) {
        if (degres_courants[i] >= 0) { 
            dfs_array_node(i);
        }
    }

    // Affiche les résultats finaux
    for (int i = 1; i <= m_arrays; ++i) {
        for (int j = 1; j < resultats[i].size(); ++j) {
            if (resultats[i][j] == 1) {
                std::cout << 'L';
            } else {
                std::cout << 'R';
            }
        }
        std::cout << "\n";
    }

    return 0;
}
</:vector></int></int></int></:pair>