Join Us
while calculating v, shouldn't we srart from the highest bit, i.e. start our loop from j=31?
Entering edit mode
Minimize Operations
Consider a weighted tree with N nodes and N-1 edges. You have the option to select an edge and adjust its weight by either increasing or decreasing it by 1 in a single operation. There are Q queries given. each consisting of two nodes U and V. Your task Is
to determine the minimum number of operations reguired to make the weight of every edge on the path from node U to node V equal.
Please note that if U and V are identical, no operations need to be performed.
Task
You need to calculate the minimum number of operations neeeded to equalize the weight of each edge on the path from the node U to node V for equal
Example
Assumptions
- N =3
- Edges = [[1,2,3],[1,3,2]]
- Q =1
- Queries =[[2,3]]
Approach
• For the first query increase the weight of the edge from1 to 3 by 1, therefore the weight of all the digest on the path from 2 to 3 would become the same in for 1 operation
Input Format
The first line contains a single integer N.
• Next N-1 lines contain 3 space-separated integers U, V, and
W denoting an edge between the nodes Uand V with weight W
•The next line contains a single integer denoting Q.
•The next Q lines contain 2 space-separated integers U, V
denoting the queried path
Output Format
Print a list of Q space-separated integers where the " integer
denotes the answer to the ith query.
Constraints
- 1 ≤ N ≤ 105
- 1 ≤ Edges[i][0] ≤ N
- 1 ≤ Edges[i][1] ≤ N
- 1 ≤ Edges[i][2] ≤ 26
- 1 ≤ Q ≤ 105
- 1 ≤ Queries[i][0] ≤ N
- 1 ≤ Queries[i][1] ≤ N
Sample Input Sample Output
7 5 3 5
1 2 3
1 3 4
2 4 4
2 5 6
3 6 6
3 7 8
3
Sneakers Shopping
Jordan goes to a shop to buy N shoes. After his purchase, the shopkeeper offers him a crazy refund on his bill. The shopkeeper tells Jordan that he can select any of the 4| shoes and the shopkeeper will refund
the sum of the square of the prices of those shoes. Now, before buying the shoes, Jordan can perform an infinite number of the following operations:
- Select any pair of two shoes
- Let's say their cost is A and B respectively.
- Update the cost of the first shoe as (A OR B)
- Update the cost of the second shoe to (A AND B)
Now, Jordan wonders what is the maximum refund he can get if the number and cost of the shoes are already decided. Help Jordan get the maximum benefit of this craziness.
Since the answer can be too great, output the answer modulo 109 + 7
Task
Print the maximum refund Jordan can get modulo 109 + 7.
Assumptions
N= 4
shoePrice =[1, 2, 3, 4]
Approach
Jordan can perform the following operations to get the maximum refund.
- Perform the operation on the cost of Shoe 3 and Shoe 4.
- The cost of Shoe 3 becomes (3 OR 4)=7 and the cost of Shoe 4 becomes (3 AND 4) = 0.
- Then, Operate on the cost of Shoe 1 and Shoe 2.
- The cost of Shoe / becomes (1 OR 2)= 3, and the cost of Shoe 2 becomes (1 AND 2) = 0.
- Then select Shoe 1 and Shoe 3 and ask for the sum pf squares of their prices as a refund.
- Now, the total refund that Jordan will get equals:
- (cost of Shoe 1)2 + (cost of Shoe 2)2
- = (32 + 72) = (9 + 49) = 58
Input format
- The first line contains an integer representing N, the number of shoes.
- The second line contains N integers denoting the cost of those N shoes.
Output format
In a single line, print the maximum refund Jordan can get.
Constraints
- 1 ≤ N ≤ 105
- 1 ≤ shoe [Pricelil ] ≤ 109
Sample Input Sample Output
5 98
3 6 7 5 3 Special Subarrays
You are given an array Arr of size N consisting of non negative integers. Find the number of subartays of Arr, which are Special
A subarray is called Special if it satisfies the following condition:
- The product of the maximum element and the minimum element of the subarray is divisible by the length of the subarray
Find the number of Special subarrays of the array Arr.
Input format :
• The first line contains 7, which represents the number of test
cases.
• For each test case:
• The first line consists of a single integer N, denoting
the size of the array Arr.
• The next line contains N space-separated integers,
denoting the elements of Arr.
Output format: For each test case, print the answer in a new line
Constraints
- 1≤ T < 10
- 1≤ N ≤5*104
- 0 ≤ Arr[i] ≤ 30
Sample Input Sample Output
2 2
2 5
1 5
3
0 1 3Explanation
The first line denotes T = 2
The first test case
Give
- N = 2
- Arr = [1,5]
Approach
There are two subarrays which are special [1] and [5]
Thus answer = 2
The second Test case
Given
- N = 3
- Arr = [0,1,3]
pproach
The valid subarrays ore
• [0). [1], [3],
[0, 1]
[0 ,1 ,3]
Thus, the answer 5
Your code must be able to print the sample output from the provided sample input. However, your code is run against muitiple hidden test cases. Therefore, your code must pass these hidden test cases to solve the problem statement
.
Entering edit mode
Special Subarray
Ample of ways to solve this problem, but all the solutions leverage the same observation: All elements are less than 30. (from constraints).
Bruteforce Solution
First lets take a look at bruteforce solution, which computes number of special subarrays starting at ith index. We compute this for all possible values of i, that is [0, N) and sum of these gives us total number of special subarrays.
for (int i = 0; i < N; ++i) {
int curMin = i, curMax = i; //points to index with min & max values
for (int j = i; j < N; ++j) {
int product = A[curMin] * A[curMax];
if (product % (j-i+1) == 0) ans++;
if (A[curMin] > A[i]) A[curMin] = A[i]; //update current Min & Max
if (A[curMax] > A[i]) A[curMax] = A[i];
}
}
cout << ans;First for loop fixes left index of subarray and second loop iterates over all possible right-index of subarray. But do we really need to iterate over all possible right-indices of subarray? No, it turns out there are only atmost 30 interesting right-indices of subarray where the product actually changes!
Optimal Solution
Lets fix left-index of subarray at i. Now to compute number of special subarrays which have left-index as i, we only need to evaluate interesting right-indices. We define interesting right-indices as potential right-indices of subarray where the product changes. Where will the product change? When jth index has a value more than current maximum or has a value lower than current minimum. This can happen only 30 times atmax since value of each element is between 0 to 30!
How can we compute the next interesting right-index? Simple we can precompute next greater element and next smaller element (it is standard problem using stack) for all elements. We start with first possible right-index, which is i itself. And then from there we find which occurs first, we find a value smaller than current smallest number or we find a value greater than current largest number seen so far. (If you are confused, try solving for simpler version: find number of subarrays which have their max number divisible by subarray length). Between current interesting right-index and next interesting right-index, value of product remains same.
So now all we need to find is how many numbers in range [current interesting number, next interesting number) actually divide the current product? We can solve this subpart, by precomputing factors of all numbers till 30*30 and then checking for the given product, which factors actually lie in range [current interesting number, next interesting number). Since they are factors, only these lengths will divide the product. This can be done using binary search or simple linear scan too (since max number of factors of any number till 900 is less than 4.)
Thus, this solves our problem in O(N * 30).
#include <bits/stdc++.h>
using namespace std;
int specialArrays(vector<int> &A) {
int n = A.size(), ans = 0, mini, maxi, curInteresting;
//precompute factors of numbers till 30 * 30
vector<int> factors[901];
for (int num = 1; num < 901; ++num) {
for (int i = 1; i * i <= num; ++i) {
if (num % i == 0) {
factors[num].push_back(i);
if (i * i != num) factors[num].push_back(num/i);
}
}
sort(factors[num].begin(), factors[num].end());
}
//precompute next greater element
vector<int> nextGreater(n, n), nextSmaller(n, n);
stack<int> S;
for (int i = 0; i < n; ++i) {
while (!S.empty() and A[S.top()] < A[i]) {
nextGreater[S.top()] = i;
S.pop();
}
S.push(i);
}
while (!S.empty()) S.pop();
//precompute next smaller element
for (int i = 0; i < n; ++i) {
while (!S.empty() and A[S.top()] > A[i]) {
nextSmaller[S.top()] = i;
S.pop();
}
S.push(i);
}
//<debug printing helper functions
//for (int num = 1; num <= 10; ++num) {
//cout << num << ": ";
//for (auto divisor: factors[num]) cout << divisor << ", ";
//cout << endl;
//}
//for (int i = 0; i < n; ++i) cout << A[i] << ", "; cout << endl;
//for (int i = 0; i < n; ++i) cout << nextGreater[i] << ", "; cout << endl;
//for (int i = 0; i < n; ++i) cout << nextSmaller[i] << ", "; cout << endl;
///debug>
//compute answer
for (int i = 0; i < n; ++i) {
mini = maxi = curInteresting = i;
while (mini < n and maxi < n) {
int product = A[mini] * A[maxi];
int nextInteresting = min(nextSmaller[mini], nextGreater[maxi]);
if (product == 0) { //product is 0 implies all of right-indices in current range will contribute to number of special subarrays since any length will divide 0
ans += (nextInteresting - curInteresting);
} else {
ans += distance(lower_bound(factors[product].begin(), factors[product].end(), curInteresting - i + 1),
upper_bound(factors[product].begin(), factors[product].end(), nextInteresting - i)); //find length of subarray in range [curInteresting-i+1, nextInteresting-i) which divides current product
}
if (nextSmaller[mini] < nextGreater[maxi]) mini = nextSmaller[mini]; else maxi = nextGreater[maxi];
curInteresting = nextInteresting;
}
}
return ans;
}
int main() {
vector<int> A = {1, 3, 2, 5};
cout << specialArrays(A); // ans should be 7: {4 single size subarray, {3,2}, {2,5}, {1,3,2}}
return 0;
}Let me know if something isn't clear.
Entering edit mode
Sneakers Shopping:
Here is a probable working code: https://ideone.com/pkhoRk
Entering edit mode
Minimize Operations:
Here is a probable working code: https://ideone.com/X2rjq1
Loading Similar Posts
Can you share the solution for special subarrays.
Sure, I have written my solution for special subarrays below.