Flawless's blog

By Flawless, 8 years ago,

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 ?

• 0

By Flawless, 8 years ago,

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 )

• +4

By Flawless, 8 years ago,

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

• +2

By Flawless, 8 years ago,

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 . ?

• +2

By Flawless, 8 years ago,

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;
}
}


• +10

By Flawless, 8 years ago,

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;
}