Codeforces #247 (Div.2) C.K-Tree

Problem link: http://codeforces.com/contest/431/problem/C

Simple recursion with memoization works.

Code is self explanatory

	#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
	#define mod 1000000007
	typedef long long int ll;
	int k,d,n;
	ll dp[105][2];
	ll solve(int x,int f){
	if(dp[x][f]!=-1){
	return dp[x][f];
	}
	if(x>n)
	dp[x][f]=0;
	else if((x==n)&&f)
	dp[x][f]=1;
	else{
	ll ret=0;
	for(int i=1;i<=k;i++){
	if(x+i<=n){
	ret+=solve(x+i,f||(i>=d)?1:0);
	ret%=mod;
	}
	}
	dp[x][f]=ret;
	}
	return dp[x][f];
	}
	int main(){
	REP(i,105){
	dp[i][0]=-1;
	dp[i][1]=-1;
	}
	scanf("%d%d%d",&n,&k,&d);
	ll ret=0;
	for(int i=1;i<=k;i++){
	ret+=solve(i,(i>=d)?1:0);
	ret%=mod;
	}
	cout<<ret;
	}

view raw k-tree.cpp hosted with ❤ by GitHub

What are the steps to be taken to become a good TopCoder?

Answer by Nick Wu:

1) Practice.
2) Do step 1.

Of course, that’s what everyone tells you, so let’s try to be a little more useful here.

1) Identify your current skill level.

You can do this in a variety of ways. The easiest way is to do a few SRMs and get a rough idea of what your rating is, and consequently, what problems you should work on. Use your performance in a few contests or solve a few problems in practice to see where you are.

2) Start pushing your boundaries.

I’ll give some rough information on what problems you should be working on given your color rating (these aren’t hard rules, but I believe they’re reasonable things to try.)

• Grey: Be more consistent on solving div2 easy problems.
• Green: Get faster at solving div2 easy problems, start building consistency on div2 medium problems.
• Blue: Build consistency on div1 easy problems.
• Low yellow (Below ~2000): Start building speed on div1 easy problems.
• High yellow (Above ~2000): Start working on solving div1 medium problems.
• Red: Start building speed in div1 medium problems.

The hard problems are designed to be solved by very few people so I don’t include them in my list. Yellow coders may be able to use div2 hard problems as a substitute, but you should be able to get by with just div1 medium problems.

3) Repeat steps 1 and 2.

You’ll constantly be improving, so you should work on problems that keep you interested. If you’re a blue coder, there’s not too much point to working on div2 easy problems since you will never actually do one in a regular SRM. Instead, working on building consistency in div1 easy problems, although more difficult, will be more worthwhile. Re-evaluate your skill level every so often (this will be done implicitly if you do more SRMs) and calibrate your training to match.

What are the steps to be taken to become a good TopCoder?

Spoj(SCUBADIV) – Scuba diver

problem link : http://www.spoj.com/problems/SCUBADIV/

This is similar to the classic “knapsack” dynamic programming problem.

Recurrence relation:

dp[n][O][N] = minimum total weight of cylinders required to have O and N capacity of oxygen and nitrogen (capacity of oxygen and nitrogen can exceed) provided n cylinders

dp[i][co][cn]=min(solve(i-1,co,cn),solve(i-1,max(co-oxi[i-1],0),max(cn-nitro[i-1],0))+w[i-1]);

where oxi[i-1] and nitro[i-1] denotes the oxygen and nitrogen capacity of ith cylinder,

w[i-1] denotes the weight of ith cylinder

Terminating conditions:

dp[0][0][0] = 0

