DWITE '09 R4 #2 - Verifying Distributed Work

View as PDF

Submit solution

Points: 3
Time limit: 2.0s
Memory limit: 64M

Problem type
DWITE Online Computer Programming Contest, January 2010, Problem 2

Distributed Computing – the use of a large network of computers to perform work together, could be an interesting field of Computer Science. Supercomputers are assembled as such closely connected networks. Alternatively, one could potentially create a larger network, and for cheaper, by letting individual computers contribute over a bigger network, such as the internet (some might have heard of SETI@home). Since individual nodes are someone else's computer that run untrusted code, the results are also not trusted, so some verification needs to take place that the work performed is legit.

The input will contain 5 sets of input, an odd integer 1 \le N \le 7 followed by N integers, 0 \le R \le 100 "results" for the same piece of work from N workers.

The output will contain 5 lines, a decision about the performed work. If the majority of the results agree (that is, they are the same), then it is taken as verified. If there is no major consensus, but 1 result has more matches than any other result, then it is taken as unverified, otherwise the result is unknown. Print just the decision.

Note: the majority (more than half) of 1 is 1, so a single result is always verified.

Sample Input

3
42
42
42
3
42
42
41
5
42
42
50
51
52
3
42
41
40
1
42

Sample Output

verified
verified
unverified
unknown
verified

Problem Resource: DWITE

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

There are no comments at the moment.