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

Question 3

Candy Shop

1
Entering edit mode

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;
}
``````
0
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
``````
0
Entering edit mode

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;
}
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);
}
``````

Complexity

Time Complexity: `O(N*K), N` is the number of types of candy combos and K is the different flavors of candles.

Entering edit mode
0

Is it possibe to solve it through iteration without recursion??