10571  Products
Moderator: Board moderators
10571  Products
I got AC during contest, but WA in the problemset.

 Experienced poster
 Posts: 146
 Joined: Sat Apr 26, 2003 2:51 am

 Experienced poster
 Posts: 131
 Joined: Thu Apr 17, 2003 8:39 am
 Location: Baku, Azerbaijan

 Experienced poster
 Posts: 146
 Joined: Sat Apr 26, 2003 2:51 am

 New poster
 Posts: 7
 Joined: Mon Oct 13, 2003 8:33 pm
 Location: in front of pc (sust, bangladesh)
 Contact:
10571
I have made a very nice program here. It does even check if answer is correct before printing it. In case it finds inproper answer or no answer, it makes division by zero, so that I would get runtime error.
But still I get WA.
I thought about using negative numbers, as the description does not prohibit them INSIDE the array. The following solution can be only generated with negative numbers and it looks as valid:
The fact is that IF my program were missing those solutions, it would produce a runtime error on purpose (as described in first paragraph). So I did NOT implement solutions with negative numbers.
So it seems to me that the number of spaces are beeing the reason for WA.
Or maybe the new corretion algorithim for this problem is giving only WA answers, as opposing the the one that did only give ACCEPTED.
Any suggestions?
But still I get WA.
I thought about using negative numbers, as the description does not prohibit them INSIDE the array. The following solution can be only generated with negative numbers and it looks as valid:
Code: Select all
01 00 00 09  9
00 1 9 00  9
00 2 3 00  6
02 00 00 03  6

02 02 27 27
So it seems to me that the number of spaces are beeing the reason for WA.
Or maybe the new corretion algorithim for this problem is giving only WA answers, as opposing the the one that did only give ACCEPTED.
Any suggestions?

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
There can't be test cases where negative numbers are required, because all xi and yi are >0, so it is always possible to factorize them into two positive integers.
By the way, the correction program does output accepted, look at the statistic. And in my program I check for the validity of my output and I would divide by zero in case I don't find any solution or my solution doesn't produce the required xi and yi. So I can tell you, that all input test cases have a valid solution.
Have you checked that your program assigns exactly 2 values to each row and each column?
By the way, the correction program does output accepted, look at the statistic. And in my program I check for the validity of my output and I would divide by zero in case I don't find any solution or my solution doesn't produce the required xi and yi. So I can tell you, that all input test cases have a valid solution.
Have you checked that your program assigns exactly 2 values to each row and each column?

 Experienced poster
 Posts: 146
 Joined: Sat Apr 26, 2003 2:51 am
Hey you are incorrect about the negative numbers. The product of 2 negative numbers produces a positive number. Proplem does only state that the PRODUCTS are positive. And if I used negative number 3, I could still use the number +3, if possible. So the using of negative numbers does give more possibilities of solutions (in some cases). One example was described in my previous post, and the imput is:Adrian Kuegel wrote:There can't be test cases where negative numbers are required, because all xi and yi are >0, so it is always possible to factorize them into two positive integers.
By the way, the correction program does output accepted, look at the statistic. And in my program I check for the validity of my output and I would divide by zero in case I don't find any solution or my solution doesn't produce the required xi and yi. So I can tell you, that all input test cases have a valid solution.
Have you checked that your program assigns exactly 2 values to each row and each column?
4
9 9 6 6
2 2 27 27
The only way to satisfy this input is by using negative numbers, as shown in the output below. Note that this output satisfies what the problem definition asks for (x is distint from x):
 01 00 00 09
00 1 9 00
00 2 3 00
02 00 00 03
And about the division by zero, this is EXACTLY what I did and what I described in my previous post. So my program should produce a correct and checked answer or runtime error. It should never produce WA. But when I submit, I just get WA. Below is the function that checks the solution, but it's a bit complicated.
Square[x][0].Num stores the 1st number in col x
Square[x][0].y states in what line the number above is placed
Code: Select all
int Check (void) {
int i, j, p, n;
//remark used ones
for (i=0;i<MAXNUMBER;i++) Used[i]=0;
for (i=0;i<N;i++) {
if (Used[Square[i][0].Num]  Used[Square[i][1].Num]) return 0;
Used[Square[i][0].Num] = Used[Square[i][1].Num] = 1;
if (Square[i][0].Num * Square[i][1].Num != X[i]) return 0;
for (j=0,p=1,n=0;j<N;j++) {
if (Square[j][0].y == i) {
p *= Square[j][0].Num;
n++;
if (Square[j][1].y == i) return 0;
}
else if (Square[j][1].y == i) {
p *= Square[j][1].Num;
n++;
if (Square[j][0].y == i) return 0;
}
}
if (n != 2  p != Y[i]) return 0;
}
return 1;
}

 Experienced poster
 Posts: 146
 Joined: Sat Apr 26, 2003 2:51 am
Are you talking about the input/output that judge uses for testing ? If you are, then I would first ask for the input, because I want to test it.Dmytro_Chernysh wrote:I can give you the input/output.
Mail me.
But if you are talking about another sample output and input, you can post it right here, please.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
You are right, I forgot that each number can used only once and x differs from x.
In your check function you check the results of your vector that contains the 2N values. Perhaps you should also check the values of the matrix that you print (I used a vector myself and had a stupid mistake in the transformation of the vector to the matrix).
And what is your exact output format? Did you write a blank line after each output block as required by the problem statement?
In your check function you check the results of your vector that contains the 2N values. Perhaps you should also check the values of the matrix that you print (I used a vector myself and had a stupid mistake in the transformation of the vector to the matrix).
And what is your exact output format? Did you write a blank line after each output block as required by the problem statement?
After receiving Dmytro_Chernysh's sample input, I sorted out my problem. My mistake was something so slippery that no one did see that my Check() funcion didn't check if Square[x][0].Num == Square[x][1].Num. This pairs of numbers were checked at the same time against all previously checked info, but there was no test to verify if they were distinct from each other. So my program could produce answers were a number appears twice in same column.
In the first version of my program I wanted to make some math so that this was avoited. I gave up the math and forgot to make the checkings with IF statements. Now I got Accepted. Thanks
Imaggine if the judge asked for an input that required negative outputs? Would be so much harder... I think I'm gonna implement negative numbers now just to see judge's answer.
In the first version of my program I wanted to make some math so that this was avoited. I gave up the math and forgot to make the checkings with IF statements. Now I got Accepted. Thanks
Imaggine if the judge asked for an input that required negative outputs? Would be so much harder... I think I'm gonna implement negative numbers now just to see judge's answer.