code with chinmay.c: March 2016

Saturday 12 March 2016

interview preparation

Recursion

sort a stack using recursion

Given a stack, sort it using recursion. Use of any loop constructs like while, for..etc is not allowed. We can only use the following ADT functions on Stack S:

is_empty(S) : Tests whether stack is empty or not.

push(S) : Adds new element to the stack.

pop(S) : Removes top element from the stack.

top(S) : Returns value of the top element. Note that this

function does not remove element from the stack.

Example:

Input: -3 <--- Top

-5

Output: 30 <--- Top

-3

-5

below the code of you to perform it

#include <bits/stdc++.h>
using namespace std;
#ifndef M
#define M 1000000007
#endif
typedef pair<int,int>pp;
typedef std::vector<pp> vpp;
typedef long long ll;
#ifndef pb
#define pb push_back 
#endif 
int min(int x,int y){return(x<y)?x:y;}
int max(int x,int y){return(x>y)?x:y;}
void sorted(stack<int> *s)
{
 int f=s->top();
 s->pop();
 if(s->empty())
 {
  s->push(f);
  return;
 }
 if(s->top()>f)
 {
  int x=s->top();
  s->pop();
  s->push(f);
  sorted(s);
  s->push(x);
 }
 else
 {
  sorted(s);
  s->push(f);
 }
}
int main(int argc, char const *argv[])
{
 int n,x;
 scanf("%d",&n);
 stack<int> s;
 for(int i=0;i<n;i++)
 {
  scanf("%d",&x);
  s.push(x);
 }
 sorted(&s);
 while(!s.empty())
 {
  printf("%d\n",s.top());
  s.pop();
 }
 return 0;
}

Print all non-increasing sequences of sum equal to a given number x

Given a number x, print all possible non-increasing sequences with sum equals to x.

Examples:

Input: x = 3

Output: 1 1 1

2 1

Input: x = 4

Output: 1 1 1 1

2 1 1

2 2

3 1

#include <bits/stdc++.h>
using namespace std;
#ifndef M
#define M 1000000007
#endif
typedef pair<int,int>pp;
typedef std::vector<pp> vpp;
typedef long long ll;
#ifndef pb
#define pb push_back 
#endif 
int min(int x,int y){return(x<y)?x:y;}
int max(int x,int y){return(x>y)?x:y;}
int a[100]={0};
void print(int *a,int index)
{
 for(int i=0;i<=index;i++)
  printf("%d ",a[i] );
 printf("\n");
}
void recurse(int x,int n,int *a,int index)
{
 if(x<=n && x!=0)
 {
  a[index]=x;
  if(x==n)
   print(a,index);
  recurse(x,n-x,a,index+1);
  recurse(x-1,n-x,a,index+1);
 }

}
int main(int argc, char const *argv[])
{
 int n;
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
  recurse(i,n,a,0);
 return 0;
}

Print a pattern without using any loop

Given a number n, print following pattern without using any loop.

Input: n = 16
Output: 16, 11, 6, 1, -4, 1, 6, 11, 16

Input: n = 10
Output: 10, 5, 0, 5, 10
We basically first reduce 5 one by one until we reach a negative or 0. After we reach 0 or negative, we one one add 5 until we reach n.

#include <bits/stdc++.h>
using namespace std;
#ifndef M
#define M 1000000007
#endif
typedef pair<int,int>pp;
typedef std::vector<pp> vpp;
typedef long long ll;
#ifndef pb
#define pb push_back 
#endif 
int min(int x,int y){return(x<y)?x:y;}
int max(int x,int y){return(x>y)?x:y;}
int a[100]={0};
void print(int *a,int index)
{
 for(int i=0;i<=index;i++)
  printf("%d ",a[i] );
 printf("\n");
}
void recurse(int x,int n,int flag)
{
 if(x>=n && flag==0)
  flag=1;
 if(x<=0 && flag==1)
  flag=0;
 if(flag)
 {
  printf("%d,",x-5 );
  if(x-5!=n)
  recurse(x-5,n,flag);
 }
 else
 {
  printf("%d,",x+5 );
  if(x+5!=n)
  recurse(x+5,n,flag);
 }
}
int main(int argc, char const *argv[])
{
 int n;
 scanf("%d",&n);
 printf("%d,", n);
 recurse(n,n,0);
 printf("\n");
 return 0;
}

Monday 7 March 2016

acm icpc regionals amritapuri 2015

Jump on Buildings

Problem code: AMJMP

