**Multiplication Table(div2 D)

 Multiplication Table

Bizon the Champion isn't just charming, he also is very smart.

While some of us were learning the multiplication table, Bizon the Champion had fun in his own manner. Bizon the Champion painted ann × m multiplication table, where the element on the intersection of the i-th row and j-th column equals i·j (the rows and columns of the table are numbered starting from 1). Then he was asked: what number in the table is the k-th largest number? Bizon the Champion always answered correctly and immediately. Can you repeat his success?

Consider the given multiplication table. If you write out all n·m numbers from the table in the non-decreasing order, then the k-th number you write out is called the k-th largest number.

Input

The single line contains integers n, m and k (1 ≤ n, m ≤ 5·105; 1 ≤ k ≤ n·m).

Output

Print the k-th largest number in a n × m multiplication table.

Sample test(s)

input

2 2 2

output

2

input

2 3 4

output

3

input

1 10 5

output

5

Note

A 2 × 3 multiplication table looks like this:

1 2 3
2 4 6

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

Solution is discreat binary search. We need to find largest x such that amount of numbers from table, least than x, is strictly less than k. 

suppose by descreat b search we set that let answer is X than count no of numbers in each row <=X

this can easily done in o(1) in each row (by just devide )

now value x for which exactly k no of numbers are less than x will be the answer 

main problem is redendency 

---ex suppose input is 3,5,9

soo if create array and sor it it will be like 

1 2 2 3 3 4 4 5 6 6 8 9 1014 15

now  for k=9 ans is 6 

but when we count using  our method no of numbers <=6 than it will give 10, since 6 repeats 2 times (internal repeats will never affact answer ),

so to handle this problem we count no of times 6 can be form in the given array (factorise till sqrt), in this case it is 2(let z)  and count <=6 is 10

soo answer for k=10-z+1 to 10 will be 6 

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

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli ans=1e14;
lli calc(lli n,lli m ,lli num)
 {
    lli maxi=sqrt(num);
    
    int re=0;
    for(int i=1;i<=maxi;i++)
     {
      if(num%i==0)
       {
      
        lli se=num/i;
    
        if(i<=n && se<=m)
     {
     
      re++;
     }
        if(i<=m && se<=n)
     {
    
      re++;
      } 
        if(se==i && se<=n && se<=m)
     {
  
      re--;
      } 
    }
  }
 
  return re;
  
 }


int main()
 {
  lli n,m,k;
  cin>>n>>m>>k;
  lli mini=0;
  lli maxi=n*m+2;
  int s=0;
  //discreat 
  while(mini<maxi)
   {
   lli temp=0;
    lli mid=(mini+maxi)/2;
    
   
       lli re=calc(n,m,mid);// no of times mid can be formed in the given array 
     
    
    for(int i=1;i<=n;i++)
     {
      temp+=min(mid/i,m);
          
     }
     
 
    lli r1=temp-re+1;
    lli r2=temp;
   


    if(k<=r2 && k>=r1)
     {
   
      ans=min(ans,mid);
     }
     if(temp>=k)
      {
       maxi=mid;
   }
   else 
    {
     mini=mid+1;
     
    }
    
   
   }
   cout<<ans<<endl;
 }

**Little Elephant and Cards

 Little Elephant and Cards

The Little Elephant loves to play with color cards.

He has n cards, each has exactly two colors (the color of the front side and the color of the back side). Initially, all the cards lay on the table with the front side up. In one move the Little Elephant can turn any card to the other side. The Little Elephant thinks that a set of cards on the table is funny if at least half of the cards have the same color (for each card the color of the upper side is considered).

Help the Little Elephant to find the minimum number of moves needed to make the set of n cards funny.

Input

The first line contains a single integer n (1 ≤ n ≤ 105) — the number of the cards. The following n lines contain the description of all cards, one card per line. The cards are described by a pair of positive integers not exceeding 109 — colors of both sides. The first number in a line is the color of the front of the card, the second one — of the back. The color of the front of the card may coincide with the color of the back of the card.

The numbers in the lines are separated by single spaces.

Output

On a single line print a single integer — the sought minimum number of moves. If it is impossible to make the set funny, print -1.

Sample test(s)

input

3
4 7
4 7
7 4

output

0

input

5
4 7
7 4
2 11
9 7
1 1

output

2

Note

In the first sample there initially are three cards lying with colors 4, 4, 7. Since two of the three cards are of the same color 4, you do not need to change anything, so the answer is 0.

