**Dominoes(insert atmost k numbers and make maximum length of continuous number )

Dominoes

There are N dominoes arranged in a straight line. For each domino you know its coordinate, an integer value. It is guaranteed all the coordinates are distinct. You have another set of K dominoes. You should place these dominoes at integer coordinates in a way that will preserve the property that all the coordinates are distinct. You want to maximize the size of a subset of dominoes that are placed at consecutive coordinates.

Standard input

The first line contains two integer values N and K.

The second line contains N integer values, the coordinates of the initial dominoes.

Standard output

The output should contains a single value representing the size of the maximum subset of dominoes that can have consecutive coordinates.

Constraints and notes

• 1 ≤ N ≤ 100 000
• 1 ≤ K ≤ 100 000
• The coordinates of the dominoes are between 1 and 1 000 000

Input	Output	Explanation
8 4 1 2 3 4 10 11 14 15	8	It is optimal to place the dominoes at coordinates 12, 13, 16 and 17.

===========================EDITORIAL==================================

I DID THIS PROBLEM WITH SIMPLE SLIDING CONCEPT ..

FIRST OF ALL SORT THE NUMBERS , THAN  FIRST CALCULATE MAXIMUM  LENGTH IF START FORM THE FIRST NUMBER , NOW ONE OBSERVATION IS THAT IF WE START FORM INDEX 0 ANT WE CAN MAKE A CONTINUOUS NUMBER TILL INDEX 3( IN K OPERATIONS) THAN IF WE START FORM INDEX 1 THAN AT LEAST WE WILL REACH TILL INDEX 3 ( IN K OPERATIONS)..

   WITH THE HELP OF THIS PROPERTY WE CAN SOLVE THIS PROBLEM USING SLIDING WINDOW..

=============================CODE====================================

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

#define ff first

#define ss second

#define mp make_pair

#define ph push_back

#define mod 1000000007

#define debug 0

vector<int>v[100010];

int main()

 {

 

  int n,kk;

   cin>>n>>kk;

   int last=0;

    int count=0;

   for(int i=0;i<n;i++)

     {

      int a;

       cin>>a;

          v[0].push_back(a);

   }

   int ans=0;

   sort(v[0].begin(),v[0].end());

  

     int k=0;

           int size=v[k].size();

            int l=0;

           int re=kk;

      for(int i=0;i<size;i++)

       {

        if(i!=0)

            {

           re+=v[k][i]-v[k][i-1]-1;

}

if(l<i)

                 {

              l=i;

              re=kk;

         }

         while(re>=0)

          {

          

            if(l+1==size)

             {

               ans=max(ans,v[k][l]+re-v[k][i]+1);

               re=0;

               break;

 }

          else if(re>=v[k][l+1]-v[k][l]-1)

           {

             re-=v[k][l+1]-v[k][l]-1;

             l+=1;

   }

   else

   {

     ans=max(ans,v[k][l]-v[k][i]+1+re);

     break;

   }

      }

}

cout<<ans<<endl;

 }

======================ANOTHER APPROACH ============================

WE CAN ALSO SOLVE THIS PROBLEM USING BINARY SEARCH 

SEE THE CODE 

#include<bits/stdc++.h>

using namespace std;

/*      my general mistakes that costed me a lot

          * check for overflows

          * check and mod and use int type variables where possible to avoid tles

          * while multiplying two variables whose value can exceed integer 

          limt make sure to typecase them

          * use scanf when you are not working with the best possible optimisation

          * return a value from a function that has a return type sometimes the 

          compiler may give the correct answer but there will be problem in the judge

          * be very cautious about uninitiaalised variables , infact never keep them

          or handle them properly*/

#define ff first

#define ss second

#define mp make_pair

#define pb push_back

#define ll long long int

#define pp pair<int,int> 

#define ve vector

#define mod 1000000007

/************************************CODE BEGINS HERE************************/

int h[2000010];

int main()

