7.4 KiB
Miscelleneous Problems 14
Valuable Nodes
Problem Statement
Given a tree T containing N nodes numbered [1,2, ..., N] rooted at node 1. Each node has a value associated with it. You need to choose some of the nodes from the tree such that the sum of values of the chosen nodes is maximum possible. Moreover, if you have chosen a node V you cannot choose any of its children or grand children. In simple words, you have to choose a subset of nodes such that no two nodes in the chosen set have a parent-child relation or grandfather-grandchild relation between them.
Constraints: 1 <= N <= 500,000 1 <= value of node <= 10,000
Input:
vector<int> A : A[i] --> Parent of node number i+1.
(A[2] = 1 means parent of node number 3 is 1).
vector<int> B : value[i] --> value associated with
node number i+1.
Note: Parent of node number 1 is 0 (A[0] = 0).
Output:
A number containing the maximum possible sum.
(As the answer can be large, output the answer modulo 1000000007)
Example:
Input:
A : [0, 1, 1, 1, 3, 3, 6, 6]
B: [1, 2, 3, 4, 5, 100, 7, 8]
Output:
111
Node number 2, 4, 5 and 6 are chosen. Sum = 2 + 4 + 5 + 100 = 111
Brute Force
- The absolute brute force would be to take every subset.
- Check if it contains a child-parent or grandchild-grandparent relationship.
- Maximize the sum of values among these subsets.
Hints
- Can we optimize the above brute force?
- We can select the node only if its child and grandchild are not selected.
- Can we reduce this problem to an array problem? That array problem will look as follows:
- You are given an array. There is a value stored at every cell. You need to find a subset with highest value sum. If you include A[i] into the set, you cannot include A[i-2], A[i-1], A[i+1], and A[i+2] into the set.
- The above problem can be solved using Dynamic Programming.
- We can store, for all index i, the maximum value of a valid subset of A[0..i].
dp[i] = max(dp[i-3]+A[i], dp[i-1])
- We just look at
dp[i-3]
anddp[i-1]
asdp[i-2]
is already included indp[i-1]
.
- Can we apply a similar approach to our tree problem?
Code
#define ll long long int
int mod = 1000000007;
int getMaxDP(int node, vector<vector<int>> &child, vector<vector<int>> &ggchild, vector<int> &dp, vector<int> &value){
if(dp[node] != -1) return dp[node];
int first = 0, second = 0;
first = value[node]%mod;
for(auto ggc: ggchild[node]){
first = (first%mod + getMaxDP(ggc,child,ggchild,dp,value)%mod)%mod;
}
for(auto c: child[node]){
second = (second%mod + getMaxDP(c,child,ggchild,dp,value)%mod)%mod;
}
return max(first, second);
}
int Solution::solve(vector<int> &A, vector<int> &B) {
int n = A.size();
vector<vector<int>> adj(n);
vector<vector<int>> ggchild(n);
vector<int> dp(n,-1);
for(int i = 1; i<n; ++i){
adj[A[i]-1].push_back(i);
}
for(int i = 0; i<n; ++i){
for(auto c: adj[i]){
for(auto gc: adj[c]){
for(auto ggc: adj[gc]){
ggchild[i].push_back(ggc);
}
}
}
}
return getMaxDP(0,adj,ggchild,dp,B);
}
Time Complexity
- Since we are calculating every dp only once the time complexity will be
O(E+V)
. Since it is a tree the time complexity will beO(n)
.
Dry Run
A : [0, 1, 1, 1, 3, 3, 6, 6]
B: [1, 2, 3, 4, 5, 100, 7, 8]
Children:
1: 2,3,4
2:
3: 5, 6
4:
5:
6: 7, 8
7:
8:
Great Grand Children
1: 7,8
2:
3:
4:
5:
6:
7:
8:
DP:
1: max(DP(2)+DP(3)+DP(4), B(1)+DP(7)+DP(8))
= max(2+105+4, 1+7+8) = 111
2: B(2) = 2
3: max(DP(5) + DP(6), B(3)) = max(100+5, 3) = 105
4: B(4) = 4
5: B(5) = 5
6: max(DP(7)+DP(8), B(6)) = max(7+8, 100) = 100
7: B(7) = 7
8: B(8) = 8
String Rotation
Problem Statement
Give a string S find lexicographically smallest string possible after circular rotation.
Lexicographically smallest: First string in dictionary order.
Circular rotation: Pushing the last character to the start.
Input Format
Argument 1: Length of the String
Argument 2: Given string
Constraint
0 < |S| <= 5000
Sample Input 1
BCABDADAB
Sample Output 1
ABBCABDAD
Brute Force
- Consider all rotations and minimize over all of them.
Hints
- This is a simple question included to encourage all of you to solve at least one problem.
- So, Go ahead and solve this question.
Code
string Solution::solve(int A, string B) {
string doubleB = B + B;
set<string> s;
for(int i = 0; i < A; ++i){
s.insert(doubleB.substr(i,A));
}
return *s.begin();
}
Time Complexity
- Each string comparision may take
O(n)
time. Here,n
is the length of string. - We have to compare strings
O(n)
times. Thus the total time complexity will beO(n^2)
. - If we use a set, the time complexity will be
O(n^2\log{n})
. This is because insertion in set will takeO(n\log{n})
time.
Ways to Arrange Two Objects
Problem Statement
You are given two types of objects : A and B. There is an infinite supply of both the type of objects . All the objects of type A are identical and same is the case with all the objects of type B.
Given two integers N and L, find the number of ways in which you can arrange the N objects such that you don't have L or more consecutive objects of type A together.
Constraints:
1 < N < 100001
1 < L < 100001
1 < N*L < 100001
Input Format
Input consists on one line containing the value of N and L.
Output Format
Return number of ways modulo 10^9 + 7
Example:
Input:4 2
Output: 8
Explanation:
{B,B,B,B}
{B,B,B,A}
{B,B,A,B}
{B,A,B,B}
{A,B,B,B}
{A,B,A,B}
{A,B,B,A}
{B,A,B,A}
Brute Force
- We can consider all the possible arrangements of A and B.
- For each arrangement, we can check if there are L consicutive A's. We can neglect those arrangements and count others.
- This approach will take
O(n * 2^n)
time.
Hints
- We can neglact some arrangements even before making them if at each i we keep count of consecutive A's ending at i.
- Suppose there are L-1 A's ending at i. For example L = 3 and N = 6 and i = 3
{B, A, A}
now on the next step we can not include A.
- Can we memoize these states in dp?
Solution
- Dp state: dp[i][j] number of arrangements of A and B of length i with j consicutive A's towards the end.
dp[i][0]=\sum_{k\in{[0,L-1]}}dp[i-1][k]
dp[i][j]_{j>0} = dp[i-1][j-1]
Code
int mod = 1000000007;
int Solution::solve(int A, int B) {
vector<vector<int>> dp(A+1, vector<int>(B,0));
dp[0][0] = 1;
for(int i = 1; i <= A; ++i){
for(int j = 0; j< B; ++j){
if(j == 0){
int val = 0;
for(int k = 0; k<B; ++k){
val = (val%mod + dp[i-1][k]%mod)%mod;
}
dp[i][j] = val;
}else{
dp[i][j] = dp[i-1][j-1];
}
}
}
int res = 0;
for(int k=0; k < B; ++k){
res = (res%mod + dp[A][k]%mod)%mod;
}
return res;
}
Time Complexity
- It takes
O(1)
time to calculate most of the dp states. There areO(N)
corresponding todp[i][0]
that will takeO(L)
time. - There are
O(N* L)
dp states. Thus the time complexity will beO(N* L)
.
Dry Run
N = 4, L = 2
j-> | 0 | 1 |
---|---|---|
i = 0 | 1 | 0 |
1 | 1 | 1 |
2 | 2 | 1 |
3 | 3 | 2 |
4 | 5 | 3 |
Answer | 8 |