Given an array of n elements. ‘k’ operations need to be performed on the array.

For each operation start_index, end_index,trim_value is given. One has to trim the value starting from the start_index to end_index inclusive.

If the value at that index is more than or equal to trim value then make it equal to trim_value else leave it as it is. for each A[i] for i between start and end , A[i] = min(A[i],h) .

After performing, ‘k’ such operations find the maximum value of the array.

I have a solution of O(n + k*log(n)). I think it can be optimized to O( n*log(n) ) at least, if not better.

Note: Please try not to use Segment tree or BIT.

Constraints -> n<=10^6 (sure) , A[i] <= 10^6 (Not quite sure of this though)

For Eg. Given array = 7, 2, 8, 5, 1, 6, 4 and k = 3

Following are the k operation (start, end, value) -

1 3 4 => Now the array = 4, 2, 4, 5, 1, 6, 4

3 5 5 => Now the array = 4, 2, 4, 5, 1, 6, 4

4 7 4 => Now the array = 4, 2, 4, 4, 1, 4, 4

So the Maximum value is 4 in the array.

You will be given a stream of integers to process, We have to design a data structure which supports Operations like Insertion and Deletion and should work in O(log(n)) time.

And Also we have to find the (MIN GAP) minimum absolute difference between any two integers processed before in O(1) i.e constant time.

We have to design a data structure that supports the above operations.

For Eg. If we have the data 2, 5, 7, 8, Here min gap is 1 (8-7).

But After deletion of 8, the data becomes — 2, 5, 7 and now the Min gap is 2 (7-5) .

And After deletion of 5, the data becomes 2, 7 and now Min Gap is 5.

Note For deletion will be given a key as a parameter, We have to find that key value if present and delete it.

Given a binary tree,

We have to remove a single edge and partition the tree into two new trees such that difference of their diameters remains less than a given constant k.

Please suggest me an approach of O(n) time complexity.

There are n nodes(1,2.. n) in a weighted graph with m (m>n) bi-directional edges.

All weights are positive and there are no multiple edges.

There is one fixed origin(Node 1). We will always start traveling from the origin.

Now we have to find the number of ways to reach each of the nodes(starting from the origin) with minimum cost.(All paths counted should have the minimum cost to reach that node).

Expected complexity O(m*log(m)).

Input — First line contains n , m .

Next m lines contain u,v,w. => There is an edge between u and v of weight w(w>0).

Output — Print n-1 lines one for each node other than origin, containing the number of ways to reach each of the nodes(starting from the origin) with minimum cost.

Sample Test -

4 5

1 2 5

1 3 3

3 2 2

3 4 7

2 4 5

Output —

2

1

3

Here is my solution, Please check if this will work for all cases, I did modified Dijkstra + DP.

#include <bits/stdc++.h>
using namespace std;
 
#define N 5001
#define fi first
#define se second
#define MOD 1000000007
 
#define pb push_back
 
#define ll long long
 
#define eps 1.0e-9
#define inf 1e9 + 5
#define double long double
 
#define pp pair<int,int>

vector< pp > adj[N];
int dis[N],dp[N];

int main()
{
  ios::sync_with_stdio(0);
  int i,j,k,m,n,t;
  cin>>n>>m;
  for(i=0;i<m;i++)
  {
    int u,v,w;
    cin>>u>>v>>w;
    //u--;v--;
    adj[u].pb({w,v});
    adj[v].pb({w,v});
  }
  priority_queue< pp , vector<pp > , greater<pp> > pq;
  for(int i=0;i<=n;i++) dis[i] = INT_MAX;
  dis[1] = 0;
  dp[1] = 1;
  pq.push({0,1});

  while(!pq.empty())
  {
    pp tp = pq.top();
    int u = tp.se;
    int d = tp.fi;
    pq.pop();
    if(dis[u]<d) continue;

    for(i=0;i<adj[u].size();i++)
    {
      int v = adj[u][i].se;
      int w = adj[u][i].fi;
      if(d + w <= dis[v] )
      {
        if(dis[v]==d+w) dp[v] += dp[u];

        if(d + w < dis[v])
        {
          dis[v] = d + w;  
          dp[v] = dp[u];
          pq.push({dis[v],v}); 
        }
      }
    }
  }
  
  cout<<endl;

  for(int i = 1;i<=n;i++)
  {
    cout<<i<<" dis = "<<dis[i]<<" ways = "<<dp[i]<<endl;
  }
return 0;
}

