The Inquisitive Mind

Campus knack at Flipkart

2010-08-18T07:28:00.000-07:00

Its time for on-campus hiring at Flipkart.com. Come Friday, and student at NIT Surathkal, would be (supposedly!) hitting their heads on gritty problems posed by the Flipkart.com at the event of On-Campus Hiring. I recently joined Flipkart, and essentially I am not a part of the recruitment team, but yeah! I am a part of Flipkart.com and I am excited :) I guess everyone would be!! Good luck guys! We would like to see a bunch of you here, and I am sure, you would love working in here.

Well, yeah! I have been and perhaps would be away from some algorithm/analytical problems, working on some real-life problems at Flipkart but it has been interesting, and if I come across something that should be shared with you, yours truly would do the service.

Recently, I have been working on some basic utils at the Flipkart, that makes life easier, faster and efficient for other teams. So if I am not over-estimating, I am a part of the OS team for the instance Flipkart.com (Can you guess which technology I am working on rite now by my statements :P :P).

Well, yeah I have a news. I have started learning perl, and I have started liking the MacOS terminal. I never knew it was so damn powerful, and I would like to share some of the hacks that I come across to make your life easier on the terminal. And if you are not using it still, well then do get used to it! In industry, the terminal is your only and sufficient help.

And problem lovers, well dont worry, if I do come vis-a-vis with a new/interesting problem , I wouldn't delay posting it here on the blog.

Till Then,

Enjoy, and Keep computing :)

Vivek

nitkkr.vivek@gmail.com

Yahoo Hack Day @ Bangalore

2010-07-26T00:49:00.000-07:00

Hey folks,

Last weekend, I was at the Taj Residency. Now before you jump to any conclusions (as my PG room mate did :P ) , it was the Open Hack, Bangalore 2010, organized by Yahoo. It was series of tech-talks on Yahoo tools on YDN, followed by a 24 hour over-nite, hack development contest. For those who might be confused by the overloaded term "hack", it is in simple terms any application which is build on something, to add a feature or make it better and simpler to be used.

We saw a lot of new applications and ideas coming up, along with a sleepless virtual two day, 1 night stay at Taj Residency's Vijaynagar and Trinity Hall. Yours truly also tried a hand at developing a hack over PayPal API which gives you real time updates in your mail-box over changing Forex rates. Well anyone wants to keep a check over the foreign exchange rates and get a notification over the same in his mail-box can mail me and we can try and work something out.

Over all it was a great experience, with real good info on the Yahoo tools like YAP, YQL and YUI, and I hope to work on some of them soon. Would keep you'll updated though.

Ok, for those who are looking for the solution of the last week's puzzle, I am sure it would have been a good experience and although till now we dont have a concrete proof, what we do have is a strong and almost logically convincing solution from Kapil Garg. As Kapil puts in, if Alladin just moves diagonally opposite to the point where Roger is heading, Alladin would end up leaving the circle. People who love calculus may try writing some differential equations which may help them get a concrete proof. Its not hard to visualise that Alladin would follow a out-spreading spiral-kind path from the centre of the circle while Roger would keep revolving through the circumference in one direction. This reminds me of a similar problem from previous IIT-JEE papers with three people at the three ends of equilateral triangle, start moving towards each other continuously, where would they eventually meet.

For this post, I don't have a puzzle yet but I am sure you would be interested in Yahoo tools if you go on YDN. For a lead, I would ask you to visit YQL and see what all data you can access. It really seemed magical to me that YQL includes almost everything on the earth and web in the YQL and helps you extract info from it. Also, you can think of a hack that you would have made had you been here in Bangalore at the Open Hack. Do share your ideas with us, and who knows you may end up be on the stage with Yahoo Unique Hack prizes (they had almost 7 categories of prizes :) ).

Meanwhile, i would work on ideas/puzzles and would try keeping you a brain-knacker soon.

Cheers , (Yahoo??)

Vivek

nitkkr.vivek@gmail.com

Str8 from the most happening place in Bangalore

2010-07-12T02:46:00.000-07:00

Hey amigos,

Hope you'll are doing well at your new job/higher study course.

