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.

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

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

git fetch origin  (gets current changes...this is important other wise

you 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  

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 problem unsolved

Couldn't solve this problem...feeling disappointed :(

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?


 

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.

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!