Question: Jaguar, Recently Asked Questions in IIT-K, November 2022

Entering edit mode

Question 1

Jaguar 1.1

You are given a book with n chapters.
Each chapter has a specified list of other chapters that need to be understood in order to understand this chapter. To understand a chapter, you must read it after you understand every chapter on its required list. Currently you don't understand any of the chapters. You are going to read the book from the
beginning till the end repeatedly until you understand the whole book. Note that if you read a chapter at a moment when you don't understand some of the required chapters, you don't understand this chapter. Determine how many times you will read the book to understand every chapter, or determine tha you will never understand every chapter no matter how many times you read the book.
Input Each test contains multiple test cases. The first line contains the number of test cases t (1≤ t ≤ 2*10^4).The first line of each test case contains a single integer n (1 ≤ n ≤ 2*10^5) - number of chapters. Then n lines follow. The i-th line begins with an integer k_i (O ≤ k_i ≤ n-1) - number of chapters
required to understand the i-th chapter. Then ki integers Ai1, a_i2;.., a_iki, (1 ≤ a_ij ≤ n,a_ij≠ i,a_ij=a_il, for
j ≠ 1) follow - the chapters required to understand the i-th chapter.It is guaranteed that the sum of n and sum of k_i; over all testcases do not exceed 2*10^5.

Output For each test case, if the entire book can be understood, print how many times you will
read it, otherwise print -1.

Question 2

Click here to Practice

Jaguar 2.1

You are given two arrays a1, a2, ..., an and b1, b2, .., bn. In each step, you can set aj = ai - bi
if ai > bi. Determine the minimum number of steps that are required to make all a's equal.
Input format
First line: n
Second line: a1, a2, ..., an
Third line: b1, b2, ..., bu

Output format

Print the minimum number of steps that are required to make all a's equal. If it is not possible,
then print - 1.

Constraints

1 ≤ n, ai, bi; ≤ 5000

Sample input 1

2
5 6
4 3

Sample output 1

-1

Sample input 2

5
5 7 10 5 15
2 2 1 3 5

Sample output 2

ADD COMMENT • link

Entering edit mode

Question 1 solved using a simple variation of topo sort-

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

int main() {

int n;
cin>>n;
vector<int>adj[n+1];
vector<int>in(n+1);
for(int i=1;i<=n;i++){
int k;
cin>>k;
for(int j=0;j<k;j++){
int x;
cin>>x;
in[i]++;
adj[x].push_back(i);
}
}
priority_queue<int,vector<int>,greater<int>>pq;
for(int i=1;i<=n;i++){
if(in[i]==0){
pq.push(i);
}
}
if(pq.size()==0){
cout<<"-1\n";
return 0;
}
int c=0;
while(pq.size()){
c++;
priority_queue<int,vector<int>,greater<int>>pq1;
while(pq.size()){
auto it=pq.top();
pq.pop();
for(auto it1:adj[it]){
in[it1]--;
if(in[it1]==0){
if(it1>it){
pq.push(it1);
}
else{
pq1.push(it1);
}
}
}
}
while(pq1.size()){
pq.push(pq1.top());
pq1.pop();
}
}
for(int i=1;i<=n;i++){
if(in[i]>0){
cout<<"-1\n";
return 0;
}
}
cout<<c<<endl;
return 0;

}

ADD REPLY • link 15 months ago

fvdfgv • 0

Entering edit mode

Question 1

Overview

You are given a book with n chapters.
Each chapter has a specified list of other chapters that need to be understood in order to understand this chapter. To understand a chapter, you must read it after you understand every chapter on its required list.

Currently, you don't understand any of the chapters. You are going to read the book from the beginning till the end repeatedly until you understand the whole book.
Note that if you read a chapter at a moment when you don't understand some of the required chapters, you don't understand this chapter.
Determine how many times you will read the book to understand every chapter, or determine that you will never understand every chapter no matter how many times you read the book.

Solution

