Find the number of pages in the book

Posted on January 31, 2015 by vishnujayvel

Sheldon is so bored that he started counting the number of digits used to represent the each page in the book he was reading. The pages are numbered in sequential order starting from 1.If the total number of decimal digits used is 189 can you find out the number of pages in the book ?

Answer in comment section 🙂

What are the best ways to excel in a summer internship?

Posted on January 27, 2015 by vishnujayvel

My answer from Quora:

Kellen , Elynn and Erin have already covered all important points for excelling in a internship. Here is my 2 cents 🙂
Take notes :
Right from the day 1 take notes of

observation that you make

pseudocode of algorithms that you design

questions to ask your mentor/manager

sample test cases and expected output

software architecture

errors and its solution

important development tool commands

Split your project into several small tasks and maintain seperate note for each task. Initially you might feel that it is unnecessary and waste of time. Trust me this will help you in a long run.
I would recommend evernote to take notes.
(A sample internship devlog notebook in evernote)

Track your progress :
Use progress tracking apps such as trello to classify your task into “todo, doing, done” list. Divide your task for the day into a set of small tasks and prioritize it .

This will give you a reality check everytime you review your progress and you will tend to plan your work accordingly.

Manage time :
During your internship it is very important to meet your deadlines. You will be expected to finish your work on time, So track your time effiiciently!
Use time management app such as Rescuetime to track what you do everyday. With so many distractions and social platforms in your digital life, it’s easy to get distracted. RescueTime helps you understand your daily habits so you can focus and be more productive. Download both chrome browser(if you use chrome) and desktop version of Rescuetime.

Listen to coffitivity :
If you want to concentrate on your work and stop hearing the noise around your workstation try using coffitivity. Coffitivity – Increase Your Creativity!
This is what coffitivity team describes about their app:

Research shows it’s pretty hard to be creative in a quiet space.
And a loud workplace can be frustrating and distracting.
But, the mix of calm and commotion in an environment like a coffee house is proven to be just what you need to get those creative juices flowing.

Initially I found this to be crazy and stupid idea. But pretty soon I realized how effective it was and so I used it throughout my internship period.

Make yourself home :
Personalize your workstation so that you will feel like home. Stick some posters or add any creative accessories and turn your boring workstation into a fun place to work.

My friend drew this for me 🙂 I stuck this in my workstation during my summer internship at Amazon.

Finally ,be passionate about the work you are doing and enjoy doing it.

To read about my internship experience :
Vishnu Jayvel’s answer to What is it like to intern at Amazon?

What are the best ways to excel in a summer internship?

Spoj(GAMES) – HOW MANY GAMES

Posted on January 18, 2015 by vishnujayvel

Brute force will give you TLE even though it will pass initial test cases.

The logic behind this problem is to represent the average score x in the form of a/b where b is minimum.

We know x=a/b . First let us bring x in the form of a/b by multiplying x with pow(10,number of digits after decimal point)

Example: x=30.25 Here we multiply x with pow(10,2) so now a=3025 and b=100

Now we have to reduce the fraction a/b to its least form.

The greatest common divisor is useful for reducing fractions to be in lowest terms. For example, gcd(42, 56) = 14, therefore,

\frac{42}{56}=\frac{3 \cdot 14 }{ 4 \cdot 14}=\frac{3 }{ 4}.

Similarly 3025/100=121*25/4*25=121/4

Now we find gcd(a,b) which is nothing but gcd(x*pow(10,numberOfDigitsAfterDecimalPoint),pow(10,numberOfDigitsAfterDecimalPoint))

FInally answer is b/gcd(a,b)

Where b = pow(10,numberOfDigitsAfterDecimalPoint)

a = x*pow(10,numberOfDigitsAfterDecimalPoint)

So ans for average score x=30.25 is 100/gcd(3025,100)=100/25=4

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	int gcd(int a,int b){
	if(a<b)
	return gcd(b,a);
	if(b==0)
	return a;
	return gcd(b,a%b);
	}
	int main(){
	int t;
	scanf("%d",&t);
	while(t--){
	string str;
	cin>>str;
	int len=str.length();
	int c=0;
	int decimalPointFlag=0;
	for(int i=len-1;i>=0;i--){
	if(str[i]=='.'){
	decimalPointFlag=1;
	break;
	}
	else{
	c++;
	}
	}
	int power=0;
	int number=0;
	int numerator;
	if(decimalPointFlag){
	for(int i=0;i<len;i++){
	if(str[i]!='.'){
	number=number*10+str[i]-'0';
	}
	}
	power=pow(10,c);
	numerator=number;
	printf("%d\n",power/gcd(numerator,power));
	}
	else{
	printf("1\n");
	}


	}
	}

