CodeFriday-1 JUIT Solution

Bob and the Examination:

Practice

Author: Arpit Mishra

DIFFICULTY:

Simple

PROBLEM:

Bob is appointed as an invigilator for an examination. In the examination hall there are N students with roll number 1 to N and N benches. The seating arrangement is as follows: first all odd roll number students are seated and then all even roll number students. Bob wants to know the roll number of the student sitting on K^{th} bench. Since Bob is weak at maths he needs your help.

EXPLANATION:

The numbers are divided into two sequences first the odd sequence(1, 3, 5,\dots whose n^{th} term is 2*n-1) and then even sequence(2, 4, 6,\dots whose n^{th} term is 2*n). To find out which roll number is at K^{th} bench one needs to find the position where even numbers start which will be ceil(N/2)+1. So if K is in the first half the answer will be 2*K-1 and if it is in the second half the answer will be 2*(K-ceil(N/2)).

SOLUTION1:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	long long n,k;
	cin>>n>>k;
	if(k<=(n+1)/2)
		cout<<(k*2)-1;
	else
		cout<<(k-(n+1)/2)*2;
	return 0;
}

SOLUTION2:

Setter's Solution
#include <iostream>
using namespace std;
int main() {
	int n,k;
	cin>>n>>k;
	int a[n];
	int c=0;
	for(int i=1;i<=n;i=i+2){
	    a[c]=i;
	    c++;
	}
		for(int i=2;i<=n;i=i+2){
	    a[c]=i;
	    c++;
	}
	cout<<a[k-1];
	return 0;
}

Find Steps:

Practice

Author: Arpit Mishra

DIFFICULTY:

Simple

PROBLEM:

You are provided a number N. In one step, you can either divide N by 6(if N is 0) or multiply N by 2.
Find the minimum number of steps required to get 1 from N or check if it is not possible.

EXPLANATION:

FIND STEPS : If the number consists of other primes than 2 and 3 then the answer is -1. Otherwise, let cnt2 be the number of twos in the factorization of n and cnt3 be the number of threes in the factorization of n. If cnt2>cnt3 then the answer is -1 because we can’t get rid of all twos. Otherwise, the answer is (cnt3−cnt2)+cnt3.

Time complexity: O(logn).

SOLUTIONS:

Setter's Solution
 #include <bits/stdc++.h>

using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		int cnt2 = 0, cnt3 = 0;
		while (n % 2 == 0) {
			n /= 2;
			++cnt2;
		}
		while (n % 3 == 0) {
			n /= 3;
			++cnt3;
		}
		if (n == 1 && cnt2 <= cnt3) {
			cout << 2 * cnt3 - cnt2 << endl;
		} else {
			cout << -1 << endl;
		}
	}
	
	return 0;
}

Candies:

Practice

Author: Arpit Mishra

DIFFICULTY:

Easy

PREREQUISITES:

Greedy

PROBLEM:

There is a candy shop that sells N varieties of candies. The i-th variety has a_i candies.
You want to buy as many candies as possible. If you buy b_i candies of variety i, then for all 1 \leq j \lt i either b_j = 0 (you bought 0 candies of type j) or b_j \lt b_i (you bought less candies of type j than of type i).
Remember, there is no shortage of money.

EXPLANATION:

It is optimal to proceed greedily from the back of the array. If we have taken c candies of the i+1 type, then we can only take min(c-1,a_i) candies for type i. If this value is less than zero, we take 0 from here.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    int cur=INT_MAX;
    ll ans=0;
    for(int i=n-1;i>=0;i--)
    {
        cur=min(cur-1,a[i]);
        cur=max(0,cur);
        ans+=cur;
    }
    cout<<ans;
    return 0;
}

Minimum Area:

Practice

Author: Arpit Mishra

DIFFICULTY:

Simple

PROBLEM:

You are provided four points p on x-axis, q on y-axis, r(min - value on x-axis) and s(min - value on y-axis). Initially, p≥r and q≥s. You can perform the following operation less than or equal to n times:

Select either p or q and reduce it by 1. Where point p cannot become less than r, and point q cannot become less than s. Find the minimum possible area under p,q(p⋅q) you can cover by applying the given operation less than or equal to n times.

EXPLANATION:

The only fact required to solve the problem: if we start decreasing the number, we are better to end decreasing it and only then decrease the other number. So, we can just consider two cases: when we decrease a first, and b after that and vice versa, and just take the minimum product of these two results. The rest is just implementation.

SOLUTION1:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long

ll s(ll a, ll b, ll x, ll y, ll n) {
	ll t=min(a-x, n);
	a-=t;
	n-=t;
	t=min(b-y, n);
	b-=t;
	return a*b;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	int t=1;
	cin>>t;
	while(t--) {
		ll a, b, x, y, n;
		cin>>a>>b>>x>>y>>n;
		cout<<min(s(a, b, x, y, n), s(b, a, y, x, n))<<"\n";
	}
	return 0;
}

Group:

Practice

Author: Arpit Mishra

DIFFICULTY:

Easy

PREREQUISITES:

