#include <bits/stdc++.h>
#define pf printf
#define sf(a) scanf("%d",&a)
#define sfl(a) scanf("%lld",&a)
#define sff(a,b) scanf("%d %d",&a,&b)
#define sffl(a,b) scanf("%lld %lld",&a,&b)
#define sfff(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define db double
#define ft float
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define sz(x) x.size()
#define qu queue
#define pqu priority_queue
#define vc vector
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define all(x) x.begin(),x.end()
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define loop0(i,n) for(int i=0;i<n;i++)
#define loop1(i,n) for(int i=1;i<=n;i++)
#define stlloop(x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define case(z,x) cout<<"Case "<<i<<": "<<x<<endl
#define case(z) cout<<"Case "<<z<<": "
#define PI 3.14159265358979323846264338328
#define valid(tx,ty) tx>=0 && tx<r && ty>=0 && ty<c
#define MAX 2000
#define inf 10000000
/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*---------------------------------------------------------------------*/
using namespace std;
int main()
{
//CIN;
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int t;
sf(t);
loop1(z,t)
{
int a,b;
sff(a,b);
int c=a+b;
pf("Case %d: %d\n",z,c);
}
return 0;
}
Page 37 of 66
Light OJ – 1023 – Discovering Permutations
#include <bits/stdc++.h>
#define pf printf
#define sf(a) scanf("%d",&a)
#define sfl(a) scanf("%lld",&a)
#define sff(a,b) scanf("%d %d",&a,&b)
#define sffl(a,b) scanf("%lld %lld",&a,&b)
#define sfff(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define sffff(a,b,c,d) scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d) scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e) scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e) scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
#define sfc(a) scanf("%c",&a)
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define db double
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define max3(a, b, c) max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c) min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define for0(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define forrev(i,n) for(int i=n-1; i>=0; i--)
#define forab(i,a,b) for(int i=a;i<=b;i++)
#define forba(i,b,a) for(int i=b;i>=a;i--)
#define stlloop(x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define case1(z) cout<<"Case "<<z<<": "
#define case2(z) printf("Case %d:\n",z)
#define PI acos(-1) //3.14159265358979323846264338328
#define valid(tx,ty) tx>=0 && tx<row && ty>=0 && ty<col
#define intlim 2147483648
#define MAX 100005
#define inf 100000008
ll power(int n,int p)
{
ll ans=1;
for1(i,p) ans*=n;
return ans;
}
ll m=1000001;
ll bigmod(ll n,ll p)
{
if(p==0) return 1;
else if(p%2==0)
{
ll x=(bigmod(n,p/2))%m;
return (x*x)%m;
}
else return ((n%m)*(bigmod(n,p-1)%m))%m;
}
/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*---------------------------------------------------------------------*/
using namespace std;
int main()
{
//CIN;
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int t,n,k;
sf(t);
for1(z,t)
{
string s;
sff(n,k);
char ch='A';
for1(i,n)
{
s+=ch;
ch++;
}
case2(z);
int i=0;
do
{
cout<<s<<endl;
i++;
}
while(i<k && next_permutation(all(s)));
}
return 0;
}
SPOJ – YODANESS – Yodaness Level
Problem link: SPOJ – YODANESS – Yodaness Level
Solution : This problem is of relatively easy logic as a BIT problem. About like the logic of the problem SPOJ – Inversion Count. But do not compare with that. Because the logic is not same but the concept is about similar. So you have to catch the concept by yourself in pen n paper, you will get your simple logic 🙂
#include <bits/stdc++.h>
#define pf printf
#define sf(a) scanf("%d",&a)
#define sfl(a) scanf("%lld",&a)
#define sff(a,b) scanf("%d %d",&a,&b)
#define sffl(a,b) scanf("%lld %lld",&a,&b)
#define sfff(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define sffff(a,b,c,d) scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d) scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e) scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e) scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
#define sfc(a) scanf("%c",&a)
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define db double
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define max3(a, b, c) max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c) min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define for0(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define forrev(i,n) for(int i=n-1; i>=0; i--)
#define forab(i,a,b) for(int i=a;i<=b;i++)
#define forba(i,b,a) for(int i=b;i>=a;i--)
#define stlloop(x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define case1(z) cout<<"Case "<<z<<": "
#define case2(z) printf("Case %d: ",z)
#define PI acos(-1) //3.14159265358979323846264338328
#define valid(tx,ty) tx>=0 && tx<row && ty>=0 && ty<col
#define intlim 2147483648
#define MAX 100005
#define inf 100000008
ll power(int n,int p)
{
ll ans=1;
for1(i,p) ans*=n;
return ans;
}
ll m=1000001;
ll bigmod(ll n,ll p)
{
if(p==0) return 1;
else if(p%2==0)
{
ll x=(bigmod(n,p/2))%m;
return (x*x)%m;
}
else return ((n%m)*(bigmod(n,p-1)%m))%m;
}
/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*---------------------------------------------------------------------*/
using namespace std;
ll tree[30004],input[30004];
map<string,int> mp;
vector<string> v;
ll query(ll idx)
{
ll sum=0;
while(idx>0)
{
sum+=tree[idx];
idx-= idx & (-idx);
}
return sum;
}
void update(ll idx,ll val, int n)
{
while(idx<=n)
{
tree[idx]+=val;
idx+=idx&(-idx);
}
}
int main()
{
CIN;
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int t;
cin>>t;
for1(z,t)
{
int n,c=0;
cin>>n;
string s,ss,str;
for1(i,n)
{
cin>>s;
v.pb(s);
}
for1(i,n)
{
cin>>s;
c++;
mp[s]=c;
}
for0(i,sz(v)) {input[i+1]=mp[v[i]];}
ll ans=0;
for1(i,n)
{
update(input[i],1,n);
ll x=query(input[i]-1);
ans+=(input[i]-x-1);
}
cout<<ans<<endl;
mp.clear();
v.clear();
ms(tree,0);
}
return 0;
}
Light OJ – 1085 – All Possible Increasing Subsequences
Problem Link: Light OJ – 1085 – All Possible Increasing Subsequences
Solution Hint:
This problem can be solved by both BIT and Segment tree. I have applied BIT here. You can read the blog here to have a better understanding… Here solution hint is given somewhat but you have to do the code.
The most crutial part is how we deal with repeated values !! I request you please do some pen n paper work regarding this n brainstorm yourself that how you will deal with that. If you find a reasonable way, do accordingly, if that works, congratzz!! 😀 if not, no matter, you are probably puzzling things, but one great hint is – there can be many ways to sort it out n it’s easy, believe me 🙂
Now you can see my code.
I have just subtracted the repeated values elements from my cummulative sum… because, here we are running query for index [i-1] for each i , that is for each element in the vector that is ended woth that element in the resultant subsequence. So of course it’s not a valid subsequence to end with repeated value !!
And the subtraction is less complicated because guess !! I have already sorted the vector on which I am running queries !! So there is no chance of calculating a index which is greater that the next index !! Because the STL sort function automatically sort a vector with pair firstly according to first elements from lower to higher, then if first elements are equal, then by second elements from lower to higher values.
#include <bits/stdc++.h>
#define pf printf
#define sf(a) scanf("%d",&a)
#define sfl(a) scanf("%lld",&a)
#define sff(a,b) scanf("%d %d",&a,&b)
#define sffl(a,b) scanf("%lld %lld",&a,&b)
#define sfff(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define sffff(a,b,c,d) scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d) scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e) scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e) scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
#define sfc(a) scanf("%c",&a)
#define pii pair<int,int>
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define pbp(a,b) push_back({a,b})
#define db double
#define ft float
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sz(x) x.size()
#define all(x) x.begin(),x.end()
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define max3(a, b, c) max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c) min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define for0(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define forrev(i,n) for(int i=n-1; i>=0; i--)
#define forab(i,a,b) for(int i=a;i<=b;i++)
#define forba(i,b,a) for(int i=b;i>=a;i--)
#define stlloop(x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define case1(z) cout<<"Case "<<z<<": "
#define case2(z) printf("Case %d: ",z)
#define PI acos(-1) //3.14159265358979323846264338328
#define valid(tx,ty) tx>=0 && tx<row && ty>=0 && ty<col
#define intlim 2147483648
#define MAX 200005
#define inf 100000008
/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*---------------------------------------------------------------------*/
using namespace std;
ll tree[100005],m=1000000007;
vector<pair<ll,ll> > v;
ll query(ll idx)
{
ll sum=0;
while(idx>0)
{
sum=((sum%m)+(tree[idx]%m))%m;
idx-=idx & (-idx);
}
return sum;
}
void update(ll idx,ll val,ll n)
{
while(idx<=n)
{
tree[idx]=((tree[idx]%m)+(val%m))%m;
idx+=idx & (-idx);
}
}
int main()
{
//CIN;
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int t;
sf(t);
for1(z,t)
{
int n;
sf(n);
for1(i,n)
{
ll x;sfl(x);
v.pb(make_pair(x,i));
}
sort(all(v));
ll sum,ans=0,x=-inf,k;
for0(i,sz(v))
{
sum=(1+query(v[i].ss-1))%m;
if(v[i].ff!=x)
{
k=sum;
x=v[i].ff;
}
else
{
sum-=k;
k=(k%m+sum%m)%m;
}
update(v[i].ss,sum,n);
ans=(ans%m+sum%m)%m;
}
case2(z);
pf("%lld\n",ans);
ms(tree,0);
v.clear();
}
return 0;
}
SPOJ – INVCNT – Inversion Count
#include <bits/stdc++.h>
#define pf printf
#define sf(a) scanf("%d",&a)
#define sfl(a) scanf("%lld",&a)
#define sff(a,b) scanf("%d %d",&a,&b)
#define sffl(a,b) scanf("%lld %lld",&a,&b)
#define sfff(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define sffff(a,b,c,d) scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d) scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e) scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e) scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
#define sfc(a) scanf("%c",&a)
#define pii pair<int,int>
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define pbp(a,b) push_back({a,b})
#define db double
#define ft float
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sz(x) x.size()
#define all(x) x.begin(),x.end()
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define max3(a, b, c) max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c) min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define for0(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define forrev(i,n) for(int i=n-1; i>=0; i--)
#define forab(i,a,b) for(int i=a;i<=b;i++)
#define forba(i,b,a) for(int i=b;i>=a;i--)
#define stlloop(x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define case1(z) cout<<"Case "<<z<<": "
#define case2(z) printf("Case %d:\n",z)
#define PI acos(-1) //3.14159265358979323846264338328
#define valid(tx,ty) tx>=0 && tx<row && ty>=0 && ty<col
#define intlim 2147483648
#define MAX 200005
#define inf 100000008
/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*---------------------------------------------------------------------*/
using namespace std;
ll input[200005],tree[10000007];
ll query(ll idx)
{
ll sum=0;
while(idx>0)
{
sum+=tree[idx];
idx-=idx & (-idx);
}
return sum;
}
void update(ll idx,ll val,int n)
{
while(idx<=n)
{
tree[idx]+=val;
idx+=idx & (-idx);
}
}
int main()
{
//CIN;
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int t,x,y;
sf(t);
for1(z,t)
{
int n;
sf(n);
for1(i,n) sfl(input[i]);
ll maxi=*max_element(input,input+n);
ll sum=0;
forba(i,n,1)
{
update(input[i],1,maxi);
sum+=(query(input[i-1]));
}
pf("%lld\n",sum);
ms(tree,0);
}
return 0;
}
Fall out, Codes! 