view raw GAMES.cpp hosted with ❤ by GitHub

Topcoder SRM 646 Div 2 TheGridDivTwo

Posted on January 17, 2015 by vishnujayvel

Link – http://community.topcoder.com/stat?c=problem_statement&pm=13628&rd=16278

Well, this is a simple graph problem once you get the logic !

A simple BFS traversal is enough to find the maximum x coordinate value.

A visited array is maintained to log the coordinates that are visited (inorder to avoid visiting the same point again)

First of all since John can move in any directions , he can end up in in negative coordinates also. So to represent negative coordinates as array index move origin(0,0) to (1000,1000).(transformation of coordinates. x=x+1000, y=y+1000)

On each traversal compare the x coordinate with current ans and updated it if x Value>ans

On returning the maximum x coordinate dont forget to decrement it with 1000 (inverse transformation of coordinates)

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <queue>
	#include <deque>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>

	using namespace std;


	class TheGridDivTwo {
	public:
	typedef struct point{
	int x;
	int y;
	int k;
	}point;
	int valid(int x,int y){
	return (x>=0)&&(y>=0)&&(x<=2002)&&(y<=2002);
	}
	int find(vector <int> x, vector <int> y, int k) {
	int visited[2002][2002];
	queue<point>q;
	memset(visited,0,sizeof visited);
	point origin;
	origin.x=1000;
	origin.y=1000;
	origin.k=k;
	q.push(origin);
	visited[1000][1000]=1;
	for(int i=0;i<x.size();i++){
	visited[1000+x[i]][1000+y[i]]=1;
	}
	int ans=1000;
	while(!q.empty()){

	point temp=q.front();
	point temp1;
	q.pop();
	if(temp.k<=0)
	continue;
	if(valid(temp.x+1,temp.y)&&(!visited[temp.x+1][temp.y])){
	visited[temp.x+1][temp.y]=1;
	ans=max(ans,temp.x+1);
	temp1.x=temp.x+1;
	temp1.y=temp.y;
	temp1.k=temp.k-1;
	q.push(temp1);
	}
	if(valid(temp.x-1,temp.y)&&(!visited[temp.x-1][temp.y])){
	visited[temp.x-1][temp.y]=1;
	temp1.x=temp.x-1;
	temp1.y=temp.y;
	temp1.k=temp.k-1;
	q.push(temp1);

	}
	if(valid(temp.x,temp.y+1)&&(!visited[temp.x][temp.y+1])){
	visited[temp.x][temp.y+1]=1;
	temp1.x=temp.x;
	temp1.y=temp.y+1;
	temp1.k=temp.k-1;
	q.push(temp1);

	}
	if(valid(temp.x,temp.y-1)&&(!visited[temp.x][temp.y-1])){
	visited[temp.x][temp.y-1]=1;
	temp1.x=temp.x;
	temp1.y=temp.y-1;
	temp1.k=temp.k-1;
	q.push(temp1);

	}

	}
	return ans-1000;
	}
	};



	<%:testing-code%>
	//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!

view raw TheGridDivTwo .cpp hosted with ❤ by GitHub

Codeforces Round #285 (Div. 2) C. Misha and Forest

Posted on January 14, 2015 by vishnujayvel

Problem link – http://codeforces.com/contest/501/problem/C

This is an interesting graph problem 🙂

Since the graph is acyclic, there will be leave(s) (with degree = 1). Identify those leaves. Consider a leaf i.Its xor value (let it be j) will directly give you its neighbour(since xor of a number is the number itself).Add (i,j) as an edge to the ans vector. Now decrement the degree of the node j and also apply xor to j’s xor sum value to remove i. After removing leaf i from the forest, the forest will still remain a forest . So similarly find the leaves in the current forest (and also the edges which is why we are doing this) and carefully prune the leaves until the forest becomes empty.

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	#include <stdio.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	typedef long long int ll;

	int main(){
	int n,v,s;
	vector<pair<int,int> > arr,ans;

	scanf("%d",&n);
	vector<int>leaves;

	REP(i,n){
	scanf("%d%d",&v,&s);
	arr.pb(mp(v,s));
	if(v==1)
	leaves.pb(i);
	}
	int l=0;
	while(l<leaves.size()){
	if(arr[leaves[l]].first==1){
	ans.pb(mp(leaves[l],arr[leaves[l]].second));
	arr[arr[leaves[l]].second].first--;
	if(arr[arr[leaves[l]].second].first==1)
	leaves.pb(arr[leaves[l]].second);
	arr[arr[leaves[l]].second].second^=leaves[l];
	arr[leaves[l]].first--;

	}
	l++;
	}

	printf("%d\n",ans.size());
	REP(i,ans.size()){
	printf("%d %d\n",ans[i].first,ans[i].second);
	}


	}

