f.nasim's blog

By f.nasim, 11 years ago, In English

Problem statement.

"....a string is good if you can obtain an anagram of the string p from it, replacing the "?" characters by Latin letters....."

Does it mean if I can obtain an anagram of p without replacing "?" characters a good string? I think no. What do you guys think?

My contest submission gets WA on pretest 4 because I didn't count those good strings but I got AC with this.

Read more »

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

By f.nasim, 11 years ago, In English

Hi, I am trying to participate virtually on codeforces beta round 86 (div 2). But as I try to register it always says "Invalid day or time format". I have tried many combinations of date-time but response is same. Does anyone know how to set the time properly? Please share.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By f.nasim, 11 years ago, In English
Problem link
Why does my following solution get WA. I used kmp prefix function to compute the prefix of the given string and its reverse,pi2[] and pi1[] respectively.

Then I computed the longest prefix and suffix of the string which are palindromes. If the rest of the string except the palindrome prefix or suffix is also a palindrome I output it as an "alindrome". I handled two special cases for checking "palindrome" with length 1 and other "palindrome"s. All other strings are "simple".

Please help me with some test cases or pointing out any flaw in my reasoning or code. Code follows.
#include <stdio.h>
#include <string.h>
 
#define MAX 200005
 
int pi1[MAX],pi2[MAX],m;
 
void pre1(char P[])
{
    int i,k=m;
    pi1[m-1]=m;
 
    for(i=m-2;i>=0;i--)
    {
        while(k!=m && P[k-1]!=P[i])
            k=pi1[k];
 
        if(P[k-1]==P[i]) k--;
        pi1[i]=k;
    }
}
 
void pre2(char P[])
{
    int i,k=-1;
    pi2[0]=-1;
 
    for(i=1;i<m;i++)
    {
        while(k>=0 && P[k+1]!=P[i])
            k=pi2[k];
 
        if(P[k+1]==P[i]) k++;
        pi2[i]=k;
    }
}
 
int main()
{
    int t,i,k;
    char str[MAX];
 
    scanf("%d",&t);
 
    while(t--)
    {
        scanf("%s",str);
        m=strlen(str);
 
        pre1(str);
        int p=m;
        int f=1;
        for(i=0;i<m;i++)
        {
            while(p!=m && str[p-1]!=str[i])
                p=pi1[p];
 
            if(str[p-1]==str[i]) p--;
            if(i && str[i]!=str[i-1]) f=0;
        }
 
        if(f==1 && m>1)
        {
            printf("alindrome\n");
            continue;
        }
 
        if(p==0)
        {
            printf("palindrome\n");
            continue;
        }
 
        pre2(str);
        int r=-1;
        for(i=m-1;i>=0;i--)
        {
            while(r>=0 && str[r+1]!=str[i])
                r=pi2[r];
 
            if(str[r+1]==str[i]) r++;
        }
 
        for(i=p-1;i>=0;i--)
            if(str[i]!=str[p-i-1])
                break;
 
        if(i==-1)
        {
            printf("alindrome\n");
            continue;
        }
 
        for(i=r+1;i<m;i++)
            if(str[i]!=str[m-1-i+r+1])
                break;
 
        if(i==m)
        {
            printf("alindrome\n");
            continue;
        }
 
        printf("simple\n");
    }
 
    return 0;
}

Read more »

Tags uva, wa
 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

By f.nasim, 11 years ago, In English
Hi everyone. I am trying hard to collect a soft copy of the book Programming Pearls by Jon Bentley. But most of the available ones are pdf version of the Programming Pearls website not the complete book.

Can anyone share any link to the complete book Programming Pearls. Thanks in advance.

Read more »

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

By f.nasim, 11 years ago, In English
Hi. In CF I read a problem whose solution is like this: for given N output the longest array of divisors which are all divisors of N and all smaller divisors are divisor of the larger ones. For example if N=72 the ans may be 24,8,4,2,1. But I have forgotten the contest no. Does anyone remember this? Please post the contest no.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By f.nasim, 11 years ago, In English
As per televisions and news agencies there has been a catastrophic earthquake and a resulting tsunami in Japan. We express deep sympathy to the affected people of Japan and nearby countries and hope situation will improve as soon as possible.

In Codeforces we have many coder friends from Japan. Are you all guys OK? Share your experiences,feelings with us if you can. Thanks.

Read more »

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

By f.nasim, 12 years ago, In English
How many different spanning trees are possible in a graph with n vertices? Also explain the calculation.Thanks in advance.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By f.nasim, 12 years ago, In English
What's the problem in the following code? It gets wrong answer on test case 3.

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>

using namespace std;

int main()
{
    int n,m,v,i;

    scanf("%d %d %d",&n,&m,&v);

    if(m<n-1)
    {
        printf("-1");
        return 0;
    }

    if((m-n+1)>n-3)
    {
        printf("-1");
        return 0;
    }

    for(i=1;i<n;i++)
        printf("%d %d\n",i,i+1);

    int count=0;

    for(i=1;count<m-n+1;i++)
    {
        if(i!=v-1 && i!=v && i!=v+1)
        {
            //printf("%d %d\n",i,v);
            printf("%d %d\n",min(i,v),max(i,v));
            count++;
        }
    }

    return 0;
}

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By f.nasim, 12 years ago, In English
Does anyone have the test data for the three practice session problems(CHIP, FISH and ROBOT) in IOI 2007? The official website (http://ioinformatics.org/locations/ioi07/contest/) doesn't contain test data for these problems.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By f.nasim, 12 years ago, In English
/*
Can anyone tell me what's wrong in the following code. It is repeatedly getting "Wrong answer on test 4".
*/

#include<iostream>
#include<cmath>

using namespace std;

long long max(long long x, long long y)
{
    if(x>y)
        return x;

    return y;
}

long long min(long long x, long long y)
{
    if(x<y)
        return x;

    return y;
}

int main()
{
    long long t,n,m,x1,y1,x2,y2,p,q,r,s;

    cin >> t;

    while(t--)
    {
        cin >> n >> m >> p >> q >> r >> s;

        x1=y1=1;
        x2=fabs(p-r)+1;
        y2=fabs(q-s)+1;

        if(x2==n && y2==m)
        {
            cout << m*n-2 << endl;
            continue;
        }

        long long rbound=n-fabs(x2-x1);
        long long bbound=m-fabs(y2-y1);

        long long maxx=max(x1,x2);
        long long maxy=max(y1,y2);

        long long over=(rbound-maxx+1)*(bbound-maxy+1);
        long long count=(rbound*2)*bbound;
        long long tot=count-over;

        cout << (m*n)-tot << endl;
    }

    return 0;
}

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By f.nasim, 12 years ago, In English
Given an unsorted sequence A={a0,a1,a2,......an-1} of n integers. How do I find the longest increasing sub-sequence of the given sequence. Is there any dynamic programming solution.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By f.nasim, 12 years ago, In English
Can anyone tell actually what's the behind that problem.I proved many individual cases but didn't find any formula or pattern, except for the numbers given by n(n+1)/2.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it