Combinatorics

PROBLEM:

There are N men and M women in a theatre club. They need to select a group of exactly K actors comprising at least 4 men and at least 1 woman to set a play “Hamlet”. How many ways of making a choice for a group are there?

EXPLANATION:

Since the constraints are small, let’s just iterate through all possible numbers i of men in the group and count how many ways we can form the group with i men. First, consider only the values where i \geq 4. Given i, it’s clear that the number of women in the group must be j = K-i. Given the values of i and j, there are \binom{n}{i} * \binom{m}{j} ways to form the group, since we can combine the men independently with the women. Just sum \binom{n}{i} * \binom{m}{j} for each pair (i,j). We can precompute all the values of \binom{i}{j} using Pascal triangle.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll c[31][31];
    for(int i=0;i<=30;i++)
    {
        for(int j=0;j<=30;j++)
        {
            if(j==0||i==j)
                c[i][j]=1;
            else
                c[i][j]=c[i-1][j-1]+c[i-1][j];
        }
    }
    int n,m,k;
    cin>>n>>m>>k;
    ll a=0;
    for(int i=4;i<k;i++)
    {
        if(i<=n&&k-i<=m)
            a+=c[n][i]*c[m][k-i];
    }
    cout<<a;
    return 0;
}

Cheating during pandamic:

Practice

Author: Arpit Mishra

DIFFICULTY:

Easy

PREREQUISITES:

Graph

PROBLEM:

Due to COVID-19, 2020 has been a tough year for Indian Students is especially
problematic as students need to spend long period in crowded classes where
social distancing is difficult to maintain.
To minimize the spread of COVID-19, each column is separated by 12 fts.
.The Institution are hoping that by not making any one “hub”, the spread of the virus will be significantly limited.
The Institute wants to conduct exam and students want to cheat in class. Classes normally have N bench in a column ,
running in various directions. Amidst the pandemic, each bench has carefully arranged these N benches in a sequence
with each assigned a number from 1 to N. Cheating can only be done between pairs of benches that are adjacent
in this sequence, they can cheat in both directions. That is, cheating can be done
from bench i to bench j if and only if ∣i−j∣=1.
To make things more complicated, some students have their own restrictions on wanting
a chit slip and passing a chit slip. These restrictions are indicated by the characters WC1…N (wanting chits)
and PC1…N ,(passing chit) each of which is either “N” or “Y” :
• If WCi = “N”, then incoming slips to bench i from any other bench are disallowed. Otherwise, if WCi = “Y”, they may be allowed.
• If PCi = “N”, then passing chits from state i to any other bench are disallowed. Otherwise, if Pi = “Y”, they may be allowed.
As a consulting data scientist of the class, your job is to determine which benching
between the various benches are possible. Let Pi,j = “Y” if it’s possible to travel from
state i to state j via a sequence of 0 or more trains (which may pass through other states along the way),
and Pi,j = “N” otherwise. Note that Pi,i is always “Y”. Output this N∗N matrix of characters

EXPLANATION:

 We can make a truth table for the students that can get or pass chits
You can either do this using a graph or a simple 2d matrix
Here is an impimentation using matrix
For each starting student s, the set of destination countries which 
it's possible to reach must form some consecutive interval As..Bs
A_s..B_sAs​..Bs​, such that As≤s≤Bs As​≤s≤Bs​.
We can begin by assuming that Bs=s  and then repeatedly increase 
Bs until it has reached either student N or the first student after
s which is unreachable from it. As long as Bs<N 
it should be incremented if chits are allowed from student 
Bs​ to student Bs+1, which is the case if and only if 
OBs​​=IBs​+1​= "Y".
The above process can be performed for each starting student 
s, and repeated similarly to compute each As​ value. 
A1..N​ and B1...N​ may then be used to populate the required P matrix.
 Each part of this solution takes O(N^2) time.
End of the day we can just print the truth table for the sequence 

SOLUTIONS:

Setter's Solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
void solve()
{
    int n;

    cin>>n;
    string in;
    string out;
    char m[50][50];
    cin>>in;
    cin>>out;
    for (int i=0;i<n;i++){
            int counter=1;
            for(int j=i;j>=0;j--){
                if(i==j){
                        m[i][j]='Y';
                        }
                else{
                    if(in[j]=='Y' && out[j+1]=='Y' && counter == 1){
                            m[i][j]='Y';

                    }
                    else{
                        m[i][j]='N';
                        counter=0;
                    }
                }
        }
        counter=1;
        //runsecond loop here
            for(int j=i+1;j<n;j++){

                    if(in[j]=='Y' && out[j-1]=='Y' && counter == 1){
                            m[i][j]='Y';

                    }
                    else{
                        m[i][j]='N';
                        counter=0;
                    }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<m[i][j];
        }
        cout<<"\n";
    }
}



int main()
{
	//This is done in cpp to increase input output speed of cout and cin
	//Since speed of printf and scanf is more this will componsate it
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    for (int q=1; q<=t; q++)
    {
        cout<<"Case #"<<q<<": \n";
        solve();
    }
}