qwertsboy1234's blog

By qwertsboy1234, history, 3 years ago, In English

Here are some funny doubts i have,hope you help->

Why is question mark missing from -is-this-fft-?

SecondThread where is your elder brother FirstThread?

why dreamoon_love_AA?

How is this guy tourist when he just sits at one place and do coding?

Why is this guy maha_chutiya?

Why is this guy hopeless_and_broken?

Do scott_wu and neal fight in themself for rating?

Is demoralizer really healthy?

The biggest Doubt

What on the Earth does Errichto mean???????????????????????????????

Full text and comments »

  • Vote: I like it
  • +128
  • Vote: I do not like it

By qwertsboy1234, history, 4 years ago, In English

Mine favorite is-**Are you pretest 2,because i am not getting what's wrong with you**. Tell your Favorite one liner.

Full text and comments »

  • Vote: I like it
  • +405
  • Vote: I do not like it

By qwertsboy1234, history, 4 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +143
  • Vote: I do not like it

By qwertsboy1234, history, 4 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • -5
  • Vote: I do not like it

By qwertsboy1234, history, 4 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it