ABCD - Colours A, B, C, D

no tags 

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.


[a natural number N ≤ 50000]

[a string of 2N letters from the set {A, B, C, D}, representing the first row of the table]


[a string of 2N letters from the set {A, B, C, D}, representing the second row of the table]





hide comments
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

Last edit: 2016-12-16 18:59:58
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..
answer can be :DCBDCB
was a life saver ...finally ac :-)

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!

poojan : 2016-03-09 14:36:18

2 WA ans But Finally Got It Awsome Que! One wa bcs Not terminate string '\0':
Very Good Que! Must do!

enigmus: 2016-02-24 15:19:52

Hint: Try building up your solution from smaller pieces

Ankit: 2016-02-18 17:23:42

My program runs for a O(n) but still it gives Time Limit Exceeded. Stuck badly. !!

Added by:Adrian Satja Kurdija
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