Problem:


Score : 1200 points

Problem Statement

There are infinitely many cards, numbered 1, 2, 3, ...
Initially, Cards x_1, x_2, ..., x_N are face up, and the others are face down.

Snuke can perform the following operation repeatedly:

Select a prime p greater than or equal to 3. Then, select p consecutive cards and flip all of them.

Snuke's objective is to have all the cards face down.
Find the minimum number of operations required to achieve the objective.

Constraints

1 ≤ N ≤ 100

1 ≤ x_1 < x_2 < ... < x_N ≤ 10^7

Input

Input is given from Standard Input in the following format:

N
x_1 x_2 ... x_N

Output

Print the minimum number of operations required to achieve the objective.

Sample Input 1

2
4 5

Sample Output 1

2

Below is one way to achieve the objective in two operations:

Select p = 5 and flip Cards 1, 2, 3, 4 and 5.

Select p = 3 and flip Cards 1, 2 and 3.

Sample Input 2

9
1 2 3 4 5 6 7 8 9

Sample Output 2

3

Below is one way to achieve the objective in three operations:

Select p = 3 and flip Cards 1, 2 and 3.

Select p = 3 and flip Cards 4, 5 and 6.

Select p = 3 and flip Cards 7, 8 and 9.

Sample Input 3

2
1 10000000

Sample Output 3

4



Sample input:
2
4 5


Sample output:
2

Submission status: Wrong Answer

Solution code:
import itertools
from math import sqrt
def chunk(a):
    i = 0
    res = []
    while i < len(a):
        res.append(a[i])
        while i != len(a) - 1 and a[i + 1] == a[i] + 1:
            i += 1
        res.append(a[i] + 1)
        i += 1
    return res

def augment(g, src, dest):
    o = [None] * len(g)
    q = [(src, src)]
    while q:
        w = q.pop()
        if o[w[0]] is None:
            o[w[0]] = w[1]
            for s in g[w[0]]:
                if o[s] is None:
                    q.append((s, w[0]))
    if not o[dest]:
        return False
    i = dest
    while i != src:
        g[o[i]].discard(i)
        g[i].add(o[i])
        i = o[i]
    return True

def match(a):
    l = {}
    c = 0
    matches = 0
    for i, j in a:
        if i not in l:
            l[i] = c
            c += 1
        if j not in l:
            l[j] = c
            c += 1
    L = {v: k for k, v in l.items()}
    g = [set() for i in range(len(l) + 2)]
    src = len(l)
    dest = src + 1
    for i, j in a:
        g[src].add(l[i])
        g[l[i]].add(l[j])
        g[l[j]].add(dest)
    while augment(g, src, dest):
        matches += 1
    return matches

def prime(n):
    for i in range(2, min(n, int(sqrt(n) + 7))):
        if n % i == 0:
            return False
    return n > 1

def pairs(b):
    c = []
    for i in b:
        for j in b:
            if i % 2 == 0 and j % 2 == 1 and prime(abs(i - j)):
                c.append((i, j))
    return c

