Code Vita Questions and Solutions #2
Problem A: Pascal Pyramid
Pascal’s triangle giving binomial coefficients is well known. In this triangle, elements in each row can be obtained by adding two adjacent elements in the previous row. The pyramid of numbers we construct in this problem is similar to the Pascal triangle. We start with six numbers at the base of the pyramid and construct the pyramid one layer at a time by adding the two adjacent numbers in the previous layer. For Example, starting with the numbers 1 2 3 4 5 6 in the base, we get the following pyramid. The apex of the pyramid is filled with the product of the numbers in the row below instead of the sum. In the above pyramid, the apex is filled with the number 48 x 64 =3072. The aim is to get the largest number possible at the apex of the pyramid. The input will be a set of N positive integers. Six need to be chosen from these and arranged at the base to get the largest possible number at the top.
Input Format: The first line of the input is N, the total number of integers that will be given. The second line is a set of N (not necessarily distinct) comma separated positive integers from which the six numbers at the base need to be selected.
Output Format: The output is one line with an integer representing the maximum value of the apex of the pyramid when six integers are selected and arranged suitably at the base.
Constraints: N < 13 Integers provided for selection ≤ 100
Example 1:
Input
8
10,4,74,61,8,37,2,35
Output
746415
Explanation There are 8 numbers given, from which the 6 numbers in the base are to be selected and arranged so as to maximize the apex number. One way of doing this is in the figure below.
Solution in C++:
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
ll N,x,idx;
vector <ll> v,v1,v2,v3;
ll f1,f2,f3,f4,f5,f6,ans;
int main()
{
cin>>N;
for(int i=0;i<N;i++){
cin>>x;
v.push_back(x);
sort(v.begin(),v.end());
idx=v.size()-1;
v1.push_back(v[idx]); idx — ;
v1.push_back(v[idx]); idx — ;
v2.push_back(v[idx]); idx — ;
v2.push_back(v[idx]); idx — ;
v3.push_back(v[idx]); idx — ;
v3.push_back(v[idx]);
for(int i=0;i<2;i++){
f3=v1[i];
f4=v1[(!i)];
for(int j=0;j<2;j++){
f2=v2[j];
f5=v2[(!j)];
for(int k=0;k<2;k++){
f1=v3[k];
f6=v3[(!k)];
ans=max(ans,(f1+4*f2+6*f3+4*f4+f5)*(f2+4*f3+6*f4+4*f5+f6));
cout<<ans<<endl;
return 0;
}Problem B: Bride Hunting
Sam is an eligible bachelor. He decides to settle down in life and start a family. He goes bride hunting.
He wants to marry a girl who has at least one of the 8 qualities mentioned below:-
1) The girl should be rich.
2) The girl should be an Engineer/Doctor.
3) The girl should be beautiful.
4) The girl should be of height 5.3".
5) The girl should be working in an MNC.
6) The girl should be an extrovert.
7) The girl should not have spectacles.
8) The girl should be kind and honest.
He is in search of a bride who has some or all of the 8 qualities mentioned above. On bride hunting, he may find more than one contenders to be his wife.
In that case, he wants to choose a girl whose house is closest to his house. Find a bride for Sam who has maximum qualities. If in case, there are more than one contenders who are at equal distance from Sam’’s house; then
print ““Polygamy not allowed””.
In case there is no suitable girl who fits the criteria then print “”No suitable girl found””
Given a Matrix N*M, Sam’s house is at (1, 1). It is denoted by 1. In the same matrix, the location of a marriageable Girl is also denoted by 1. Hence 1 at location (1, 1) should not be considered as the location of a marriageable Girl’s location.
The qualities of that girl, as per Sam’’s criteria, have to be decoded from the number of non-zero neighbors (max 8-way) she has. Similar to the condition above, 1 at location (1, 1) should not be considered as the quality of a Girl. See Example section to get a better understanding.
Find Sam, a suitable Bride and print the row and column of the bride, and find out the number of qualities that the Bride possesses.
NOTE: — Distance is calculated in number of hops in any direction i.e. (Left, Right, Up, Down and Diagonal)
Constraints
2 <= N,M <= 10²
Input Format
First Line contains the row (N) and column (M) of the houses.
Next N lines contain the data about girls and their qualities.
Output
It will contain the row and column of the bride, and the number of qualities that Bride possess separated by a colon (i.e. :)
Explanation
Example 1
Input:
2 9
1 0 1 1 0 1 1 1 1
0 0 0 1 0 1 0 0 1
Output:
1:7:3
Explanation:
The girl and qualities are present at (1,3),(1,4),(1,6),(1,7),(1,8),(1,9),(2,4),(2,6),(2,9).
The girl present at (1,3) has 2 qualities (i.e. (1,4)and (2,4)).
The girl present at (1,4) has 2 qualities.
The Bride present at (1,6) has 2 qualities.
The Bride present at (1,7) has 3 qualities.
The Bride present at (1,8) has 3 qualities.
The Bride present at (1,9) has 2 qualities.
The Bride present at (2,4) has 2 qualities.
The Bride present at (2,6) has 2 qualities.
The Bride present at (2,9) has 2 qualities.
As we see, there are two contenders who have maximum qualities, one is at (1,7) and another at (1,8).
The girl who is closest to Sam’s house is at (1,7). Hence, she is the bride.
Hence, the output will be 1:7:3.
Example 2
Input:
6 6
1 0 0 0 0 0
0 0 0 0 0 0
0 0 1 1 1 0
0 0 1 1 1 0
0 0 1 1 1 0
0 0 0 0 0 0
Output:
4:4:8
Explanation:
The bride and qualities are present at (3,3),(3,4),(3,5),(4,3),(4,4),(4,5),(5,3),(5,4),(5,5)
The Bride present at (3,3) has 3 qualities (i.e. (3,4),(4,3) and (4,4)).
The Bride present at (3,4) has 5 qualities.
The Bride present at (3,5) has 3 qualities.
The Bride present at (4,3) has 5 qualities.
The Bride present at (4,4) has 8 qualities.
The Bride present at (4,5) has 5 qualities.
The Bride present at (5,3) has 3 qualities.
The Bride present at (5,4) has 5 qualities.
The Bride present at (5,5) has 3 qualities.
As we see, the girl present in (4,4) has maximum number of Qualities. Hence, she is the bride.
Hence, the output will be 4:4:8.
Solution in C++:
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
ll N,M;
ll mat[1000][1000];
ll x_dist,y_dist,t_dist;
ll prop_ans=-1e9,prod_dist=1e9,x_ans,y_ans;
ll f1(ll x, ll y){
if(x<1||x>N||y<1||y>M||mat[x][y]==0) return 0;
return 1;
}
ll f2(ll x , ll y){
if(mat[x][y]==0) return 0;
return f1(x-1,y)+f1(x+1,y)+f1(x,y-1)+f1(x,y+1)+f1(x-1,y-1)+f1(x-1,y+1)+f1(x+1,y-1)+f1(x+1,y+1);
}
ll f(pair<ll,pair<ll,ll>> a, pair<ll,pair<ll,ll>> b){
if(a.first!=b.first) return a.first>b.first;
else max(a.second.first,a.second.second)<max(b.second.first,b.second.second);
}
int main()
{
cin>>N>>M;
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
cin>>mat[i][j];
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
mat[i][j]=f2(i,j);
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
if(i==1&&j==1){
//do nothing
else{
if(prop_ans<mat[i][j]){
prop_ans=mat[i][j];
prod_dist=max(i-1,j-1);
x_ans=i;
y_ans=j;
else if(prop_ans==mat[i][j]){
ll temp=max(i-1,j-1);
if(prod_dist>temp){
prod_dist=temp;
x_ans=i;
y_ans=j;
cout<<x_ans<<”:”<<y_ans<<”:”<<prop_ans<<endl;
return 0;
}Problem C: Super ASCII String Checker
In the Byteland country a string “S” is said to super ascii string if and only if count of each character in the string is equal to its ascii value.
In the Byteland country ascii code of ‘a’ is 1, ‘b’ is 2 …’z’ is 26.
Your task is to find out whether the given string is a super ascii string or not.
Input Format:
First line contains number of test cases T, followed by T lines, each containing a string “S”.
Output Format:
For each test case print “Yes” if the String “S” is super ascii, else print “No”
Constraints:
1<=T<=100
1<=|S|<=400, S will contains only lower case alphabets (‘a’-’z’).
Sample Input and Output
Input
2
bba
scca
Output
Yes
No
Explanation:
In case 1, viz. String “bba” -
The count of character ‘b’ is 2. Ascii value of ‘b’ is also 2.
The count of character ‘a’ is 1. Ascii value of ‘a’ is also 1.
Hence string “bba” is super ascii.
Solution in C++:
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
ll N,status;
string s;
map<char,ll>m;
int main()
{
cin>>N;
while(N — ){
cin>>s;
m.clear();
for(int i=0;s[i];i++){
m[s[i]]++;
status=1;
for(auto i:m){
if(int(i.first-’a’)+1!=i.second) status=0;
if(status) cout<<”Yes”<<endl;
else cout<<”No”<<endl;
return 0;
}