{

   

 int n;

 cin>>n;

 int k;

 cin>>k;

 int mx=0;

 for(int i=0;i<n;i++)

 {

  int aa;

     cin>>aa;

     mx=max(mx,aa+k);

     h[aa]++;

 }

 for(int i=1;i<=mx;i++)

 {

  h[i]+=h[i-1];

 }

 int res=0;

 for(int i=1;i<=mx;i++)

 {

            int low=1;

            int high=i;

            int ans=0;

            bool f=0;

            while(low<=high)

            {

                 if(low==high)

f=1;

int mid=(low+high)/2;

int len=i-mid+1;

int req=len-(h[i]-h[mid-1]);

// if(i==10)

// {

//   cout<<"mid "<<mid<<" "<<req<<endl;

// }

if(req<=k)

{

ans=(i-mid+1);

high=mid;

}

else low=mid+1;

if(f)

break;

  }

//   cout<<"for "<<i<<" "<<ans<<endl;

  res=max(ans,res);

 }

 cout<<res<<endl;

 return 0;

}

*****D. Robin Hood( find max - min in the array after k operations , in each step add 1 at some index and subtract from some index )( 2 binary search )

D. Robin Hood

We all know the impressive story of Robin Hood. Robin Hood uses his archery skills and his wits to steal the money from rich, and return it to the poor.

