Flawless's blog

By Flawless, 11 years ago, In English

I was trying a Problem on Vertex Cover.I can't think of any good algo to do this. www.spoj.pl/problem/PT07X/ Can anyone give any hint to the method ? just a little hint ?

Full text and comments »

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

By Flawless, 11 years ago, In English

Hello Everyone. I was busy with my exams. before that i read on CROC entry that it will be open for Non- Russian to participate too ! I tried hard to find link to register for it..but i can't find the Registration link So can anyone provide link, i am looking forward to this..

Thanks a lot, Flawless (just another human )

Full text and comments »

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

By Flawless, 11 years ago, In English

What is the most efficient way to find Lowest Common Ancestor in Binary Tree ?

Full text and comments »

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

By Flawless, 11 years ago, In English

is it true that if you have added someone in your friend list on CF. you and him/her can never be in same room . ?

Full text and comments »

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

By Flawless, 11 years ago, In English

I know you can get an AC in problem with normally optimized prime sieve. but sometimes while doing problem on SPOJ. i noticed when i have execution time of 2 sec (for example), many good coders (Respected) have brought down their execution time to 0.5 sec around .

Here is what i have done for my optimized prime sieve.

Optimization i have done-
1. running main iteration loop to only square root of Limit.
2. avoid for even numbers.
3. not checking for multiple of 2 and 3
4. Prime numbers are of form 6k+1 or 6k+5.
5. in inner loop of j, insted of j+=i, i did j+=2*i. because i*i(as i will be odd for sure, i haven't run this loop for "2") will be odd for sure. so i*i+i will be odd for sure. so skip it by j+=2*i

Since even numbers and multiple of 3 are never marked. so they will never be checked while collecting all primes

 #define lim 10000009
 vector<bool> isprime(lim,1);
 void sieve()
 {
    int i,j,t,v,sq;
    isprime[1]=isprime[0]=0;
    sq=sqrt(lim);
    for(i=5,t=2;i<=sq; )
    {
         if(isprime[i])
         {
              for(j=i*i;j<lim;j+=2*i)
                 isprime[j]=0; // 0 means composite- not prime , 1 means prime
         }
         i+=t;
         t=6-t;
    }
}

Can i improve this more ??? Please help

Full text and comments »

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

By Flawless, 11 years ago, In English

Respected Admin or Anyother coder i submitted this code for problem B. i am getting correct answer for Sample testcase but on codeforces i get "0" for this... i tested for many times and problem still prevails.. Many many advance thanks :)

 #include<iostream>
 #include<cstdio>
 #include<algorithm>
 #define LL long long int
 using namespace std;
 int main()
 {
	LL n,t,i;
	cin>>n>>t;
	LL arr[n];
	for(i=0;i<n;i++)
		cin>>arr[i];
	LL count=0,sum,start,j,ans,temp;
	temp=0;
	start=0;
	count=0;
	for(i=0;i<n;i++)
	{
		sum+=arr[i];
		if(sum<=t)
			temp++;
		else		
		if(sum>t)
		{
			count=max(count,temp);			
			j=start;
			temp++;			
			while(1)
			{							
				sum-=arr[j];
				j++;	
				temp--;
				if(sum<=t)
					break;
				if(j>i)
					break;
							
			}
			start=j;		
		}
			
	}
	count=max(count,temp);
	cout<<count<<endl;
	return 0;
 }

Full text and comments »

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