B. Shaass and Bookshelf

B. Shaass and Bookshelf

Shaass has n books. He wants to make a bookshelf for all his books. He wants the bookshelf's dimensions to be as small as possible. The thickness of the i-th book is ti and its pages' width is equal to wi. The thickness of each book is either 1 or 2. All books have the same page heights.

Shaass puts the books on the bookshelf in the following way. First he selects some of the books and put them vertically. Then he puts the rest of the books horizontally above the vertical books. The sum of the widths of the horizontal books must be no more than the total thickness of the vertical books. A sample arrangement of the books is depicted in the figure.

Help Shaass to find the minimum total thickness of the vertical books that we can achieve.

Input

The first line of the input contains an integer n, (1 ≤ n ≤ 100). Each of the next n lines contains two integers ti and wi denoting the thickness and width of the i-th book correspondingly, (1 ≤ ti ≤ 2, 1 ≤ wi ≤ 100).

Output

On the only line of the output print the minimum total thickness of the vertical books that we can achieve.

Sample test(s)

input

5
1 12
1 3
2 15
2 5
2 1

output

5

input

3
1 10
2 1
2 4

output

3

-------------------------------------------------------editorial---------------------------------------------------


dp code but unable to decode decode latter
#include <bits/stdc++.h>
using namespace std;
int w[100],t[100],dp[303];
int main(){
int n,i,j,sum=0;cin>>n;
for(i=0;i<n;++i)
cin>>t[i]>>w[i],sum+=t[i];
for(i=0;i<n;++i)
for(j=sum;j>=t[i]+w[i];--j)
dp[j]= max(dp[j],dp[j-t[i]-w[i]]+t[i]);
cout<<sum-dp[sum]<<endl;
}

-------------------------------------------------gready-----------------------------------------------------------------

As said in the statement, the thickness of each book is either 1 or 2. Think about when we want to arrange v1 books of thickness 1 andv2 books of thickness 2 vertically and arrange all other n - v1 - v2 books horizontally above them to achieve a configuration with total thickness of vertical books equal to v1 + 2v2. Is it possible to find such arrangement? Because the total thickness of vertical books is fixed it's good to calculate the minimum possible total width of horizontal books. As the width of a book doesn't matter in vertical arrangement it's good to use the books with shorter width horizontally and the ones with longer width vertically. So pick out v1 books with longest width among books of thickness 1 and do the same with books of thickness 2. The sum of width of n - v1 - v2 remaining books should be at most v1 + 2v2.

The solution would be to try the things we explained above for all possible values of v1 and v2. And print the best answer. :)

There exists other ways to solve this problem mostly using dynamic programming but this was the intended solution of the problem.

Here is a nice implementation in C++ from contestant Bayram: 3485189 (You should also know that 'bir' means 'one' in Turkish and 'iki' means two!)

now think dp approach since if width will not be 1 , 2 that it will be quit tough by this approach

-----------------------------------------------------code---------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

int main()

 {

   int ans=0;

   int n;

    cin>>n;

    int p=0,q=0;

    int sum=0;

    int o[109],t[109];

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

     {

     

       int a,b;

        cin>>a>>b;

        if(a==1) o[p++]=b;

        else t[q++]=b;

        sum+=b;

}

sort(o,o+p);

sort(t,t+q);

//for(int i=0;i<p;i++)cout<<o[i]<<" ";cout<<endl;

// for(int j=0;j<q;j++) cout<<t[j]<<" ";

int st1=p-1;

int st2=q-1;

int base=0;

while(st1>=0 && st2>=0)

 {

 // cout<<"sts "<<st1<<" "<<st2<<"sum "<<sum<<endl;

  if(sum-o[st1]<=base+1)

   {

     cout<<base+1<<endl;

     return 0;

  }

  else if(st1>=1 && sum-o[st1]-o[st1-1]<=base+2)

  {

  

     cout<<base+2<<endl;

     return 0;

  }

  else if(sum-t[st2]<=base+2)

  

  {

   cout<<base+2<<endl;

   return 0;

  }

  else if(sum-t[st2]-o[st1]<=base+3)

  {

   cout<<base+3<<endl;

   return 0;

  }

  else

  {

   int bb=0;

  // cout<<st1<<" "<<st2<<endl;

   int max1=o[st1];

   bb=1;

 //  cout<<"a "<<max1<<endl;

   if(st1>=1) 

  {

   max1+=o[st1-1];bb++;

  }

   //cout<<"b "<<max1<<endl;

   int max2=t[st2];

  // cout<<"maxi1 "<<max1<<" max2 "<<max2<<endl;

   if(max1>max2)

    {

   base+=bb;

     st1-=2;

     sum-=max1;

    // base+=2;

    

   }

   else

   {

    st2-=1;

    sum-=max2;

    base+=2;

   }

  }

  

// cout<<"sts "<<st1<<" "<<st2<<" base "<<base<<" sum "<<sum<<endl;

 }

 if(st1<0)

  {

   while(st2>=0)

    {

      sum-=t[st2];

      base+=2;

      if(base>=sum)

      {

        cout<<base<<endl;

        return 0;

}

st2-=1;

   }

  }

  

  if(st2<0)

  {

   while(st1>=0)

    {

      sum-=o[st1];

      base+=1;

      if(base>=sum)

      {

        cout<<base<<endl;

        return 0;

}

st2-=1;

   }

  }

 }