dp[0][oxi][nitro]=INFINITY where oxi>0 and nitro>0

	#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;
	const int MAX = 1024;
	const int INF = 999999999;
	int N, O, n, t, cs;
	int nitro[MAX], oxi[MAX], w[MAX];
	int dp[MAX][22][80], visited[MAX][22][80];
	int solve(int i, int co, int cn)
	{
	if(dp[i][co][cn]!=-1){
	return dp[i][co][cn];
	}
	if(co==0&&cn==0){
	dp[i][co][cn]= 0;
	}
	else if(i==0){//if we considered all cylinders and if co and cn are still not equal to zero
	//then its not possible to satisfy the required condition. Hence return INF in order to eliminate all
	//recursive paths leading to this status
	dp[i][co][cn]= INF;
	}else{
	//either select the ith cylinder or move on to i-1th cylinder
	//Be careful about the index:
	//ith cylinder oxi[i-1] capacity of oxygen and nitro[i-1] capacity of nitrogen
	dp[i][co][cn]=min(solve(i-1,co,cn),solve(i-1,max(co-oxi[i-1],0),max(cn-nitro[i-1],0))+w[i-1]);
	}
	return dp[i][co][cn];
	}
	int main()
	{
	scanf("%d", &t);
	while(t--){
	scanf("%d %d %d", &O, &N, &n);
	for(int i=0;i<n+1;i++)
	for(int j=0;j<O+1;j++)
	for(int k=0;k<N+1;k++)
	dp[i][j][k]=-1;
	for(int i = 0; i < n; i++)
	scanf("%d %d %d", &oxi[i], &nitro[i], &w[i]);
	//dp[n][O][N] gives the minimum total weight of cylinders required to have O and N capacity of oxygen
	//and nitrogen (capacity of oxygen and nitrogen can exceed)
	printf("%d\n", solve(n, O, N));
	}
	return 0;
	}

view raw SCUBADIV.cpp hosted with ❤ by GitHub

Codeforces #273 (Div.2) C.Table Decorations

Problem link: http://codeforces.com/problemset/problem/478/C

Logic:

Case 1:

If (number of maximum colored balloon)/2 is greater than or equal to sum of rest of the 2 colored balloons, then we can decorate each table with 2 balloons from maximum colored balloon and 1 balloon from either of the 2 other colored balloons.

Case 2:

If (number of maximum colored balloon)/2 is lesser than the sum of rest of the 2 colored balloons, then maximum number of tables that we can decorate would be (total number of balloons available)/3.

	#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(){
	ll arr[3];
	REP(i,3){
	cin>>arr[i];
	}
	sort(arr,arr+3);
	if(arr[0]+arr[1]<=arr[2]/2){
	cout<<arr[0]+arr[1];
	}
	else{
	cout<<((arr[0]+arr[1]+arr[2])/3);
	}
	}

view raw TableDecorations.cpp hosted with ❤ by GitHub

Codeforces #260(Div 1) A.Boredom

problem link: http://codeforces.com/problemset/problem/455/A

This problem can be solved using dp approach.

Whenever the contraint on n is around 10^5 you have to think in terms of single dimensional recurrence relation.

Let count[i]=number of times i occured in the input array

dp[i]=maximum points that can be obtained by considering elements upto i

There can be 2 possibilities

case 1: i is selected

If you selecting i, then you have to select all such occurences of i to maximize the points. Also element i-1 cannot be selected because it will be eliminated.

So points scored in this case= i*count[i]+dp[i-2]

case 2: i is not selected

If you are not selecting i, then you have to move over to the next element to score points which is i-1 .

So points scored in this case = dp[i-1]

So thus we get the recurrence relation dp[i]=max(dp[i-1],dp[i-2]+count[i]*i)

	#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
	#define MAX 100005
	typedef long long int ll;
	ll dp[MAX];
	ll count1[MAX];
	int main(){
	int n,x;
	cin>>n;
	REP(i,n){
	cin>>x;
	count1[x]++;
	}
	dp[0]=0;
	dp[1]=count1[1];
	for(int i=2;i<MAX;i++){
	dp[i]=max(dp[i-1],dp[i-2]+i*count1[i]);
	}
	cout<<dp[MAX-1];
	}

view raw Boredom.cpp hosted with ❤ by GitHub

Codeforces #266 (Div 2) – Number of Ways

Problem link : http://codeforces.com/contest/466/problem/C

Logic:

Let sum of elements in array = S

If S%3==0 then the array cannot be divided into 3 equal parts . So print zero.

Otherwise,

Have a count array where count[i]=number of subarrays in arr[i…n] whose sum is equal to S/3

Now iterate from the first element and add elements to a variable called “temp”

At iteration i, if temp==S/3 then we have found first part of the “3 equal parts array”.count[i+2] will give you the number of ways the rest of the 2 equal parts of the array could be arranged.

