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
ayushgupta1997:
2017-12-21 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:
2017-07-24 23:50:31
stuck on test case 18....ques is very easy though i am wondering where am i making mistake |
|
candide:
2017-04-11 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:
2017-03-21 15:21:48
really nice problem..try breaking down to subproblem (keep in mind length of given row is even)..:)
|
|
stark_attack:
2017-02-17 08:23:35
getting WA answer after 18th testcase any suggestions . |
|
vivek4434:
2017-01-30 21:10:37
what is meant by first condition ??
|
|
papan_97:
2016-12-16 18:16:04
Tried again after a long time...this time AC in second go after a stupid runtime error i made. Even after getting AC i couldn't believe it was so simple .. :p
|
|
sanjay:
2016-06-02 08:58:42
Took a long time to get AC |
|
rayofhopee:
2016-05-20 16:34:58
If stuck at testcase 9.....try this..
|
|
comp0zr:
2016-05-08 04:52:11
Two compilation errors because I forgot to remove a few isolated references to a debugging macro I added, but after I did that I got and AC on my first scored submission (which at this point in my development as a programmer is quite an accomplishment!). Like usual, I spent all night coming up with a convoluted algorithm that included multi-dimensional arrays and random number generation, but eventually gave up and realized while I was out for the day how simple the solution for this actually is! Completely trashed my original approach and ended up finishing it in about 2 hours... like well-designed algorithms so often seem to be, the best approaches are often much simpler than they first appear. In any case, this site is great, I can see an immense improvement in my understanding of many concepts since I've been here. Cheers! |
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 |