-2

I encountered a problem from 2011 Canadian Computing Competition (senior division question no 5), and I have no clue how to solve it. Here is the question:

You are walking by a row of K (4 ≤ K ≤ 25) lights, some of which are on and some of which are off. In this initial configuration, there is no consecutive sequence of four lights that are on. Whenever four or more consecutive lights are on, the lights in that consecutive block will turn off. You can only turn on lights that are off. What is the minimum number of lights you need to turn on in order to end up with all K lights off?

Input Description The first line of input will consist of the integer K, indicating the number of lights. Each of the next K lines will have either the integer 0 (to represent a light that is off) or the integer 1 (to represent a light that is on).

Output Specification Your program should output the minimum number of lights that must be turned on in order to have all K lights be off.

Sample Input 1 5 1 1 0 1 1

Output for Sample Input 1 1

Explanation of Sample 1 Notice that turning on the third light will create five consecutive lights that are on, which will in turn cause all of these five lights to be off. Note: At least 30% of the test cases will have K ≤ 10.

I don't know which type of algorithm I should use to solve this problem, since there seem to be too many possibilities. Any help will be appreciated, and I understand python, c++ and java.

IVlad
  • 43,099
  • 13
  • 111
  • 179
Tony
  • 19

2 Answers2

1

Seems like a shortest path problem on a graph, G=(V,E) where V={all light configurations} and E={ (u,v) | moving from state u to state v by turning on some light}.

This problem is solveable by a simple BFS (since the graph is unweighted), and you can even make it faster by using a bi-directional BFS, since you have a single target node.

I once explained on details how to work bi-directional search and why it is better in a different thread:


Algorithm idea: do a BFS search simultaneously from the source and the target: [BFS until depth 1 in both, until depth 2 in both, ....].
The algorithm will end when you find a vertex v, which is in both BFS's front.

Algorithm behavior: The vertex v that terminates the algorithm's run will be exactly in the middle between the source and the target.
This algorithm will yield much better result in most cases then BFS from the source [explanation why it is better then BFS follows], and will surely provide an answer, if one exist.

why is it better then BFS from the source?
assume the distance between source to target is k, and the branch factor is B [every vertex has B edges].
BFS will open: 1 + B + B^2 + ... + B^k vertices.
bi-directional BFS will open: 2 + 2B + 2B^2 + 2B^3 + .. + 2B^(k/2) vertices.

for large B and k, the second is obviously much better the the first.


NOTE, that this solution does NOT require storing the whole graph in memory, it only requires implementing a function: successor(v) which returns all the successors of a vertex [all vertices you can get to, within 1 step from v]. With this, only the nodes you open [2 + 2B + ... + 2B^(k/2) as explained above] should be stored. To further save memory, you can use Iterative Deepening DFS from one direction, instead of BFS, but it will consume more time.

Community
  • 1
  • 1
amit
  • 175,853
  • 27
  • 231
  • 333
  • I'm pretty sure this won't work, as there 2^25 = ~30 million nodes (I didn't downvote). – IVlad Feb 09 '15 at 19:15
  • @IVlad Which is not too bad, considering you don't actually have to store all of them, just those on the same distance as shortest path - which is usually significantly smaller, also note that a state can be represented by an integer as a bitvector. The fairly low number of lamps is a strong hint for an exponential solution. – amit Feb 09 '15 at 19:18
  • To fasten means "to secure", not to make faster. – David Conrad Feb 09 '15 at 19:18
  • I agree that it's definitely an exponential solution, but I disagree with your graph theoretic approach. I strongly doubt you can get this to run under the time and memory constraints of a contest. – IVlad Feb 09 '15 at 19:21
  • @IVlad In Europe's ACM, the problem [4959 - Jumping monkey](https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2960), which has a restriction of 21 "monkeys" was solved in the same way. I agree, the difference is *16, but it's not THAT far off. – amit Feb 09 '15 at 19:24
  • Well, maybe, but I still have my doubts. I don't have a better idea anyway, and it's a nice approach, +1. :) – IVlad Feb 09 '15 at 19:26
  • @IVlad: You "strongly doubt" that you can search an implicitly-defined graph with only 33M nodes on a modern computer? – tmyklebu Feb 09 '15 at 19:45
  • @tmyklebu - programming contests can set time limits as low as 0.1 seconds. And their hardware is rarely modern. So yes, I do. – IVlad Feb 09 '15 at 19:48
  • @IVlad: Yeah, I'm familiar with programming contests. The CCC doesn't do that. – tmyklebu Feb 09 '15 at 19:49
  • @tmyklebu - the OP mentioned nothing about that particular setting. My comment still stands in general, but thanks for making it clear that the restrictions are probably not very draconian. – IVlad Feb 09 '15 at 19:52
  • @IVlad: "Canadian Computing Competition" is in the question title. – tmyklebu Feb 09 '15 at 19:52
  • @tmyklebu - and that's supposed to tell me anything about their hardware and choice of time limits? – IVlad Feb 09 '15 at 19:53
  • @IVlad: Well, you can do research on essential aspects of the question instead of wondering aloud. Stage 1 of the CCC is (was?) judged by the students' high-school teachers. They are given directions on how to judge the programs (check for correct output and don't wait too long), but no particular environment or limits are prescribed. The contest has a primarily educational aim, and high-school teachers tend to employ common sense here rather than trying to screw their students with absurd time limits. – tmyklebu Feb 09 '15 at 19:58
  • @tmyklebu - I didn't wonder about anything, I just mentioned an aspect that I thought might be helpful for other people reading the question and answers. If you think my comments are useless and your only intention is to call me out on it and not help improve them, then you might as well just report them next time. – IVlad Feb 09 '15 at 20:03
  • @IVlad: My intention was to point out that your strong doubt is unfounded. – tmyklebu Feb 09 '15 at 20:06
0

I do not see a particular directed algorithm for this; I think I would treat it as a dynamic programming problem.

The initial active set contains the initial light sequence.

At each subsequent step, generate all sequences which can be reached by flipping one switch; in general, you will only flip a switch which is next to an "on" light. Drop all sequences which have already been seen.

As soon as you encounter the "all lights off" sequence, stop and return the current step-number (== the number of times you flipped a switch).

Hugh Bothwell
  • 55,315
  • 8
  • 84
  • 99