CodeForces.com is a web site for competitive programming. One of the 2 really famous sites in internet. Yesterday I was fighting with a the problem 2 in Division B from competition number 814 for about 1 hour, until I have managed to solve it. The problem itself was not that complicated, but the point was that some of the instructions were not very clear, e.g. they were somehow “hidden” in the examples.
Anyhow, this is the problem:
On that night, Sengoku constructed a permutation p1, p2, …, pn of integers from 1 to n inclusive, with each integer representing a colour, wishing for the colours to see in the coming meteor outburst. Two incredible outbursts then arrived, each with n meteorids, colours of which being integer sequences a1, a2, …, an and b1, b2, …, bn respectively. Meteoroids’ colours were also between 1 and n inclusive, and the two sequences were not identical, that is, at least one i (1 ≤ i ≤ n) exists, such that ai ≠ bi holds.
Well, she almost had it all — each of the sequences a and b matched exactly n - 1 elements in Sengoku’s permutation. In other words, there is exactly one i (1 ≤ i ≤ n) such that ai ≠ pi, and exactly one j (1 ≤ j ≤ n) such that bj ≠ pj.
For now, Sengoku is able to recover the actual colour sequences a and b through astronomical records, but her wishes have been long forgotten. You are to reconstruct any possible permutation Sengoku could have had on that night.
The first line of input contains a positive integer n (2 ≤ n ≤ 1 000) — the length of Sengoku’s permutation, being the length of both meteor outbursts at the same time.
The second line contains n space-separated integers a1, a2, …, an (1 ≤ ai ≤ n) — the sequence of colours in the first meteor outburst.
The third line contains n space-separated integers b1, b2, …, bn (1 ≤ bi ≤ n) — the sequence of colours in the second meteor outburst. At least one i (1 ≤ i ≤ n) exists, such that ai ≠ bi holds.
Output n space-separated integers p1, p2, …, pn, denoting a possible permutation Sengoku could have had. If there are more than one possible answer, output any one of them.
Input guarantees that such permutation exists.
So, what do we have? 3 Lines for input, 1 line for output. Like this:
|
1 2 3 |
4 1 1 3 4 1 4 3 4 |
|
1 |
1 2 3 4 |
The idea is that we should give as an output such a line, that is exactly with 1 position different from the other 2 lines. At the beginning I thought that this may be translated as 1 999 3 4 for the current test, as far as 999 is also not present in both 1 1 3 4 and 1 4 3 4. However, there seems to be a hidden condition, which I could not find anywhere – the condition is that in case of equality, the given number should be a number between 1 and the maximum number given in the input. Thus, in the example, such number is 2 so it is given there.
So, let’s start with the analysis of the solution. First we read the input and we split it into 2 lists liB and liA. Then, whenever we see a different element in position i in either LiA or LiB we add it in liC or liD, depending on whether this is the first or the second time we see a different element. We remember the position of the element as well.
In the general case the problem is quite easy – we have 2 different lists as output and we are assured that we have at least one good output. Thus, we compare the count of the distinct values in liC with the values in liC if (liC.Distinct().Count() == liC.Count()). Then, depending on the answer we print either liC or liD.
However, there can be a case, that we do not have two distinct positions, but only one (as in the example). Thus, we have to work a bit more – we declare iMin, iMax and iVal, just to see which is the value, that should be added (in our example it is 2). iVal is initially set to -1, thus it can be checked whether it is changed. If it is not changed, then its value is either 1 or iMax+1.
At last we have to print the list, but this is really a trivial task. In the current example I have a method for this.
Here comes the code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
using System; using System.Collections.Generic; using System.Linq; class Startup { static void Main() { int n = int.Parse(Console.ReadLine()); int iVal = -1; int k = 0; int position = -1; List<int> liA = new List<int>(); List<int> liB = new List<int>(); List<int> liC = new List<int>(); List<int> liD = new List<int>(); liA = Console.ReadLine().Split().Select(int.Parse).ToList(); liB = Console.ReadLine().Split().Select(int.Parse).ToList(); for (int i = 0; i < n; i++) { if (liA[i] == liB[i]) { liC.Add(liA[i]); liD.Add(liA[i]); } else { position = i; k++; if (k == 1) { liC.Add(liB[i]); liD.Add(liA[i]); } else { liC.Add(liA[i]); liD.Add(liB[i]); } } } if (k == 1) { int iMin = Math.Min(liA.Min(), liB.Min()); int iMax = Math.Max(liA.Max(), liB.Max()); for (int i = iMin; i < iMax; i++) { if ((!liA.Contains(i)) && (!liB.Contains(i))) { iVal = i; break; } } if (iVal == -1) { if (iMin == 2) { iVal = 1; } else { iVal = ++iMax; } } liC[position] = iVal; liD[position] = iVal; } if (liC.Distinct().Count() == liC.Count()) { Console.WriteLine(PrintListInLine(liC)); } else { Console.WriteLine(PrintListInLine(liD)); } } public static string PrintListInLine(List<int> myList) { string strPrint = ""; for (int i = 0; i < myList.Count; i++) { strPrint += myList[i] + " "; } strPrint = strPrint.Trim(); return strPrint; } } |
Enjoy!