The logic here is “if arr[0…i] sums upto S/3 and if arr[i+j…n] sums upto S/3 then inbetween elements arr[i+1…j-1] will also sum upto S/3 ” here j varies from 2 to n-2.

	#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
	#define MAX 10000005
	typedef long long int ll;
	int arr[1000005];
	int count1[1000005];
	int main(){
	int n;
	cin>>n;
	ll s=0;
	REP(i,n){
	cin>>arr[i];
	s+=arr[i];
	}
	if(s%3!=0){
	cout<<"0";
	return 0;
	}
	ll sum=s/3;
	ll temp=0;
	for(int i=n-1;i>=0;i--){
	temp+=arr[i];
	if(temp==sum){
	count1[i]+=1;
	}
	}
	for(int i=n-2;i>=0;i--){
	count1[i]+=count1[i+1];
	}
	temp=0;
	ll ans=0;
	for(int i=0;i+2<n;i++){
	temp+=arr[i];
	if(temp==sum){
	ans+=count1[i+2];
	}
	}
	cout<<ans;
	}

view raw TheNumberOfWays.cpp hosted with ❤ by GitHub

Which data structure is best suited for making a simple phone book program that returns a number given users name and vice versa?

Answer by Vishnu Jayvel:

Thanks for the A2A.
It depends … There is a tradeoff between space and time complexity when you use any datastructure, be it trie or ternary search tree or hash table.
Trie
  Trie uses a lot of space but we can search in O(n) where n= maximum string length.
But how much memory could you afford ?
If there is 2000 contacts and each contact at the max requires 64 bytes ( 64 character),
Worst case approximately 2000X64 bytesX(nodesize=64 bytes) = 8000KB of memory is required. If your RAM could accomodate such huge trie then you can go for it.  You will need 2 tries ( one for contact name and other for phone number) on the whole.
Ternary search tree
 Space efficient compared to Trie and it searches in O(logn) time. But you can go for either trie or Ternary search tree only if the memory could satisfy the space complexity.
Database ( Hashing)
Create a table with Phone number and contact as fields and do indexing for both the fields. You will be storing the database in the internal phone storage . Based on the query you can send back the result set from the database.
You can take advantage of pagination !You need not show entire result at the same time .For example, if the result set has 50 records fetch 10 records first and then display it the screen , at the same time keep ready of the next 10 records to be displayed in the next page and later when there is time fetch 10 more records and so on.
Since indexing is done by hashing the key(search term),If there is collision more buckets will be created.So it is important to create a good hash function so that there is little or no collision.
Blend of both trie and Hashing
If the collision is unavoidable and if there is so many buckets, hash table might take more time in fetching the result. The you can create a trie initially which can be used to fetch the correct bucket in the hash table which has the result and later you can do binary search in the set of values in the respective bucket and fetch the result.

I hope this helps. Correct me if iam wrong.

Which data structure is best suited for making a simple phone book program that returns a number given users name and vice versa?

What is it like to intern at Amazon?

Answer by Vishnu Jayvel:

I interned at Amazon India – Chennai during summer 2014.

In short:
I had a very good experience. It was fun and challenging.

In detail:
Amazon has always been a dream company for me and I was so excited when I got an offer to intern in Amazon. I was working in Kindle Book Content team.

Smart people everywhere :
Amazon is filled with smart engineers and anytime you roam around the office you could find a group of super talented people brainstorming about some interesting challenges. I was highly motivated by my co-workers everyday.

Interns get challenging projects:
Your work at Amazon totally depends on the team you're on. My manager gave me a project that had good business value for Amazon and was expected to go for production soon. I was very excited by the thought that my project is going to impact millions of Kindle Book readers around the world, so I started to take ownership from the day one.

I wanted to make the best use of my internship period at Amazon. I had periodic brainstorming and feedback sessions with my manager. I adopted Kanban flow (sorted the tasks into ‘todo’,’doing’ and ‘done’), a methodology for task management. This helped me to have reality checks and find my weaker areas.

Bias for action:
At Amazon, everyone is expected to figure out things on their own.
Right from the beginning of my internship, I was encouraged by my manager to make decisions on my own and proceed with my tasks. In fact I was not assigned a mentor and I had to directly report to my manager.

He gave me complete freedom to make changes in the codebase. With great freedom, comes great responsibility. There were scenarios where I was ambiguous in choosing the right path. But as time went on, I got used to this. Thanks to Amazon, I improved my decision making sills.

Nice perks :

• Pretty good stipend
• Sodexo meal coupons
• 24/7 cab facility

Sometimes I went to the office at midnight to collaborate with my manager, who is based in Seattle. I got an Amazon cab anytime I wanted.

Flexible work schedule:
Employees can come in late, work from home, or leave early if they want to. I normally went to office at 11 in the morning. Since nobody monitored me, I had complete freedom. I felt very relaxed and could concentrate on my work without any pressure.

