Escaping the Jail

Hope you all are enjoying your vacations back at home. Its very cold here at my hostel and as I am writing the post, I am almost freezing :P

Anyways, Mr Winger is very happy as his wine party was great, Thanks to Kapil and Shashank. The greedy algorithm does the trick for this problem. Sort the activity of guests according to times. Whenever a guest comes in, give him a old used glass if possible, else get a new glass. Whenever a guest goes out, just take the glass from him and add it to the old glass stock. For a C/C++ implementation, do get in touch with me.

Well, I do wanted to share about palindromes in this post, but I am in a hurry. So lets keep the theory for the next post :)

Mr Sanders, the in-charge of New Orleans Jail has 23 prisoners in his custody. He offers them to take each of them in a room, one by one. The room has 2 switches. On entering the room, a prisoner has to toggle the condition of any one of the two switches. Mr Sanders randomly selects the prisoners each day, so there is an equal probability of selecting each of the 23 prisoners. On any day, a prisoner can assert that all his co--prisoners along with him have visited the room at least once. However, if his assertion is false all of the prisoners would be fed to alligators. On the other hand, on a right assertion they all would be set free. The prisoners want to know about the room and the switches, but Mr Sanders refuses to give any more information.

The prisoners can discuss their strategy for tonight. After that, they wont be allowed to talk to each other. Can you help the prisoners decide a strategy which would let them surely escape the prison? Prisoners also want to know the average time before they get out of the prison. Considering a random selection of prisoners by Mr Sanders, try predicting this value as per your strategy.

Keep puzzling.. enjoy :)
Take Care
Vivek
nitkkr.vivek@gmail.com