HackerEarth Solutions

Advertisements

Benny And The Broken Odometer

Problem Link

This problem can be solved using Digit Dp .

Source Code:

#include<bits/stdc++.h>
using namespace std;
char nm[20];
int dp[20][2][2],len=0;

int solve(int pos,int tight,int st)
{
// tight= unrestricted range or restricted range
// st= any particular condition like here i=3

if(pos==len)
{
return st==1;
}
if(dp[pos][tight][st]!=-1)
return dp[pos][tight][st];
int rs=0;
int lm=tight? nm[pos]-‘0’:9;
for(int i=0;i<=lm;i++)
{
int nwtig=(nm[pos]-‘0’==i);
rs+=solve(pos+1,nwtig && tight,st|(i==3));

}
dp[pos][tight][st]=rs;
return rs;

}
int num()
{
int res=0;
for(int i=0;i<len;i++)
{
res=res*10+(nm[i]-‘0’);

}
return res;
}

int work()
{

int rs=num();
return rs-solve(0,1,0);
}

int main()
{

int n,t,cs=1;
scanf(“%d”,&t);
while(t–)
{
int x,y;
scanf(“%s”,nm);
memset(dp,-1,sizeof dp);
len=strlen(nm);
printf(“%d\n”,work());
}
}

257C. View Angle

Problem Link: http://codeforces.com/problemset/problem/257/C

 

It is a basic geometry problem ,you have to find the minimum angle .

 

<Code>

 

/*********************************************************

 

Y O U A R E A M A Z I N G

R E M E M B E R T H A T.

 

**********************************************************/

 

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

//===============typedef
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector< vi > vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef set<int> si;
typedef map<string, int> msi;
typedef pair< double , double > pd;
//=================Constant
const ll MOD=1e9+7;
const ll N=1e5;
const ll inf=10000000;

//=============define
#define cln(a) memset(a,0,sizeof a);
#define clni(a) memset(a,inf,sizeof a);
#define all(x) x.begin(), x.end()
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define sz(a) int((a).size())
#define pb push_back
#define sp(c,x) ((c).find(x) != (c).end()) // for set,map
#define vp(c,x) (find(all(c),x) != (c).end()) // for vector
#define uu first
#define vv second
#define fr(i,a,b) for(int i=int(a);i<int(b);++i)
#define nfr(i,a,b) for(int i= int(a);i>=int(b);–i)
#define tc cin>>t ; while(t–)
#define pc() cout<<“Case “<<cs++<<“: ”
#define mx (int)1e5+10
#define s2(x,y) int x,y;scanf(“%d %d”,&x,&y)
#define s2l(x,y) ll x,y;scanf(“%lld %lld”,&x,&y)
#define s3(x,y,z) int x,y,z;scanf(“%d %d %d”,&x,&y,&z)
#define s3l(x,y,z) ll x,y,z;scanf(“%lld %lld %lld”,&x,&y,&z)
#define sc(x) int x; scanf(“%d”,&x)
#define scl(x) ll x; scanf(“%lld”,&x)
#define pfs(x) printf(“%d “,x)
#define pfl(x) printf(“%d\n”,x)
#define el puts(“”);
#define getcx() getchar()
#define Fi freopen(“inp.txt”,”r”,stdin)
#define rt return 0
#define dbg(x) cerr<<x<<endl
#define pi acos(-1)
int main()
{
sc(n);
vector< double > ans;
fr(i,0,n)
{
s2(x,y);
ans.pb(atan2(y,x)*180/pi);  // angle
}

sort(all(ans));
double ck;

ck=0;
for(int i=0;i<n-1;i++)
{
ck=max(ck,abs(ans[i+1]-ans[i]));
}
ck=max(ck,360-abs(ans[0]-ans[n-1]));
cout.precision(12);
cout<<360-ck<<endl;
}

448B

Problem Link

 

View Code
#include<bits/stdc++.h>
using namespace std;
#define all(s) sort(s.begin(),s.end())
string s,t;
bool ar()
{all(s);all(t);
return s==t;
}

