coffeewithkaran007
BAN USERMy Approach :
-Make a segment tree for two most maximum elements for each range
-Find the ans while traversing the seg tree.
Time Complexity :
T(n) = 2*(n-1) + n = O(n)
/*
Given an array of integers you to find the range l,r such that
and operation of largest two element in that range is maximum.
For example:
Input
6 1 6
Output
1 3
You have to print lexicographically smallest range.
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
struct item
{
ll f;
ll s;
};
ll st,en,mx;
vector<ll> A;
vector<item> tree;
void build(long long node,long long start,long long end)
{
if(start == end)
{
// Leaf node will have a single element
tree[node].f=A[start];
// ll temp=A[start];
// ll k=0;
// while(temp)
// {
// temp/=2;
// k++;
// }
// tree[node].s=(1<<(k))-1;
tree[node].s=1;
}
else
{
long long int mid = (start + end) / 2;
// Recurse on the left child
build(2*node+1, start, mid);
// Recurse on the right child
build(2*node+2, mid+1, end);
//store two max elements
if(tree[2*node+1].f<tree[2*node+2].f)
{
tree[node].f=tree[2*node+2].f;
tree[node].s=max(tree[2*node+1].f,max(tree[2*node+1].s,tree[2*node+2].s));
}
else
{
tree[node].f=tree[2*node+1].f;
tree[node].s=max(tree[2*node+2].f,max(tree[2*node+1].s,tree[2*node+2].s));
}
}
}
item query(long long int node,long long int start,long long int end,long long int l,long long int r)
{
if(r < start or end < l)
{
item temp;
temp.f=-1;
temp.s=-1;
return temp;
}
if(l <= start and end <= r)
{
return tree[node];
}
item temp;
long long int mid = (start + end) / 2;
item p1 = query(2*node+1, start, mid, l, r);
item p2 = query(2*node+2, mid+1, end, l, r);
if(p1.f<p2.f)
{
temp.f=p2.f;
temp.s=max(p1.f,max(p1.s,p2.s));
}
else
{
temp.f=p1.f;
temp.s=max(p2.f,max(p1.s,p2.s));
}
return temp;
}
long long int nextPowerOf2(long long int n)
{
long long count = 0;
//First n in the below condition is for the case where n is 0
if (n && !(n&(n-1)))
return n;
while( n != 0)
{
n >>= 1;
count += 1;
}
return 1<<count;
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
int main()
{
ll n,i,j,x,tree_size;
cin>>n;
for(i=0;i<n;i++)
{
cin>>x;
A.push_back(x);
}
tree_size=2*nextPowerOf2(n)-1;
tree.resize(tree_size+1);
mx=-1;
st=-1;
en=-1;
build(0,0,n-1);
//traverse seg tree n get answer by anding two max elements of the array......done in the build function
item temp;
for(i=0;i<n;i++)
{
for(j=i;j<n;j++)
{
temp=query(0,0,n-1,i,j);
ll x=temp.f;
ll y=temp.s;
if(i==j)
{
y=x;
}
if((x&y)>mx)
{
mx=(x&y);
st=i;
en=j;
}
else if((x&y)==mx)
{
if(i<st)
{
st=i;
en=j;
}
else if(i==st)
{
if(j<en)
{
st=i;
en=j;
}
}
}
}
}
cout<<"Required range is : "<<st+1<<" to "<<en+1;
return 0;
}
/*
Given a matrix of n*n. Each cell contain 0, 1, -1.
0 denotes there is no diamond but there is a path.
1 denotes there is diamond at that location with a path
-1 denotes that the path is blocked.
Now you have start from 0,0 and reach to last cell & then return back to 0,0 collecting maximum no of diamonds.
While going to last cell you can move only right and down.
While returning back you can move only left and up.
*/
#include<bits/stdc++.h>
using namespace std;
long long n,d[1000][1000],ans[1000][1000];
pair<long long,long long> prev[1000][1000];
void solve()
{
long long i,j;
if(d[0][0]!=-1)
{
ans[0][0]=d[0][0];
prev[0][0]=make_pair(-1,-1);
}
for(i=1;i<n;i++)
{
if(d[0][i]==-1)
break;
ans[0][i]=ans[0][i-1]+d[0][i];
prev[0][i]=make_pair(0,i-1);
}
while(i<n)
{
ans[0][i]=-1;
i++;
}
for(i=1;i<n;i++)
{
if(d[i][0]==-1)
break;
ans[i][0]=ans[i-1][0]+d[i][0];
prev[i][0]=make_pair(i-1,0);
}
while(i<n)
{
ans[i][0]=-1;
i++;
}
for(i=1;i<n;i++)
{
for(j=1;j<n;j++)
{
if(d[i][j]==-1)
{
ans[i][j]=-1;
continue;
}
if(ans[i-1][j]>ans[i][j-1])
{
ans[i][j]=ans[i-1][j]+d[i][j];
prev[i][j]=make_pair(i-1,j);
}
else
{
ans[i][j]=ans[i][j-1]+d[i][j];
prev[i][j]=make_pair(i,j-1);
}
}
}
}
void update()
{
long long i,j;
pair<long long,long long> node;
i=n-1;
j=n-1;
while(i!=-1&&j!=-1)
{
node=prev[i][j];
d[i][j]=0;
i=node.first;
j=node.second;
}
}
void init()
{
long long i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
ans[i][j]=0;
}
}
}
int main()
{
long long i,j,res;
res=0LL;
cin>>n;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
cin>>d[i][j];
}
}
solve();
res=res+ans[n-1][n-1];
update();
init();
solve();
res=res+ans[n-1][n-1];
cout<<"Max Path Diamonds : "<<res;
return 0;
}
Approach 1 :
We precompute the value of factorial modulo p in an array..
then we get an expression of the form (a/b)%p
We evaluate this with the help of the euler phi function..
Approach 2:
Use Lucas theorem.. Much more elegant method..
For non-negative integers m and n and a prime p, the following congruence relation holds:
\binom{m}{n}\equiv\prod_{i=0}^k\binom{m_i}{n_i}\pmod p,
where
m=m_kp^k+m_{k-1}p^{k-1}+\cdots +m_1p+m_0,
and
n=n_kp^k+n_{k-1}p^{k-1}+\cdots +n_1p+n_0
are the base p expansions of m and n respectively. This uses the convention that \tbinom{m}{n} = 0 if m < n.
- coffeewithkaran007 July 02, 2015
- coffeewithkaran007 June 02, 2016