20 months ago

Gigaliths 580

IIT Ropar

2 MCQs + 3 Coding questions , 2hours time MCQ Q1 : Given graph , find number of edges that are bridge. Q2 : Clean code principles

Coding

Q1

We are given an array containing integers. We have to convert this array such that the resulting array is a geometric progression. What we need to return is the multiplying ratio of this geometric progression. We have to make sure we make a resulting array such that ratio is maximum.

Example
Given array = [64 , 100 , 125]
Resulting array = [64 , 80 , 100 , 125] 
Answer : ratio in simplest form = 5/4

contraints : Array size <= 1e5

Q2

Equation : (a*m)%n = r Given a , n , r : Find smallest m such that the above equation satisfies.

constraints : a,n,r <= 1e18

Q3

Given a list of strings. and a 2d matrix containing different letters.

We have to choose letters from the matrix to create the list of string with the condition that if you choose some letter from ith row , that row gets erased. (Basically , you can choose only one letter per row)

return if its possible or not to create all words.

Example : 
words = ["sony"]
matrix: 
s s s s 
s n n n
n s o s
y o s y

answer = true , cells = [(0,0) , (2,2) , (1,1) , (3,1)]

constraints : list size <= 1e5 , matrix columns = 6 , matrix rows <= 15

20 months ago

Gigaliths 580

IIT Ropar

Question 1 : Approach ( All tests passed )

-> For each element in the array , prime factorize it (store it like a map)
-> The max ratio that needs to be printed would be surely gcd of the powers of individual primes for each array integer. (think !)
-> Some primes will increase from left to right , while some will decrease from left to right. 
     -> this will be useful for understanding which primes would be part of numerator / denominator.
-> Eg=> [64 , 100 , 125] -> [ {2:6 , 5:0} , {2:2 , 5:2} , {2:0 , 5:3} ]
-> increasing prime = 5 (will come in numerator)
-> decreasing prime = 2 (will come in denominator)
-> our ratio will be (5^a)/(2^b)
-> a = gcd(0,2,3) = 1
-> b = gcd(6,2,0) = 2
-> answer = (5^1) / (2^2) == 5/4
-> If there is some prime which is not monotonic, then return -1. (However , they gave only valid arrays as tests)

complexity = O(Nlogn) (for sieve) , however O(Nsqrt(N)) was also accepted.

1 day ago

admin 1.6k

Hyderabad

Alternative Solution to Q3

We can reduce this problem to the classical Maximum Bipartite Matching problem.

• Using BFS or DFS one can implement Kuhn's algorithm O(NM)
• Or alternatively use a faster solution of Hopcraft Karp O(sqrt(N) * M)
• Or alternatively, use some fast Network Flow algorithms like Dinic with scaling which run very fast in practice.

9 months ago

Akshay Sharma 990

Chandigarh

Question 2

Prerequisite: Linear Congruence Equation

> Step By Step Solution :

• Equation : (a*m)%n=r . Find smallest m
• According to the equation we are given with a,n,r whose value is less than 1e18 it's clearly understandable from the constraints that we can't iterate all possible integers and find the smallest r.
  • Let's modify our equation a little bit and let the maths do the magic : (A*M)=R (mod N)
  • Here where A, R, and N are given integers and M is an unknown integer.
  • Let's suppose here M is equal to X so Now we need to find X
  • It is required to find the value X from the interval [1 to N-1] which is the smallest one.
  • Clearly, on the entire number line there can be infinitely many solutions that will differ from each other in N*K, where K is any integer. If the solution is not unique, then how to get all the solutions? that satisfy our equation

> There can be Multiple cases for the solution

