The faster, the better :)

Well, Mr Sanders is biting his nails cause Kapil and Shashank got the strategy for the prisoners within a day of posting the puzzle. Great Work guys!

Edit: I saw the mail from Pulkit Agrawal very late, but he had explained the solution in a very elegant manner. Kudos to you too sir!

The key to the solution is keeping one prisoner as the counting man. One of the switches is a counting switch which is changed whenever a prisoner except the counting man finds it in off state, provided he has never toggled the switch before. In all other cases, he toggles the other switch which is dummy switch. On the other hand, the counting man simple switches off the counting switch (in case it is on) and increases his count which is initally zero, otherwise he also plays around with the dummy switch. So as soon as the count reaches 22, he knows that all have been once into the room. To account for the absence of knowledge of initial condition of the switch, he waits till count reaches 23.

As Aditya puts in, this is the algorithm for Stop and Wait protocol (he remembers to have read it in Computer Networks lectures :-O)

Ok, for this week, I don't have much. Have been excited over going home this weekend (that is once in 6 months :-) ). So I would put down a puzzle I remember from 1st year of my college.

A shopkeeper needs to weigh 125 packets of sugar. The packets are of weights 1kg,2 kg, 3kg, 4kg.... 125kg. Now, he seems to be in a hurry and wants to weigh it in minimum time possible. Of course the only operation consuming time is changing the weights on the balance. Hence, we plan to give him a strategy to weigh all the 125 packets with minimum changes of weights on the balance. Any suggestions for the strategy? He should also use the minimum number of weight-bars possible. Also, being a professional shopkeeper, he will weigh using the weight bars only,i.e. the already prepared packets cannot be used to weigh the packets prepared later.

Cheers,

Merry Christmas and a very Happy New year!

Vivek

nitkkr.vivek@gmail.com

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

Arranging a Wine Party

I am sure you would have enjoyed solving last post's puzzle. I know it was a bit tricky, more cause it was from Google Code Jam'08 Onsite Practice Round. Still, we have two correct entries sent by the third day from the date of the post. While Shashank Srikant used a C++ implementation to get the answer, following it up with a well-built logic, Kapil Garg went past the puzzle with a simple yet elegant observation.

The last ball that remain is only BLACK.

You might notice, that the number of white balls in the bag changes only in even numbers. Hence, starting of with a even number of white balls, and doing only transactions that cause changes in even numerals, you can never reach a state of 1 white ball in the bag. Hence, the ball has to be black :)

Well, this week I also came through a good algorithm development question. I still cannot figure out the perfect logic for it. I thought the blog would be great platform to share the problem. And I would be really thankful if someone can send a probable approach.

Mr Winger is having a party. He has a list of guests along with their in-times and out-times from the party. Anytime, a guest enters the party, he is given a glass of wine. The guest returns the glass as soon as he leaves the party. Given the list of guests and their in/out times, can you help Mr X in deciding what is the minimum number of glasses required for his party.

For Eg, if guest 1 comes at time 2units and leaves at time 3units, while guest 2 comes at time 3units, the glass of guest 1 can be given to guest 2 and hence, only 1 glass is needed. On the other hand, had the guest 2 come at time 2units, we would have needed 2 glasses.

I do have one more puzzle over which I am still hitting my head. Lets keep that for the next week.

Till then,

Good Luck,

and Keep puzzling

Regards,

Vivek

nitkkr.vivek@gmail.com

Help TorNador! Create Magic!

Hey folks,
This week is awesome. I am finished with all my exams, and have been enjoying my time. This week has been high for placements at the college and I am expecting a lot more people getting jobs in the coming days.
Ok, coming back to the issue of discussion. Once again, Kapil Garg and Aditya Nema chipped in with their gritty insights and divided the cake equally into two parts. Kapil supplemented his solution with a mathematical proof, while Aditya relied on logic to crack the puzzle.

Any plane passing through the middle of a cuboid divides it in two equal parts. We can consider the given cake as combinaton of two cuboids, a full cuboid and the hole being a cuboid of negative weight. Now, the plane through the two centres simultaneously give you the solution. If you still want a more convincing proof, try proving it for a 2-D geometry and you can extend it to 3-D. And yeah, I am always there if you still need some more details on the solution.

Ok, this week I had been going through Rabin-Karp string algorithm. A single pass through the string can let you manipulate the string well. It uses application of hashing technique. Hence, O(N) being the runtime, the algorithm lets you perform fast, infact very fast operations. The only drawbacks being that it cannot be applied to very long string. I would suggest the computer programmers to go through it once for sure. This section has it explained well. Try applying it to test whether a string is palindrome or not.

Ok, well for others, I do have a puzzle.

TorNador is an old and famous magician. Due to his age, he keeps forgetting the tricks for magics. He has a bag with 10 white balls, and 8 black balls. He calls one person from the audience and asks him to perform the following operations successively.
1. Take two balls out from the bag.
2. If the balls are of same colour, put a black ball inside the bag, else put a white ball back.

You can assume that there is an infinite supply of both white and black balls and hence the person can always put a ball back in the bag.

When one ball is left in the bag, the person asks Tornador the colour of the ball. Help TorNador give the answer. If you think the answer is not definite, give the expected value of the last ball being white.

Would be back in the weekend...
Till then help TorNador and keep puzzling :)
Vivek
nitkkr.vivek@gmail.com

I want an equal share!!!

Hello frnds,
Long time since last mail... hehe, blame it all on the schedule of practicals and the last minute preparations of the minor project.
Lets start off with the solution to previous post puzzle. Shankey would be thankful to Aditya Nema, who provided the solution to the fruit dillema.

80 oranges, 19 apples and 1 banana is what Shankey would be buying to take back 100 fruits, for exactly Rs 100.

Well, today's puzzle would be more on a geometrical analysis. I had found this puzzle in a Intel's interview paper.

Chicku and Chicki are fighting on a cake prepared by their mother. The delicious choclate cake, is a rectangluar cuboid. Due to the fight, they have already cutoff a cuboidal hole from the cake. So, the cake, now is basically a cuboid with a cuboidal hole. Not wanting to mess around anymore, they want to divide the cake equally amongst them. By a single straight cut of a knife through the cake, help them divide the cake equally. Give the solution suitable for the hole of any size and position.

Meanwhile, this week I would be busy with some string algorithms and hence you can expect the next post to contain some basic string manipulation theory and some interesting puzzles on that :)

Till then,
Keep Smiling and puzzling :) :)
Vivek
nitkkr.vivek@gmail.com