Select two points uniformly randomly inside a square. What is the probability that the center of the square will lie inside the circle drawn with these two points as ends of diameter?
Source: Rishab Vaid
Source: Rishab Vaid
Friday, 24 October 2014
Thursday, 18 September 2014
Puzzle #5: Save the king
Problem: There are 500 barrels of wine and exactly one of them is poisoned. The king wants to identify the poisoned barrel but he is ready to sacrifice only 4 prisoners. They have 4 days to find the poisoned barrel. The poison has the property that after consuming it one can die anytime in the next 24hrs. Give the strategy to find the poisoned barrel.
Source: Shahbaz also CSE blog
Source: Shahbaz also CSE blog
Friday, 12 September 2014
Puzzle #4: Stop the roll
Problem: You are in a dicey situation. You friend gave you a dice and asked you to keep rolling till you get a sum of 100 or more. Now,you have to tell the most probable number at which you are going to stop.
Solution: You will stop at or before 105. Now, trick is to think backwards. You can get 105, only if you ever reach 99. Similarly, you can get 104, only from 99 or 98. You can get to 100, from maximum previous sums i.e. 94, 95, 96, 97, 98 and 99. Therefore, 100 is the most probable stopping point. P(105) = P(105|99).P(99) = P(99)/6 . Similiarly, P(104) = (P(99)+P(98))/6, ...P(100) = (P(94)+...+P(99))/6
Source: Rishab
Solution: You will stop at or before 105. Now, trick is to think backwards. You can get 105, only if you ever reach 99. Similarly, you can get 104, only from 99 or 98. You can get to 100, from maximum previous sums i.e. 94, 95, 96, 97, 98 and 99. Therefore, 100 is the most probable stopping point. P(105) = P(105|99).P(99) = P(99)/6 . Similiarly, P(104) = (P(99)+P(98))/6, ...P(100) = (P(94)+...+P(99))/6
Source: Rishab
Maths puzzle #3- XOR magic
Problem: You are given a set of n numbers, C = { c_1, c_2, ..., c_n}and you have to find the minimum size of subset of C from which you can create the given n numbers by only doing xor operations on the elements of the subset.
Solution: One starts by thinking about the properties of XOR. There are only a few properties that I know, like x + y + x = y ( I'll represent XOR by + through out the post). So, I have to find a subset V = { v_1, v_2,...,v_k} such that a_i1*v_1+a_i2*v_2+...+a_ik*v_k = c_i, for all elements of C and a_ij are either 0 or 1. This looks similat to c_i being linear combination of V. So, we check if there is a vector space with XOR as the addition operation and voilà, if a euclidean vector space is over the field Z_2, then addition operation is x+y % 2 which is the definition of XOR. So, now all we need to find is the rank of matrix [c_1 c_2 ...c_n] . To find the rank reduced matrix by elementary operations (gauss elimination)
Source: Rishab Vaid who read it perhaps on Topcoder
Solution: One starts by thinking about the properties of XOR. There are only a few properties that I know, like x + y + x = y ( I'll represent XOR by + through out the post). So, I have to find a subset V = { v_1, v_2,...,v_k} such that a_i1*v_1+a_i2*v_2+...+a_ik*v_k = c_i, for all elements of C and a_ij are either 0 or 1. This looks similat to c_i being linear combination of V. So, we check if there is a vector space with XOR as the addition operation and voilà, if a euclidean vector space is over the field Z_2, then addition operation is x+y % 2 which is the definition of XOR. So, now all we need to find is the rank of matrix [c_1 c_2 ...c_n] . To find the rank reduced matrix by elementary operations (gauss elimination)
Source: Rishab Vaid who read it perhaps on Topcoder
Tuesday, 9 September 2014
Maths puzzle #2 - Divisibility by 100
Given any 51 integers, prove that there exist two integers a, b such that a^2 - b^2 is divisible by 100
Solution: Start thinking by why only 51? If we divide any number by 50 it will give 50 possible remainders, which means there are two integers a, b which give the same remainder. So, a = 50q1+r and b = 50q2+r where 0<= r < 50.
a^2 - b^2 = (a-b)*(a+b) = 50(q1-q2) * 2(25(q1+q2)+r), hence divisibility by 100
Source: Manish asked me this problem, who was in turn asked by Rustam, who read it in Mathematical circles: the russian experience
Solution: Start thinking by why only 51? If we divide any number by 50 it will give 50 possible remainders, which means there are two integers a, b which give the same remainder. So, a = 50q1+r and b = 50q2+r where 0<= r < 50.
a^2 - b^2 = (a-b)*(a+b) = 50(q1-q2) * 2(25(q1+q2)+r), hence divisibility by 100
Source: Manish asked me this problem, who was in turn asked by Rustam, who read it in Mathematical circles: the russian experience
Sunday, 24 August 2014
Maths Puzzle #1
Source: CSE blog
Question: A random permutation of integers from 1 to N is arranged in a circle. Prove that there exist k consecutive integer with sum >= k(n+1)/2
Observation: In several puzzles where a comment has to be made about the sum, it is worthwhile to look at the average. Here we ask the question what is the average of each group of k-integers? We know the sum of 1 to n is n(n+1)/2. But in our case every number is part of multiple groups, for ex: number at kth position from start is part of group number 1,2,....k. So every number appears k times, making total sum of all the k-integer groups to be k*n*(n+1)/2. As there are total of n such groups (again count!), average sum of these n groups is k*(n+1)/2, implying there exist a group with value greater than equal to k*(n+1)/2
A stronger statement can also be made if n/k is an integer. There are (n/k) disjoint groups of size at least k. These (n/k) groups can be identified by mentioning the start position. Example, if we start at element 1, the n/k groups will start from 1, k+1, 2k+1,... ((n/k)-1)*k+1. Total sum of these (n/k) groups is n(n+1)/2, thus average sum of each group is n(n+1)/(2*(n/k)) = k(n+1)/2, thus there is at least one group among these n/k groups with sum >= n(k+1)/2
If instead of starting at 1, we start at two, we will get a entirely different set of n/k groups of size k each. In this way we can continue till the start point is k. Thus there will be k different groups of size k each such that there is sum is >=k(n+1)/2
Average trick works in several other puzzles as well. Kaizad rustomji gave me some of those which I'll post later.
Question: A random permutation of integers from 1 to N is arranged in a circle. Prove that there exist k consecutive integer with sum >= k(n+1)/2
Observation: In several puzzles where a comment has to be made about the sum, it is worthwhile to look at the average. Here we ask the question what is the average of each group of k-integers? We know the sum of 1 to n is n(n+1)/2. But in our case every number is part of multiple groups, for ex: number at kth position from start is part of group number 1,2,....k. So every number appears k times, making total sum of all the k-integer groups to be k*n*(n+1)/2. As there are total of n such groups (again count!), average sum of these n groups is k*(n+1)/2, implying there exist a group with value greater than equal to k*(n+1)/2
A stronger statement can also be made if n/k is an integer. There are (n/k) disjoint groups of size at least k. These (n/k) groups can be identified by mentioning the start position. Example, if we start at element 1, the n/k groups will start from 1, k+1, 2k+1,... ((n/k)-1)*k+1. Total sum of these (n/k) groups is n(n+1)/2, thus average sum of each group is n(n+1)/(2*(n/k)) = k(n+1)/2, thus there is at least one group among these n/k groups with sum >= n(k+1)/2
If instead of starting at 1, we start at two, we will get a entirely different set of n/k groups of size k each. In this way we can continue till the start point is k. Thus there will be k different groups of size k each such that there is sum is >=k(n+1)/2
Average trick works in several other puzzles as well. Kaizad rustomji gave me some of those which I'll post later.
Monday, 28 July 2014
Github - basics
This is a basic step by step process to get started with github and git
1. install git and sign up on github
2. Start by creating a repository which is basically a project
3. on your local machine use git clone <repository_address>
4. Step 3 will download all the files from github in the current location on the local machine
5. Make changes to the file and use git add <filename> to add to local repository
6. Use git commit to commit to the repository
7. Finally use git push to push the current version to github
Use git pull to pull from a repository
Tutorial :http://gitimmersion.com/lab_13.html
Repository is a project
Commit is like a revision of a file. Git every time you save it creates a unique ID (a.k.a. the "SHA" or "hash") that allows you to keep record of what changes were made when and by who
Branch: Branch is a parallel version of repo. the "master" branch is the primary branch which has the live code. When you want to make some change, create a new branch, make changes and merge your branch back with master branch. Merging is done via "pull". which means pulling a branch in another I suppose. To merge your changes with master, you create a "pull request" which is accepted/rejected by repository collaborators.
A fork is a copy of a repository. Fork someonelse repository to for ex createing a patch and send a pull request. If you plan to send a pull request then you also need to keep uptodate with the changes in the original (and not forked) repository. You can setup this by specifiying upstream in your forked repository.
git remote -v gives you the current remote repo.
Add upstream by git remote add upstream https://original-repo-as-upstream
Once you have a fork you can do whatever you want without impacting the opriginal project.
1. You can create a branch and add your changes
2. And send a pull request if you want to merge back.
#Get Add, commit
Once you make changes to file, git knows that the file has changed. (do git status)
but it doesn't know if it should actually recreate hash (which commit does) . So the next step is to "stage" the file for commit by doing git add filename. To commit everything that is staged you do git commit -m "message".
Git only save the changes you made not the entire file. There for if you make some changers to a file, do a git add fname.txt and git commit -m "change1". Followed by more changes., Now the latest (version) commit has only the initial change and not the latest change. You have to stage and commit the new changes.
The commits pile up on the stack as you nake changes to your file, but you can go back anytime by using checkout command. git checkout <hash> takes you to the hash version.
Revert unstaged changes by git checkout <filename>
Revert commited change git revert HEAD (to revert last commit) or git revert <hash> for some othere commit.
HEAD: the current commit your repo is on. Most of the time
Add to commited changes by git commit --ammend -m "some message"
Get changes from remote:
git fetch will fetch the commit from remote branches but will not merge with local branch.
To merge to local git merge origin/master
You can combine these two together by doing git pull
// MEssed up your local dev branch
Deleting:
Locally: git branch -d branch_name
This deletes local branch if it is fully merged with upstream.
git branch -D branch_name
This forcce deltes the branch irrespective of merging.
Its shorthand for git branch --delete --force
To delete remote branch do
git push origin --delete branchname
IF you say git checkout -b <branch> it takes you to the latest version of this branch. git branch --all gives a list of all branches. Current branch is shown with HEAD pointer.
1. install git and sign up on github
2. Start by creating a repository which is basically a project
3. on your local machine use git clone <repository_address>
4. Step 3 will download all the files from github in the current location on the local machine
5. Make changes to the file and use git add <filename> to add to local repository
6. Use git commit to commit to the repository
7. Finally use git push to push the current version to github
Use git pull to pull from a repository
Tutorial :http://gitimmersion.com/lab_13.html
Repository is a project
Commit is like a revision of a file. Git every time you save it creates a unique ID (a.k.a. the "SHA" or "hash") that allows you to keep record of what changes were made when and by who
Branch: Branch is a parallel version of repo. the "master" branch is the primary branch which has the live code. When you want to make some change, create a new branch, make changes and merge your branch back with master branch. Merging is done via "pull". which means pulling a branch in another I suppose. To merge your changes with master, you create a "pull request" which is accepted/rejected by repository collaborators.
A fork is a copy of a repository. Fork someonelse repository to for ex createing a patch and send a pull request. If you plan to send a pull request then you also need to keep uptodate with the changes in the original (and not forked) repository. You can setup this by specifiying upstream in your forked repository.
git remote -v gives you the current remote repo.
Add upstream by git remote add upstream https://original-repo-as-upstream
Once you have a fork you can do whatever you want without impacting the opriginal project.
1. You can create a branch and add your changes
2. And send a pull request if you want to merge back.
#Get Add, commit
Once you make changes to file, git knows that the file has changed. (do git status)
but it doesn't know if it should actually recreate hash (which commit does) . So the next step is to "stage" the file for commit by doing git add filename. To commit everything that is staged you do git commit -m "message".
Git only save the changes you made not the entire file. There for if you make some changers to a file, do a git add fname.txt and git commit -m "change1". Followed by more changes., Now the latest (version) commit has only the initial change and not the latest change. You have to stage and commit the new changes.
The commits pile up on the stack as you nake changes to your file, but you can go back anytime by using checkout command. git checkout <hash> takes you to the hash version.
Revert unstaged changes by git checkout <filename>
Revert commited change git revert HEAD (to revert last commit) or git revert <hash> for some othere commit.
HEAD: the current commit your repo is on. Most of the time
HEAD points to the latest commit in your branch, but that doesn't have to be the case. HEAD really just means "what is my repo currently pointing at". In the event that the commit HEAD refers to is not the tip of any branch, this is called a "detached head"Add to commited changes by git commit --ammend -m "some message"
Branch:
git checkout -b <branchname> is a shortcut for git branch <branchname> followed by a git checkout <branchname>.
Merging:
Merging brings the changes in two branches together. Let’s go back to the greet branch and merge master onto greet. By merging master into your branch periodically, you can pick up any changes to master and keep your changes in greet compatible with changes in the mainline.
git fetch will fetch the commit from remote branches but will not merge with local branch.
To merge to local git merge origin/master
You can combine these two together by doing git pull
// MEssed up your local dev branch
git fetch origin (gets current changes...this is important other wiseyou may miss changes)git reset --hard origin/master
Deleting:
Locally: git branch -d branch_name
This deletes local branch if it is fully merged with upstream.
git branch -D branch_name
This forcce deltes the branch irrespective of merging.
Its shorthand for git branch --delete --force
To delete remote branch do
git push origin --delete branchname
IF you say git checkout -b <branch> it takes you to the latest version of this branch. git branch --all gives a list of all branches. Current branch is shown with HEAD pointer.
.
Master: The name of the default branch that git creates for you when first creating a repo. In most cases, "master" means "the main branch".The default name that git gives to your main remote repo. Your box has its own repo, and you most likely push out to some remote repo that you and all your coworkers push to. That remote repo is almost always called origin, but it doesn't have to be.
git pull = git fetch+git merge
Friday, 20 June 2014
Project Ideas
Very little guidance in my current project. It seems like I have been dropped into an ocean when I was still making myself comfortable in a swimming pool. I have a very large data set approximately 9x10^8 entries and as each of them is a 64 bit double it takes up a lot of space = 7.2 GB, it is impossible to fit into the memory given all the other variables that I want to store. I tried using float but that gave me strange results.
Another concern is that the data is very sparse. In a matrix of size 9million X 3 million, I have only 14 million non zero entries, now most of the rows have nearly one or 2 non zero entries. On an average every row has less than 2 non zero entries. Need to think
Project Ideas : Old and new
1. Application to aggregate donations for humanitarian cause
2. Matter: Crowd sourced news platform
3.
Another concern is that the data is very sparse. In a matrix of size 9million X 3 million, I have only 14 million non zero entries, now most of the rows have nearly one or 2 non zero entries. On an average every row has less than 2 non zero entries. Need to think
Project Ideas : Old and new
1. Application to aggregate donations for humanitarian cause
2. Matter: Crowd sourced news platform
3.
Sunday, 15 June 2014
Saturday, 14 June 2014
Some puzzles
Sometimes I feel I am so dumb that I should not be allowed to solve puzzles. I spent the complete day today to figure out my mistake in this simple problem on codechef june long contest. I figured out the solution in first 10 minutes but was handling a simple corner case in the wrong way. The worst part is I tested my code on the corner case multiple times and overlooked the error. What a dumbass I have turned out to be. Any way, I am still not able to figure out the solution to the next problem.
Dheeraj Baba also told me some puzzles today...I will mention them here and think about them.
1) One based on the famous handshaking lemma: In a party there are 5 couples including the host. Every person in the party shakes hand with every person he doesnt know. At the end of the party the male host announces that he asked every one the number of hands the shook and everyone gave a different answer. How many hands did the female host shook? The host mayn't know everyone they invited.
2) Given a tree, find the two vertex which are maximum distance apart?
3) What is the minimum number of coins of giver denomination required to make a sum of N? see this
4) Number of possible configurations of a rubic's cube?
Dheeraj Baba also told me some puzzles today...I will mention them here and think about them.
1) One based on the famous handshaking lemma: In a party there are 5 couples including the host. Every person in the party shakes hand with every person he doesnt know. At the end of the party the male host announces that he asked every one the number of hands the shook and everyone gave a different answer. How many hands did the female host shook? The host mayn't know everyone they invited.
2) Given a tree, find the two vertex which are maximum distance apart?
3) What is the minimum number of coins of giver denomination required to make a sum of N? see this
4) Number of possible configurations of a rubic's cube?
Tuesday, 20 May 2014
SRM621
My first match on Topcoder. i competed in division 2 and solved the 250 and 500 pts problem. Both were easy problem and simple logic was used to solve the problem. 250pt problem was about sorting, lexicographically or length wise. No problems there just define a fucntion for comparison of length and another for lexicographical ordering (use compare functionin string class), just scan through the list and check ith and i+1th string. Takes O(n) time.
500pt problem can be solved just by sorting the sequence and maintaining a marker which says that all the sums from 1 to marker can be obtained using first i numbers of the sorted sequence. Check for this invariant at each step and problem can be solved in O(n logn) for sorting + O(n) for chechking validity time.
I can't solve the third problem. I didn't have enough time. I took long enough to solve these problems. I need to be faster. I got very few points for these because I took way too much time. Now I'll try rest of the problems of i.e. 1000pt and div1 all the problems, in a timed environment.
500pt problem can be solved just by sorting the sequence and maintaining a marker which says that all the sums from 1 to marker can be obtained using first i numbers of the sorted sequence. Check for this invariant at each step and problem can be solved in O(n logn) for sorting + O(n) for chechking validity time.
I can't solve the third problem. I didn't have enough time. I took long enough to solve these problems. I need to be faster. I got very few points for these because I took way too much time. Now I'll try rest of the problems of i.e. 1000pt and div1 all the problems, in a timed environment.
Tuesday, 13 May 2014
Statistical Machine Learning
Last 1 semester I have dabbled in Statistical Machine Learning. My thesis is in a related field. Ideas here need a very clear understanding of linear algebra, probability statistics and optimization and sometimes a bit of complexity theory. Some proofs are very very non intuitive to me at present. Looking at the profile of people working in this field give me self doubt. I think the best strategy is to not think to much about this and just do it! Let us see...I should be optimistic, if they have done it then so can I!
Friday, 11 April 2014
Cards, bags and coins
http://www.codechef.com/APRIL14/problems/ANUCBC/
I have invested almost 2 days in the above problem...but all in vain...I am still getting wrong answer. I believe my algorithm is right and I am not able to catch the error. It is frustrating and I'll stop now. After the contest, I'll make sure the reason for this.
I have invested almost 2 days in the above problem...but all in vain...I am still getting wrong answer. I believe my algorithm is right and I am not able to catch the error. It is frustrating and I'll stop now. After the contest, I'll make sure the reason for this.
Tuesday, 25 March 2014
Library Etiquette
Library is wonderful place, full of knowledge and silence. People should learn and respect the silence part(at least) or have the common courtesy to have discussion in the lonely corner. Some students of IITK don't comprehend this or chose to ignore it completely. Feeling Annoyed!
Saturday, 22 March 2014
I Hate Real Analysis
This is a rant....Real analysis doesn't make any sense to me....weird things to prove weird things...this sequence subsequence interior point closure really annoyed me today...little I learnt.
Saturday, 8 February 2014
Topcoder problem took me whole day to solve! :(
This problem took me almost the entire day to solve, even when I peeked at the solution and read the editorial. Phew!!! Before I could further glorify my failure let me note down here what I learnt.
1) If you are going for a recursive solution always think in terms of recursion tree. What is going to be the input to the recursive function and what is going to be the output.
2) Finding expectation can be broken down as sum of conditional expectation.
3) Be cautious about the base case, what should you return so that recursive function gives right solution.
4) Use bitwise masking for configurations/subsets etc if applicable, constaraints give the hint.
5) Cry some more.
1) If you are going for a recursive solution always think in terms of recursion tree. What is going to be the input to the recursive function and what is going to be the output.
2) Finding expectation can be broken down as sum of conditional expectation.
3) Be cautious about the base case, what should you return so that recursive function gives right solution.
4) Use bitwise masking for configurations/subsets etc if applicable, constaraints give the hint.
5) Cry some more.
Saturday, 18 January 2014
Big integer in C++
I am not a big fan of code ppl write in coding competitions as it looks ugly. Too much is compromised for efficiency. One case in point is using big integer in C++. Some of the problems expect the use of big integer class. As there is no standard big integer in C++, one is left with 2 options. Write your own or copy somebody elses. But as one is allowed to submit only one file, it means everything will be dumped in that single file. I have decided to write my own when need arises. Only including the functions that I need.
Basically, a short way, at least for these competitions is to take every integer as a vector of intgeres (representing digits) and then do the operations as one did in school. Create the result digit by digit. Define operators for comparison on vector<int>.
Basically, a short way, at least for these competitions is to take every integer as a vector of intgeres (representing digits) and then do the operations as one did in school. Create the result digit by digit. Define operators for comparison on vector<int>.
Tuesday, 14 January 2014
Too much on my plate?
If you try and do everything, you may endup messing everything. Currently, I am trying to do the following: I am doing four courses this sem - Algo2, MFML,DS,SI. I am doing networks course on courseera. I am trying to participate in an ongoing ML competition. I have to build a better webpage work on the video player. I also like to take part in competitive programming and not to forget the research for which I have 4 credits this semester. This seems too much for a semester. Seems like I will have to drop networks. Shit, I so wanted to do that course. May be in summers then....phew!!!! Need an internship as well.....but on the priority list for now is Assignment 1 solutions for Algo2, readup on that competition, research work...read those goddamn papers.
Anyway, Ruskin bond is an amazing writer, his stories are a constant pacifier in this urge to follow your passion thing. God,human beings are too many people in one.
Yes before I forget, I am also growing fat (85 Kg today...sob sob) and losing hair rapidly. I am also having shit days of depression, I think.
Anyway, Ruskin bond is an amazing writer, his stories are a constant pacifier in this urge to follow your passion thing. God,human beings are too many people in one.
Yes before I forget, I am also growing fat (85 Kg today...sob sob) and losing hair rapidly. I am also having shit days of depression, I think.
Wednesday, 8 January 2014
Thought on that video player
It seems like a really good idea to me. I will use it all the time if such service was ever provided. We need to make it and let the campus use it. Talk to swapnil about this. Definitely!