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:

*Sengoku still remembers the mysterious “colourful meteoroids” she discovered with Lala-chan when they were little. In particular, one of the nights impressed her deeply, giving her the illusion that all her fancies would be realized.*

*On that night, Sengoku constructed a permutation p _{1}, p_{2}, …, p_{n} 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 a_{1}, a_{2}, …, a_{n} and b_{1}, b_{2}, …, b_{n} 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 a_{i} ≠ b_{i} 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 a _{i} ≠ p_{i}, and exactly one j (1 ≤ j ≤ n) such that b_{j} ≠ p_{j}.*

*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.*

*Input*

*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 a _{1}, a_{2}, …, a_{n} (1 ≤ a_{i} ≤ n) — the sequence of colours in the first meteor outburst.*

*The third line contains n space-separated integers b _{1}, b_{2}, …, b_{n} (1 ≤ b_{i} ≤ n) — the sequence of colours in the second meteor outburst. At least one i (1 ≤ i ≤ n) exists, such that a_{i} ≠ b_{i} holds.*

*Output*

*Output n space-separated integers p _{1}, p_{2}, …, p_{n}, 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!