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 | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
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 ?
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 ?
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 . ?
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;
}
Name |
---|