IOI 2019 - Ngày 1

Adnan sở hữu cửa hàng giày lớn nhất ở Baku. Một hộp chứa \(n\) đôi giày vừa được chuyển đến cửa hàng. Mỗi đôi gồm hai chiếc giày có cùng kích cỡ: một chiếc bên trái và một chiếc bên phải. Adnan đã đặt tất cả \(2n\) chiếc giày thành một hàng gồm \(2n\) vị trí, được đánh số từ \(0\) đến \(2n-1\) theo thứ tự từ trái sang phải.

Adnan muốn sắp xếp lại các chiếc giày thành một sắp xếp hợp lệ. Một sắp xếp được gọi là hợp lệ khi và chỉ khi với mỗi \(i\) (\(0 \leq i \leq n-1\)), tất cả các điều kiện sau đều thỏa mãn:

• Các chiếc giày ở vị trí \(2i\) và \(2i+1\) có cùng kích cỡ.
• Chiếc giày ở vị trí \(2i\) là giày trái.
• Chiếc giày ở vị trí \(2i+1\) là giày phải.

Để đạt được mục tiêu này, Adnan có thể thực hiện một dãy các hoán đổi. Trong mỗi lần hoán đổi, anh ta chọn hai chiếc giày liền kề tại thời điểm đó và hoán đổi chúng (nghĩa là nhấc chúng lên và đặt từng chiếc giày vào vị trí cũ của chiếc giày kia). Hai chiếc giày liền kề nhau nếu vị trí của chúng khác nhau một đơn vị.

Hãy xác định số lần hoán đổi ít nhất mà Adnan cần thực hiện để có được một sắp xếp hợp lệ cho các chiếc giày.

Chi tiết cài đặt

Bạn cần cài đặt hàm count_swaps. Trong đề gốc, hàm được mô tả bằng chữ ký int64 count_swaps(int[] S). Với C++, khai báo chính xác trong tệp shoes.h là:

long long count_swaps(std::vector<int> S);

Tệp cài đặt C++ cần bao gồm header:

# include "shoes.h"

• \(S\): một mảng gồm \(2n\) số nguyên. Với mỗi \(i\) (\(0 \leq i \leq 2n-1\)), \(|S[i]|\) là một giá trị khác \(0\) bằng kích cỡ chiếc giày ban đầu được đặt ở vị trí \(i\). Ở đây, \(|x|\) là giá trị tuyệt đối của \(x\), bằng \(x\) nếu \(x>0\) và bằng \(-x\) nếu \(x<0\). Nếu \(S[i]<0\), chiếc giày ở vị trí \(i\) là giày trái; ngược lại, nó là giày phải.
• Hàm cần trả về số lần hoán đổi ít nhất giữa các chiếc giày liền kề để có được một sắp xếp hợp lệ. Giá trị trả về là số nguyên 64 bit.

Các ví dụ

Ví dụ 1

Xét lời gọi dưới đây:

count_swaps([2, 1, -1, -2])

Adnan có thể thu được một sắp xếp hợp lệ sau \(4\) lần hoán đổi.

Chẳng hạn, trước tiên anh ta có thể hoán đổi các chiếc giày \(1\) và \(-1\), tiếp theo \(1\) và \(-2\), sau đó \(-1\) và \(-2\), và cuối cùng là \(2\) và \(-2\). Anh ta sẽ có được sắp xếp hợp lệ \([-2, 2, -1, 1]\). Không thể có được bất kỳ sắp xếp hợp lệ nào với ít hơn \(4\) lần hoán đổi. Do đó, hàm cần trả về \(4\).

Ví dụ 2

Trong ví dụ dưới đây, tất cả các chiếc giày đều có cùng kích cỡ:

count_swaps([-2, 2, 2, -2, -2, 2])

Adnan có thể hoán đổi các chiếc giày ở vị trí \(2\) và \(3\) để thu được sắp xếp hợp lệ \([-2, 2, -2, 2, -2, 2]\), do đó hàm cần trả về \(1\).

Các ràng buộc