I am writing this mail straight from Koramangala, supposed to be the most happening place of Bangalore. I joined Flipkart.com two weeks back, and it has been an awesome experience since then. Great Co-workers! Friendly environment and working on deeper real life problems. Being a fresher, I can't ask for a much. Its 3:20 pm on my MacBook ( yeah, I work on a MacBook now, thanks to Flipkart ), and as I turn my head around, I see someone struggling with debugging on her MacBook, someone surfing topcoder.com, yet another co-worker relaxing with a glass which supposedly contains coffee and yet another fresher relaxing on a beanbag and pondering over a problem which might have appeared on his MacBook.

Now, I have been away from blogging for a long time just cause I haven't had a good problem to start off with. But while I was talking to an old friend Raunak, I came across a nice mathematics problem which I thought would be a nice one to kick start my blog again.

So, we have a circle of radius R. Our fast, smart and intelligent dog, Roger is on the circumference at some point. Roger is restrained to move on and only on the circumference of the circle. Our hero, Alladin, is standing on the centre of the circle and wants to get out of the circle as soon as possible. Speed of Roger is 4 times that of speed of Alladin. Now, as Alladin starts moving out intelligent dog Roger calculates his direction and moves towards the point of exit. Alladin cannot make an exit from the point if Roger is standing there. So is it possible for our hero to evade the dog and break the "Ring" to come out?

Do pour in with queries and answers and suggestions. I have some ideas on the problem, but I am still searching for a particular solution with proof.

Cheers,

Vivek

nitkkr.vivek@gmail.com

Are yoou'll on?

2010-05-19T10:34:00.001-07:00

Well I guess it has been a week, and I still don't have any entry. Looks like the puzzle stumped people! Ohk, for people who have not noticed, I would like to give you'll a hint:
1. You can use prime number theory. That will help you in a great way.
2. Go by limiting the maximum possible value for the product, and then eliminate some cases. You would be left with very less numbers.
3. And takes the lines of both the students very seriously :P. Those are the only and sufficient hints.
4. If you still can't get it, drop me a mail and I would like to help you get closer to the solution.

Ohk, well I have a lead on the greatest integer function solution for finding the maximum of the two numbers, given by Sarvana. Although it works only for numbers with same sign , but then it is a great find indeed. And as you will see its simple yet elegant.

let x = a * [ a / b ] + b * [b / a], that would be equal to
max ( a , b ) * ( max / min ) .

now, either of [ a / b ] or [ b / a ] would be zero or both would be 1.

in any case, lets divide x by y = [ a / b ] + [ b / a ] .

This cancels out the multiplicant with the max(a,b) you get the required answer.

Well, I think this is completely see through and doesn't requires explanation. And please drop in our comments and views about the solution. :)

People, do get your brains working for the number guessing problem. Its tough, but I am sure you'll can crack it once you set on it.

Cheers,
Vivek
nitkkr.vivek@gmail.com

How did they know the numbers?

2010-05-13T10:22:00.000-07:00

Well, this has been a happening week. With the most dreaded teacher setting one of toughest paper for the final year guys, to extending of date sheet insanely, I would say NIT Kurukshetra final year guys would have had a tough time digesting all the flash news.

Anyways, lets get back to the solution for previous week's puzzle. Well lot of entries this week. Shashank, Sarvana, Pradeep and Pulkit Sir chipping with a great way.

The essence of the solution being :

max ( a , b ) = (a + b ) /2 - | a - b |/2.
Now, before you say modulus is not a mathematical operator, I would quote Pulkit Sir's way of seeing this " absolute value is just the distance from 0 on a number line". Now, this is perfectly mathematical and its just the way you percieve it.

Still, if for hard-core exrepssion lovers, |a| is sqrt ( x**2).
I have a hint that this problem may be solved by another method of using greatest integer function ( [ ] ). Well, I will keep trying, and if you get a solution on this thread, do drop me a mail.

This week, we have a puzzle contributed by Pulkit Sir again, and i thoroughly enjoyed solving the puzzle owing to the careful drafting of the puzzle wordings. I am sure you would enjoy it :)

A teacher says: I'm thinking of two natural numbers greater than 1.
Try to guess what they are.
The first student knows their product and the other one knows their
sum.
First: I do not know the sum.
Second: I knew that. The sum is less than 14.
First: I knew that. However, now I know the numbers.
Second: And so do I.
What were the numbers?

