SPOJ

Pages: 123
ne555 wrote:
Nope.
So? and what does that Example mean?

Example

Input:
2
1 10
3 5

Output:
2
3
5
7

3
5
remember that stdin and stdout are different streams
Also, clarity
ok, the iput comes from one file and the output goes to another, fine. But that's rather marginal
There are no files involved, you read from one stream and output to the other, there is no need to hold output until the end.
also what does the number to the right of "running" mean when you have just submitted and its done compiling. It is always running(0). Does that mean something? Does it mean I haven't completed any of the inputs, if that is so something must really be wrong with the program, and probably not the optimization.
Still haven't got it working so are you saying the problem is just that it is not fast enough? Then I have no idea how to improve it without starting over, but the program I have made should be really fast. Also have anyone completed this challenge and knows how they want the output/input?
If SPOJ supported C++11 I would just move primes up to 1000m calculation to the compile time. It probably is still possible in C++03 but is pain in the ass to create. Hmm... You can probably statically initialize first n numbers in your array whare n depends on maximum size of source.
@Filiprei
The most recent code you posted has the wrong output for the sample input. http://ideone.com/9YJPHu
I slightly improved the code, actually I decided to make a new program but it is still over the time limit. :/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// exception_handling.cpp : Defines the entry point for the console application.
//

#include <iostream>


using namespace std;
bool isPrime(int n);

int main()
{

	int num;
	cin >> num;
	int x1, x2;

	while(num)
	{
		cin >> x1 >> x2;
		while(x1 <= x2)
		{
			if(isPrime(x1))
				cout << x1 << endl;
			x1++;
		}
		num--;
	}
	return 0;
}


bool isPrime(int n)
{
	if(n == 1 || n == 0)
		return false;

	if(n % 2 == 0 && n != 2)
		return false;

	int sq = sqrt(n);

	for(int i = 3;i <= sq; )
	{
		if(n % i == 0)
		{
			return false;
		}
		i += 2;
	}

	return true;
}
Close, but the output is still wrong http://ideone.com/PQ3PiS
hint you're missing a line break.
They probably don't care about a line break :P Anyways, not the problem.
They probably don't care about a line break :P

Since they go out of the way to explicitly mention it when describing output, I would guess that they do.


Anyways, not the problem.

Not the biggest problem, anyway. That would be the algorithm.
closed account (3qX21hU5)
They do care a lot about a line break. The thing with programming competition problems is their output needs to be perfect, meaning even something as stupid as a missing white space or missing line break will give you the incorrect answer.

The computer that is checking your output vs the correct output will see that missing line break as a error and will give you incorrect answer.
Last edited on
well, if it was the problem it would say wrong answer instead of the time running out :/ And also it shouldn't be hard to make a system flexible when it comes to line breaks.
closed account (3qX21hU5)
Not necessarily. You can still run over the time limit with the wrong output.
The computer doesn't know if you have the exact right output until the end of the program. So once it reaches the designated time limit it just stops checking to see if you have the right answer (Because someone could write a infinite loop and be waiting forever). So it never gets to check to see if its the right answer so it just says the program has hit the time limit.

To demonstrate this, enter this code in the website and submit it for your problem. What answer does it give you?

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>

using namespace std;

int main()
{
    while (true)
    {
        int i = 0;
    }
}


I have done a bunch of SPOJ questions and other websites questions like it. On every one of them you need to have your output formatted perfectly (White spaces and line breaks included).

So for your code you need to come up with a better algorithm to get under the time limit and you need to take care of the formatting like naruku mentioned.
Last edited on
At live competitions there is often a preliminary "No - Wrong Answer" followed by a "Yes - Check Whitespace" when a human checks it, but for online judges you have to have spacing exact.
That wasn't really my point. What I meant was exactly what you said, it wouldn't matter because it would say wrong answer if that was the main problem. I am mainly focusing on the algorithm working. I think I have to give this up, I don't want to use too much time on these prime generation algorithms.
closed account (3qX21hU5)
The main reasons why is live competitions are checked by humans whereas online are checked by computers which can't pick up on them easy fixes as easily.

But its good practice though, always have the output exactly how it is suppose to be. If you created a program for a customer you wouldn't say well it's no big deal if this text editor doesn't put a space after each word it outputs ;p

I've always wanted to get into live competitions, but never know where to go to sign up for one. It also seems like you need to find a team to enter the competitions and I barely know a few other people that program :(.
Last edited on
@Zereo there have been many single-person teams not associated with any school, ask competition hosts if you can participate. Generally schools and colleges/universities host these competitions, so contact ones in your area.

@Filiprei: Have you tried measuring how long your program takes to execute? It might be close.
@LB he should find single-core 733 MHz cpu first to get results similar to online ones :)
Pages: 123