• \(1 \leq n \leq 100\,000\).
• Với mỗi \(i\) (\(0 \leq i \leq 2n-1\)), \(1 \leq |S[i]| \leq n\).
• Luôn có thể đạt được một sắp xếp hợp lệ các chiếc giày bằng cách thực hiện một dãy hoán đổi nào đó.
• Giới hạn thời gian: \(1\) giây. Giới hạn bộ nhớ: \(1024\) MiB.

Phân nhóm

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo khuôn dạng sau:

• Dòng \(1\): \(n\).
• Dòng \(2\): \(S[0]\; S[1]\; S[2]\; \ldots\; S[2n-1]\).

Trình chấm mẫu ghi ra một dòng duy nhất chứa giá trị trả về của count_swaps.

Dữ liệu ví dụ 1

2
2 1 -1 -2

4

Dữ liệu ví dụ 2

3
-2 2 2 -2 -2 2

1

Nguồn: Đề thi chính thức IOI 2019, ngày thi 1, bài Shoes (Arranging Shoes); bản tiếng Việt, bản Markdown và gói đính kèm của ban tổ chức.

Thành phố Baku có \(n\) điểm du lịch, được đánh số từ \(0\) đến \(n-1\). Thành phố cũng có \(m\) con đường hai chiều, được đánh số từ \(0\) đến \(m-1\). Mỗi con đường nối hai điểm du lịch khác nhau. Có thể di chuyển giữa hai điểm du lịch bất kì thông qua những con đường này.

Fatima đang lên kế hoạch thăm tất cả các điểm du lịch trong ba ngày. Cô ấy đã quyết định sẽ thăm \(a\) điểm du lịch vào ngày thứ nhất, \(b\) điểm du lịch vào ngày thứ hai và \(c\) điểm du lịch vào ngày thứ ba. Vì vậy, cô ấy sẽ phân hoạch \(n\) điểm du lịch thành ba tập \(A\), \(B\) và \(C\) có kích thước tương ứng là \(a\), \(b\) và \(c\). Mỗi điểm du lịch thuộc đúng một tập, do đó \(a+b+c=n\).

Fatima muốn tìm các tập \(A\), \(B\) và \(C\) sao cho ít nhất hai trong ba tập này liên thông. Một tập \(S\) các điểm du lịch được gọi là liên thông nếu có thể di chuyển giữa hai điểm du lịch bất kì trong \(S\) bằng cách sử dụng các con đường và không đi qua bất kì điểm du lịch nào không thuộc \(S\). Một phân hoạch các điểm du lịch thành các tập \(A\), \(B\) và \(C\) được gọi là hợp lệ nếu thỏa mãn các điều kiện trên.

Hãy giúp Fatima tìm một phân hoạch hợp lệ của các điểm du lịch với \(a\), \(b\) và \(c\) cho trước, hoặc xác định rằng không tồn tại phân hoạch hợp lệ nào. Nếu có nhiều phân hoạch hợp lệ, bạn có thể tìm bất kì phân hoạch nào trong số đó.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau trong C++, với khai báo trong tệp split.h:

std::vector<int> find_split(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q);

• \(n\): số lượng điểm du lịch.
• \(a\), \(b\) và \(c\): kích thước mong muốn của các tập \(A\), \(B\) và \(C\) tương ứng.
• \(p\) và \(q\): các mảng có độ dài \(m\), chứa các điểm đầu mút của các con đường. Với mỗi \(i\) (\(0 \leq i \leq m-1\)), \(p[i]\) và \(q[i]\) là hai điểm du lịch được nối bằng con đường \(i\).
• Hàm cần trả về một mảng có độ dài \(n\). Gọi mảng này là \(s\). Nếu không tồn tại phân hoạch hợp lệ nào, \(s\) phải chứa \(n\) số \(0\). Ngược lại, với \(0 \leq i \leq n-1\), \(s[i]\) phải nhận một trong ba giá trị \(1\), \(2\) hoặc \(3\), cho biết điểm du lịch \(i\) thuộc tập \(A\), \(B\) hoặc \(C\) tương ứng.