• [When Unique Solution is available ] Lets consider the simple case where A and N are coprime that is __GCD(A, N)==1 (gcd=Greatest Common divisor) then we will find the inverse of A and multiply both sides of the equation with the inverse.
  • X= R * A` (MOD N).
  • [When No Solution exists] This is the case when A and N are not coprime i.e __GCD(A, N)!=1 Then the solution will now exist and we will print -1
  • [Multiple Solution] When the G= gcd(A, N ) is greater than 1 we can iterate from 0 to G-1 and using the value (i) we will find all such solutions and print the minimum one. This can be proved by the Extended Euclidean Algorithm

• Time complexity : O(log(min(A, N))

9 months ago

Akshay Sharma 990

Chandigarh

Question 3

Understanding Problem

• We are given a grid of N*M which consist of N rows and M columns and in every position, we are given some character from a to z
  • We were also given a list/String of Name that we have to find in the grid if its present or not
  • But there is one condition that we are only allowed to choose one word from one row.

Approach (For smaller constraints where N amd M are less than 5)

• If we read the constraints carefully first hint we get is that the length of the given word is 1e5 while the grid size is too small. So if the length of the given string is greater than the number of rows we will print No as we have to choose only one word from each row.
  • This question can be solved in multiple ways one of them is using dynamic programming and recursion.
  • We are going to maintain a freq array that will count the number of times an element occurs in the given string
  • We will use some X that will store the length of string that is present.
  • So the approach is pretty simple we will be selecting a row and making a recursive call choose some position in the grid and check if the character is needed or not if it's needed we will decrease its frequency and increase our X counter and move ahead and make a recursive call for the next row.
  • Just keep checking if we are on ith row and the last column of that row in that case also we are going to make a recursive call.
  • In the last just check if the length of X is equal to the length of the string or not and print the answer.

9 months ago

Akshay Sharma 990

Chandigarh

Question 1

Breakdown

• The first question statement is very much clear itself only
  • We are given an array and we have to form a Gp
  • To understand this question more clearly you need to have some knowledge of senior secondary school maths
  • we have to convert the array into a GP (It does not specify either if we need to delete, insert or update any element)
  • So we assume that the only operation that we can do is insert any element in between such that the ratio of GP is maximised.
  • If modification or deletion operations are allowed then simply we delete all elements and choose the min and maximum elements in the array So assuming that we are only adding the element in the array to make it a perfect G.P

Approach

• Traverse the array from the left and computer the ratio of two neighbouring elements and store all the ratios in an array of double.
• Check if the array of ratios is having the same ratio or not
• If yes simply we didn't modify the array and return as it is
• if No then we can start our check from the lowest ratio and make all ratios similar to it.
• Why the lowest ratio? because if when we insert an element between an array the ratio decrease so we can't able to make the lowest ratio equal to the highest ratio so the best approach is to choose the lowest ratio first.
• Time Complexity: O(N)

4 days ago

Vibhaas Nirantar Srivastava • 0

Thrissur

The 9th testcase for Problem 1 are probably wrong, seeing that problem author himself has incorrect solution. Here is an alternate solution to the problem:

• We know that the ratio r must be less than or equal a[i] / a[i-1] for all 1 <= i <= n.
• So, we find the minimum value of the difference a[i] - a[i-1], and from then we use a[i] as the numerator and a[i-1] as the denominator of the ratio
• While we cannot find a GP fitting the sequence with the current numerator, we decrease the numerator. This is because, we know that the GP should be integer sequences. So the element following a[i-1] must be an integer in the range [a[i] + 1, a[i+1]]
• If we successfully find a numerator that has the given sequence as a subset, we are done! and print the sequence. otherwise, we print -1

It can be proven that this solution runs in amortized O(n).

Code:
 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

ll n;
vector<ll> a;

bool check_ratio(ll num, ll deno, bool debug = false) { 
    // Check if the GP generated by the a[0] as starting value and
    // ratio (num / deno) is a valid GP for our question
    unordered_set<ll> s;
    ll cur = a[0];
    while(cur <= a[n-1]) {
        s.insert(cur);
        if(debug) cout << cur << "\n";
        if((cur * num) % deno != 0 && cur < a[n-1]) return false;
        cur = (cur * num) / deno;
    }
    for(auto x : a) {
        if(!s.count(x)) return false;
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n;
    a = vector<ll>(n);
    for(auto &x : a) cin >> x;
    
    if(n == 0 || n == 1) { // degenerate cases 
        for(auto x : a) cout << x << " ";
        return 0;
    }

    if(a[0] == 0 && a[n-1] != 0) { // degenerate cases 
        cout << "-1"; return 0;
    }

    if(n == 2 || a[0] == a[n-1]) { // degenerate cases 
        for(auto x : a) cout << x << " ";
        return 0;
    }

    // Find the minimum difference and run the check ratio function on it
    ll min_diff_i = 1;
    for(ll i = 1; i < n; i++) {
        if(a[i] - a[i-1] < a[min_diff_i] - a[min_diff_i - 1]) {
            min_diff_i = i;
        }
    }

    // now ratio has to be less than or equal to a[min_diff_i]/a[min_diff_i-1]
    ll ratio_num = a[min_diff_i], ratio_denom = a[min_diff_i - 1];
    while(ratio_num != ratio_denom && !check_ratio(ratio_num, ratio_denom)) ratio_num--;

    if(ratio_num == ratio_denom) { // nothing worked, -1 case
        cout << "-1";
        return 0;
    }

    // we found some valid ratio, lets print the GP
    vector<ll> ans;
    ll cur = a[0];
    while(cur <= a[n-1]) {
        ans.push_back(cur);
        cur = (cur * ratio_num) / ratio_denom;
    }

    for(auto x : ans) cout << x << " ";

    return 0;
}