Join Us
Loading Similar Posts
Entering edit mode
Finding arrays
Given an array S of N elements. We need to find the count of distinct arrays A of N elements that exists such that:
• Ali| < A[i + 1] for all 1 ≤ i < N.
• Sum of digits of A[i] is equal to S[i] for all 1 ≤ i ≤ N.
• 1≤ A[i] ≤ 103
An array A is said to be different from array B if there exists an index I such that All 1 -
Since the count can be very large. Output the answer modulo 109 + 7.
Note: Consider 1-based indexing.
Input format
• First line contains an integer T, denoting the number of test cases
• For each test case:
• First line contains an Integer N.
• Second line contains N space-separated integers, denoting array S.
Output format
For Eachtest case print the required answer in a new line
Constraints
- 1 < T ≤ 5
- 1 < N ≤ 100
- 1 ≤ Si ≤ 30
Sample Input Sample Output
1 10
2
2 1Explanation
Given arrays are possible - 1- [2,10]
2 -[2,100]
3-[2,1000]
4-[11,100]
5-[11,1000]
6-[20,100]
7-[20,1000]
8-[101,1000]
9-[110,1000]
The first line denotes the number of test case, T=1
The first test case
Given
• N=3
• A = [1. 2. 3)
• M = 2
• B = 14. 11
Approach
The hybrid sequence S = [1, 4, 1, 2, 3] gives the maximum value
Sample Input
4
3
10 15 16
6
3 6 10 14 12 17
10
3 9 9 3 11 7 14 15 11 17
9
2 7 3 5 9 13 9 14 11
Sample Output
101776
142727553
303300404
19829619Hybrid maximum
A hybrid sequence is a sequence that can be divided into two disjoint subsequences. Every subsequence is an array.
Given two arrays, A and B, of sizes N and M, respectively. You i also given a hybrid sequence S.The expression (Sigma_1) = 1)'(-N + Mimax(S_1....5_]] - \Sigma_0
- 10-N MiminiS S._J) calculates the difference between the sum of the maximum values and the sum of the minimum values the hybrid sequence S.
Find the maximum of value of this expression for all possible hybrid
sequences.
Notes
Use 1-based indexing.
A subsequence is a sequence obtained by deleting zero or
more numbers (not necessarily consecutive) from the original
sequence without changing the order of the remainingelements
Function description
Complete the function hybridMaximum. This function takes the following 4 parameters and returns the maximum value of the expression that can be obtained:
- N: Represents of the number of elements in A
- A: Represents the elements in A
- M: Represents the number of elements in B
- B: Represents the elements in B
Input format for custom testing
• The first line contains an integer N denoting the
number of elements in A.
• The second line contains N space-separated integers
denoting the elements in A.
• The third line contains an integer M denoting the
number of elements in B.
• The lourth line contains M space-separated integers
denoting the elements in B.
Output format
For each test case, print the maximum value of the expression
that can be obtained, in a new line.
Constraints
- 1 ≤ T ≤ 1000
- 1 ≤ N, M < 1000
- 1 ≤ Ai ≤ 106 V € [1,N]
- 1 ≤ Bi ≤ 106 V € [1, M]
Sample Input Sample Output
1 12
3
1 2 3
2
4 1
Note: Use this input format if you are testing against custom inputor writing code in a language where we don't provide boilerplatecode.
The first line contains 7, which represents the number of test
cases..For each test case:line contains an integer
Median Path
Given a tree of n nodes and n- 1 edges. Each node has a value, which is stored in an array C. G (1 S iS n) denotes the value of node 1.
Find the sum of the medians of all simple paths of odd length starting from node 1,
Notes
• Use 1-based indexing
•The median is the number in the middle of a list of numbers when the numbers
are arranged from smallest to biggest (or biggest to smallest).
• In graph theory, a simple path is a path in a graph that does not go through the
same vertex twice.
• A tree is a graph where any two nodes are connected by exactly one path. This
means that there is no way to get from one node to another by doing through the
same node twice. Trees are also acyclic, which means that there are no loops.
This means that you can't start at any node and end up back at the same node
by following the edges
Function description
Complete the solve function. This function takes the following 3 parameters and returns
an integer:
n. Represents the number of nodes in a tree
C Represents an array denoting the node values
edges: Represents a 20 array of edges
input format for custom testing
Constraints
1<T ≤ 10
1S n ≤ 105
1≤ Ci ≤ 109
Sample Input Sample Output
2 20
5 7
7 6 10 1
1 2
2 3
1 4
2 5
6
1 2 4 3 1 5
1 4
Approach
All paths of odd length and their median are
GCvalue in path from 1 to 1 is (node, - 7) and the median is Z
• C values in path from 1 to 3 are (node, = 7, node, = 6, nodes
9) and their median is 7
• C values in path from 1 to 5 are (node; - 7, nodez * 6, nodes
1) and their median is 6.
Hence to final answvor wa be 7 + 7 + 6 = 20
Prime Path
Given an N‹ N grid G and each cell of the grid contains an integer. In one step you can travel from any cell Gus, to Gns, if abs(ji - jz) + abs(i, - iz) ≤ p at a cost of floor(VGiji.
Here p is the number of unique prime factors of the integer at
Guts
Find the minimum cost to move from the top-left corner cell to the
bottom-right corner cell, no matter how many steps you take.
Notes
• abs(x) means taking the absolute value of a number x or Ix.
•floor(x) represents the largest integer y such that y<x.
• Va represents the square root of x.
• Use 1-based indexing
Function description
Complete the solve function. This function takes the following
2 parameters and returns the minimum cost to reach the bottom-
rigbt comer of the arid.
N: Represents the size of the grid
• G: Represents a double dimension array of size N x
N denoting the grid
Input format for custom testing
Note: Use this input format if you are testing against custom input
or writing code in a language where we don't provide boilerplate
code.
•The first line contains T, which represents the number of test
cases.
• For each test case:
• The first line contains an integer N representing the
size of the grid.
• The next Nines contain N
separated integers denoting the grid.
Output format
For each test case, print the minimum cost required to reach the
bottom-right corner of the grid in a new line
Constraints
- 1 ≤ T ≤ 5
- 1 ≤ N < 103
- 2 ≤ G, ≤ 10°
- 1≤i≤N
- 1≤j≤N
Sample Input Sample Output
2 7
3 5
13 12 15
5 6 9
2 4 8
3
2 3 5
30 4 8
5 2 8Test case 1
Given
• N=3
Grid G is as follows:
Approach
You can follow these steps
1. You start at (1, 1) From (1, 1) we can move to (2. 1) since (2-1)41-1) ≤ 1
(the number of unique prime factors of 13 is 1. The cost of this step
Is 3.
2 From (2. 1) you can move t& (2, 2) since (2-2)+(2-1) < 1 (the number of
unique prime factors of 5 is 1). The cost of this step is 2
3. From (2. 2 we can move to (3, 3) since (3-2)+(3-2) < 2 (the number
of unique prime factors of 6 is 2) The cost of this step is 2.
Thus to move from (1, 1) to (3, 3) you require 3 steps and the minimum
required cost is 7.
Test case 2
Please refer to the example for this test case.
Entering edit mode
Hybrid maximum solution
/*---------JAI HO GURUDEV---------*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define f(i,n) for(ll i=0;i<n;i++)
#define fast cin.tie(0), cout.tie(0), cin.sync_with_stdio(0), cout.sync_with_stdio(0);
#define f1(i,n) for(ll i=n;i>=0;i--)
#define fo(i,a,b) for(ll i=a;i<=b;i++)
#define forr1(i,a,b) for(ll i=a;i>=a;i--)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define sor(vec) sort(vec.begin(),vec.end())
#define asor(ar) sort(ar,ar+ar.size());
#define rsor(vec) sort(vec.rbegin(),vec.rend());
#define dbg(var) cout<<#var<<"="<<var<<" "
#define vl vector<ll>
#define yes cout << "YES"<< endl;
#define no cout << "NO"<< endl;
#define out(n) cout << n << endl;
#define num(n) ll n; cin >> n;
#define mxe(v) *max_element(v.begin(),v.end()) // find max element in vector
#define mne(v) *min_element(v.begin(),v.end()) // find min element in vector
#define pb push_back
#define so(arr,n) sort(arr,arr+n)
const ll MOD = 998244353;
const ll mod= 1000000007;
const ll N = 1e3 + 1;
vector<int>adj[N];
vector<bool>vis(N,false);
int sol(int i,int j,int mx,int mn,vector<int> &a,vector<int> &b,vector<vector<int>> &dp)
{
// cout<<i<<" "<<j<<<" "<<mx<<" "<<mn<<endl;
int n=a.size();
int m=b.size();
if(i==n && j==m)
return 0;
if(dp[i][j]!=-1)
return dp[i][j];
int res=0;
if(i<n)
{
res=max(res,max(mx,a[i])-min(mn,a[i])+sol(i+1,j,max(mx,a[i]),min(mn,a[i]),a,b,dp));
}
if(j<m)
{
res=max(res,max(mx,b[j])-min(mn,b[j])+sol(i,j+1,max(mx,b[j]),min(mn,b[j]),a,b,dp));
}
return dp[i][j]=res;
}
void solve()
{
int n;
cin>>n;
vector<int> a(n);
f(i,n)
cin>>a[i];
int m;
cin>>m;
vector<int> b(m);
f(i,m)
cin>>b[i];
vector<vector<int>> dp(n+1,vector<int>(m+1,-1));
cout<<sol(0,0,INT_MIN,INT_MAX,a,b,dp)<<endl;
}
int32_t main()
{
solve();
}
Entering edit mode
MEDIAN PATH
#include <bits/stdc++.h>
using namespace std;
void dfs(int node, int parent, vector<int> &val, vector<vector<int>> &adj, vector<int> &ans, int &sum, int &len)
{
ans.push_back(val[node]);
len++;
if (len % 2 == 1)
{
sort(ans.begin(), ans.end());
sum += ans[ans.size() / 2];
}
for (auto i : adj[node])
{
if (i == parent)
{
continue;
}
dfs(i, node, val, adj, ans, sum, len);
}
ans.pop_back();
len--;
}
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<int> val(n + 1, 0);
for (int i = 1; i <= n; i++)
{
cin >> val[i];
}
vector<vector<int>> adj(n + 1);
for (int i = 0; i < n - 1; i++)
{
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> ans;
int sum = 0;
int len = 0;
dfs(1, -1, val, adj, ans, sum, len);
cout << sum << endl;
}
return 0;
}