Our well known coding mafia went to the city. Farzi Coder is the boss here. He hired a new member namedLambu Keyboard in his gang. Farzi Coder is so smart (at least that's what he thinks), so he wants to testLambu Keyboard's programming skills. He gave him this task:
There are n buildings (numbered from left to right) with heights H1, H2...Hn. You can start jumping from any building.
The rules of jumping are:
You can only jump to a building with lesser height than the height of the current building.
In first turn you can jump either way, and 2nd jump will be in the opposite direction of previous jump and must end in between current index and previous index, i.e if we start jumping from building 5, initially we can jump in either direction. Let's say we jump to building 8, then in next jump we can only jump in left direction and only on buildings with indices 6, 7. Let's say we jump to building 6, then next time we can only jump in right direction and between 6 and 8 i.e to 7.
We need to find the maximum number of jumps he can make, considering every building as the starting point.
Input
First line contains an integer n i.e. the number of buildings.

Second line contains n space separated integers denoting heights of buildings from 1 to n.
Output
One line containing n integers, the ith integer will denote the maximum possible number of jumps starting from ith building.
Constraints
1 ≤ n ≤ 5000
1 ≤ H1, H2 ... Hn ≤ 10000
Sample
Input

5
1 3 4 2 5

Output

0 1 1 1 2

Explanation

If starting building is with height 1 then you can't jump to any other building.

If starting building is with height 3 then you can jump either to building with height 2 on right or with height 1 on left. But there will be at most one jump.

If starting building is with height 5 then one possible optimal sequence is to jump to building with height 3 then to building with height 2. So maximum number of jumps is 2.

Discuss the solution

this is one of the medium dp i suggest.

first of all get the sorted form of the values and hence get the indices
second make a two dimensional dp

now suppose for
6,5,1,3,4,2,7,6,1,3,9
I want to find how many jumps does the '2' can make left hand side-

for range (5,5) = 0
for range (4,5) = 0
for range (3,5) = 1
for range (2,5) = 1
for range (1,5) = 1
dp[i][j]=max((a[i]>a[j])?(1+dp[j][i-1]):0,dp[i][j+1])

I want to find how many jumps does the '2' can make right hand side-

for range (7,7) = 0
for range (7,8) = 0
for range (7,9) = 1
for range (7,10) = 1
for range (7,11) = 1

dp[i][j]=max((a[i]>a[j])?(1+dp[j][i+1]):0,dp[i][j-1])

so for each element you will do the same now since we are proceeding the in the increasing order of value so we are doing bottom to top dp and thus storing the value efficiently

now for the input (1,3,4,2,5) given the dp table value will proceed as-

0 0 0 0 0 
0 0 0 0 0 
0 0 0 0 0 
0 0 0 0 0 
0 0 0 0 0 
------------------------
0 0 0 0 0 
0 0 0 0 0 
0 0 0 0 0 
1 0 0 0 0 
0 0 0 0 0 
------------------------
0 0 0 0 0 
1 0 0 1 1 
0 0 0 0 0 
1 0 0 0 0 
0 0 0 0 0 
------------------------
0 0 0 0 0 
1 0 0 1 1 
1 1 0 1 1 
1 0 0 0 0 
0 0 0 0 0 
------------------------
0 0 0 0 0 
1 0 0 1 1 
1 1 0 1 1 
1 0 0 0 0 
2 2 2 1 0 
------------------------

hope you all have got the idea and here is the solution of the question in c++.

/*
jump on buildings
by chinmay rakshit
8/3/2016
*/
#include <bits/stdc++.h>
using namespace std;
#ifndef M
#define M 1000000007
#endif
typedef pair<int,int>pp;
typedef std::vector<pp> vpp;
typedef long long ll;
#ifndef pb
#define pb push_back 
#endif 
int min(int x,int y){return(x<y)?x:y;}
int max(int x,int y){return(x>y)?x:y;}
int dp[5005][5005]={0};
int main(int argc, char const *argv[])
{
 int n,a[5005];
 scanf("%d",&n);
 vpp v;
 for(int i=1;i<=n;i++)
 {
  scanf("%d",&a[i]);
  v.pb(pp(a[i],i));
 }
 sort(v.begin(),v.end());
 for(int z=0;z<n;z++)
 {
  int i=v[z].second;
  for(int j=i-1;j>=1;j--)
   dp[i][j]=max((a[i]>a[j])?(1+dp[j][i-1]):0,dp[i][j+1]);
  for(int j=i+1;j<=n;j++)
   dp[i][j]=max((a[i]>a[j])?(1+dp[j][i+1]):0,dp[i][j-1]);
 }
 for(int i=1;i<=n;i++)
 {
  int ac=0;
  for(int j=1;j<=n;j++)
   ac=max(ac,dp[i][j]);
  printf("%d ",ac);
 }
 return 0; 
}

hope you liked.. :)

code with chinmay.c