bool autom()
{
int c=0,sz=0;
int l=s.size();
for(int i=0;i<l;i++)
{
if(s[i]==t[c])
c++,sz++;
}

return sz==t.size()?1:0;

}
bool bt()
{
all(s);
all(t);
int c=0,sz=0;
int l=s.size();
for(int i=0;i<l;i++) { if(s[i]==t[c]) c++,sz++; } return sz==t.size()?1:0; } int main() { cin>>s>>t;
if(autom())
cout<<"automaton"<<endl;
else if(ar())
cout<<"array"<<endl;
else if(bt())
cout<<"both"<<endl;
else
cout<<"need tree"<<endl;

}

 

GSS1

#Problem Link

Prerequisites:

1.  e-maxx

 

 

View Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mx = 50010;
ll a[mx];

struct data {
int sum, pref, suff, ans ;
}tree[4*mx] ;
data make_data ( ll val ) {
data res ;
res. sum = val ;
res. pref = res. suff = res. ans = val ;
return res ;
}
data combine ( data l, data r ) {
data res ;
res. sum = l. sum + r. sum ;
res. pref = max ( l. pref , l. sum + r. pref ) ;
res. suff = max ( r. suff , r. sum + l. suff ) ;
res. ans = max ( max ( l. ans , r. ans ) , l. suff + r. pref ) ;
return res ;
}

void build(ll node,ll b,ll e)
{
if(b==e)
{
tree[node]=make_data(a[b]);
}
else{
int mid=(b+e)/2;
build(node*2,b,mid);
build(node*2+1,mid+1,e);
tree[node]=combine(tree[node*2],tree[node*2+1]);
}
}
void buildsm(ll node,ll b,ll e)
{

}

ll update(ll node,ll b,ll e,ll x,ll y)
{

}

data query(ll node,ll b,ll e,ll l,ll r)
{
if(l==b &&e==r)
return tree[node];
int mid=(b+e)/2;
if(r<=mid) return query(node*2,b,mid,l,r); if(l>mid)
return query(node*2+1,mid+1,e,l,r);
return combine(query(node*2,b,mid,l,mid),query(node*2+1,mid+1,e,mid+1,r));
};
ll n,q;
int main()
{

scanf(“%lld”,&n);
memset(tree,0,sizeof tree);
memset(a,0,sizeof a);
for(ll i=1;i<=n;i++)
{scanf(“%lld”,&a[i]);
}
build(1,1,n);
//buildsum(1,1,n);
scanf(“%lld”,&q);
while(q–)
{
ll x,y;
scanf(“%lld %lld”,&x,&y);
{
printf(“%lld\n”,query(1,1,n,x,y).ans);
//cout<<query(1,1,n,x,y)<<endl;
}

}

}

 

 

126B – Password

This problem is based on Z- algorithm

To learn this algorithm  – Click here!

 

View Code

#include<bits/stdc++.h>
using namespace std;
void solve(string s)
{
int l=s.size();
int z[l];
int left,right;
left=right=0;
for(int k=1;k<l;k++) { if(k>right)
{
left=right=k;
while(right {
right++;
}
z[k]=right-left;
right–;
}
else{
int k1=k-left;
if(z[k1]<right-k+1)
{
z[k]=z[k1];
}
else{
left=k;
while(right {
right++;
}
z[k]=right-left;
right–; }

}
}
int mxz = 0, res = 0,n=l;
for(int a=1;a<l;a++){
//printf(“%d %d\n”, a, Z[a]);
if(a + z[a] == l){
if(z[a] <= mxz){
for(int j=0;j<z[a];j++) printf(“%c”, s[j]); return ; } } mxz = max(mxz, z[a]); } puts(“Just a legend”); } int main() { string s; cin>>s;

solve(s);
}

 

Z algorithm

Today we will try with a new algorithm – Z algorithm

This algo is used in pattern matching,there is another algo for pattern matching

This algorithm works in O(length of text+length of pattern) complexity

and space complexity is similar to time complexity that means O(length of text+length of pattern)

This algorithm is very easy.

</>Video Tutorial

 

</>Visualization

 

</> Blog

 

#Problemset