So drop me a mail as soon as you find the numbers.

Cheers,

Vivek,
nitkkr.vivek@gmail.com

Max with Maths

2010-05-04T08:02:00.000-07:00

Hey folks,

Well, this has been a super fundoo week. Last working day at college, scribble day and followed by a sleepy lazy preparatory leave. Its time to gear up for the final end semesters (phew!) of my B.Tech degree.

So, as you may assume I haven't been able to prepare a challenging puzzle for you'll. But then, you'll must be busy with exams too, and so I would let this week pass by with a simple puzzle again. Well before that, lets see the solution to previous week's puzzle. Shashank Srikant from NITK was the first one to chip in with the solution after a small discussion. And we had a really good entry from IIIT Allahabad, by Siddharth Shankar, who takes on the problem with a approach which was new for me as well.

Well, if you remember the basic formula of area of the triangle .5 * base * height, this problem could not have taken more than 2 minutes of deep thinking. Divide the base of the triangle into 9 equal parts and now join those points with the third vertex. Now height of each of the triangle is same and as base is 1/9th of the original triangle, you end up with each area 1/9th of the original triangle.

What Siddharth came up with was based on similarity of triangles, which he eventually extends to equal triangles. Lets see the diagram he attached:

I hope this makes it very clear, although I would like to discuss if anyone has any doubts.

Ok, now the puzzle for this week. Well, computer programmers have a very easy way to find the maximum or minimum of a number. Just include a math library and you have a direct function. Or else, you can use a if loop or much better, use a conditional operator.

What about people who dont know programming but only know math. So this week we sought to help those people. Give me an expression involving only mathematical operators and 'a', and 'b', which finds the maximum of 'a' and 'b'.
Your expression can contain any mathematical operator like !,-,+,/,* etc etc.., besides 'a' and 'b' but no programming constructs.

Cheers,
Good luck for your exams
Vivek Agarwal
nitkkr.vivek@gmail.com

Equal Division

2010-04-27T21:09:00.000-07:00

Hey folks,
Since I am in a mess of sessional (last of my college life.. phew! ), I would straight away go to the question for this post. This one was asked to one of my friends in an interview lately. And believe me, its easier than i may appear at the first go.

How do you divide a triangle (any valid triangle), into 9 equal parts.
Edit: By equal parts, I mean the triangle should have equal areas. Apologies if that small miss from my side messed up your head a bit 2 much.

Well, I dont have much to say, except that at this point of time, Compiler Design has blown me off! So while I find the chapters, you can ponder over the problem, and yeah mail me the solution as soon as you get a leaf on it. :)

C ya,
Vivek
nitkkr.vivek@gmail.com

Only half a chance :(

2010-04-27T00:44:00.000-07:00

Hey,
Seems like the last week problem sent you'll a bit hay-wire. I got two correct entries from Kapil Garg and Pradeep Sharma, but the logic/proof given by them were not pretty convincing. Pradeep Sharma, our very own Pandit, came really very close and almost cracked the problem.

Now, lets consider the condition when there are k people in the queue ( k>=2 ). By a little hand calculation you can see that probability that kth person gets kth seat kor k = 2 , is 0.5 . Again, for k = 3 , the possible configurations are (1,2,3) , ( 2,1,3) , (3,1,2) , (3,2,1 ). Here also, we have the probability to be 0.5. You may convince youself for k = 4 ,5 and so on, till you patience permits.
Here we can generalise the answer to be 0.5 for each k >=2 . Now lets see a rigid proof for this.
We use Mathematical Induction:

Lets say, F ( n ) denotes the probability that nth person sits in nth seat, the total number of people in the queue being n.
Also, lets say F ( n ) = 0.5 for all n >=2 .
Now we prove this for F ( n + 1 ) .

For the last person to sit on his seat, the first person must sit on any seat except n. Let she sits on seat k.
Now all the passengers from 2 to k-1 sit on their respective sits, with k , k + 1 , k + 2 ... n still remaining, the seats vacant being 1,k+1,k+2,...n .
This is similar to the initial case, just that the kth person is equivalent to drunk girl with his seat number being 1. Hence we have a recursive relation like:

F ( n + 1 ) = 1/(n+1) + sum for k = 2 to n { 1 / ( n + 1 ) * [F ( n + 1 - ( k -1 ) - 1 )] } .

The first 1/(n+1) means the girl sits on 1st seat. The other one is summation means the person sits on kth seat and now we remain with N + 1 - 1 - ( k - 1) people to be seated.

each F ( k ) is 1/2 and hence you can get the answer as 1 / 2.

While you convince yourself about the above solution, you can mail me for clarifications. I will soon have a new post ( Infact, I am working on it rite now :) ) .