We will construct a graph, where there is a directed edge from a to b if chapter a is needed to understand chapter b. This edge has weight 0 if b>a and 1 otherwise.
The answer is the length of the longest weighted path in this graph incremented by 1. If there exists a cycle we should output −1.
If the graph is a DAG, we can use topological sort and a simple DP to calculate the answer.

Code

  void dfs(ll v)
  {
    for (auto it : adj[v])
    {
        if (color[it.ff] == 0)
        {
            color[it.ff] = 1; // Set value as 1
            dfs(it.ff);
        }
        else if (color[it.ff] == 1) // Means a cycle a present in the graph
        {
            flag = 1; // Make flag 1
        }
    }
    color[v] = 2; // Set value of color to 2
  }
  void solve()
  {
    ll n;
    cin &gt;&gt; n;
    flag = 0;
    for (ll i = 1; i &lt;= n; i++)
    {
        ll x;
        cin &gt;&gt; x;
        for (ll j = 0; j &lt; x; j++)
        {
            ll y;
            cin &gt;&gt; y;
            if (i &gt; y)
            {
                adj[y].pb({i, 0});
            }
            else
            {
                adj[y].pb({i, 1});
            }
            ind[i]++; // increase dependency by 1
        }
    }
    for (ll i = 1; i &lt;= n; i++)
    {
        if (color[i] == 0)
        {
            color[i] = 1;
            dfs(i);
        }
    }
    if (flag)
    {
        for (ll i = 1; i &lt;= n; i++) // reset all values
        {
            color[i] = 0;
            d[i] = 0;
            ind[i] = 0;
            adj[i].clear();
        }
        cout &lt;&lt; -1 &lt;&lt; endl; // If cycle is present then its never possible to read all the chapters
        return;
    }
    queue&lt;ll&gt; q;
    for (ll i = 1; i &lt;= n; i++)
        color[i] = 0;
    for (ll i = 1; i &lt;= n; i++)
    {
        if (ind[i] == 0) // If a particular chapter has no dependency
        {
            color[i] = 1;
            q.push(i); // insert it in a queue
            d[i] = 0;
        }
    }
    ll ans = 0;
    while (!q.empty())
    {

        ll v = q.front();
        color[v] = 1;
        q.pop(); // Take out the element
        for (auto it : adj[v])
        {
            ind[it.ff]--; // decrese the dependency by 1
            if (ind[it.ff] == 0)
            {
                q.push(it.ff);
            }
            d[it.ff] = max(d[it.ff], d[v] + it.ss); // increase the distance accordingly
        }
    }
    for (ll i = 1; i &lt;= n; i++)
    {
        ans = max(ans, d[i] + 1); // answer would be maximum of all possible distances + 1(for starting)
        color[i] = 0;
        d[i] = 0;
        ind[i] = 0;
        adj[i].clear();
    }
    cout &lt;&lt; ans &lt;&lt; endl;
    return;
}

ADD COMMENT • link 2.0 years ago Ujjwal Srivastava 320

Entering edit mode

Q2)

Solution for 2

First of all let's analyze when we can convert a[i] to X it can be done iff (a[i] - p * b[i])==X, where p is number of steps we have used for i_th integer
So now we know when we can convert any a[i] to X, so let's iterate over all possible values of X 0 < =X < =max_element of array, because we cannot make X > max_element of array, due to the fact we can only reduce number in any step not increase them,, and since we can only apply operation when a[i]>=b[i], and all a[i]'s are >=1 initially, so X cannot be less than 0
Now for number of steps, we need to check the following for converting a[i] to X
- a[i]>=X
- (a[i]-X) should be multiple of b[i], because a[i] - X = p * b[i]
- Number of steps would be p, p = (a[i]-X) / b[i]

Pseudo Code

Iterate over values of X in [0....max_element of array]
    possible = 1
    steps=0
    for ( int i=0;i &lt; n;i++)
       if(a[i] &gt; =X and ((a[i]-X) is divisible by b[i]) )
           steps= steps + (a[i]-X)/b[i]
       else
           possible=0
    if(possible)
        answer=min(answer,steps)

If you do not get any valid possible than output -1

ADD COMMENT • link 2.0 years ago Shikhar Mehrotra 480