Các ví dụ

Ví dụ 1

Xét lời gọi hàm sau:

find_split(9, 4, 2, 3, {0, 0, 0, 0, 0, 0, 1, 3, 4, 5},
                       {1, 2, 3, 4, 6, 8, 7, 7, 5, 6});

Một kết quả đúng có thể trả về là \([1, 1, 3, 1, 2, 2, 3, 1, 3]\). Kết quả này mô tả phân hoạch sau:

• \(A=\{0, 1, 3, 7\}\).
• \(B=\{4, 5\}\).
• \(C=\{2, 6, 8\}\).

Các tập \(A\) và \(B\) liên thông.

Ví dụ 2

Xét lời gọi hàm sau:

find_split(6, 2, 2, 2, {0, 0, 0, 0, 0}, {1, 2, 3, 4, 5});

Không tồn tại phân hoạch hợp lệ nào. Vì vậy, kết quả đúng duy nhất là \([0, 0, 0, 0, 0, 0]\).

Giới hạn

• \(3 \leq n \leq 100\,000\).
• \(2 \leq m \leq 200\,000\).
• \(1 \leq a, b, c \leq n\).
• \(a+b+c=n\).
• Có nhiều nhất một con đường nối mỗi cặp điểm du lịch.
• Có thể di chuyển giữa hai điểm du lịch bất kì thông qua các con đường.
• \(0 \leq p[i], q[i] \leq n-1\) và \(p[i] \neq q[i]\) với mọi \(0 \leq i \leq m-1\).

Giới hạn thời gian: 2 giây. Giới hạn bộ nhớ: 1024 MiB.

Các subtasks

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

• Dòng \(1\): \(n\ m\).
• Dòng \(2\): \(a\ b\ c\).
• Dòng \(3+i\) (với \(0 \leq i \leq m-1\)): \(p[i]\ q[i]\).

Trình chấm mẫu in ra một dòng duy nhất chứa các phần tử của mảng do find_split trả về, cách nhau bởi dấu cách.

Dữ liệu mẫu 1

9 10
4 2 3
0 1
0 2
0 3
0 4
0 6
0 8
1 7
3 7
4 5
5 6

1 1 3 1 2 2 3 1 3

Dữ liệu mẫu 2

6 5
2 2 2
0 1
0 2
0 3
0 4
0 5

0 0 0 0 0 0

Nguồn: Đề thi chính thức IOI 2019, ngày 1, bài “Split the Attractions” (split); bản tiếng Việt, bản Markdown và gói đính kèm của ban tổ chức.

Vào đầu thế kỷ 19, nhà cai trị Hoseyngulu Khan Sardar ra lệnh xây dựng một cung điện trên một cao nguyên nhìn xuống dòng sông rất đẹp. Cao nguyên này được mô hình hóa như một lưới ô vuông \(n \times m\). Các hàng của lưới được đánh số từ \(0\) đến \(n-1\) và các cột được đánh số từ \(0\) đến \(m-1\). Gọi ô tại hàng \(i\) và cột \(j\) (\(0 \leq i \leq n-1\), \(0 \leq j \leq m-1\)) là ô \((i,j)\). Mỗi ô \((i,j)\) có một chiều cao cụ thể, ký hiệu là \(a[i][j]\).

Hoseyngulu Khan Sardar yêu cầu các kiến trúc sư của mình chọn một khu vực hình chữ nhật để xây dựng cung điện. Khu vực này không được chứa bất kỳ ô nào ở các biên của lưới (hàng \(0\), hàng \(n-1\), cột \(0\) và cột \(m-1\)). Do đó, các kiến trúc sư cần chọn bốn số nguyên \(r_1\), \(r_2\), \(c_1\) và \(c_2\) (\(1 \leq r_1 \leq r_2 \leq n-2\) và \(1 \leq c_1 \leq c_2 \leq m-2\)), xác định một khu vực bao gồm tất cả các ô \((i,j)\) sao cho \(r_1 \leq i \leq r_2\) và \(c_1 \leq j \leq c_2\).

