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
|
Vipul Pandey:
2014-01-05 15:47:33
good one! normal bracktracking will give tle. think little differently. |
|
Mitch Schwartz:
2013-12-15 06:24:55
I believe a custom judge is being used that allows any correct solution to pass. My AC code prints a different result for the second example case. It could be checked more thoroughly, if someone were motivated to do so. Last edit: 2013-12-15 06:32:08 |
|
cegprakash:
2013-12-15 04:20:12
nowhere in the question it's mentioned lexicographical order. Why? All possible solutions will be accepted? |
|
Avaneesh Rastogi:
2013-10-31 17:56:18
Seems like a lot of people don't read the problem-statement carefully.
|
|
Anurag Pratik:
2013-10-17 20:12:30
Watch out for the input format! |
|
californiagurl:
2013-09-25 09:50:48
@ouditchya:ur answer is just the reverse of victor's ....
|
|
Yanzhe Chen:
2013-09-05 02:34:38
Backtracing is TLE :-( |
|
suman:
2013-06-21 04:23:56
Can anyone check my solution. I m getting right answer for every tricky case given in comments.. but still wrong answer |
|
akshay khanna:
2013-06-20 16:58:57
if we print the input array from 2nd element till the end i.e 2n-1 characters; and print the last character such that it is not equal to previous one, shouldn't it give the correct answer ?
|
|
pranav gupta:
2013-04-10 11:33:54
will any solution do or it has to be smallest one in lexicographical order? Could you please provide me a test case where my solution is going wrong. I've tried too long to debug this now without knowing what exactly to debug. |
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 |