The 2003 27 th Annual ACM International Collegiate Programming Contest World Finals sponsored by IBM Problem B
Hollywood's newest theater, the Atheneum of Culture and Movies, has a huge computer-operated marquee composed of thousands of light bulbs. Each row of bulbs is operated by a set of switches that are electronically controlled by a computer program. Unfortunately, the electrician installed the wrong kind of switches, and tonight is the ACM's opening night. You must write a program to make the switches perform correctly. A row of the marquee contains n light bulbs controlled by n switches. Bulbs and switches are numbered from 1 to n, left to right. Each bulb can either be ON or OFF. Each input case will contain the initial state and the desired final state for a single row of bulbs.
The original lighting plan was to have each switch control a single bulb. However the electrician's error caused each switch to control two or three consecutive bulbs, as shown in Figure 1. The leftmost switch (i = 1) toggles the states of the two leftmost bulbs (1 and 2); the rightmost switch (i = n) toggles the states of the two rightmost bulbs (n-1 and n). Each remaining switch (1 < i < n) toggles the states of the three bulbs with indices i-1, i, and i+1. (In the special case where there is a single bulb and a single switch, the switch simply toggles the state of that bulb.) Thus, if bulb 1 is ON and bulb 2 is OFF, flipping switch 1 will turn bulb 1 OFF and bulb 2 ON. The minimum cost of changing a row of bulbs from an initial configuration to a final configuration is the minimum number of switches that must be flipped to achieve the change.
You can represent the state of a row of bulbs in binary, where 0 means the bulb is OFF and 1 means the bulb is ON. For instance, 01100 represents a row of five bulbs in which the second and third bulbs are both ON. You could transform this state into 10000 by flipping switches 1, 4, and 5, but it would be less costly to simply flip switch 2. You must write a program that determines the switches that must be flipped to change a row of light bulbs from its initial state to its desired final state with minimal cost. Some combinations of initial and final states may not be feasible. For compactness of representation, decimal integers are used instead of binary for the bulb configurations. Thus, 01100 and 10000 are represented by the decimal integers 12 and 16.
The input file contains several test cases. Each test case consists of one line. The line contains two non-negative decimal integers, at least one of which is positive and each of which contains at most 100 digits. The first integer represents the initial state of the row of bulbs and the second integer represents the final state of the row. The binary equivalent of these integers represents the initial and final states of the bulbs, where 1 means ON and 0 means OFF.
To avoid problems with leading zeros, assume that the first bulb in either the initial or the final configuration (or both) is ON. There are no leading or trailing blanks in the input lines, no leading zeros in the two decimal integers, and the initial and final states are separated by a single blank.
The last test case is followed by a line containing two zeros.
For each test case, print a line containing the case number and a decimal integer representing a minimum-cost set of switches that need to be flipped to convert the row of bulbs from initial state to final state. In the binary equivalent of this integer, the rightmost (least significant) bit represents the n th switch, 1 indicates that a switch has been flipped, and 0 indicates that the switch has not been flipped. If there is no solution, print "impossible". If there is more than one solution, print the one with the smallest decimal equivalent.
Print a blank line between cases. Use the output format shown in the example.
Sample Input Output for the Sample Input
12 16 Case Number 1: 8
1 1
3 0 Case Number 2: 0
30 5
7038312 7427958190 Case Number 3: 1
4253404109 657546225
0 0 Case Number 4: 10
Case Number 5: 2805591535
Case Number 6: impossible
First of all, we need to deal with decimal strings. Internally, we represent light bulbs and light switches with binary strings. The input strings for initial and final states of light bulbs need to be converted to binary strings from decimal strings. The solution representing a string of ON/OFF of light switches internally can be best represented as binary string. However, the output format is required to be decimal string. Therefore, we also need to handle the conversion from binary string to decimal string as well.
With the sample case 4, the initial and final states of input are "30" and "5", which can be represented as
"30" --> "11110" "5" --> "101"
We need to find out the difference between the initial state and final state. This can be done by implementing exclusive-or operation on two binary strings. Given the sample case 4, the difference between initial state and final state is "11011":
"11110" XOR "00101" --> "11011"
Let I be the binary string for initial state, F be the final state, D be the binary string representing the difference between I and F, S be the string of light switches we are trying to find. That is: S XOR I = F. Then S XOR (I XOR F) = F XOR F. Therefore S XOR D = 0.
Based on S XOR D = 0, we need to find a string of ON/OFF light switches that can eliminate the difference between the inital state and final state. In other words, by flipping some light switches on the difference state, make it all zeros. For example, with the difference state "11011" of sample case 4, we can turn off switch 1, turn on switch 2, turn off switch 3, turn on switch 4, turn off switch 5.
flip switch 2 1 1 0 1 1 --> 0 0 1 1 1 flip switch 4 0 0 1 1 1 --> 0 0 0 0 0
To find out the combination of light switches that need to be flipped, we start from switch one, we try with the switch one off, then we consider next switch. If the next switch could be off, we then move on to the switch after. Otherwise, we try with the switch on, if this will elminate all difference of previous bulbs, we move on the next, otherwise, we will backtrack to a off switch. With the off switch, we will try with the switch on. If with switch on does not work, we will keep backtacking until there is no other possible combination of light switches or we find one switch that can be flipped. With the latter case, we can start to try next switch again. Once the last switch has been tried successfully, then we get a solution.
difference state switch state state after applying switch(es) 11011 0 11011 11011 00 11011 NOT OK 11011 01 00111 00111 010 00111 00111 0101 00000 00000 01010 00000 00000 no more switch, one solution 01010 is found. backtrack 00000 01011 NOT OK backtrack 00111 011 01001 NOT OK backtrack 11011 1 00011 00011 10 00011 00011 100 00011 00011 1000 00011 00011 10001 00000 00000 no more switch, another solution 10001 is found. All combinations have been tried. Since "01010" and "10001" have the same cost (containing same number of ON switches), we just keep the first solution.
Print the minimal cost solution as decimal string. With the sample solution "01010", we need to convert it to decimal string "10".
#include <vector> #include <string> #include <iostream> using namespace std; namespace lightbulbs_acm_programming_contest_world_final_2003b { // The function decimals2binarys will generate a binary string based on the input decimal string // sample input sample output // "16" "10000" // "3" "11" // "12" "1100" // "1025" "10000000001" // Please note that the dec_str could be as long as 100 decimal digits, so the routine should be // generic enough to handle very long strings. string decimals2binarys(string dec_str) { string binary_s; size_t next = 0; size_t et = dec_str.size(); do { int r = 0; size_t st = next; while (st < et) { int d = 0; d = r * 10 + dec_str[st]-'0'; r = d%2; d = d/2; dec_str[st++] = d+'0'; } binary_s.insert(binary_s.begin(),r+'0'); while(next<et&&dec_str[next]=='0') next++; } while(next<et); return binary_s; } // The function binarys2hexs will convert a binary string to a hexical string. // sample input sample output // "1011" "B" // "10000" "10" // "11010" "1A" // "101010001111" "A8F" string binarys2hexs(string bstr) { string hexs; size_t et = bstr.size(); while(et>0) { size_t st; if (et<4) st = 0; else st = et-4; int d=0; for (size_t i=st; i<et; i++) d = d*2+bstr[i]-'0'; char h; if (d<10) h = '0'+d; else h = 'A'+d-10; hexs.insert(hexs.begin(),h); et = st; } return hexs; } // The hexs2decimals function will convert hexical string to decimal string with equal value // Sample input (input hex string) Sample output (return string) // "FF" "255" // "FFEE" "65518" // "FFFF" "65535" // "10" "16" string hexs2decimals(string hexs) { string decimal_s; size_t next = 0; size_t et = hexs.size(); do { int r = 0; size_t st = next; while (st < et) { int d = 0; d = r * 16 + (hexs[st]>='0'&&hexs[st]<='9'?(hexs[st]-'0'):(10+hexs[st]-'A')); r = d%10; d = d/10; hexs[st++] = (d>=0&&d<=9)?(d+'0'):('A'+d-10); } char c=r+'0'; decimal_s.insert(decimal_s.begin(),c); while(next<et&&hexs[next]=='0') next++; } while(next<et); return decimal_s; } // The function binarys2decimals will generate a decimal string based on the input binary string // sample input sample output // "10000" "16" // "11" "3" // "1100" "12" // "10000000001" "1025" string binarys2decimals(string binary_str) { return hexs2decimals(binarys2hexs(binary_str)); } // xor_char implements XOR on two chars represent 0 and 1 // sample input sample output // 0 0 0 // 0 1 1 // 1 0 1 // 1 1 0 inline char xor_char(char c1, char c2) { return (c1==c2)?'0':'1'; } // xor_bstr implements XOR on two binary strings // sample input sample output // 1001 1 1000 // 1010 11 1001 // 1100 1011 0111 // 1111 111 1000 string xor_bstr(string &op1, string &op2) { string s; string::reverse_iterator it1=op1.rbegin(), it2=op2.rbegin(); for(; it1!=op1.rend()&&it2!=op2.rend(); it1++, it2++) s.insert(s.begin(), xor_char(*it1,*it2)); if(it1!=op1.rend()) { for(;it1!=op1.rend();it1++) s.insert(s.begin(), *it1); } else if(it2!=op2.rend()) { for(;it2!=op2.rend();it2++) s.insert(s.begin(), *it2); } return s; } // flipchar implements flip operation on 0 and 1 represented by char // sample input sample output // 1 0 // 0 1 inline char flipchar(char c) { return (c=='0')?'1':'0'; } // calculate the cost of a solution i.e. number of '1' in a binary string // sample input sample output // 1001000 2 // 0010000 1 // 1110000 3 int costof(string switches) { int cost = 0; for (size_t t = 0; t<switches.size(); t++) if (switches[t]=='1') ++cost; return cost; } // search_solution function will start constructing with a partial solution described // by: // diff_stat -- difference state upon which the solution will apply // prev -- with any pre[i] is the state of i after applying solution[i-1] // and solution[i] upon diff_stat // solution -- light switches // current_idx -- current light bulb state to consider // startswitch -- '0' or '1' to indicate ON or OFF switch to try // bool search_solution(const string &diff_stat, string &prev, string &solution, size_t ¤t_idx, char startswitch) { size_t first_idx = current_idx; while(current_idx<solution.size()) { if (current_idx==0) { if (startswitch=='0') { solution[current_idx] = '0'; prev[current_idx] = diff_stat[current_idx]; } else { solution[current_idx] = '1'; prev[current_idx] = flipchar(diff_stat[current_idx]); } } else { if (prev[current_idx-1]=='0') { if (current_idx==first_idx&&startswitch=='1') //start with '1', violate last bit state return false; solution[current_idx] = '0'; //current switch off prev[current_idx] = (solution[current_idx-1]=='0')?diff_stat[current_idx]: flipchar(diff_stat[current_idx]); //flip by last switch } else // prev[current_idx-1]=='1' { solution[current_idx] = '1'; prev[current_idx] = (solution[current_idx-1]=='1')?diff_stat[current_idx]: flipchar(diff_stat[current_idx]); } } current_idx++; } return prev[current_idx-1]=='0'; } // lightbulbs function will search for solution of minimal cost based on the initial // state, final state, and print the result with case number. void lightbulbs(string init_stat, string final_stat, int caseno) { init_stat = decimals2binarys(init_stat); final_stat = decimals2binarys(final_stat); string diff_stat = xor_bstr(init_stat,final_stat); //our goal is to change diff_stat to 0 by applying the light switches string minimalcost_solution; int mincost; string solution(diff_stat.size(),'0'); string prev(diff_stat.size(),'0'); size_t current_idx = 0; char startswitch = '0'; //backtracking do { bool res = search_solution(diff_stat, prev, solution, current_idx, startswitch); if (res==true) { if (minimalcost_solution.size()==0) { minimalcost_solution = solution; mincost = costof(solution); } else { if (costof(solution)<mincost) { minimalcost_solution = solution; mincost = costof(solution); } } } //backtracking while(current_idx>0&&solution[current_idx-1]=='1') current_idx--; if (current_idx==0) { //no more solution break; } --current_idx; startswitch = '1'; }while(1); if (minimalcost_solution.size()>0) cout<<"Case Number "<<caseno<<": "<<binarys2decimals(minimalcost_solution)<<endl; else cout<<"Case Number "<<caseno<<": impossible"<<endl; } // lightbulbs_solver() will first read in all pairs of initial/final states. It will try to solve // each pair of initial/final state by calling lightbulbs function, which will find a minimal cost // solution that consists of a string of ON/OFF switches. By applying the solution to the light bulbs // with the initial state, those light bulbs will turn into the final state. // If a solution does not exist for a pair of initial/final state, lightbulbs function will print "impossible" // with the case number. void lightbulbs_solver() { vector<string> init_stats; vector<string> final_stats; string init_s, final_s; do { cin>>init_s; cin>>final_s; if (init_s!="0"||final_s!="0") { init_stats.push_back(init_s); final_stats.push_back(final_s); } else break; } while(1); for (size_t t=0; t<init_stats.size(); t++) { if (t!=0) cout<<endl; //print blank line between cases lightbulbs(init_stats[t], final_stats[t], (int)t+1); } } }