Question: Edfora, Recently Asked Online Assessments in IITs, September, 2022 | Energy | Shunting Yard Problem | Candy Shop

Entering edit mode

Question 1

Click here to Practice

Energy

1.1 1.2

Question 2

Click here to Practice

Shunting Yard Problem

2.1 2.2

Question 3

Candy Shop

Click here to Practice

3.1 3.2

ADD COMMENT • link

Entering edit mode

Question 1 Energy

Overview

Given ith and jth node of binary tree find intensity of light at jth node if ith node was hit by a head wave.

Approach:

Intensity of light produced by photon decreases by one for its neighbouring nodes. So the decrement is equal to distance between the wave heated node and jth node. So, the problem is reduced to find distance between two nodes of binary tree.
The approach to solving this problem is straightforward, i.e., via first finding the LCA(Least Common Ancestor) of the two given nodes and then calculating - (the distance between LCA and node1) + (the distance between LCA and node2). This would be the shortest distance between two nodes of a Binary Tree.
- To find LCA elevate the lower node until both node come on same level. Then start elevating both of them by one until both node become the same photon.
- To find parent we just have to divide current node by 2, thus time complexity of elevating is O(log(n)) where n is the value on that node.

Complexity

> O(log(i) + log(j)) where i is the value on heated photon and j is value on emitting photon.

PseudoCode

   long long par(long long node){      // find and return parent
     if(node&amp;1) node-=1;
     return (node&gt;&gt;1);
   }
   long long find_level(long long node)
   {
     long long root =1;
     while((root&lt;&lt;1)&lt;=node) root&lt;&lt;=1;
     return root;
   }
   int find_dis(long long i, long long j){
     int ans = -1;
     if(i&gt;j) swap(i,j);
     long long level_of_i  = find_level(i);   // to find the minimum power of two which is just smaller or equal to node
     while(par(j)&gt;=level_of_i){
       ans-=1;
       j = par(j);
     }
     while(i!=j){
       ans-=2;
       i = par(i);
       j = par(j);
     }
     return ans;
   }

ADD COMMENT • link 23 months ago Rishabh Verma 170

Entering edit mode

Question 2

Overview

We have an expression in infix form
We have to evaluate the expression

Approach

First, we will have to convert infix to postfix format. We will do this using a stack.

If we encounter an operand, then we will add it to the postfix string.
If we encounter an operator, if the precedence of this operator is greater than the current top of the operator stack then we push the operator.
Otherwise, we pop the operator from the stack and add it to the postfix string, and push the current operator in the stack.

Then we will evaluate this postfix expression.

If we encounter an operand, then we add it to the value stack.
If we encounter an operator, then we pop two values from the stack and push the result back into the stack
If we encounter the right parenthesis, then we keep repeating the above step till we get the left parenthesis and pop it.
The final value left in the stack would be our answer.

Time Complexity

O(n) as each element of the string would be inserted and removed from the stack a constant number of times.

PseudoCode

       if(isnumber(s)){
            values.push(stoi(s));
        }
        else if(s=="("){
            ops.push(s);
        }
        else if(s == ")"){
            while(!ops.empty() &amp;&amp; ops.top() != "(")
            {
                int firstval=values.top();
                int secondval = values.top();
                values.pop();
                                values.pop();
                string op = ops.top();
                ops.pop();
                int result=eval(firstval,secondval,op);
                                values.push(result);
            }
            if(!ops.empty())
            ops.pop();
        }
        else {
                                int firstval=values.top();
                int secondval = values.top();
                values.pop();
                                values.pop();
                string op = ops.top();
                ops.pop();
                int result=eval(firstval,secondval,op);
                                values.push(result);
                }
// To evaluate the postfix expression
      while(!operators.empty()){
        int secondval = values.top();
        values.pop();
        int firstval = values.top();
        values.pop();   
        string operator = operators.top();
        operators.pop();
        int result=eval(firstval,secondval,operator);
        values.push(result);
    }
// final value in stack is the answer

ADD COMMENT • link 23 months ago Harsh Priyadarshi 70

Entering edit mode

Question 3: Candy Shop

Overview

Given N types of candy combos, each candy combo having some cost C containing candles of one or more flavors. Buy candy combos in such a way as to have all the flavors at the end and incur the minimum cost in doing so.

Approach

The idea is to use dynamic programming.
For each position, we have two choices either include it or not include it.
We can fasten the solution using bitmasking by converting the candy combo string to integer.

Pseudocode

int rec(int i, int mask, int N, int K, vector&lt;int&gt;&amp;to_dec, vector&lt;int&gt;&amp;cost) {
if (i == N) {
    if (mask == ((1 &lt;&lt; K) - 1))return 0;
    else return INF;
}
if (dp.find({i, mask}) != dp.end())return dp[ {i, mask}];
int op1 = cost[i] + rec(i + 1, mask | to_dec[i], N, K, to_dec, cost); // first option is to include current string
int op2 = rec(i + 1, mask, N, K, to_dec, cost);          // second option not to include
return dp[ {i, mask}] = min(op1, op2);
}