APIO 2020 Problems and Solutions – Painting Walls

APIO 2020 Problems and Solutions – Painting Walls
Time limit1500 ms
Memory limit512 MB

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][0]B[j][0], colour B[j][1]B[j][1], \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≤yNM. 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.

Task :

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], [1], [2], [3]]B=[[0,1],[1],[2],[3]]. 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], [1], [2], [3]]) 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][0] \lt B[j][1] \lt \ldots \lt B[j][A[j] - 1] \lt K0≤B[j][0]<B[j][1]<…<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) :

  • No additional constraints.

Sample Grader :

The sample grader reads the input in the following format:

N M K
C[0] C[1] ... C[N-1]
A[0] B[0][0] B[0][1] ... B[0][A[0]-1]
A[1] B[1][0] B[1][1] ... B[1][A[1]-1]
.
.
.
A[M-1] B[M-1][0] B[M-1][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];
}

 39 total views,  4 views today

Post Disclaimer

the above hole problem statement is given by apio2020.id but the solution is generated by the SLTECHACADEMY authority if any of the query regarding this post or website fill the following contact form thank you

Leave a Reply

Your email address will not be published. Required fields are marked *