Cheers,
Vivek
nitkkr.vivek@gmail.com

Can I sit in my seat?

2010-04-21T18:49:00.000-07:00

Hey folks,
Well, I know this post would come as a surprise especially after such a long break, but it's just that I was not able to find time and content to post. Anyways, better late than never! Here I start :)

Now, as some of you'll might be knowing, I started this blog with an idea to concentrate on problem solving and algorithms. But, as it turns out, puzzle solving is an integral part and it seems like I cannot do without that. Well, so may be I will start intermixing my posts now-onwards, with puzzles and code snippets that I hope should prove to be more helpful.

Ok, for this week, I have an interesting puzzle. Many of you might have heard it, but for those who haven't, this puzzle guarantees to give you a run for your sleep.

I am going back to my hometown on vacations, and I am already at the airport. It is a long queue of 100 people waiting to board the plane. We each have a ticket with our seats numbered, i-th person having the ticket for i-th seat. I am the last person in the line and not to mention, my seat was number 100. But first person in the line was a crazy drunk girl and she will randomly select her seat once she is in the flight. All others of us were normal and would occupy our respective seat if it was un-occupied. Otherwise, we will also select one of the empty seats at random. What is the probability that I will get to sit on seat #100.

Well, so get set go!

Happy puzzling,
Vivek
nitkkr.vivek@gmail.com

Long Time! But here I come !! :)

2010-03-18T19:03:00.000-07:00

Hey,
Guys I know, I have been off the record for a long time; But lets begin again, cause its never too late, rite?

Oh'k, first of all, lets see the last post's puzzle! I didn't get any answers for that one; So I assume even you'll were having a busy time! Okay, that one was Gray Code arithmetic problem, where each subsequent entry has a difference at one bit-position. We need to maintain log(N) bits, and then maintain a Gray Code-sequence which gives us ll the possible value. Maybe you'll would like to peek into the wiki article of Gray Code arithmetic.

Well, this season I had been occupied with many things. From placements to minor project and extending it to some personal programming things, my calendar was always occupied with something or the other. I would like to share about my personal findings regarding Javascripts, CSS and Java language, may be in the next post.
Coz, rite now, its times to get ready for the class of Software Testing. Hey! did I tell you? I am attending classes even!

Cheers,
Vivek Agarwal

The faster, the better :)

2009-12-20T13:48:00.000-08:00

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

2009-12-16T00:47:00.000-08:00

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

2009-12-12T10:30:00.000-08:00

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!

2009-12-08T21:56:00.000-08:00

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!!!

2009-12-04T06:13:00.000-08:00

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

The Fruit dillema

2009-11-25T07:44:00.000-08:00

Ok this has been a long gap, almost of a week. Well, the week has been quite interesting for me. Couple of doubts over Kapil's solution, Lots of tension about the end-sem (it still carries!! :P ). This week I have a couple of interesting things. But before that, lets say "Great Work!" to Aditya Nema for solving all the three problems from last week's post.

Before going, as always let me give you the solutions:

1. a&!(a-1) gives you the last set bit (Phew! wasnt that simple yet elegant).

2. 59 is the number which on divided by 2,3,4,5,6 gives 1,2,3,4,5 as remainders repectively.

3. the Algorithm:
int count_bits(int A)
{
int ret=0;
while(A)
{
ret++;
A=A&(A-1);
}
return ret;
}

