Here are some funny doubts i have,hope you help->
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Here are some funny doubts i have,hope you help->
Mine favorite is-**Are you pretest 2,because i am not getting what's wrong with you**. Tell your Favorite one liner.
Many codes are going to fail system test today for the problem B of contest Codeforces round 717.Its my prediction,let's see what happens.
I am getting tle in this problem of cses Longest Pallindrome.Can anyone suggest me some optimisation . MY LOGIC: I maintained hash values for the string and for the reverse of it.Then i am doing binary search checking for values from i=1 to i=n. Example: for example if our string is abyuuy then maintain hash values for abyuuy and maintain hash values for yuuyba.Then while oing binary search from 1 to let say we are at 4 then i will start checking from i=0 and at i=2 i found (using hash values) that its pallindrome so i found it,You can understand it more from my code Effectively the complexity is o(nlogn) but its giving tle. Here is my code
#include<bits/stdc++.h>
using namespace std;
#define dd double
#define ll long long int
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define pr pair<ll,ll>
#define pri pair<pr,ll>
#define pir pair<ll,pr>
#define ppr pair<pr,pr>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll INF=1e8;
ll mod=1e9+9;
ll power(ll x,ll y,ll m)
{
ll res=1;
x = x%m;
if(x==0)
return 0;
while(y>0)
{
if(y&1)
res = (res*x)%m;
y = y>>1;
x = (x*x)%m;
}
return res%m;
}
ll modInverse(ll n,ll p)
{
return power(n,p-2,p);
}
pr check(string &str1,vector<ll> &h,vector<ll> &p,vector<ll> &h1,vector<ll> &p1,ll val)
{
// cout<<val<<endl;
pr ans=mp(-1ll,-1ll);
ll n=str1.length(),i,j,t;
if(val==1)
{
ans=mp(0ll,0ll);
return ans;
}
for(i=0;i<=n-val;i++)
{
if(val%2!=0)
{
ll t1,t2,val1,val2;
t1=i,t2=i+val/2-1;
if(i==0)
{
val1=h[t2];
}
else
{
val1=(h[t2]-h[t1-1]+2*mod)%mod;
val1=(val1*modInverse(p[t1],mod))%mod;
}
t1=t2+2;
t2=t1+val/2-1;
t1=n-1-t1;
t2=n-1-t2;
swap(t1,t2);
if(t1==0)
{
val2=h1[t2];
}
else
{
val2=(h1[t2]-h1[t1-1]+2*mod)%mod;
val2=(val2*modInverse(p1[t1],mod))%mod;
}
if(val1==val2)
{
ans=mp(i,i+val-1);
return ans;
}
}
else
{
ll t1,t2,val1,val2;
t1=i,t2=i+val/2-1;
if(i==0)
{
val1=h[t2];
}
else
{
val1=(h[t2]-h[t1-1]+2*mod)%mod;
val1=(val1*modInverse(p[t1],mod))%mod;
}
t1=t2+1,t2=t1+val/2-1;
t1=n-1-t1;
t2=n-1-t2;
swap(t1,t2);
if(t1==0)
{
val2=h1[t2];
}
else
{
val2=(h1[t2]-h1[t1-1]+2*mod)%mod;
val2=(val2*modInverse(p1[t1],mod))%mod;
}
if(val1==val2)
{
ans=mp(i,i+val-1);
return ans;
}
}
}
return ans;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("inp.txt","r",stdin);
freopen("otpt.txt","w",stdout);
#endif
fastio;
ll te=1;
// cin>>te;
while(te--)
{
string str1;
cin>>str1;
ll n=str1.length(),i,j,t;
vector<ll> h(n),p(n),h1(n),p1(n);
h[0]=str1[0]-'a';
p[0]=1;
ll a=31,b=1e9+9;
for(i=1;i<n;i++)
{
p[i]=(p[i-1]*a)%b;
h[i]=(h[i-1]+(str1[i]-'a')*p[i])%b;
}
string str2=str1;
reverse(str2.begin(),str2.end());
h1[0]=str2[0]-'a';
p1[0]=1;
for(i=1;i<n;i++)
{
p1[i]=(p1[i-1]*a)%b;
h1[i]=(h1[i-1]+(str2[i]-'a')*p1[i])%b;
}
ll l=1,r=n;
pr pr1,pr2,ans;
ans=mp(0,0);
while(l+1<r)
{
ll midi=(l+r)/2;
//cout<<midi<<endl;
pr1=check(str1,h,p,h1,p1,midi);
pr2=check(str1,h,p,h1,p1,midi+1);
if(pr1.fi==-1&&pr2.fi==-1)
{
r=midi-1;
}
else
{
if(pr2.fi!=-1)
{
l=midi+1;
}
else
{
l=midi;
}
if(ans.sc-ans.fi+1<pr1.sc-pr1.fi+1)
{
ans=pr1;
}
if(ans.sc-ans.fi+1<pr2.sc-pr2.fi+1)
{
ans=pr2;
}
}
}
if(l+1==r)
{
pr1=check(str1,h,p,h1,p1,r);
if(ans.sc-ans.fi+1<pr1.sc-pr1.fi+1)
{
ans=pr1;
}
}
for(i=ans.fi;i<=ans.sc;i++)
{
cout<<str1[i];
}
cout<<endl;
}
}
Last time i wrote one such blog ,people came and upvoted and downvoted depending on their mood but noone replied,if you want to downvote me you can do that but plz help me in my problem. Any help is welcome.Thanks.
Here is a codechef problem Friends. Here is my solution ,its giving wrong answer.Can anybody help me find out the error.
#include<bits/stdc++.h>
using namespace std;
#define dd double
#define ll long long int
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define pr pair<ll,ll>
#define pri pair<pr,ll>
#define pir pair<ll,pr>
#define ppr pair<pr,pr>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll INF=1e18;
ll mod=1e9+7;
int main()
{
#ifndef ONLINE_JUDGE
freopen("inp.txt","r",stdin);
freopen("otpt.txt","w",stdout);
#endif
fastio;
ll te=1;
while(te--)
{
ll n,i,j,t;
cin>>n;
vector<vector<char> > v1(n,vector<char>(n));
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
cin>>v1[i][j];
}
}
ll ans=0;
queue<pr> q;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(v1[i][j]=='0')
{
q.push(mp(i,j));
}
}
}
q.push(mp(-1ll,-1ll));
ll last=q.size();
ll ct=0;
while(1)
{
ct++;
pr p=q.front();
q.pop();
if(p.fi==-1)
{
if(last==q.size()||q.empty())
{
break;
}
last=q.size();
q.push(p);
continue;
}
ll i=p.fi,j=p.sc;
for(t=0;t<n;t++)
{
if(v1[t][i]=='1'&&v1[t][j]=='1'&&t!=i&&t!=j)
{
break;
}
}
if(t==n)
{
q.push(p);
continue;
}
if(v1[i][j]!='1')
{
ans+=1;
}
v1[j][i]='1';
v1[i][j]='1';
}
cout<<2*ans<<endl;
}
}
Thanks in advance.
Name |
---|