All Tracks Algorithms Dynamic Programming Dynamic Programming and Bit Masking Problem

AltF4 and UV Strip

Algorithms, Hard


AltF4 and his best friend CtrlF4 have been given a project on UV rays. They have been given N UV strips which they have to divide between themselves. Each UV strip is 30 meters long with a patch in every 1 meter. The patch is either holed (which means rays can pass through it) or it is covered. A sample 5 meter long UV strip is shown at the end of the problem statement. 1st, 2nd and 4th patches are holes and UV rays can pass through them.

Lets assume they divided the strips and AltF4 has P (1 ≤ P < N) of them (CtrlF4 has N - P,). AltF4 then follows the following method to combine his strips until he is left with only one.

  • Optimally choose any two strips from his set until there is only one.
  • Place the chosen strips one over the other so that the patches overlap. Glue them together to make it one. The patches where both the strips in the combination were "covered" have become excessive thick, so punch them to make holes in these patches.
  • GoTo step 1.

CtrlF4 performs a similar algorithm on his set of strips. Finally they take their last remaining strip and share it with one another. Because AltF4 and CtrlF4 are close friends and do not want their friend ship to break, the final strips should be exactly the same.

Your task is to help divide the strips such that their end results are exactly same. Of course it might not be always possible to divide the strips in the above manner. You are a genius and have the power to flip the state of any patch of any strip (from covered to holed and holed to covered). You want to minimize the use of this power though.

You have a closer relation with AltF4 though. Once you have used the minimum number of flips to get the final strip of both as exact same, you count the number of holes (in all the strips) with each one of them. You want that AltF4 should have the maximum number of holes possible.

Input & Output

The first line of the input contains the number of test cases T, description of T test cases follows. Each test cases begins with a line having an integer N. N lines follow which represents the description of the strips. Each line is a string of 30 characters, with letters C and H. C denotes "covered" patches and H denotes "holed" patches.

For each test case, you need to output 2 integers separated by space. The first is the minimum number of flips (or power) you need to use to make the final strip same. The second number is the maximum number of holes AltF4 can get such that you used your minimum power.


T ≤ 3000
2 ≤ N ≤ 10000

0 5
1 2

1) There are 4 strips with 1st ans 2nd exactly same and 3rd and 4th exactly same. AltF4 can give the first strip to CtrlF4 and keep the rest with him. So he has 5 holes in total. Firstly he combines last two strips, the resultant strip is HHHHHHHHHHHHHHHHHHHHHHHHHHHHHH. He then combines the resultant strip with 2nd one to get the final strip as HCCCCCCCCCCCCCCCCCCCCCCCCCCCCC. This is exactly same as what he has given to CtrlF4.

2) In the second case, 1st strip is taken by AltF4 and 2nd one is given to CtrlF4. He flips the second patch to make it H. Now both are same. Also AltF4 has 2 holes in all his strips.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

November Rain

View All Notifications