Pink and Blue
Xenny was a teacher and he had N students. The N children were sitting in a room. Each child was wearing a white T-shirt, with a unique number from the range 1 to N written on it. T-Shirts of pink and blue color were to be distributed among the students by Xenny. This made the students very happy.
Xenny felt that a random distribution of T-Shirts would be very uninteresting. So, he decided to keep an interesting condition:
Every student would get a T-Shirt that is of a different color than his/her friends. That is, if X and Y are friends and X has a Pink T-Shirt, then Y should compulsorily have a Blue T-Shirt, and vice-versa.
Also, Xenny had a belief that Boys should wear blue T-Shirts and Girls should wear pink T-Shirts. If a boy was given a pink T-Shirt or a girl was given a Blue T-Shirt, he called it an inversion.
So, Xenny wanted to distribute T-Shirts in the above-mentioned interesting manner and also wanted to minimize “inversions”. Help him solve the task.
Note: There are no disjoint groups of friends in the room. That is, 2 distinct groups with finite number of students do not exist, but exactly 1 group of students exists in the given situation.
Input
The first line is the number of test cases T.
First line of each test case contains 2 space-separated integers – N and M – number of students and number of friendships present respectively.
Second line consists of N space-separated characters, where ith character denotes the gender of the ith student. B: Boy, G: Girl.
M lines follow. Each line consists of 2 space-separated integers, u and v, showing that u is a friend of v and vice-versa.
Output
If Xenny could distribute the T-Shirts in the desired way, print the minimum number of inversions required.
Else, print -1.
Constraints
1 ≤ N ≤ 105
1 ≤ M ≤ 105
1 ≤ u, v ≤ N
Colors of T-Shirt are represented by uppercase characters ‘B’ and ‘G’
Sample
Input
3
3 2
B G B
1 2
1 3
6 9
B B B G G G
3 5
2 6
4 2
6 3
3 1
3 4
6 1
5 1
1 4
6 5
G G G B G G
6 3
1 3
2 3
4 3
5 3
Output
1
-1
2
Explanation
#1
Student 1 can be given a Blue T-Shirt. Hence, Student 2 and 3 would receive Pink T-Shirts. Since, Student 3 is a Boy and has received a Pink T-Shirt, number of inversions = 1.
input:
10
3 2
B G B
1 2
1 3
6 9
B B B G G G
3 5
2 6
4 2
6 3
3 1
3 4
6 1
5 1
1 4
6 5
G G G B G G
6 3
1 3
2 3
4 3
5 3
91 1026
B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B
41 13
65 24
46 42
61 82
77 24
91 23
57 50
90 20
86 55
85 12
41 23
65 50
46 12
61 76
85 63
57 20
47 9
73 82
45 9
58 19
79 76
44 34
59 26
72 34
71 26
66 48
43 63
64 88
91 80
72 8
71 48
86 8
67 80
43 76
53 20
77 55
51 60
25 49
64 20
62 87
52 63
85 87
22 48
89 12
51 34
77 87
47 40
58 48
41 24
91 13
46 23
57 29
54 87
51 83
58 26
41 34
61 63
85 34
59 19
57 7
62 60
84 9
44 55
59 9
85 60
75 42
56 82
52 24
74 13
46 82
53 29
73 55
69 83
4 12
71 50
85 80
86 60
74 23
53 7
57 60
47 49
71 87
78 49
84 76
67 12
65 12
89 63
59 50
16 29
90 60
75 83
51 88
43 23
91 49
56 13
79 82
59 40
57 8
71 9
53 82
69 40
65 88
77 88
74 42
89 82
77 26
62 9
1 7
69 50
77 76
64 76
61 12
81 55
62 19
58 83
81 50
81 9
43 80
85 9
46 63
79 23
51 48
90 29
64 24
61 87
53 42
77 29
89 50
90 7
71 60
43 12
56 20
89 42
61 49
65 60
72 87
89 29
43 34
59 7
62 48
45 40
74 63
81 40
62 26
77 34
51 19
56 70
52 20
46 70
53 9
68 87
75 20
45 83
52 50
85 76
46 40
61 80
62 70
57 48
81 83
86 88
52 88
58 55
65 48
91 19
57 26
74 55
73 80
54 82
51 76
52 70
41 63
65 42
90 82
71 20
86 20
43 49
67 76
65 76
91 82
89 70
62 29
51 24
75 55
67 82
52 19
44 80
41 82
81 20
73 40
57 87
45 76
86 48
56 60
71 24
53 60
81 34
66 20
47 42
64 12
86 83
67 9
56 34
84 50
62 83
59 63
68 48
64 34
58 24
56 8
79 87
68 40
66 40
68 49
53 87
45 26
73 42
61 23
44 49
72 49
86 7
69 55
59 82
73 12
52 26
46 80
72 23
51 7
57 88
78 13
32 70
71 82
72 88
71 40
77 8
75 24
78 55
41 7
65 23
66 9
72 76
69 26
36 82
69 12
43 9
65 26
59 42
47 7
53 80
54 70
58 13
44 40
74 40
89 80
62 34
79 50
69 48
66 82
44 70
91 70
74 50
68 76
51 12
66 76
67 7
78 20
43 82
59 87
51 50
81 70
64 26
45 88
41 8
56 48
79 63
53 40
81 88
64 48
52 83
58 42
91 8
46 9
43 13
44 9
57 23
47 12
45 12
75 9
58 20
65 87
78 83
74 83
14 24
72 63
86 19
81 26
84 7
79 88
86 34
47 80
62 24
75 48
58 88
85 7
74 7
53 23
57 76
52 60
56 55
53 49
77 20
90 12
64 55
43 7
56 29
89 49
79 34
57 24
39 88
54 80
69 24
43 29
17 34
85 70
65 40
75 49
61 34
75 88
81 13
53 76
66 42
69 34
71 13
15 26
81 60
71 19
86 12
51 26
79 8
73 9
52 29
44 82
41 80
68 88
90 42
73 19
78 8
85 83
66 7
46 49
79 13
77 13
57 63
90 23
54 49
78 50
58 60
59 49
66 12
90 49
90 70
51 87
91 60
31 63
90 13
59 23
45 24
43 40
67 55
64 83
85 8
59 13
72 13
90 55
81 24
45 50
10 20
91 29
73 50
45 82
74 9
47 76
51 9
84 80
73 20
78 19
2 8
74 19
5 13
59 80
75 26
21 42
54 8
52 40
35 80
46 34
79 48
62 88
57 42
54 34
44 12
86 24
74 76
57 12
90 34
69 20
67 60
41 49
44 42
68 63
66 26
90 76
62 13
66 80
61 8
91 88
74 48
62 23
69 88
73 29
78 26
52 9
77 48
74 26
68 9
53 12
77 63
75 19
78 60
52 55
91 20
56 50
61 83
91 48
64 50
37 83
85 50
58 40
56 24
71 34
85 48
68 24
64 40
86 63
69 29
85 26
86 50
90 87
67 20
43 60
73 60
11 23
44 63
47 82
71 49
51 23
75 50
78 29
79 24
68 83
57 82
64 19
54 26
78 7
68 23
89 13
84 42
53 63
81 87
64 9
54 60
72 82
61 70
68 7
47 23
51 80
84 34
58 29
45 19
78 88
44 24
77 70
74 88
72 40
62 63
45 29
68 34
58 7
86 40
61 26
85 13
41 76
74 34
45 55
89 40
44 76
91 76
72 19
72 20
77 49
54 29
43 88
85 19
46 55
51 40
84 13
54 55
78 48
67 13
91 24
65 13
53 34
65 49
90 63
30 60
81 19
43 20
67 19
56 12
89 34
79 83
44 23
68 20
57 9
53 83
43 42
90 48
61 19
68 50
89 83
62 8
45 48
66 87
73 48
56 88
61 13
65 34
38 87
81 48
77 42
58 82
73 26
54 20
52 12
33 76
79 20
27 50
51 49
57 70
47 63
64 7
52 42
61 88
57 40
73 70
75 82
69 8
52 80
67 24
91 55
56 19
72 80
61 50
68 19
66 63
71 8
58 9
41 55
65 82
78 76
79 70
77 82
72 60
53 70
69 60
89 60
84 8
47 87
69 70
75 63
84 48
78 24
44 88
74 24
79 29
71 80
86 23
52 49
41 12
68 13
77 23
57 49
47 34
84 63
84 12
91 12
56 26
46 13
68 26
47 8
64 42
45 8
81 29
43 24
91 34
78 87
85 24
59 29
81 8
86 26
45 34
73 34
91 83
72 9
45 60
67 83
56 76
44 87
41 83
79 26
53 19
51 63
57 80
73 83
54 24
84 88
85 55
46 50
86 9
59 70
66 23
90 8
54 50
81 82
58 49
46 20
71 83
62 82
59 60
66 49
90 50
51 82
52 76
56 7
44 26
74 70
72 42
86 80
43 55
67 50
64 80
65 70
61 24
44 48
59 8
72 48
62 7
67 88
67 8
56 83
72 70
91 7
46 83
71 70
69 82
73 23
54 19
78 12
52 7
74 20
89 20
79 9
77 9
51 42
68 42
47 48
52 13
91 26
56 40
79 55
68 8
66 8
91 40
67 29
91 9
69 13
58 34
41 42
61 55
85 42
66 34
45 20
69 23
58 12
64 87
85 20
68 60
72 55
69 49
75 34
72 29
71 63
77 40
51 13
58 80
73 24
78 23
43 83
85 88
46 60
89 19
65 20
72 7
90 26
54 12
28 55
41 9
79 19
89 7
79 60
64 63
86 70
52 82
67 26
41 19
46 8
61 48
44 8
68 29
47 13
45 13
51 70
84 24
58 23
65 80
65 9
61 42
85 29
77 80
74 82
62 49
86 82
67 70
73 63
44 60
41 70
74 60
84 70
66 70
54 88
67 40
53 8
68 80
75 23
54 7
78 82
84 83
65 29
89 8
81 23
53 50
86 87
57 55
6 19
78 34
41 20
65 55
46 19
84 49
44 7
73 87
54 83
75 8
43 26
75 70
44 29
18 40
65 63
90 83
71 23
43 48
61 29
78 42
69 87
75 12
58 76
64 23
66 60
46 48
59 88
64 13
54 48
71 55
58 63
41 29
65 8
46 26
79
Code Solution:
package practice;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
/*
* vấn đề lúc này là tô màu bị failse
* TH1: 2 học sinh chưa tô màu thì đẩy vào queue
TH2: 2 học sinh tô màu giống nhau => -1
TH3: 2 học sinh tô màu khác nhau => tiếp tục tô tiếp
TH4: học sinh x tô màu, học sinh y chưa tô màu
TH5: học sinh y tô màu, học sinh x chưa tô màu
bài này làm 1 queue thì tràn bộ nhớ vì Integer chỉ khoảng 10^9
còn để “LONG” thì có khi pass, mà dễ bị lỗi memory
làm ok nhất vẫn là 2 queue
Còn 1 testcase dễ xịt đó là khi mà số đảo ngược lớn quá 1 nửa thì đảo ngược lại n-count
Vẫn chưa code tối ưu lắm vì chưa để ý độ phức tạp thuật toán
optimate memory, thí dụ nhưu Integer thì 32 bit, còn boolean thì 2 bit thì phải
Với lại khi code thì viết theo clearn code vào (code sạch) chứ viết theo kiểu xử lý trong hàm main
vs lại khai báo biến static như thế thành ra code bẩn, khai báo vô tội vạ.
Ouput:
1
-1
2
27
221
399
4593
111
19
17179
Ở trong testCase đang thiếu bắt đầu từ test thứ 3 nên ko chạy được solution là đúng
*/
public class PinkAndBlue {
int t, n, m, x, y, front, rear, check, count;
int arrGioiTinh[];
int color[];
int queueStart[];
int queueEnd[];
String s;
Scanner sc = new Scanner(System.in);
/*
* B(nam) – 1 G(0) – nu ao xanh – 1 ao hong – 0
*/
void BFS() {
int tempx = queueStart[front];
int tempy = queueEnd[front];
// front++;
if (arrGioiTinh[tempx] == 1) {
color[tempx] = 1;
color[tempy] = 2;
} else {
color[tempx] = 2;
color[tempy] = 1;
}
while (front != rear) {
tempx = queueStart[front];
tempy = queueEnd[front];
front++;
if (color[tempx] == 0 && color[tempy] == 0) {
queueStart[rear] = tempx;
queueEnd[rear] = tempy;
rear++;
}
if (color[tempx] != 0 && color[tempy] != 0) {
if (color[tempx] == color[tempy]) {
check = -1;
return;
}
}
if (color[tempx] != 0 && color[tempy] != 0) {
if (color[tempx] != color[tempy]) {
continue;
}
}
if (color[tempx] == 0 && color[tempy] != 0) {
color[tempx] = 3 – color[tempy];
}
if (color[tempx] != 0 && color[tempy] == 0) {
color[tempy] = 3 – color[tempx];
}
}
}
void Init() {
check = 0;
count = 0;
front = rear = 0;
arrGioiTinh = new int[n + 1];
color = new int[n + 1];
queueStart = new int[1000000];
queueEnd = new int[1000000];
}
void solution() {
t = sc.nextInt();
for (int tc = 1; tc <= t; tc++) {
n = sc.nextInt();
m = sc.nextInt();
sc.nextLine();
Init();
for (int i = 1; i <= n; i++) {
s = sc.next();
if (s.equalsIgnoreCase(“B”)) {
arrGioiTinh[i] = 1;
}
}
sc.nextLine();
for (int i = 0; i < m; i++) {
x = sc.nextInt();
y = sc.nextInt();
queueStart[rear] = x;
queueEnd[rear] = y;
rear++;
}
BFS();
for (int i = 1; i <= n; i++) {
if (arrGioiTinh[i] == 1) {
if (color[i] == 2) {
count++;
}
}
if (arrGioiTinh[i] == 0) {
if (color[i] == 1) {
count++;
}
}
if (count > n – count) {
count = n – count;
}
}
if (check == -1) {
System.out.println(-1);
} else {
System.out.println(count);
}
}
}
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream(“PinkAndBlue.txt”));
PinkAndBlue p = new PinkAndBlue();
p.solution();
}
}
alexishuuuocn 