When reading trough this forum there are a lot of posts/replies of the following form
The test cases for [Problem] are weak
Or if they have done a bit more work:
The test cases for [Problem] are weak Here is a test case where most submissions fail on
I want to make a point to users making such statements: As a setter it is really hard to find such test cases beforehand. It is almost impossible to think about every wrong approach that might be taken. I am going to challenge you by putting you in the role of setter.
For my A&D class we had a practical assignment (in the first semester of last school year, so don’t worry about me cheating). This assignment was based on an algorithm in a research paper, so I will not challenge you to find the algorithm. As far as I know none of the students, including me, found the algorithm of that paper. The algorithm I made did however pass all test cases, and I challenge you to make a test case for which my algorithm would fail.
The problem “you created”
You are given a graph where each vertex has at most 4 neighbors. Find the maximum size of a set such that there is no edge connecting two vertices of that set.
Find the maximum independent set of a degree-4 graph.
The solution “you have come up with”
See https://link.springer.com/article/10.1007/s10878-017-0115-3 for the paper on the algorithm to solve the problem. I do not expect you to be able to read scientific papers.
A setter would not have access to this solution.
Make a test case for which my algorithm will fails. The requirements for test cases are:
- It must be (easily) verifiable by hand.
- You must provide the expected answer
- The input has the form
N M from_1 to_1 from_2 to_2 ... from_N to_N
where N (1\leq N\leq 200) is the number of edges, M (1\leq M\leq 100) the number of vertices (yes, this is backwards compared to what is standard in competitions; but that is how it was phrased for the assignment). and vertices are numbered 1-M. Edges are bidirectional. Self-loops are not allowed.
Full list of requirements of the test case:
- graph must be a simple graph; so no double edges between nodes
- graph may not contain self-loops
- each vertex of the graph must have at most 4 edges
- the number of edges (N) is at most 200 (and at least 1)
- the number of vertices (M) is at most 100 (and at least 1)
- from_i in between 1 and M
- to_i in between 1 and M
Post your test cases below, I will reply with the result of my algorithm; one of
- TLE (executed for more than one second)
- RTE (exception during execution)
And the output of the program in case of an AC or WA. I will grade test cases against the weakest version of my algorithm; although for the assignment I handed in a more robust version. Your goal is for me to receive one of the latter three verdicts on your text case.