There are n citizens in Kekoland, each person has ci coins. Each day, Robin Hood will take exactly 1 coin from the richest person in the city and he will give it to the poorest person (poorest person right after taking richest's 1 coin). In case the choice is not unique, he will select one among them at random. Sadly, Robin Hood is old and want to retire in k days. He decided to spend these last days with helping poor people.

After taking his money are taken by Robin Hood richest person may become poorest person as well, and it might even happen that Robin Hood will give his money back. For example if all people have same number of coins, then next day they will have same number of coins too.

Your task is to find the difference between richest and poorest persons wealth after k days. Note that the choosing at random among richest and poorest doesn't affect the answer.

Input

The first line of the input contains two integers n and k (1 ≤ n ≤ 500 000, 0 ≤ k ≤ 109) — the number of citizens in Kekoland and the number of days left till Robin Hood's retirement.

The second line contains n integers, the i-th of them is ci (1 ≤ ci ≤ 109) — initial wealth of the i-th person.

Output

Print a single line containing the difference between richest and poorest peoples wealth.

Examples

input

4 1
1 1 4 2

output

2

input

3 1
2 2 2

output

0

Note

Lets look at how wealth changes through day in the first sample.

1. [1, 1, 4, 2]
2. [2, 1, 3, 2] or [1, 2, 3, 2]

So the answer is 3 - 1 = 2

In second sample wealth will remain the same for each person.

===================EDITORIAL=================

We observe that we can apply operations separately this means first we will apply all increase operations, and after will apply all decrease operations, vice versa. We will use following algorithm.

We have to apply following operation k times, add one to minimum number in array. We will simply binary search over minimum value after applying k operation. Let's look how to check if minimum will be great or equal to p. If  is less or equal to kthen we can increase all elements to at least p. In this way we can find what will be minimum value after k operations.

Let's say this minimum value to m. After we find it we will increase all numbers less than m to m. But there may be some operations we still didn't apply yet, this number can be at most n - 1, otherwise minimum would be greater than m because we can increase all numbers equal to m by one with this number of increases. Since minimum has to be same we just have to increase some elements in our array that equal to m.

We will use same algorithm for decreasing operations. Finally we will print max element — min element in final array. Overall complexity will be O(nlogk).

 CORRECTNESS PROOF 

 this is quit simple to prove that  both increase operations ans decrease operations can be done separately , since we have K operations , we can use these all these k operation ( while decreasing ) on any element without thinking about which element will be added with this  value , since which ever element will be added with this value will remain less than the mid( value in the b search )   , 

similarly for the  increase operation we can operate without taking care about of number which will decrease ...

=========================CODE===========================================

#include<bits/stdc++.h>

using namespace std;

typedef long long  int lli;

int arr[1000000];

int maxi;

int mini;

 int n,k;

 void set_min()

  {

  mini=arr[0];

  //  cout<<" initial min"<<mini<<endl;

  int lo=mini;

  int hi=maxi;

   int f=0;

   while(lo<=hi)

    {

    if(lo==hi)

    {

    f=1;

}

 int mid=(lo+hi)/2;

 lli ext=0;

 lli less=0;

 for(int i=0;i<n;i++)

        {

         if(arr[i]>mid)

          {

           ext+=arr[i]-mid;

}

else

{

less+=mid-arr[i];

}

}

 

if(less<=k && less<=ext)

 {

  lo=mid+1;

  mini=mid;

 }

 else

 {

  hi=mid;

 }  

 

 

 

 if(f==1) break;

}

//  cout<<" final min "<<mini<<endl;

  }

  

  void set_max()

  {

  maxi=arr[n-1];

   //cout<<" initial max "<<maxi<<endl;

  int lo=0;

  int hi=maxi;

   int f=0;

  while(lo<=hi)

    {

    if(lo==hi)

    {

    f=1;

}

 int mid=(lo+hi)/2;

 lli ext=0;

 lli less=0;

 for(int i=0;i<n;i++)

        {

         if(arr[i]>mid)

          {

           ext+=arr[i]-mid;

}

else

{

less+=mid-arr[i];

}

}

 

//  cout<<" mid "<<mid<<" "<<ext<<" "<<less<<endl;

if(ext<=k && less>=ext)

 {

 

   maxi=mid;

   hi=mid;

 }

 else

 {

  lo=mid+1; 

 }  

 

 

 

 if(f==1) break;

}

 //cout<<" final max "<<maxi<<endl;

  }

int main()

 {

 

   cin>>n>>k;

   

    for(int i=0;i<n;i++)

     {

    scanf("%d",&arr[i]);

}

sort(arr,arr+n);

set_max();

set_min();

cout<<maxi-mini<<endl;

 } 

**Tile Painting: Revisited!

Tile Painting: Revisited!

Nikita just came up with a new array game. The rules are as follows:

• Initially, there is an array, A$A$, containing N$N$ integers.
• In each move, Nikita must partition the array into 2$2$ non-empty parts such that the sum of the elements in the left partition is equal to the sum of the elements in the right partition. If Nikita can make such a move, she gets 1$1$ point; otherwise, the game ends.
• After each successful move, Nikita discards either the left partition or the right partition and continues playing by using the remaining partition as array A$A$.

Nikita loves this game and wants your help getting the best score possible. Given A$A$, can you find and print the maximum number of points she can score?

Input Format

The first line contains an integer, T$T$, denoting the number of test cases. Each test case is described over 2$2$lines in the following format:

1. A line containing a single integer, N$N$, denoting the size of array A$A$.
2. A line of N$N$ space-separated integers describing the elements in array A$A$.

Constraints

• 1≤T≤10$1\le T\le 10$
• 1≤N≤214$1\le N\le 2^{14}$
• 0≤Ai≤109$0\le A_i\le {10}^9$

Scoring

• 1≤N≤28$1\le N\le 2^8$ for 30%$30\mathrm{\%}$ of the test data
• 1≤N≤211$1\le N\le 2^{11}$ for 60%$60\mathrm{\%}$ of the test data
• 1≤N≤214$1\le N\le 2^{14}$ for 100%$100\mathrm{\%}$ of the test data

Output Format

For each test case, print Nikita's maximum possible score on a new line.

Sample Input

3
3
3 3 3
4
2 2 2 2
7
4 1 0 1 1 0 1

Sample Output

0
2
3

Explanation

Test Case 0:

Nikita cannot partition A$A$ into 2$2$ parts having equal sums. Therefore, her maximum possible score is 0$0$and we print 0$0$ on a new line.

Test Case 1:

Initially, A$A$ looks like this:

She splits the array into 2$2$ partitions having equal sums, and then discards the left partition:

She then splits the new array into 2$2$ partitions having equal sums, and then discards the left partition:

At this point the array only has 1$1$ element and can no longer be partitioned, so the game ends. Because Nikita successfully split the array twice, she gets 2$2$ points and we print 2$2$ on a new line.

------------------------------------------------EDITORIAL------------------------------------------

Solution

This problem can be solved using straightforward dynamic programming. Let's maintain a DP[N][N]table where an entry DP[L][R] denotes the maximum points we can score by playing the game on a subarray from L to R.

We can fill up the DP table in O(N3)$O(N^3)$ using following recursive recurrence:

• DPL,R=max(DPL,R,max(DPL,X,DPX+1,R)+1)$D{P}_{L,R}=max(D{P}_{L,R},max(D{P}_{L,X},D{P}_{X+1,R})+1)$ if ∑L≤i≤XAi=∑X<i≤RAi$\sum _{\begin{array}{c}L\le i\le X\end{array}}{A}_i=\sum _{\begin{array}{c}X<i\le R\end{array}}{A}_i$
• DPL,R=0$D{P}_{L,R}=0$ if there is no such X$X$.

C++ Code:
Language : C++

const int maxn = 2048 + 10;
int dp[ maxn ][ maxn ], n;
long long int A[ maxn ];

long long int sum(int l, int r) {
    return A[r] - A[l-1];
}

int solve(int l, int r) {
    int &ret = dp[l][r];
    if( ret != -1 ) return ret;
    ret = 0;
    for(int x=l; x<r; x++) {
        if(sum(l, x) == sum(x+1, r)) // valid x
            ret = max(ret, max(solve(l, x), solve(x+1, r)) + 1);
    }
    return ret;
}

int main() {
    int t; cin >> t;
    while( t-- ) {
        int n; cin >> n;
        for(int i=1; i<=n; i++) {
            cin >> A[i];
            A[i] += A[i-1];
        }
        memset(dp, -1, sizeof dp);
        cout << solve(1, n) << "\n";
    }
    return 0;
}

Careful observation reduces the complexity to O(N2)$O(N^2)$. It should be noted that maximum points for a subarray can be calculated by considering only the first valid X$X$ for a subarray (rather than by considering all valid X$X$).

Steps Involved:

• Find first valid X$X$ for all subarrays.
• Populate DP as shown above but by considering only first valid X$X$.

C++ code:

Language : C++

const int maxn = 2048 + 10;
int n; 
long long int A[ maxn ];
int L[ maxn ][ maxn ], dp[ maxn ][ maxn ];

int solve(int l, int r) {
    if( l > r ) return 0;
    if( L[l][r] == -1 ) return 0;
    int &ret = dp[l][r];
    if( ret != -1 ) return ret;
    ret = 0;
    ret = max(ret, max(solve(l, L[l][r]), solve(L[l][r]+1, r)) + 1);
    return ret;  
}

int main() {
    int t; cin >> t;
    while( t-- ) {
        int n; cin >> n;
        for(int i=1; i<=n; i++) {
            cin >> A[i];
            A[i] += A[i-1];
        }

        for(int i=1; i<=n; i++) {
            for(int j=i; j<=n; j++) {
                L[i][j] = -1; // to store first valid X
                dp[i][j] = -1; // to store maximum points
            }
        }

        // finding first valid X for each subarray
        for(int i=1; i<=n; i++) {
            long long int s = 0;
            int l = i;
            for(int j=i; j<=n; j++) {
                s += A[j] - A[j-1];
                if( s % 2 == 0 ) {
                    s /= 2;
                    while( l < j && A[l]-A[i-1] < s) l++;
                    if( l < j && A[l]-A[i-1] == s ) L[i][j] = l;
                    s *= 2;
                }
            }
        }
        cout << solve(1, n) << "\n";
    }
    return 0;
}

We can optimize the above solution to work in O(Nlog(N))$O(Nlog(N))$ using binary search. Find the first valid X$X$in the range [L,R]$[L,R]$ using binary search, then divide the range into 2$2$ parts (i.e.: [L,X] & [X+1,R]$[L,X]\mathrm{\&}[X+1,R]$), compute the answer for both parts recursively and then take the maximum answer from both parts to compute the answer of range [L,R]$[L,R]$. This can be implemented as follows:

C ++ Code:

long long a[100010];

ll sum(int l, int r) {
    return a[r] - a[l-1];
}

// binary search to find first valid X
// within subarray [l, r]
int get(int l, int r, ll s) {
    int low, high, mid;
    low = l;
    high = r;
    while( low <= high ) {
        mid = ( low + high ) / 2;
        ll x = sum(l, mid);
        if( x == s && (mid == l || sum(l, mid-1) != s )) {
            return mid;
        } else if( x >= s ) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

int solve(int l,int r){
    ll s = sum(l, r);
    if( l != r && s % 2 == 0 ) {
        int ind = get(l, r, s/2);
        if( ind != -1 ) {
            // compute maximum from 2 parts 
            return max(solve(l, ind), solve(ind+1, r)) + 1;
        }
    }
    return 0;
}

int main() {
    int t;
    cin>>t;
    while (t--){
        int n;
        cin>>n;
        assert(n <= 16384);
        for (int i=1;i<=n;i++) {
            cin>>a[i];
            a[i]+=a[i-1];
        }
        cout<<solve(1,n)<<endl;
    }
    return 0;
}

/ MY CODE

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
  int n;
lli arr[162390];
int solve(int l,int r,lli ms)
 {
          if(l>=r) return 0;
          if(r>=n) return 0;
         int  ci=l;
         lli cs=0;
         int f=1;
         while((cs<ms/2 || f==1) && ci<=r)
             {
               
                f=0;
                   cs+=arr[ci];
                   ci++;
                
    }
    if(cs==ms/2  && ms%2!=1)
     {
      return max(solve(l,ci-1,ms/2),solve(ci,r,ms/2))+1;
     }
     else return 0;
    
 }
int main()
{
  
//  freopen("abc.txt","r",stdin);
//  freopen("pqr.txt","w",stdout);
  int t;
   cin>>t;
   while(t--)
   {
      //cout<<"bacl";
    scanf("%d",&n);
      lli sum=0;
      for(int i=0;i<n;i++)
         {
          scanf("%lld",&arr[i]);
         sum+=arr[i];
    }
    if(sum%2==1)
    {
       cout<<0<<endl;
    }
    else
    cout<<solve(0,n-1,sum)<<endl;
    
   }
}

 Set by ma5termind

Problem Setter's code :

#include <bits/stdc++.h>
using namespace std;

#define ll long long int

long long a[100010];

ll sum(int l, int r) {
    return a[r] - a[l-1];
}

int get(int l, int r, ll s) {
    int low, high, mid;
    low = l;
    high = r;
    while( low <= high ) {
        mid = ( low + high ) / 2;
        ll x = sum(l, mid);
        if( x == s && (mid == l || sum(l, mid-1) != s )) {
            return mid;
        } else if( x >= s ) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

int solve(int l,int r){
    ll s = sum(l, r);
    if( l != r && s % 2 == 0 ) {
        int ind = get(l, r, s/2);
        if( ind != -1 ) {
            return max(solve(l, ind), solve(ind+1, r)) + 1;
        }
    }
    return 0;
}

int main() {
    int t;
    cin>>t;
    while (t--){
        int n;
        cin>>n;
        assert(n <= 16384);
        for (int i=1;i<=n;i++) {
            cin>>a[i];
            a[i]+=a[i-1];
        }
        cout<<solve(1,n)<<endl;
    }
    return 0;
}

 Tested by nikasvanidze

Problem Tester's code :

//O(N*ANS)
#include <bits/stdc++.h>
using namespace std;
long long a[1000000];

int sol(int l,int r){
    for (int x=l;x<r;x++)
    if (a[x]*2==a[r]+a[l-1]) return max(sol(l,x),sol(x+1,r))+1;
    return 0;
}

int main() {
    int t;
    cin>>t;
    assert(t<=10);
    while (t--){
        int n;
        cin>>n;
        assert(n<=16384);
        for (int i=1;i<=n;i++) {
            cin>>a[i];
            assert(a[i]<=1000000000ll);
            a[i]+=a[i-1];
        }
        cout<<sol(1,n)<<endl;
    }
    return 0;
}