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
|
CoNtRaDiCtIoN:
2015-05-27 12:31:32
awesome problem :) |
|
Rajat (1307086):
2015-03-28 00:56:52
There are several solutions, but if you apply the correct logic you will get one and only one.
|
|
chamini2:
2015-02-13 23:46:34
It's not test 18, it's wrong answer in general. |
|
Malinga:
2014-12-25 16:23:20
Getting wrong answer in 18th test case...any suggestions please ?? |
|
Anubhav Balodhi :
2014-12-18 14:10:04
got AC, after lot of tries :-) |
|
Retaliation:
2014-12-07 07:40:41
I got an internal error while submitting the code in python.
|
|
Francis:
2014-05-14 07:22:42
after WA,TLE,SIGSEGV finally get AC in a simple way in O(n), but still TLE with backtrace and dfs.
|
|
Rishav Goyal:
2014-03-11 11:42:21
weo ! nice indeed! |
|
Kushagra Sinha:
2014-03-05 18:51:10
Finally AC ... not "simple" by any means ... it is an NP-complete problem ... do not waste time trying to find a "simple" closed-form solution ... |
|
newbie:
2014-01-31 13:43:49
@author...i am getting wa many times...can you plz check submission no. 10976986 |
Added by: | Adrian Satja Kurdija |
Date: | 2011-03-13 |
Time limit: | 0.300s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |
Resource: | inspired by a math puzzle |