### f.nasim's blog

By f.nasim, 11 years ago,

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.

• -32

By f.nasim, 11 years ago,

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.

• 0

By f.nasim, 11 years ago,
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;
}


• -1

By f.nasim, 11 years ago,
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.

• -11

By f.nasim, 11 years ago,
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.

• 0

By f.nasim, 11 years ago,
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.

• +72

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

• 0

By f.nasim, 12 years ago,
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;
}

• 0

By f.nasim, 12 years ago,
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.

• 0

By f.nasim, 12 years ago,
/*
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;
}

• 0

By f.nasim, 12 years ago,
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.

• 0

By f.nasim, 12 years ago,
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.