In the second sample, you can turn the first and the fourth cards. After that three of the five cards will be of color 7.

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

It is nice to use the map structure in this problem, but you can solve it without map (using sorting and binary serach). Lets iterate through all possible colors that we have and suppose that this currect color is the one that will make our set funny. The minimal number through all this will be the answer. To find the minimal number of turns to make our set funny using current color we need to know two numbers: the number of cards with current color on the front side and the number of cards with the current color on back side (but not at the same time). Let it be integers a and b. Let m = (n + 1) / 2 — the minimal number of the same cards required to get the funny set. Then if a + b < m it is impossible to make set funny using current color at all. If a ≥ m then the answer is 0, otherwise the answer ism - a.

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

implementation is easy ..

only tricky thing is that there may  be possibility a card which is not in front side but  , it can made answer. because on opposite side its enough pairs are available ..

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

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

#define test()    int test_case;cin>>test_case;while(test_case--)

#define fr(i,n) for(int i=0;i<n;i++)

#define frr(i,a,n) for(int i=a;i<n;i++)

#define sll(a) scanf("%lld",&a)

#define sl(a) scanf("%ld",&a)

#define si(a) scanf("%i",&a)

#define sd(a)  scanf("%ld",&a)

#define sf(a) scanf("%f",&a)

#define rn(a) return a

#define pai pair<int,int>

#define pal pair<li,li>

#define pall pair<lli,lli>

//#define ff first

//#define second second

#define mod  1000000007

#define mp make_pair

#define pb push_back

#define pll(a) printf("%lld\n",a)

#define pl(a) printf("%lld\n",a)

#define pi(a) printf("%d\n",a)

#define pd(a) printf("%lf\n",a)

#define pf(a) printf("%f\n",a)

#define lc (start+end)/2

#define rc  lc+1

int main()

 {

  int n;

   cin>>n;

   vector<pall> v;

   vector<lli> v1;

   map<lli,int> back;

   set<lli> s;//  will contain all distinct colour which can be give answer 

   

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

    {

    lli a,b;

     cin>>a>>b;

     

     s.insert(a);

     s.insert(b);

     

     v.pb(mp(a,b));

     

     v1.pb(a);// it used for applying b'search since not applicable on vector<pair>

     

     

     

    if(a!=b)// means there is some card of different colour on opposoit side

           // which can be used after swap, eliminate a==b sice if both side card are same

           // colour than no meaning of togling

     {

       

      back[b]++;

     

 }

     

}

sort(v.begin(),v.end());

sort(v1.begin(),v1.end());

int mini;

if(n%2==1) mini=n/2+1;

else

mini=n/2;

 

  int ans=INT_MAX;

  set<lli> :: iterator its;

 

  for(its=s.begin();its!=s.end();its++)

  {

  vector<lli> :: iterator it,itv;

    lli clr=*its;

 

    itv=lower_bound(v1.begin(),v1.end(),clr);

    it=upper_bound(v1.begin(),v1.end(),clr);

    int temp=it-v1.begin();

    it--;

    int cov=it-itv+1;

 

    if(cov>mini)

     {

      cout<<"0";

      return 0;

 }

 else

 {

  int req=mini-cov;

  if(req<=back[*its])

  ans=min(ans,req);

 

 }

 

    

 }

 if(ans!=INT_MAX)

 cout<<ans<<endl;

 else

 cout<<"-1"<<endl;

 return 0 ;

 }

***Largest Rectangle in a Histogram(divide concure +segtree)

Problem H: Largest Rectangle in a Histogram

Source file: histogram.(c|cc|hs|java|pas)
Input file: histogram.in

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

Input Specification

The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1<=n<=100000. Then follow n integers h₁,...,h_n, where 0<=h_i<=1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.

Output Specification

For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.

Sample Input

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

Sample Output

8
4000

-------------------------------------------editiorial------------------------------------

Largest Rectangular Area in a Histogram | Set 2

Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have same width and the width is 1 unit.

For example, consider the following histogram with 7 bars of heights {6, 2, 5, 4, 5, 2, 6}. The largest possible rectangle possible is 12 (see the below figure, the max area rectangle is highlighted in red)



