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 | 164 |

1 | maomao90 | 164 |

3 | Um_nik | 163 |

4 | atcoder_official | 160 |

5 | -is-this-fft- | 158 |

6 | awoo | 157 |

7 | adamant | 156 |

8 | TheScrasse | 154 |

8 | nor | 154 |

10 | djm03178 | 153 |

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-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/12/2024 21:19:11 (k1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|