ABCD  Colours A, B, C, D
Consider a table with 2 rows and 2N columns (a total of 4N cells). Each cell of the first row is coloured by one of the colours A, B, C, D such that there are no two adjacent cells of the same colour. You have to colour the second row using colours A, B, C, D such that:
 There are exactly N cells of each colour (A, B, C and D) in the table.
 There are no two adjacent cells of the same colour. (Adjacent cells share a vertical or a horizontal side.)
It is guaranteed that the solution, not necessarily unique, will always exist.
Input
[a natural number N ≤ 50000]
[a string of 2N letters from the set {A, B, C, D}, representing the first row of the table]
Output
[a string of 2N letters from the set {A, B, C, D}, representing the second row of the table]
Example
Input: 1 CB Output: AD
Input: 2 ABAD Output: BCDC
hide comments
rc_4594:
20180930 09:26:06
If you are thinking of a greedy solution which places the least frequency letter which is valid(which does'nt match with the adjacent letters) at every point


nadstratosfer:
20180127 16:56:15
Got best time in Py3 with the same O(n) code that TLEd until I made a certain assumption about test cases. Also, with 18 separate testfiles my runtime of 0.37s mostly measures the total of interpreter startups (same code ACs in 0.08s in Py2 where interpreter launches faster). Pointless trying to optimize when AC itself is a lottery. Frustratingly stupid way of setting an otherwise interesting problem. Last edit: 20180127 17:38:19 

mark42:
20180127 09:49:44
AC in one go.. seriously this piece of spoj made my day


biswajitk123:
20180112 22:32:40
awesome logic!simply beautiful!!!


d_y1997:
20171222 13:19:18
18th testcase if wrong ..


ayushgupta1997:
20171221 19:53:32
Became one of my fav problem :) .Got one runtime error as max size of array will be 2*n I took n. Solved myself, made my day!!


dunjen_master:
20170724 23:50:31
stuck on test case 18....ques is very easy though i am wondering where am i making mistake 

candide:
20170411 12:41:30
Accurate problem description. Solution needs much more tricky logic than algorithmics. Keep it simple! remember: you have 4 colors and each row has even length ... 

Pratik Ritesh:
20170321 15:21:48
really nice problem..try breaking down to subproblem (keep in mind length of given row is even)..:)


stark_attack:
20170217 08:23:35
getting WA answer after 18th testcase any suggestions . 
Added by:  Adrian Satja Kurdija 
Date:  20110313 
Time limit:  0.190s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 
Resource:  inspired by a math puzzle 