Ok! Lets see the doubts over Kapil's solution, as pointed out by Jasveer Singh Maan :).
Please refer the diagram in the previous post.
AEG and FEG are equilateral triangles. So each angle of these must be 60 degrees. Hence AEF= AEG+FEG=120 degree.
Now, AEFCB is a regular pentagon. So each internal angle should be 102 degrees (I think it is a requirement of regular polygon!). So there is a contradiction as AEF is internal angle of pentagon. I still havent drawn it with proper geometrical instruments but the argument seems to be very strong. So at the moment, Kapil's solution is not perfectly valid, the doubt being, is such a figure practically possible, and does a C actually exists?

Edit:
Well, with doubts I never meant that Kapil's solution is wrong, and I would like to apologise if any wrong meanings were conveyed. Anyways, Kapil's solution seems to be, infact are correct. There can be always a polygon with equal sides and un-equal internal angles. Jasveer perhaps mis-interpreted to call that as a "regular polygon", which essentially requires all the sides and internal angles to be equal (108 degrees).
Obviously, the best way to confirm is to draw using a compass, and cause of not finding one (you know how we keep things in hostel! :P, I am sorry about that as well ), I could not draw the diagram but yeah, it is correct cause an appproximation does confirm its validity.

Well, Mr. Kapil, we are not taking any credit from your side. Its just that someone had a small doubt and we couldn't comprehend it properly. Full points to your solution as before :). Cheer up, dude!

Ok so now this week's post.
And yes! I will try keeping this short, since last post had reviews of being a bit longer. I dont have much to share today except for a couple of sites that I came across.

If you have an appetite for maths puzzles, a bit of interest in simple programming, and a great insight, you cannot stop missing the site http://www.projecteuler.net, once you have seen it. 264 problems, each one requires a simple yet smart approach. Do try it and comment whether you liked it.

Again, if you love programming and want to get hand on some good IARCS problems, try this http://opc.iarcs.org.in
You have it graded in IOI style and you also get partial points. This helps in realising the efficiency of your solutions.

At last, a simple puzzle.
Shankey, our friend, wants to buy fruits. He has Rs 100 in his pocket and being a lover of numbers, he wants to buy exaclty 100 fruits. The market has 3 kinds of fruits available at different rates. An apple sould cost Shanket Rs 5, a banana would be for Re 1 and the cheapest of all oranges cost 5p each (Ohk that is very cheap, I know!). Help Shankey find the right combination of fruits so that he spends all the money in his pocket and end up buying 100 fruits. Remember, he loves variety and would like to take at least 1 kind of each fruit back with him.

I would appreciate if you can mail me the method by which you arrived at the solution.
Cheers,
Vivek Agarwal
nitkkr.vivek@gmail.com

The Bits & Bi(y)tes

2009-11-15T04:33:00.000-08:00

Well, before I start off with the actual content, lets thank and congratulate Mr Kapil Garg for his ingenious solution to the seven points problem. His was the first reply that I received. So I can safely assume that its only him (of course, within the domain of people who saw the problem) who has solved the problem.

Well, just a small explanation on the solution. 4 equilateral triangles ABD, AEG, CDB, FEG with unit sides, are drawn such that FC is at distance 1. Attached is the solution sent by Kapil:

Okk, so lets come back to the issue of bits and bytes.

Well smart devices, smart talks and of course smart languages. I am talking about computer, the smartest device available and its language, of course binary 0's and 1's. Basically, you can show any number in a binary format. For eg. 7 is represented by 111, and 8 by 1000, 10 is 1010 and ofcourse 15 is 1111. Now, why am I telling you this simple thing. Well, just to notice that 7 requires 3 bits and 8 requires 4 bits. With 4 bits we can represent any number till 15, where again 16 will require me to put an extra bit.

This just implies n bits can help me represent any number till 2^n -1.

Now whenever you see a question (People who are belling the CAT this year, please notice!!!) like, " I have 127 coins of Re 1. How many minimum bags I need to make (and of what denominations) so that I can share any amount till Rs 127.

The answer is: just find binary representation of 127 which I guess is 1111111 and that is 7 bits. So, we need to make 7 bags of 1,2,4,8,16,32,64 coins each and we can satisfy any demand till Rs 127. Infact, any demand from 64 to 127 will require 7 bags at least since the binary representation of 64 requires 7 bits.

