Theory: Check a certificate

Be the verifier: check a proposed answer to subset sum.

What to build

A program that checks whether chosen positions of a list form a subset with the target sum.

Requirements

  • The certificate is valid when its indices are all different, all within the list, and the chosen numbers add up to the target.
  • Print valid or invalid.

Input

Line 1: the numbers. Line 2: the target. Line 3: the chosen indices, counted from 0 (may be empty).

Output

One line.

Constraints

At most 30 numbers between −1000 and 1000.

Example

Input:

3 34 4 12 5 2
9
2 4

Output:

valid

Why it works

Checking a certificate takes one pass over it, which is what puts subset sum in NP.

Examples

Example 1 · Input
3 34 4 12 5 2
9
2 4
Expected output
valid
Example 2 · Input
3 34 4 12 5 2
9
0 5
Expected output
invalid

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Use a set to make sure no index repeats, and check each index is inside the list.

Hint 2

An empty line means the empty subset, whose sum is 0.

Solution

Show one correct solution (try it yourself first)
numbers = list(map(int, input().split()))
target = int(input())
chosen = list(map(int, input().split()))
ok = len(set(chosen)) == len(chosen) and all(0 <= i < len(numbers) for i in chosen)
print("valid" if ok and sum(numbers[i] for i in chosen) == target else "invalid")

Lesson: P, NP and NP-completeness →