Amazonians are very helpful:
I had two tasks assigned to me during my internship. For my 2nd task, I wanted to know about a feature in Amazon Kindle Direct Publishing. After finding out that the SLO (San Luis Obispo) team was handling the service, I directly contacted the software development managers from SLO and they were so helpful in helping me clear my doubts regarding their service. As an intern, I was suprised to find them friendly and helpful.

Very strict code review:
In Amazon, even if a single line of code is modified it must be reviewed by any of the team members before pushing it to the codebase. My manager reviewed all of my code. If I had made any mistake or if any of my code is unclear he will comment near the line that had issues and send me his review. He sometimes include smilies in code review. Who would do that? 🙂 He was a cool guy. Even though many of co-workers and my seniors told me that code review will be difficult and time confusing to handle, I actually found it interesting.

Each and every line of my code was read. For a system that handles millions of books, it was necessary for the code to be as optimized as possible. Even a single unnecessary instruction has to be carefully pruned from the code before it is pushed to the code base.  

Getting a return offer:
Interns are asked to fill self performance reviews, which is then looked by the mentor/manager, who also give feedback about the intern. This document plays an important role in the hiring decision.

The mentor, manager, bar raiser, and HR are the decision makers.

Conversion from intern to full-time employee is purely based on your project and your work. This can fall into 3 cases:

• Pre-Placement Interview (PPI): If you have completed your project on time and if you have done a decent job, you will be given an oppurtunity to take a pre-placement interview, which will mostly comprise of 1 or 2 technical rounds. Amazon has a very high hiring bar and so the interviews will be mostly challenging.
• Pre-Placement Offer (PPO):If your manager is impressed with your work you might even get a direct offer without any interviews.
• Rejection: If your mentor/manager thinks that you are not up to Amazon standard, you will not be given a PPI. As far as I know, this is a very rare case. No one I knew during my internship got a direct reject.

Overall, it was an enriching learning experience. Amazon has groomed me as a good software developer. For me, coding is like casting magic spells and I am always excited to write code that impacts millions of people. I'm looking forward to going back to Amazon, and yes, I got a Pre-Placement Offer. 🙂

---

To know about my productive work habits during internship refer
Vishnu Jayvel's answer to What are the best ways to excel in a summer internship?

What is it like to intern at Amazon?

Checking if a given string S = nT

i.e to find if a given string can be represented from a substring by iterating it “n” times.

This can be done in O(N)

Let N=string length

Find all prime factors of N and for each prime factor p, consider candidate substring as  N/p length prefix of original string.

Check if the original string is repetition of candidate substring . This can be done in O(N).

Also number of prime factors of N (1<=N<=1 million) can be not more than 6. Hence we can safely say that the overall complexity is O(N).

	#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;
	vector<int> getPrimeFactors(int n){
	int limit=sqrt(n);
	vector<int> primeFactors;
	if(n%2==0){
	primeFactors.pb(2);
	n/=2;
	}
	while(n%2==0){
	n/=2;
	}
	for(int i=3;i<=limit;i+=2){
	if(n%i==0){
	primeFactors.pb(i);
	n/=i;
	}
	while(n%i==0){
	n/=i;
	}
	}
	if(n>2)
	primeFactors.pb(n);
	return primeFactors;
	}
	int main(){
	string str;
	cin>>str;
	int N=str.size();
	if(N>1){
	vector<int> p=getPrimeFactors(N);//get all prime factors of N(length of string)
	//for each factor p[i] check if prefix N/p[i] is the substring that is repeated
	string candidate;
	REP(i,p.size()){
	candidate=str.substr(0,p[i]);
	int k=0;
	int flag=1;
	FOR(j,p[i],N){
	if(candidate[k]==str[j]){
	k++;
	k%=candidate.size();
	}
	else{
	flag=0;
	break;
	}
	}
	if(flag){
	cout<<"Yes!";
	return 0;
	}
	}
	cout<<"No!";
	}
	else{
	cout<<"Not possible";
	}
	return 0;
	}

view raw checkifGivenStringSIsNT.cpp hosted with ❤ by GitHub

Ron Weasley and a magical die

Ron Weasley bought a magical die having 10 sides(numbered  1 to 10) from  Zonko’s Joke Shop in hogsmeade.In this die all the even numbered sides are colored blue and all odd numbered sides are colored white. He wants to find the probabilty of getting a blue color and number 9 in a single throw. Can you answer him.(answer rounded to 3 decimal places)

[Answer in comment section]