We have discussed a Divide and Conquer based O(nLogn) solution for this problem. In this post, O(n) time solution is discussed. Like the previous post, width of all bars is assumed to be 1 for simplicity. For every bar ‘x’, we calculate the area with ‘x’ as the smallest bar in the rectangle. If we calculate such area for every bar ‘x’ and find the maximum of all areas, our task is done. How to calculate area with ‘x’ as smallest bar? We need to know index of the first smaller (smaller than ‘x’) bar on left of ‘x’ and index of first smaller bar on right of ‘x’. Let us call these indexes as ‘left index’ and ‘right index’ respectively. We traverse all bars from left to right, maintain a stack of bars. Every bar is pushed to stack once. A bar is popped from stack when a bar of smaller height is seen. When a bar is popped, we calculate the area with the popped bar as smallest bar. How do we get left and right indexes of the popped bar – the current index tells us the ‘right index’ and index of previous item in stack is the ‘left index’. Following is the complete algorithm.



--

1) Create an empty stack.

2) Start from first bar, and do following for every bar ‘hist[i]’ where ‘i’ varies from 0 to n-1. ……a) If stack is empty or hist[i] is higher than the bar at top of stack, then push ‘i’ to stack. ……b) If this bar is smaller than the top of stack, then keep removing the top of stack while top of the stack is greater. Let the removed bar be hist[tp]. Calculate area of rectangle with hist[tp] as smallest bar. For hist[tp], the ‘left index’ is previous (previous to tp) item in stack and ‘right index’ is ‘i’ (current index).

3) If the stack is not empty, then one by one remove all bars from stack and do step 2.b for every removed bar.

Following is C++ implementation of the above algorithm.



---------------------------------------stack code-------------------------------------------------------------------------------------------------

// C++ program to find maximum rectangular area in linear time

#include<iostream>

#include<stack>

using namespace std;



// The main function to find the maximum rectangular area under given

// histogram with n bars

int getMaxArea(int hist[], int n)

{

 // Create an empty stack. The stack holds indexes of hist[] array

 // The bars stored in stack are always in increasing order of their

 // heights.

 stack<int> s;



 int max_area = 0; // Initalize max area

 int tp; // To store top of stack

 int area_with_top; // To store area with top bar as the smallest bar



 // Run through all bars of given histogram

 int i = 0;

 while (i < n)

 {

  // If this bar is higher than the bar on top stack, push it to stack

  if (s.empty() || hist[s.top()] <= hist[i])

  {

   s.push(i++);



           //  cout<<" jsut push "<<endl;

  }

   

  // If this bar is lower than top of stack, then calculate area of rectangle 

  // with stack top as the smallest (or minimum height) bar. 'i' is 

  // 'right index' for the top and element before top in stack is 'left index'

  else

  {

   tp = s.top(); // store the top index

   s.pop(); // pop the top



   // Calculate the area with hist[tp] stack as smallest bar

   area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);



   // update max area, if needed

   if (max_area < area_with_top)

    max_area = area_with_top;

  }

 }



 // Now pop the remaining bars from stack and calculate area with every

 // popped bar as the smallest bar

 // cout<<i<<endl;

 while (s.empty() == false)// remaining elements in the stack are just continuous increasing elements

 {                        // so  this shows for any element tp , all elenment left to to are small , and right are bigger

  tp = s.top();

  s.pop();

 //  cout<<hist[tp] <<" ";

  area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);



  if (max_area < area_with_top)

   max_area = area_with_top;

 }



 return max_area;

}



// Driver program to test above function

int hist[1000000];

int main()

{

 

 int n;

 

  cin>>n;

  for(int i=0;i<n;i++) cin>>hist[i];

 cout <<getMaxArea(hist, n)<<endl;

 return 0;

}

---------------------------------------------seg tree+ dividconcure  approach--------------------------------------------------------------------------------

Largest Rectangular Area in a Histogram | Set 1

Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have same width and the width is 1 unit.

For example, consider the following histogram with 7 bars of heights {6, 2, 5, 4, 5, 2, 6}. The largest possible rectangle possible is 12 (see the below figure, the max area rectangle is highlighted in red)



A simple solution is to one by one consider all bars as starting points and calculate area of all rectangles starting with every bar. Finally return maximum of all possible areas. Time complexity of this solution would be O(n^2).

We can use Divide and Conquer to solve this in O(nLogn) time. The idea is to find the minimum value in the given array. Once we have index of the minimum value, the max area is maximum of following three values. a) Maximum area in left side of minimum value (Not including the min value) b) Maximum area in right side of minimum value (Not including the min value) c) Number of bars multiplied by minimum value. The areas in left and right of minimum value bar can be calculated recursively. If we use linear search to find the minimum value, then the worst case time complexity of this algorithm becomes O(n^2). In worst case, we always have (n-1) elements in one side and 0 elements in other side and if the finding minimum takes O(n) time, we get the recurrence similar to worst case of Quick Sort. How to find the minimum efficiently? Range Minimum Query using Segment Tree can be used for this. We build segment tree of the given histogram heights. Once the segment tree is built, all range minimum queries take O(Logn) time. So over all complexity of the algorithm becomes.

