The following test is on Theorem 3 of [][page 86]. The basis idea behind the theorem is the observation that if the sum of the smallest scores is less than , then the teams have lost at least points in the matches among others. Let and . Definition 25.37 loss satisfying, An intervallum satisfying sequence is called iff 25.38 (Lucz, Iványi, Sótér []) A football sequence is loss satisfying. Proof. See the proof of Theorem 3 in []. The following algorithm exploits Lemma . Loss-Test : the number of teams ; Input. : a bounded sequence of length . : a logical variable. Its is , if the input vector is Landau type, and otherwise. Output. : variable; Working variables. : vector of the loss coefficient; : sums of the values, global variables; : binomial coefficients, global variables. Loss-Test FOR TO IF RETURN RETURN 1 2 3 4 5 6 7 8 In worst case runs in time, in best case in time. We remark that is in the following a global Loss-Test variable. The number of loss satisfying sequences will be denoted by . Testing of the draw-loss property In the previous subsection exploited the fact, that scores signalize draws, allowing the Loss-Test improvement of the upper bound of the sum of the scores. Let us consider the loss sequence . made a draw, therefore one is lost and so must hold implying that the sequence is not a football sequence. This example is exploited in the following definition and lemma. Let Definition 25.39 A loss satisfying sequence is called draw loss satisfying, if and only if Lemma 25.40 (Lucz, Iványi, Sótér []) A football sequence is draw loss satisfying. The assertion follows from the fact that small scores and remainders (mod 3) of the scores both signalize lost points and so decrease the upper bound . The following algorithm exploits Lemma . Draw-Loss-Test : the number of teams ; Input. : a loss satisfying sequence of length .
The following test is on Theorem 3 of [][page 86]. The basis idea behind the theorem is the observation that if the sum of the smallest scores is less than , then the teams have lost at least points in the matches among others. Let and . Definition 25.37 An intervallum satisfying sequence is called loss satisfying, iff 25.38 (Lucz, Iványi, Sótér []) A football sequence is loss satisfying. Proof. See the proof of Theorem 3 in []. The following algorithm Loss-Test exploits Lemma . Input. : the number of teams ; : a bounded sequence of length . Output. : a logical variable. Its is , if the input vector is Landau type, and otherwise. Working variables. : variable; : vector of the loss coefficient; : sums of the values, global variables; : binomial coefficients, global variables. Loss-Test 1 2 FOR TO 3 4 IF 5 6 RETURN 7 8 RETURN In worst case Loss-Test runs in time, in best case in time. We remark that is in the following a global variable. The number of loss satisfying sequences will be denoted by . Testing of the draw-loss property In the previous subsection Loss-Test exploited the fact, that scores signalize draws, allowing the improvement of the upper bound of the sum of the scores. Let us consider the loss sequence . made a draw, therefore one is lost and so must hold implying that the sequence is not a football sequence. This example is exploited in the following definition and lemma. Let Definition 25.39 A loss satisfying sequence is called draw loss satisfying, if and only if Lemma 25.40 (Lucz, Iványi, Sótér []) A football sequence is draw loss satisfying. The assertion follows from the fact that small scores and remainders (mod 3) of the scores both signalize lost points and so decrease the upper bound . The following algorithm Draw-Loss-Test exploits Lemma . Input. : the number of teams ; : a loss satisfying sequence of length .
0046_algorithms_of_informatics_volume3.docx