view raw Misha and Forest.cpp hosted with ❤ by GitHub

Spoj(CAM5) Prayatna PR

Posted on January 14, 2015 by vishnujayvel

A simple DFS will do good.A 2D vector is used to represent the graph via adjacency list.

All you have to do is have a visited array to mark nodes in the graph that is already visited. Have a count variable to count the number of groups available.

	#include<iostream>
	#include<cstdio>
	#include<vector>
	#include<cstring>
	using namespace std;
	bool visited[100005];
	vector<vector<int> > adj(100005);
	int n;
	void dfs(int i){
	if(visited[i])
	return;
	visited[i]=1;
	for(vector<int>::iterator it=adj[i].begin();it!=adj[i].end();it++){
	if(!visited[*it])
	dfs(*it);
	}
	}
	int main(){

	int t;
	scanf("%d",&t);
	while(t--){
	int e,ans=0,x,y;
	scanf("%d %d",&n,&e);
	memset(visited,0,sizeof visited);
	for(int i=0;i<n;i++)
	adj[i].clear();
	for(int i=0;i<e;i++){
	scanf("%d %d",&x,&y);
	adj[x].push_back(y);
	adj[y].push_back(x);
	}
	for(int i=0;i<n;i++){
	if(!visited[i]){
	ans++;
	dfs(i);
	}
	}
	printf("\n%d",ans);
	}
	}

view raw CAM5.cpp hosted with ❤ by GitHub

Codeforces Round #285 (Div. 2) Problem B – Misha and Changing Handles

Posted on January 13, 2015 by vishnujayvel

Problem link – http://codeforces.com/contest/501/problem/B
consider that each word(handle) goes via chain transition. initialhandle->changeinhandle->againchangeinhandle->….->finalhandle
usedmap will keep track of all currenthandle and its immediate parenthandle.
wordmap will keep track of initial and final handle of a contestant.

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	#include <stdio.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	typedef long long int ll;

	int main(){
	int q;
	string newStr,oldStr;
	map<string,string>wordmap,usedmap;
	//consider that each word(handle) goes via chain transition. initialhandle->changeinhandle->againchangeinhandle->....->finalhandle
	//usedmap will keep track of all currenthandle and its immediate parenthandle
	//wordmap will keep track of initial and final handle of a contestant
	scanf("%d",&q);
	while(q--){
	cin>>oldStr>>newStr;
	if(usedmap.find(oldStr)==usedmap.end()){
	usedmap[oldStr]=oldStr;
	usedmap[newStr]=oldStr;
	wordmap[oldStr]=newStr;
	}
	else{
	usedmap[newStr]=usedmap[oldStr];
	wordmap[usedmap[oldStr]]=newStr;
	}
	}
	cout<<wordmap.size()<<endl;
	for(map<string,string>::iterator it=wordmap.begin();it!=wordmap.end();it++){
	cout<<it->first<<" "<<it->second<<endl;
	}
	}

view raw Misha and Changing Handles.cpp hosted with ❤ by GitHub

	vishnujayvel on Spoj( ONEZERO ) – Ones a…
	muffin on Spoj( ONEZERO ) – Ones a…
	vishnujayvel on Codeforces #296 (Div. 2) B. Er…
	Dharmesh Jogadia on Codeforces #296 (Div. 2) B. Er…
	pkn on Spoj(MIXTURES) Mixtures…

coding hangover

eat pray code :)

Monthly Archives: January 2015

Find the number of pages in the book

What are the best ways to excel in a summer internship?

Spoj(GAMES) – HOW MANY GAMES

Topcoder SRM 646 Div 2 TheGridDivTwo

Codeforces Round #285 (Div. 2) C. Misha and Forest

Spoj(CAM5) Prayatna PR

Codeforces Round #285 (Div. 2) Problem B – Misha and Changing Handles