# APIO 2020 Problems and Solutions – Painting Walls ## Problem :

It has been a while since the last time Pak Dengklek painted the wall on his house, so he wants to repaint it. The wall consists of `NN` segments, numbered from `00 to N - 1N−1`. For this problem, we assume that there are `KK `different colours, represented by an integer from `00 to K - 1K−1` (e.g., red is represented by `00`, blue is represented by `11`, and so on). Pak Dengklek wants to paint the `ii-th` segment of his wall using the colour `C[i]C[i]`.

To paint the wall, Pak Dengklek hires a contractor company with` MM` contractors, numbered from 00 to `M - 1M−1`. Unfortunately for Pak Dengklek, contractors are only willing to paint the colours that they like. Specifically, the jj-th contractor only likes `A[j]A[j]` colours and only wants to paint a segment to be coloured with either of the following colour: colour `B[j]B[j]`, colour `B[j]B[j]`, \ldots…, or colour `B[j][A[j] - 1]B[j][A[j]−1]`.

Pak Dengklek can give several instructions to the contractor company. In a single instruction, Pak Dengklek will give two parameters `xx` and `yy`, where `0 \le x \lt M0≤x<M and 0 \le y \le N - M0≤y≤N−M`. The contractor company will instruct the `((x + l) \bmod M(x+l)modM)-th` contractor to paint the `(y + ly+l)-th` segment, `for 0 \le l \lt M0≤l<M`. If there exists a value of` ll` such that the `((x + l)` `\bmod M(x+l)modM)-th` does not like colour `C[y + l]C[y+l]`, then the instruction is invalid.

Pak Dengklek has to pay for each instruction he gives, thus he would like to know the minimum number of instructions he has to give to paint all segments with their intended colour or identify if it is impossible to do so. The same segment can be painted multiple times, but it must always be painted with its intended colour.

You have to implement `minimumInstructions` function:

• `minimumInstructions(N, M, K, C, A, B)` – This function will be called by the grader exactly once.
• `NN`: An integer representing the number of segments.
• `MM`: An integer representing the number of contractors.
• `KK`: An integer representing the number of colours.
• `CC`: An array of `NN` integers representing the intended colour of the segments.
• `AA`: An array of` MM` integers representing the number of colours that the contractors like.
• `BB`: An array of `MM` array of integers representing the colours that the contractors like.
• This function must return an integer representing the minimum number of instructions Pak Dengklek has to give to paint all segments with their intended colour, or -1−1 if it is impossible to do so.

### Example :

In the first example, `N = 8N=8, M = 3M=3, K = 5K=5, C = [3, 3, 1, 3, 4, 4, 2, 2]C=[3,3,1,3,4,4,2,2], A = [3, 2, 2]A=[3,2,2], B = [[0, 1, 2], [2, 3], [3, 4]]B=[[0,1,2],[2,3],[3,4]]`. Pak Dengklek can give the following instructions:

1. `x = 1x=1, y = 0y=0`. This is a valid instruction since the first contractor can paint the zeroth segment, the second contractor can paint the first segment, and the zeroth contractor can paint the second segment.
2. `x = 0x=0, y = 2y=2`. This is a valid instruction since the zeroth contractor can paint the second segment, the first contractor can paint the third segment, and the second contractor can paint the fourth segment.
3. `x = 2x=2, y = 5y=5`. This is a valid instruction since the second contractor can paint the fifth segment, the zeroth contractor can paint the sixth segment, and the first contractor can paint the seventh segment.

It is easy to see that Pak Dengklek cannot give less than 33 instructions to paint all segments with their intended colour, thus `minimumInstructions(8, 3, 5, [3, 3, 1, 3, 4, 4, 2, 2], [3, 2, 2], [[0, 1, 2], [2, 3], [3, 4]])` should return 33.

In the second example, `N = 5N=5, M = 4M=4, K = 4K=4, C = [1, 0, 1, 2, 2]C=[1,0,1,2,2], A = [2, 1, 1, 1]A=[2,1,1,1], B = [[0, 1], , , ]B=[[0,1],,,]`. Since the third contractor only like colour 33 and none of the segment is to be painted with colour 33, it is impossible for Pak Dengklek to give any valid instruction. Therefore, `minimumInstructions(5, 4, 4, [1, 0, 1, 2, 2], [2, 1, 1, 1], [[0, 1], , , ])` should return `-1−1`.

### Constraints :

For `0 \le k \lt K0≤k<K, let f(k)f(k)` be the number of` jj` such that the `jj-th` contractor likes colour `kk`. For example, if `f(1) = 2f(1)=2`, then there are two contractors who like the colour 11.

• `1 \le N \le 100\,0001≤N≤100000.`
• `1 \le M \le \min(N, 50\,000)1≤M≤min(N,50000).`
• `1 \le K \le 100\,0001≤K≤100000.`
• `0 \le C[i] \lt K0≤C[i]<K.`
• `1 \le A[j] \le K1≤A[j]≤K.`
• `0 \le B[j] \lt B[j] \lt \ldots \lt B[j][A[j] - 1] \lt K0≤B[j]<B[j]<…<B[j][A[j]−1]<K.`
• `Sum of f(k)^2 \le 400\,000f(k)2≤400000.`

### Subtask 1 (12 points) :

• `f(k) \le 1f(k)≤1.`

### Subtask 2 (15 points) :

• `N \le 500N≤500.`
• `M \le \min(N, 200)M≤min(N,200).`
• `Sum of f(k)^2 \le 1\,000f(k)2≤1000.`

### Subtask 3 (13 points) :

• `N \le 500N≤500.`
• `M \le \min(N, 200)M≤min(N,200).`

### Subtask 4 (23 points) :

• `N \le 20\,000N≤20000.`
• `M \le \min(N, 2\,000)M≤min(N,2000).`

### Subtask 5 (37 points) :

``````N M K
C C ... C[N-1]
A B B ... B[A-1]
A B B ... B[A-1]
.
.
.
A[M-1] B[M-1] B[M-1] ... B[M-1][A[M-1]-1]``````

The sample grader prints the value returned by the `minimumInstructions` function.

## Solution :

``````#include "paint.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 200005;
const int mod = 1e9 + 7;

vector<int> use[MAXN]; // which worker can work on the color

int minimumInstructions(
int N, int M, int K, std::vector<int> C,
std::vector<int> A, std::vector<std::vector<int>> B) {
for(int i=0; i<M; i++){
for(auto &j : B[i]){
use[j].push_back(i);
}
}
vector<pi> op(M);
for(int i=0; i<M; i++){
op[i] = pi(-1e9, 0);
}
auto insert = [&](int i, int time){
if(op[i].first + 1 == time) op[i] = pi(time, op[i].second + 1);
else op[i] = pi(time, 1);
if(op[i].second >= M) return 1;
return 0;
};
vector<int> dp(N + 1);
priority_queue<pi, vector<pi>, greater<pi> > pq;
for(int i=0; i<N; i++){
pq.emplace(dp[i], i);
dp[i + 1] = 1e9;
bool good = 0;
for(auto &j : use[C[i]]){
int kappa = (i - j + M - 1) % M;
good |= insert(kappa, i);
}
if(good){
while(sz(pq) && pq.top().second < i + 1 - M) pq.pop();
dp[i + 1] = pq.top().first + 1;
}
}
if(dp[N] > 1e8) return -1;
return dp[N];
}``````

708 total views,  2 views today