n = int(input())
a = list(map(int, input().split()))
b = chunk(a)
r = match(pairs(b))
e = len(list(filter(lambda x: x % 2 == 0, b)))
o = len(b) - e
print(int(r + 2 * ((e - r) // 2 + (o - r) // 2) + 3 * (e % 2)))

Submission status: Wrong Answer

Solution code:
import itertools
from math import sqrt
def chunk(a):
    i = 0
    res = []
    while i < len(a):
        res.append(a[i])
        while i != len(a) - 1 and a[i + 1] == a[i] + 1:
            i += 1
        res.append(a[i] + 1)
        i += 1
    return res

def augment(g, src, dest):
    o = [None] * len(g)
    q = [(src, src)]
    while q:
        w = q.pop()
        if o[w[0]] is None:
            o[w[0]] = w[1]
            for s in g[w[0]]:
                if o[s] is None:
                    q.append((s, w[0]))
    if not o[dest]:
        return False
    i = dest
    while i != src:
        g[o[i]].discard(i)
        g[i].add(o[i])
        i = o[i]
    return True

def match(a):
    l = {}
    c = 0
    matches = 0
    for i, j in a:
        if i not in l:
            l[i] = c
            c += 1
        if j not in l:
            l[j] = c
            c += 1
    L = {v: k for k, v in l.items()}
    g = [set() for i in range(len(l) + 2)]
    src = len(l)
    dest = src + 1
    for i, j in a:
        g[src].add(l[i])
        g[l[i]].add(l[j])
        g[l[j]].add(dest)
    while augment(g, src, dest):
        matches += 1
    res = g[src].copy()
    for i in range(len(g)):
        if dest in g[i]:
            res.add(i)
    return len(g[dest])

def prime(n):
    for i in range(2, min(n, int(sqrt(n) + 7))):
        if n % i == 0:
            return False
    return n > 1
n = int(input())
a = list(map(int, input().split()))
b = chunk(a)
c = []
for i in b:
    for j in b:
        if i % 2 == 0 and j % 2 == 1 and prime(abs(i - j)):
            c.append((i, j))
r = match(c)
ev = len(list(filter(lambda x: x % 2 == 0, b)))
print(int(r + 2 * ((ev - r) // 2 + (len(b) - ev + r) // 2) + 1.5 * (ev % 2 + (len(b) - ev) % 2)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

import itertools
from collections import defaultdict
import numpy as np

N = int(input())
X = set(int(x) for x in input().split())

# 2は素数でないとして扱って
U = 10**7 + 100
is_prime = np.zeros(U,dtype=np.bool)
is_prime[3::2] = 1
for p in range(3,U,2):
    if p*p > U:
        break
    if is_prime[p]:
        is_prime[p*p::p+p] = 0

# imosで値を入れないといけない場所
X ^= set(x+1 for x in X)

EV = set(x for x in X if x%2 == 0)
OD = set(x for x in X if x%2 == 1)

# 1手でとれるペアを見つける：最大マッチング
# 奇点から偶点に辺を貼る
source = -1
sink = -2
graph = defaultdict(dict)
for x in EV:
    graph[x][sink] = 1
    graph[sink][x] = 0
for x in OD:
    graph[source][x] = 1
    graph[x][source] = 0
for x,y in itertools.product(OD,EV):
    if is_prime[abs(x-y)]:
        graph[x][y] = 1
        graph[y][x] = 0

def bfs():
    level = defaultdict(int)
    q = [source]
    level[source] = 1
    d = 1
    while q:
        d += 1
        if level[sink] != 0:
            break
        qq = []
        for x in q:
            for y,cap in graph[x].items():
                if cap==0 or level[y]!=0:
                    continue
                level[y] = d
                qq.append(y)
        q = qq
    return level

def dfs(v,f,level,itr):
    if v == sink:
        return f
    for w,cap in itr[v]:
        if cap==0 or level[w]!=level[v]+1:
            continue
        d = dfs(w,min(f,cap),level,itr)
        if d:
            graph[v][w] += d
            graph[w][v] -= d
            return d
    return 0

def max_flow():
    flow = 0
    while True:
        level = bfs()
        if level[sink] == 0:
            return flow
        itr = {v:iter(graph[v].items()) for v in graph}
        while True:
            f = dfs(source,10**9,level,itr)
            if f == 0:
                break
            flow += f

f = max_flow()

od = len(OD); ev = len(EV)
answer = f
od -= f; ev -= f
answer += 2*(od//2); od %= 2
answer += 2*(ev//2); ev %= 2
if od:
    answer += 3
print(answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

import itertools
from collections import defaultdict
import numpy as np

N = int(input())
X = set(int(x) for x in input().split())

# 2は素数でないとして扱って
U = 10**7 + 100
is_prime = np.zeros(U,dtype=np.bool)
is_prime[3::2] = 1
for p in range(3,U,2):
    if p*p > U:
        break
    if is_prime[p]:
        is_prime[p*p::p+p] = 0

# imosで値を入れないといけない場所
X ^= set(x+1 for x in X)

EV = set(x for x in X if x%2 == 0)
OD = set(x for x in X if x%2 == 1)

# 1手でとれるペアを見つける：最大マッチング
# 奇点から偶点に辺を貼る
source = -1
sink = -2
graph = defaultdict(dict)
for x in EV:
    graph[x][sink] = 1
    graph[sink][x] = 0
for x in OD:
    graph[source][x] = 1
    graph[x][source] = 0
for x,y in itertools.product(OD,EV):
    if is_prime[abs(x-y)]:
        graph[x][y] = 1
        graph[y][x] = 0

def bfs():
    level = defaultdict(int)
    q = [source]
    level[source] = 1
    d = 1
    while q:
        d += 1
        if level[sink] != 0:
            break
        qq = []
        for x in q:
            for y,cap in graph[x].items():
                if cap==0 or level[y]!=0:
                    continue
                level[y] = d
                qq.append(y)
        q = qq
    return level

def dfs(v,f,level,itr):
    if v == sink:
        return f
    for w,cap in itr[v]:
        if cap==0 or level[w]!=level[v]+1:
            continue
        d = dfs(w,min(f,cap),level,itr)
        if d:
            graph[v][w] -= d
            graph[w][v] += d
            return d
    return 0

def max_flow():
    flow = 0
    while True:
        level = bfs()
        if level[sink] == 0:
            return flow
        itr = {v:iter(graph[v].items()) for v in graph}
        while True:
            f = dfs(source,10**9,level,itr)
            if f == 0:
                break
            flow += f

f = max_flow()

od = len(OD); ev = len(EV)
answer = f
od -= f; ev -= f
answer += 2*(od//2); od %= 2
answer += 2*(ev//2); ev %= 2
if od:
    answer += 3
print(answer)

Submission status: Accepted

Solution code:
import itertools
from math import sqrt
def chunk(a):
    i = 0
    res = []
    while i < len(a):
        res.append(a[i])
        while i != len(a) - 1 and a[i + 1] == a[i] + 1:
            i += 1
        res.append(a[i] + 1)
        i += 1
    return res

def augment(g, src, dest):
    o = [None] * len(g)
    q = [(src, src)]
    while q:
        w = q.pop()
        if o[w[0]] is None:
            o[w[0]] = w[1]
            for s in g[w[0]]:
                if o[s] is None:
                    q.append((s, w[0]))
    if not o[dest]:
        return False
    i = dest
    while i != src:
        g[o[i]].discard(i)
        g[i].add(o[i])
        i = o[i]
    return True

def match(a):
    l = {}
    c = 0
    matches = 0
    for i, j in a:
        if i not in l:
            l[i] = c
            c += 1
        if j not in l:
            l[j] = c
            c += 1
    L = {v: k for k, v in l.items()}
    g = [set() for i in range(len(l) + 2)]
    src = len(l)
    dest = src + 1
    for i, j in a:
        g[src].add(l[i])
        g[l[i]].add(l[j])
        g[l[j]].add(dest)
    while augment(g, src, dest):
        matches += 1
    return matches

def prime(n):
    for i in range(2, min(n, int(sqrt(n) + 7))):
        if n % i == 0:
            return False
    return n > 1

def pairs(b):
    c = []
    for i in b:
        for j in b:
            if i % 2 == 0 and j % 2 == 1 and prime(abs(i - j)):
                c.append((i, j))
    return c

n = int(input())
a = list(map(int, input().split()))
b = chunk(a)
r = match(pairs(b))
e = len(list(filter(lambda x: x % 2 == 0, b)))
o = len(b) - e
print(int(r + 2 * ((e - r) // 2 + (o - r) // 2) + 3 * ((e - r) % 2)))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAXN = 1000100;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int N;
int arr[MAXN];
 
struct Dinic {
    struct Edge {
        int to, rev;
        ll c, f;
    };
    vi lvl, ptr, q;
    vector<vector<Edge>> adj;
    Dinic(int n) : lvl(n), ptr(n), q(n), adj(n) {}
    void addEdge(int a, int b, ll c, int rcap = 0) {
        adj[a].push_back({b, sz(adj[b]), c, 0});
        adj[b].push_back({a, sz(adj[a]) - 1, rcap, 0});
    }
    ll dfs(int v, int t, ll f) {
        if (v == t || !f) return f;
        for (int& i = ptr[v]; i < sz(adj[v]); i++) {
            Edge& e = adj[v][i];
            if (lvl[e.to] == lvl[v] + 1)
                if (ll p = dfs(e.to, t, min(f, e.c - e.f))) {
                    e.f += p, adj[e.to][e.rev].f -= p;
                    return p;
                }
        }
        return 0;
    }
    ll calc(int s, int t) {
        ll flow = 0; q[0] = s;
        rep(L,0,31) do { // 'int L=30' maybe faster for random data
            lvl = ptr = vi(sz(q));
            int qi = 0, qe = lvl[s] = 1;
            while (qi < qe && !lvl[t]) {
                int v = q[qi++];
                trav(e, adj[v])
                    if (!lvl[e.to] && (e.c - e.f) >> (30 - L))
                        q[qe++] = e.to, lvl[e.to] = lvl[v] + 1;
            }
            while (ll p = dfs(s, t, LLONG_MAX)) flow += p;
        } while (lvl[t]);
        return flow;
    }
};

bool pr (int x)
{
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0) return false;
    return true;
}

int main()
{
    ios_base::sync_with_stdio(0);

    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> arr[i];
    vector <int> v;
    for (int i = 0; i < N; i++)
    {
        if (i == 0 || arr[i-1] + 1 < arr[i])
            v.push_back(arr[i]);
        if (i == N - 1 || arr[i+1] - 1 > arr[i])
            v.push_back(arr[i]+1);
    }

    int m = v.size();
    Dinic d (m + 2);
    int ne = 0, no = 0;
    for (int i = 0; i < m; i++)
    {
        if (v[i] % 2 == 0)
        {
            d.addEdge (m, i, 1);
            ne++;
        }
        else
        {
            d.addEdge (i, m + 1, 1);
            no++;
        }
    }
    for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++)
        {
            if (v[i] % 2 == 0 && v[j] % 2 == 1)
            {
                if (pr (abs (i - j)))
                    d.addEdge (i, j, 1);
            }
        }

    int r = d.calc (m, m + 1);

    int res = r;
    ne -= r;
    no -= r;
    res += 2 * (ne / 2 + no / 2);
    res += 3 * (ne % 2 + no % 2);
    cout << res << "\n";
}

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

import itertools
from collections import defaultdict
import numpy as np

N = int(input())
X = set(int(x) for x in input().split())

# 2は素数でないとして扱って
U = 10**7 + 100
is_prime = np.zeros(U,dtype=np.bool)
is_prime[3::2] = 1
for p in range(3,U,2):
    if p*p > U:
        break
    if is_prime[p]:
        is_prime[p*p::p+p] = 0

# imosで値を入れないといけない場所
X ^= set(x+1 for x in X)

EV = set(x for x in X if x%2 == 0)
OD = set(x for x in X if x%2 == 1)

# 1手でとれるペアを見つける：最大マッチング
# 奇点から偶点に辺を貼る
source = -1
sink = -2
graph = defaultdict(set)
for x in EV:
    graph[x].add(sink)
for x in OD:
    graph[source].add(x)
for x,y in itertools.product(OD,EV):
    if is_prime[abs(x-y)]:
        graph[x].add(y)
        
def bfs():
    level = defaultdict(int)
    q = [source]
    level[source] = 1
    d = 1
    while q:
        d += 1
        if level[sink] != 0:
            break
        qq = []
        for x in q:
            for y in graph[x]:
                if level[y]!=0:
                    continue
                level[y] = d
                qq.append(y)
        q = qq
    return level

def dfs(v,level,itr):
    if v == sink:
        return True
    for w in itr[v]:
        if level[w]!=level[v]+1:
            continue
        if w in graph[v] and dfs(w,level,itr):
            graph[v].remove(w)
            graph[w].add(v)
            return True
    return False

def max_flow():
    flow = 0
    while True:
        level = bfs()
        if level[sink] == 0:
            return flow
        itr = {v:iter(graph[v]) for v in graph}
        while dfs(source,level,itr):
            flow += 1

f = max_flow()

od = len(OD); ev = len(EV)
answer = f
od -= f; ev -= f
answer += 2*(od//2); od %= 2
answer += 2*(ev//2); ev %= 2
if od:
    answer += 3
print(answer)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

import itertools
from collections import defaultdict
import numpy as np

N = int(input())
X = set(int(x) for x in input().split())

# 2は素数でないとして扱って
U = 10**7 + 100
is_prime = np.zeros(U,dtype=np.bool)
is_prime[3::2] = 1
for p in range(3,U,2):
    if p*p > U:
        break
    if is_prime[p]:
        is_prime[p*p::p+p] = 0

# imosで値を入れないといけない場所
X ^= set(x+1 for x in X)

EV = set(x for x in X if x%2 == 0)
OD = set(x for x in X if x%2 == 1)

# 1手でとれるペアを見つける：最大マッチング
# 奇点から偶点に辺を貼る
source = -1
sink = -2
graph = defaultdict(set)
for x in EV:
    graph[x].add(sink)
for x in OD:
    graph[source].add(x)
for x,y in itertools.product(OD,EV):
    if is_prime[abs(x-y)]:
        graph[x].add(y)
        
def bfs():
    level = defaultdict(int)
    q = [source]
    level[source] = 1
    d = 1
    while q:
        d += 1
        if level[sink] != 0:
            break
        qq = []
        for x in q:
            for y in graph[x]:
                if level[y]!=0:
                    continue
                level[y] = d
                qq.append(y)
        q = qq
    return level

def dfs(v,level,itr):
    if v == sink:
        return True
    for w in itr[v]:
        if level[w]!=level[v]+1:
            continue
        if dfs(w,level,itr):
            graph[v].remove(w)
            graph[w].add(v)
            return True
    return False

def max_flow():
    flow = 0
    while True:
        level = bfs()
        if level[sink] == 0:
            return flow
        itr = {v:iter(graph[v]) for v in graph}
        while dfs(source,level,itr):
            flow += 1

f = max_flow()

od = len(OD); ev = len(EV)
answer = f
od -= f; ev -= f
answer += 2*(od//2); od %= 2
answer += 2*(ev//2); ev %= 2
if od:
    answer += 3
print(answer)