This makes me go back to the question in my class 10 Physics Lab. Why are the denominations in a weight box of a mass-balance in ratio 1:2:2:5? The answer we were told was that this ratio can satisfy all weight combinations from 1 to 10. If I could go back, I would have said, "mam it can also be in 1,2,4,8 and with my combination you can satisfy all weights till 1 to 15".

Anyways, so simple operations on bits, We all know about them. And, OR, XOR, NOT. I dont need to tell all those.

Ok, a very interesting question, " Tell me how can you find the last set bit in a binary representation of a number. What I mean is for 2 (10) answer would be 2nd bit, for 5(101) answer would be first bit and for 10(1010) answer would be second bit. Give me an expression that helps me single out only the last set bit of a number n." Hint : Use & and - (this is not logical ~ operation.)

Well, a very important manipulation done with bits is set and subset selection. Say I have n elements (n<32) and I want to generate all possible subsets of these 32 elements. From basic perm and comb theory, the answer is 2^n subsets. Generating all these sets with hands is easy. With computers, it easier! Just loop over i from 0 to 2^n-1 and see the pattern of set bits in i. A jth set bit in i means that jth element is selected. Hence for i=0, no set bit, means no element is selected. And for i=3 (11), both 1st and 2nd elements are selected. So, say I want to print all the possible subsets of elements in an array. So the pseudo code would be

A[1...n]
for i=0 to 1<< n ....... set bits of i represents selected elements in the current subset
for j=0 to n.................... j is to iterate over all elements
if( i & j) ............ (checking if jth element is selected)
{
print A[j];
}

I know it may be difficult to see whats happening. Just iterate it for n=3,4,5 and you will understand the logic behind it. Hence, any integer can be used to depict the subset selection. Hence all set operations are just trivial. Two sub-sets represents by i & j are:

1. mutually exclusive if i & j = 0
2. are same if i = j
3. exhaustive if i | j = 2^n - 1

Just a bit more fascinating is XOR operation. If B is a subset of A, and you want to select elements of A not present in B, the simple operation is A XOR B. For any two sets A and B, the operation A-B is (A XOR B ) & A. If you dont get it, please try seeing with small numbers or else you can always email me at my id.

Well, I hope you remember the puzzle above (written in brown). I will add one more very simple puzzle and a algorithm question to keep you busy while I deal with my end-semester exams.

Puzzle: Find a number N which when divided by 2,3,4,5,6 leaves remainder 1,2,3,4,5.

Algorithm puzzle: Give me a good (non-bruteforce please!) algorithm to find the number of set bits in binary representation of a number n.

Happy bit-ing :).
Contact: nitkkr.vivek@gmail.com

The seven point puzzle

2009-11-12T01:44:00.000-08:00

So lets start off....

Well this puzzle was given to me by one of my friend and till date, I have no solution for it. Oh I should have told the problem instead of chatting :P

"You are given a 2-D paper and a pencil. Mark seven points on the paper such that if I select any three of them, at least two of them are at a distance of one from each other. "

I along with my frnds tried it but to no avail. Hopefully, I will get a solution here.. and please dont forget to mail me the same at nitkkr.vivek@gmail.com

I would like to warn you that making a regular hexagon abcdef (side equal 1 unit) with g as its centre will not work cause i can select the points a,c,e of which no combination of two points at unity distance is possible.

Next post will probably be on bit manipulation... and its not only for computer guys. You just need to know a bit of binary to get to this beautiful world of bit manipulation. And its damn interesting :)

Till then..
Happy puzzling,

The First Post: Purpose

2009-11-12T01:12:00.000-08:00

Hi folks,
I am Vivek, a final year student of NIT Kurukshetra in the discipline of Computer Engnieering. Well, what instigated me to start this blog was to share my knowledge (though very little :P)and experiments. Well, with that word experiments, I know many of you would have been getting a feeling of this being a blog for geeks. Well its not!. At least I dont think it to be so.

Here, in my free time(we get lots of those at my college), I would like to share puzzles, some maths problems and of course programming stuff (ok! after all I am in discipline of Computer Engineering).....

Well thats it!
This is a beginner's blog, so If something goes wrong, I do hope youll will be there to comment :)
And I assure you the best from my side...

tk care
Vivek @ Aricent