All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.
Moderator: Board moderators
Fuad Hassan EWU
New poster
Posts: 38 Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University
Post
by Fuad Hassan EWU » Sat Oct 27, 2007 10:23 pm
I am having TLE in this problem. Is my algo too slow. Or some where this code is falling in infinite loop??
Last edited by
Fuad Hassan EWU on Sun Oct 28, 2007 5:00 pm, edited 1 time in total.
Eagle er moto daana meley urbo
sapnil
Experienced poster
Posts: 106 Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:
Post
by sapnil » Sun Oct 28, 2007 4:00 pm
-> give up intilize
-> Generate pair for each input number
-> I think you get TLE because you generate output for each num from
1 to 1000000.
Thanks
Keep Posting
Sapnil
"Dream Is The Key To Success"
@@@ Jony @@@
Fuad Hassan EWU
New poster
Posts: 38 Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University
Post
by Fuad Hassan EWU » Sun Oct 28, 2007 4:48 pm
sapnil wrote
-> give up intilize
-> Generate pair for each input number
-> I think you get TLE because you generate output for each num from
1 to 1000000.
But sapnil i stored pair from 6 to 1000009 in the structure. Later i used the input'th index of the structure array x. yes i generated output for 6 to 1000009. but it is pre-calculation. when i take input then i didn't calculate form 6 to 1000009. i only showed the pair in the input'th index of the array x.
plz keep posting and make me clear. thanks
Eagle er moto daana meley urbo
Fuad Hassan EWU
New poster
Posts: 38 Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University
Post
by Fuad Hassan EWU » Sun Oct 28, 2007 4:59 pm
O yes sapnil i got your point and get AC. that i skip all the odd numbers. thank u.
Eagle er moto daana meley urbo
hridoy
New poster
Posts: 21 Joined: Tue May 08, 2007 10:30 am
Location: Dhaka
Contact:
Post
by hridoy » Sun Dec 16, 2007 11:16 am
Can any one please tell me why I m getting TLE??
and How can I use sieve in such a long number 1000000..?
[codeAC[/code]
Last edited by
hridoy on Fri Jan 04, 2008 9:51 pm, edited 1 time in total.
Jan
Guru
Posts: 1334 Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
Post
by Jan » Sun Dec 16, 2007 1:58 pm
1. You can calculate the primes and store them before taking the input.
2. sqrt() is a slow function. So, you can use
Code: Select all
int P = sqrt(i);
for(j=3;j<=P;j+=2)
Hope these help.
hridoy
New poster
Posts: 21 Joined: Tue May 08, 2007 10:30 am
Location: Dhaka
Contact:
Post
by hridoy » Sun Dec 16, 2007 10:32 pm
Thanks to Jan, My answer has improved but still I m getting TLE:(.. it's not working for input 1000000..
anymore suggestion form anybody???
Jan
Guru
Posts: 1334 Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
Post
by Jan » Mon Dec 17, 2007 12:35 am
You should post your new code.
hridoy
New poster
Posts: 21 Joined: Tue May 08, 2007 10:30 am
Location: Dhaka
Contact:
Post
by hridoy » Mon Dec 17, 2007 9:01 pm
[/code]#include<stdio.h>
#include<math.h>
main()
{
long n,k=0,i,j,l,m,a[200000],p,z,news;
while(1)
{
for(i=3;i<=n;i+=2)
{
z=0;
news=sqrt(i);
for(j=3;j<=news;j+=2)
if(i%j==0)
{
z=1;
break;
}
if(z==0)
{
a[k]=i;
k++;
}
}
scanf("%ld",&n);
if(n==0)
break;
p=0,l=0,m=0;
for(i=0;i<k;i++)
for(j=i;j<k;j++)
if(a
+a[j]==n&&(l-m)<=(a[j]-a))
{
m=a;
l=a[j];
p=1;
}
if(p==1)
printf("%ld = %ld + %ld\n",n,m,l);
else
printf("Goldbach's conjecture is wrong.\n");
}
}
Jan
Guru
Posts: 1334 Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
Post
by Jan » Tue Dec 18, 2007 11:35 am
You didn't get my point. I was talking about..
Code: Select all
int main()
{
generate_Primes_upto_Limit();
whlie(input())
{
...
}
return 0;
}
Hope it helps.
hridoy
New poster
Posts: 21 Joined: Tue May 08, 2007 10:30 am
Location: Dhaka
Contact:
Post
by hridoy » Wed Dec 19, 2007 9:36 pm
I m still TLE..but it's work for all critical i/0..
here is my code.
Last edited by
hridoy on Fri Jan 04, 2008 9:53 pm, edited 1 time in total.
Jan
Guru
Posts: 1334 Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
Post
by Jan » Thu Dec 20, 2007 11:26 am
Code: Select all
for(i=0;i<k;i++)
for(j=i;j<k;j++)
This is the reason for TLE.
Code: Select all
for(i=0;i<k;i++)
p = n-a[i];
use binary search to find p
Since the difference should be minimum, you can start your search form i to 0, where a
<= n/2 and a is maxium. You can break the loop if you find a solution. Hope these help.
Ahmad
New poster
Posts: 16 Joined: Thu Apr 28, 2011 10:48 pm
Post
by Ahmad » Sun May 01, 2011 7:32 pm
someone tell me why am getting wrong answer or i will sucide
here's the java code
Code: Select all
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
int r = 1000000;
boolean[] visited = new boolean[r+1];
for (int i = 2; i < r; i++) {
if (!visited[i]) {
for (int j = 2; i * j < r; j++) {
visited[i * j] = true;
}
}
}
Scanner in = new Scanner(System.in);
int n = -1;
while ((n = in.nextInt()) != 0) {
if (!visited[n])
System.out.println("Goldbach's conjecture is wrong.");
else {
boolean found = false;
for (int i = 2; i < n; i++) {
int j = n - i;
if (j!= 1 && j != i && !visited[i] && !visited[j]) {
System.out.printf("%d = %d + %d\n", n, i, j);
found = true;
break;
}
}
if (!found)
System.out.println("Goldbach's conjecture is wrong.");
}
}
}
}
sohel
Guru
Posts: 856 Joined: Thu Jan 30, 2003 5:50 am
Location: New York
Post
by sohel » Sun May 01, 2011 11:17 pm
Use the search option located at the top right corner to find existing discussions.
Don't create a new thread for a problem that already exists! Make your post on an existing one.
meee...
New poster
Posts: 4 Joined: Tue Dec 09, 2008 4:04 pm
Post
by meee... » Wed Oct 26, 2011 3:32 pm
Why am i getting TLE?
Code: Select all
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define MSG(a) cout<<#a<<"="<<a<<endl;
#define MAX 1000001
int prime[MAX];
void sieve(int n){
for(int i = 0;i<=n;i++){
prime[i]=1;
}
prime[0]=prime[1]=0;
for(int i = 2;i*i<=n;i++){
if(prime[i]){
for(int j = i;j*i<=n;j++){
prime[i*j]=0;
}
}
}
}
int main(){
int n;
sieve(MAX-1);
//for(int i = 0;i<20;i++)MSG(prime[i]);
while(scanf("%d",&n) && n){
int dist = -1;
int ini=-1,end=-11;
for(int i = 2;i<=n/2;i++){
if(prime[i] && prime[n-i] && dist<abs(n-i-i)){
dist = abs(n-i-i);
ini = i;
end = n-i;
}
}
if(dist==-1){printf("Goldbach's conjecture is wrong.\n");continue;}
printf("%d = %d + %d\n",n,ini,end);
}
return 0;
}