*Greenhouse Effect(minimum no of swap needed to sort an array if any no can be swaped at any place ans-- n-lis)

 Greenhouse Effect

Emuskald is an avid horticulturist and owns the world's longest greenhouse — it is effectively infinite in length.

Over the years Emuskald has cultivated n plants in his greenhouse, of m different plant species numbered from 1 to m. His greenhouse is very narrow and can be viewed as an infinite line, with each plant occupying a single point on that line.

Emuskald has discovered that each species thrives at a different temperature, so he wants to arrange m - 1 borders that would divide the greenhouse into m sections numbered from 1 to m from left to right with each section housing a single species. He is free to place the borders, but in the end all of the i-th species plants must reside in i-th section from the left.

Of course, it is not always possible to place the borders in such way, so Emuskald needs to replant some of his plants. He can remove each plant from its position and place it anywhere in the greenhouse (at any real coordinate) with no plant already in it. Since replanting is a lot of stress for the plants, help Emuskald find the minimum number of plants he has to replant to be able to place the borders.

Input

The first line of input contains two space-separated integers n and m (1 ≤ n, m ≤ 5000, n ≥ m), the number of plants and the number of different species. Each of the following n lines contain two space-separated numbers: one integer number si (1 ≤ si ≤ m), and one real number xi (0 ≤ xi ≤ 109), the species and position of the i-th plant. Each xi will contain no more than 6 digits after the decimal point.

It is guaranteed that all xi are different; there is at least one plant of each species; the plants are given in order "from left to the right", that is in the ascending order of their xi coordinates (xi < xi + 1, 1 ≤ i < n).

Output

Output a single integer — the minimum number of plants to be replanted.

Sample test(s)

input

3 2
2 1
1 2.0
1 3.100

output

1

input

3 3
1 5.0
2 5.5
3 6.0

output

0

input

6 3
1 14.284235
2 17.921382
1 20.328172
3 20.842331
1 25.790145
1 27.204125

output

2

Note

In the first test case, Emuskald can replant the first plant to the right of the last plant, so the answer is 1.

In the second test case, the species are already in the correct order, so no replanting is needed.

------------------------------------editorial----------------------------------

Problem

There are n points on the line, each of type from 1 to m. We can freely divide the line into m - 1 intervals and replace some points so each point with type i is inside the i-th interval numbered 1 to m from left to right. We must find the minimum number of points to replace.

Solution

First, observe that the coordinates don’t matter: only the order of the points is important. Let there be some number of points we can replace to achieve the good arrangement. Then all the other points remain in their positions, so their values must be in increasing order from left to right. Then we must find the maximum number of points that can remain in their positions, which is the longest non-decreasing subsequence of types in the input. If it is of length l, the answer is n - l.

In this problem it was enough to implement a quadratic solution. We count dp[i][j] — the length of the longest non-decreasing subsequence on prefix [1;i], with element of type j being the last in subsequence. The transition is as follows:

For easy implementation, we can maintain only array dp[j], and skip the second case.

Time: O(n2) / .

Memory: O(n2) / O(n).

Implementation: C++

-------------------------------------------------code---------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

vector<int> v;

int dp[100000];

int main()

 {

   int n,m;

    cin>>n>>m;

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

     {

      int a;

       cin>>a;

       float f;

        cin>>f;

    

        v.push_back(a);

}

 dp[0]=1;

int  ans=0;

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

    {

      int num=v[i];

      int maxi=1;

      for(int k=i-1;k>=0;k--)

            {

             if(v[k]<=num)

              {

               maxi=max(maxi,dp[k]+1);

 }

          }

          dp[i]=maxi;

          ans=max(ans,maxi);

          

      }

      cout<<n-ans<<endl;

 

 }