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 ?

# | User | Rating |
---|---|---|

1 | tourist | 3822 |

2 | Benq | 3745 |

3 | ksun48 | 3560 |

4 | Radewoosh | 3538 |

5 | peehs_moorhsum | 3532 |

6 | Um_nik | 3489 |

7 | maroonrk | 3424 |

8 | Petr | 3380 |

9 | sunset | 3338 |

10 | ecnerwala | 3336 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 207 |

2 | awoo | 181 |

2 | Errichto | 181 |

4 | Um_nik | 180 |

5 | -is-this-fft- | 175 |

6 | maroonrk | 174 |

7 | Radewoosh | 172 |

7 | tourist | 172 |

9 | SecondThread | 170 |

10 | rng_58 | 166 |

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 )

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

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

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

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/01/2021 23:29:44 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|