That's the last one, I thought as I finished the last of the emails. SEND. Blackout. I felt a shrill run down my spine. What was going on? Almost instantly the control panel started lighting up again. In a desperate attempt to figure out what had happened I tried to access one of the surveillance cameras on the bottom floor. Click!
You think you can defeat me? the deep, muffled voice pounded on my eardrums. It was him...one of Russia's most feared generals... Igor Plushenkovici. You are nothing... I have defeated your entire navy and air force... what else would you like me to do? My heart sank. You know... you are very persistent nation... but you see... persistence is this case is, well, stupidity he chuckled. Most predators like to play with their meal before they devour it, so I tell you what... we play little game I like to call: decipher the code, or presidential estate goes BOOM!. My heart started racing... what kind of sick, twisted person was this? I remembered the president telling one of his officials how vile Igor's habits were. So... the voice shrieked We play?
Two buttons appeared on the center screen of the control panel.
YES or NO?
My head was spinning... had I made the right choice? I was just another one of Igor's toys... another victim that caved into his cruelty...
Let the games begin!
A white envelope icon appeared on the screen. Click. Flash. I started reading the message, it was a code. There are two strings, denoted by A and B, whose lengths' are N and M. For each element from the A string you can subtract at most one element from the B string. Your task is to find the maximum number of unique numbers. Remember that you must only count each number once, no matter how many times it appears in the final list. Your time starts... NOW!
5:004:594:58
...
Input
N and M are on the first line. The elements from string A are on the second line and the elements from string B are on the third line.Output
On the first line of the input, print the final values of the elements of string A, and on the next line, the final numbers, in their original order.Constraints
1 ≤ N ≤ 10000 ≤ M ≤ 1000The elements of strings A and B are signed
30 bits integer numbers.If there is more than one solution, you can print any of them.
Sample
| Input | Output |
|---|---|
| 4 0 1 1 1 1 | 1 1 1 1 1 |
Problema a fost propusa in ideea de a fi o buna tema de gandire pentru participanti. Pe de o parte ea avea o solutie destul de simpla ca idee, folosind un algoritm de cuplaj in graf bipartit (care trebuia sa aiba o complexitate cel putin la fel de buna ca Algoritmul Hopcroft-Karp, in cazul limitelor din problema). Pe de alta parte, s-a lasat ca tema concurentilor gasirea unui algoritm de tip greedy corect la aceasta problema.
Solutia folosind cuplaj s-a bazat pe urmatoarea idee: Fiecare numar x are M stari: starea x, starea x-b[1], x-b[2], …, x-b[m]. Dupa o normalizare (cel mai usor se implementa cu un std::map), cuplajul se realiza intre multimea elementelor initiale si multimea elementelor finale, unde elementele finale se comprima, elementele duble fiind eliminate. Asteptam explicatia oricarei solutii greedy corecte (demonstrabil, sau macar intuitiv) pe facebook.