Overall Time = Time to build Segment Tree + Time to recursively find maximum area

Time to build segment tree is O(n). Let the time to recursively find max area be T(n). It can be written as following. T(n) = O(Logn) + T(n-1) The solution of above recurrence is O(nLogn). So overall time is O(n) + O(nLogn) which is O(nLogn).

Following is C++ implementation of the above algorithm.



-----------------------------------------------------code-----but in strict time limit this soln does not pass --------------------------------------------------------------------------------------





#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;

#define test()    int test_case;cin>>test_case;while(test_case--)
#define fr(i,n) for(int i=0;i<n;i++)
#define frr(i,a,n) for(int i=a;i<n;i++)
#define sll(a) scanf("%lld",&a)
#define sl(a) scanf("%ld",&a)
#define si(a) scanf("%i",&a)
#define sd(a)  scanf("%ld",&a)
#define sf(a) scanf("%f",&a)
#define rn(a) return a
#define pai pair<int,int>
#define pal pair<li,li>
#define pall pair<lli,lli>
#define ff first
#define ss second
#define mod  1000000007
#define mp make_pair
#define pb push_back
#define pll(a) printf("%lld\n",a)
#define pl(a) printf("%lld\n",a)
#define pi(a) printf("%d\n",a)
#define pd(a) printf("%lf\n",a)
#define pf(a) printf("%f\n",a)
#define lc (start+end)/2
#define rc  lc+1

#include<iostream>

lli ans=0;
 int n;
using namespace std;
lli arr[1010000];
struct abcd
{
 int val;
 int index;
}tree[1010000];

int laz[10100000];
#define inf 999999999
abcd query(int node,int start,int end,int r1,int r2)
 {
  
   if(r1>end  || r2<start   || start>end) 
   {
    abcd node;
    node.index=INT_MAX;
    node.val=INT_MAX;
    return node;
   }
   if(r1<=start && r2>=end)
    {
     return tree[node];
     
    }
    else
    {
     abcd q1=query(2*node,start,(start+end)/2,r1,r2);
    abcd q2=query(2*node+1,((start+end)/2)+1,end,r1,r2);
     if(q1.val<=q2.val)return q1;
     else return q2;
    }
 }
 
 
 
void build(int node , int start,int end)
 {
  //cout<<" build start "<<start<<" "<<end<<endl;
  
   if(start>end) return ;
   if(start==end)
    {
     tree[node].index=start;
     tree[node].val=arr[start];
 }
  else
   {
    build(2*node,start,(start+end)/2);
    build(2*node+1,((start+end)/2)+1,end);
    if(tree[2*node].val<=tree[2*node+1].val)
    {
     tree[node].val=tree[2*node].val;
     tree[node].index=tree[2*node].index;
      
 }
 else
 {
  
    
     tree[node].val=tree[2*node+1].val;
     tree[node].index=tree[2*node+1].index;
 
 }
    
   }
   
 }
 
 int t=10;
 lli  solve(int start,int end)
  {
   //if(t--==0) exit(0);
  lli  ans=0;
   // cout<<"solve in the range "<<start<<" "<<end<<endl;
    if(start==end)
     {
      ans=max(ans,arr[start]);
      return ans;
      
  }
  else if(start>end)
   {
    return 0 ;
   }
   else
   {
    
    abcd node=query(1,0,n-1,start,end);
    int index=node.index;
   //  cout<<" index"<<index<<endl;
     if(index==start)
      {
    //   cout<<"ans set here "<<(end-start+1)*arr[index];
       ans=max(ans,max((end-start+1)*arr[index],solve(index+1,end)));
       
       
      }
      else if(index==end)
       {
         ans=max(ans,max(ans*(end-start+1)*arr[index],solve(0,end-1)));
    }
    else
    {
     ans=max(ans,max((end-start+1)*arr[index],max(solve(start,index-1),solve(index+1,end))));
    }
    
    return ans;
   }
   return ans;
  }

int main()
{

  cin>>n;
  for(int i=0;i<n;i++)
   {
     cin>>arr[i];
     
   }
//   cout<<" before bouid ";
   build(1,0,n-1);
//   cout<<"after build "<<endl;
   
  int fin=solve(0,n-1);
  cout<<fin<<endl;
}