10571 - Products

[dwyak]

I got AC during contest, but WA in the problemset.

[Per]

Getting AC in the contest was not very difficult, since the faulty special correction seemed to accept any output. The contest submissions have been rejudged; if you check you will see that lots of people lost their credit for E.

[Dmytro Chernysh]

Year, it was no good on the contest.

But the problem is super -- no one managed to solve on the original contest in St. Petersburg

[Farid Ahmadov]

I also got AC at contest, but now I get WA.
Why? What has happened? It means contest was not true?

[Dmytro Chernysh]

Unfortunately, yes -- the contest was not true

But now WA -- of course It means it's true

[one & only]

In contest time there was a problem in judges checker program so wrong program also get accepted.

Shahriar_monzoor:
Now I find what stupid mistake I made while writing the special judge (Always reading output from judge output).

[Algoritmo]

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:

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

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?

[Adrian Kuegel]

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?

[Dmytro Chernysh]

Adrian, I'm really surprised by your the best solution. Cool !!!

I guess, next time I'll find something more difficult

And to everyone -- I can give you tests if you are really sure that your solution looks correct.

[Algoritmo]

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?

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:

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

Anyway, I didn't implement negative numbers.
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;
}

[Dmytro Chernysh]

I can give you the input/output.
Mail me.

[Algoritmo]

I can give you the input/output.
Mail me.

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.

But if you are talking about another sample output and input, you can post it right here, please.

[Adrian Kuegel]

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?

[Algoritmo]

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.

[Per]

(Assuming you've solved the problem by exhaustive search)
Why would that be so much harder?
Your branching factor would increase by a factor two, which shouldn't be critical for this problem. Otherwise there should just be some minor implementation details.