Regarding Sample Input

Problems and Contests
#1

I have gone over the rules of the contest but I am quite confused by this question. For sample input, let’s say we are in a bronze problem and the sample input is 5. Are we allowed to print 5. And if we are not, are we allowed to create an algorithm that solely prints us the sample inputs but doesn’t work for the others? Because I have seen previous contestants do this but I am also conflicted about whether it is allowed. For example, imagine I did 2 problems of a contest but then I ran out of time before doing the last one. How would it work?

#2

Yeah, you can do that. I will give you an example problem here, where many people decided to cap the solution, due to the difficulty of this problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=941. Many of the users who passed this contest decided to print “yes” without going for the full-ride solution.

#3

This is a good question – here’s the general consensus:

It is okay to hardcode/print sample cases. We’ve seen this recommended even on USACO guide I believe (feel free to include the citation for the actual webpage if you find it) and for good reason: there are actually surprisingly many cases in which people would have promoted to the next division had they printed the sample case(s) on the problem(s) they didn’t solve.

It is not okay, however, beyond the sample case, to write lookup tables that hardcode answers based on input parameters. For instance, if the answer depends on only two parameters n and k, you should not write the array \text{dp}[N][K] by hand (where capitalization denotes variable upper bounds), or it becomes a lookup table. Instead, you should write an algorithm that actually fills this array and then print the answer as a result of that algorithm. (Of course, it is not necessary to have a correct algorithm: heuristics, not necessarily provable algorithms, only partially/conditionally correct algorithms, slow algorithms, and related are always fine.)

There are also some special interesting cases:

\mathcal{O}(1) solutions written as closed formula math expressions are perfectly acceptable (see “I Would Walk 500 Miles”), since you have still written an “algorithm” (technically a constant time one, which is even better), although this is rare.

Randomized solutions are acceptable if they use a fixed seed (meaning that they produce the same results each time they are run).

The yes/no problem seems to be (fortunately) an isolated case. I’m not sure what they were thinking when they proposed it, but one justification of why simply printing “yes” or “no” was acceptable would be if someone argued they created a (bogus) proof for how the answer is always one or the other and simply wrote the \mathcal{O}(1) “algorithm” for the closed formula.

2 Likes
Cheating policy
#4

You say that lookup tables are not allowed. Does that mean that the following code for MooBuzz is not allowed?

import java.io.*;

public class MooBuzz {
    public static void main(String[] args) throws IOException {
        int[] rem = new int[]{-1, 1, 2, 4, 7, 8, 11, 13};
        BufferedReader in = new BufferedReader(new FileReader("moobuzz.in"));
        PrintWriter out = new PrintWriter(new FileWriter("moobuzz.out"));
        int N = Integer.parseInt(in.readLine());
        out.println(N / 8 * 15 + rem[N % 8]);
        out.close();
    }
}

Thanks,
rayfish

#5

No, because some computation is still being performed.

#6

This doesn’t count as a lookup table. In general, a lookup table takes advantage of the fact that answers can be precomputed and tabulated by an external program at an otherwise non-permissible time complexity and prints them just by looking up the input parameters. In this case, however, you have a mathematical formula based on the structure of the problem, which is completely allowed, even if it were \mathcal{O}(1) (see our math solution to “I Would Walk 500 Miles”).