10571 - Products

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:

10571 - Products

Post by dwyak » Wed Oct 15, 2003 7:20 am

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

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Wed Oct 15, 2003 7:38 am

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
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh » Wed Oct 15, 2003 1:30 pm

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
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov » Fri Oct 17, 2003 4:22 pm

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

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

Post by Dmytro Chernysh » Fri Oct 17, 2003 7:04 pm

Unfortunately, yes -- the contest was not true :-(

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

one & only
New poster
Posts: 7
Joined: Mon Oct 13, 2003 8:33 pm
Location: in front of pc (sust, bangladesh)
Contact:

Post by one & only » Fri Oct 17, 2003 7:50 pm

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
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:

10571

Post by Algoritmo » Tue Oct 21, 2003 3:52 pm

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Tue Oct 21, 2003 4:43 pm

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
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh » Tue Oct 21, 2003 6:50 pm

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
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:

Post by Algoritmo » Tue Oct 21, 2003 7:29 pm

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?
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
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh » Tue Oct 21, 2003 7:46 pm

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

Algoritmo
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:

Post by Algoritmo » Wed Oct 22, 2003 2:04 am

Dmytro_Chernysh wrote: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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Oct 22, 2003 7:55 am

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
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:

Post by Algoritmo » Wed Oct 22, 2003 4:21 pm

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Wed Oct 22, 2003 11:50 pm

(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.

Post Reply

Return to “Volume 105 (10500-10599)”