We are given the results of a tennis match between two players A and B as a string.

For eg- "ababbabaa", Here If the ith character is 'a' then it represents that the ith game is won by Player A.

A set is a positive integer.

The Player who is first to win (set value e.g 1,2,3,4... ) games will win the set.

We have to find out all valid sets that are possible for the string and output the outcome of the match (The one who wins more sets wins the match).

For eg If Set size = 3 , ababb | abaa , Resuts in a draw.

If Set size = 2 , aba | bb | aba | a , Which is not a valid Match so set = 2 is not possible.

If Set Size = 6 |ababbabaa| , Won by Player A

We are given n ranges `(L1,R1) , (L2,R2) , ... .. (Ln,Rn)'
All ranges are integer values between (0 to 10^6). We have to find out the total number of unique integers across all the ranges?

Ex. For n = 3, (1,4) , (2,3) , (4,5) the answer is 5.

My solution is to sort the ranges according to their L value and then iterate one by one using two pointers. Time Complexity O(n*Log(n)).

Is there any better solution than this(may be using Hash Maps)?

I am stuck in this problem for past few days, need some help. We are given an array with input size(1, 2000) which consists of digits(0-9) only.

We are given a set of pair of digits (N,M) = {(N1,M1), (N2,M2), (N3,M3), (N4,M4)} containing exactly 4 elements.

In pair (N, M), N denotes the digit and M corresponds to the minimum need of the number in the array.

Output is an array that has a minimum count of each element of N. We need to make some changes in original array to get the output such that cost is minimized.

Let C(x, y) be cost of changing number x to number y, then C(x, y) = |x-y|. Our task is to minimize the total cost of changes.

Input Format
First line: Consists of the array
Four lines continue each containing pair (Nx, Mx) where xE{1, 2, 3, 4}

Output Format
Total cost of changes.

Example 1: If an array is {1, 2, 3, 4, 5} and N values of pair (N, M) are 2, 3, 4, 5. Now lets consider that minimum one 2, zero 3, two 4 and zero 5 are needed in array, the input will be like:

1 2 3 4 5
2 1
3 0
4 2
5 0

Output:
1

Explanation
We change 5 to 4 and cost becomes |5-4| and we get Output array {1, 2, 3, 4, 4}

Example 2:

1 1 1 5 3 7 7 7 8 9 6 5 4 1 2
1 1
3 5
5 0
8 2

Explanation
This means that minimum one 1 , five 3's, zero 5's and two 8's should be present in array.

We change 2 to 3, 4 to 3, two 5 to 3. Cost for this change is 6. Then we change 9 to 8 and cost becomes 7. This is the minimal cost and we get magic array {1, 1, 1, 3, 3, 7, 7, 7, 8, 8, 6, 5, 3, 1, 3}

My Approach
My approach to this problem was a greedy approach in which I checked the closest digit to the given digit of N and then changed that digit. This approach wont work every time. Sometime it would be better to use a digit other than the closest digit to find minimum cost as this closest digit can be used by other digit of set N for replacement to obtain a better cost.

Example for which Approach Fail

1 1 2 3 4 4 4 7 9 10
3 4
7 3
9 1
10 1

Explanation:
In this case if we use greedy approach then, for 3 we will change 2 and two 4s to 3 which is wrong as this step will increase total cost.

Minimum cost for this solution is when array changes to 1 3 3 3 3 7 7 7 9 10 ans output becomes 10 which by using greedy-approach comes out to be 12.