Entering edit mode

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]** ≤ 10^{3 }

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 10^{9} + 7.

**Note**: Consider 1-based indexing.

• 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.

For Eachtest case print the required answer in a new line

- 1 < T ≤ 5
- 1 < N ≤ 100
- 1 ≤ Si ≤ 30

```
Sample Input Sample Output
1 10
2
2 1
```

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
19829619
```

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

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

• 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.

- 1 ≤ T ≤ 1000
- 1 ≤ N, M < 1000
- 1 ≤ A
_{i}≤ 10^{6}V € [1,N] - 1 ≤ B
_{i}≤ 10^{6}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

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

1<T ≤ 10

1S n ≤ 10^{5}

1≤ Ci ≤ 10^{9}

```
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

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

- 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 8
```

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

Loading Similar Posts