Ngoài ra, một khu vực được coi là hợp lệ khi và chỉ khi mỗi ô \((i,j)\) trong khu vực này thỏa mãn điều kiện sau:

• Xét hai ô liền kề với khu vực này trên hàng \(i\) (ô \((i,c_1-1)\) và ô \((i,c_2+1)\)) và hai ô liền kề với khu vực này trên cột \(j\) (ô \((r_1-1,j)\) và ô \((r_2+1,j)\)). Chiều cao của ô \((i,j)\) phải nhỏ hơn hẳn chiều cao của cả bốn ô này.

Nhiệm vụ của bạn là giúp các kiến trúc sư tìm ra số lượng khu vực hợp lệ cho cung điện (nghĩa là số lượng cách chọn \(r_1\), \(r_2\), \(c_1\) và \(c_2\) xác định một khu vực hợp lệ).

Chi tiết cài đặt

Bạn cần cài đặt hàm sau trong C++, với khai báo trong tệp rect.h:

long long count_rectangles(std::vector<std::vector<int> > a);

• \(a\): một mảng hai chiều các số nguyên có kích thước \(n \times m\), biểu diễn chiều cao các ô.
• Hàm phải trả về số lượng khu vực hợp lệ cho cung điện, dưới dạng số nguyên 64 bit.

Ví dụ

Ví dụ 1

Xét lời gọi sau (viết theo cú pháp C++):

count_rectangles({{4,  8,  7,  5,  6},
                  {7,  4,  10, 3,  5},
                  {9,  7,  20, 14, 2},
                  {9,  14, 7,  3,  6},
                  {5,  7,  5,  2,  7},
                  {4,  5,  13, 5,  6}});

Có \(6\) khu vực hợp lệ được liệt kê dưới đây, vì vậy hàm trả về \(6\):

• \(r_1 = r_2 = c_1 = c_2 = 1\).
• \(r_1 = 1\), \(r_2 = 2\), \(c_1 = c_2 = 1\).
• \(r_1 = r_2 = 1\), \(c_1 = c_2 = 3\).
• \(r_1 = r_2 = 4\), \(c_1 = 2\), \(c_2 = 3\).
• \(r_1 = r_2 = 4\), \(c_1 = c_2 = 3\).
• \(r_1 = 3\), \(r_2 = 4\), \(c_1 = c_2 = 3\).

Ví dụ, \(r_1 = 1\), \(r_2 = 2\), \(c_1 = c_2 = 1\) là một khu vực hợp lệ bởi vì cả hai điều kiện sau đây đều thỏa mãn:

• \(a[1][1] = 4\) nhỏ hơn hẳn \(a[0][1] = 8\), \(a[3][1] = 14\), \(a[1][0] = 7\) và \(a[1][2] = 10\).
• \(a[2][1] = 7\) nhỏ hơn hẳn \(a[0][1] = 8\), \(a[3][1] = 14\), \(a[2][0] = 9\) và \(a[2][2] = 20\).

Ràng buộc

• \(1 \leq n,m \leq 2500\).
• \(0 \leq a[i][j] \leq 7\,000\,000\) với mọi \(0 \leq i \leq n-1\), \(0 \leq j \leq m-1\).
• Giới hạn thời gian: 5 giây.
• Giới hạn bộ nhớ: 1024 MiB.

Chấm điểm

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

• Dòng \(1\): \(n\ m\).
• Dòng \(2+i\) (với \(0 \leq i \leq n-1\)): \(a[i][0]\ a[i][1]\ \ldots\ a[i][m-1]\).

Trình chấm mẫu in ra trên một dòng duy nhất giá trị trả về của count_rectangles.

Dữ liệu vào mẫu

6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6

Dữ liệu ra mẫu

6

Nguồn: Đề thi chính thức IOI 2019, ngày thi 1, bài Rectangles (rect); bản tiếng Việt, bản Markdown của ban tổ chức và gói đính kèm chính thức.