skpro19's blog

By skpro19, history, 8 years ago, In English

The problem is 294C.

The tutorial says this:

The third sample is ...#...#... where # is a switched on lamp and . is a switched off lamp. As you can see we have three different types of lights. The first three lights (Type A), the 5th to 8th lights (Type B) and the last three lights (Type C). We have to switch on the lights three times for each type of lights. Aside from the order of moves for each type there are  possible permutations of the string AAABBBCCC which tells us how to combine the steps of different types. Switching on the lights is done uniquely for types 1 and 3. But for type 2 each time we have to possible options until we're left with one off light. So there are 2^(3 - 1) ways to do this. So the answer would be 1680*1*4*1 = 6720.

I can not understand the  part. A little help would be very much appreciated.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If you can understand that we have to find the number of permutations of the string AAABBBCCC, read through this.

If you are having a hard time understanding why we have to find the number of permutations of the string AAABBBCCC, think about it this way — if we want to go turn on a light in the type "A", there is only one possible way to do so. For type "B" there are two ways to do it except at the very final light in type "B". Therefore, we can just find the number permutations of the string AAABBBCCC.

(very bad explanation, I know. Sorry..)