Problem A Black Chain Time Limit: 0.1 Second There is a linear chain of n black rings. The weight of every black ring is exactly 1g. We want to genera

Transcription

1 Problem Set Please check that you have 12 problems that are spanned across 32 pages in total (including this cover page). A. Black Chain (2 pages) Korean translation available B. Farm (1 page) Korean translation available C. Lucid Strings (2 pages) D. Matching (2 pages) E. Panokseon (2 pages) Korean translation available F. Parcel (1 page) Korean translation available G. Passport Control (2 pages) Korean translation available H. Path Embedding (2 pages) I. Registration (1 page) Korean translation available J. Sliding Blocks (3 pages) K. Suffix-Freeness (2 pages) L. Three Robots (2 pages) The memory limits for the twelve problems are all the same, 512MB. ICPC 2018

2 Problem A Black Chain Time Limit: 0.1 Second There is a linear chain of n black rings. The weight of every black ring is exactly 1g. We want to generate all possible weights from 1g to ng using this black chain. To do this, we need to remove some single rings from the chain. Since it is very difficult work to remove a single ring from the chain, we want to remove the minimum number of rings as possible. For example, consider the black chain with 7 rings as shown in Figure A.1. If ring 3 is removed, the chain would be separated into a single ring, a chain with rings from 1 to 2, and a chain with rings from 4 to 7 as shown in Figure A.2. Using them we can generate all weights from 1g to 7g as shown in Figure A.3. Figure A.1: A black chain with a length of 7. Figure A.2: A black chain separated into 3 pieces. Weight 1g 2g 3g 4g 5g 6g 7g Rings Configuration [3] [1-2] [3] [1-2] [4-7] [3] [4-7] [1-2] [4-7] Figure A.3: Rings configurations for generating all weights from 1g to 7g. [3] [1-2] [4-7] Given a chain with n black rings, write a program to compute the minimum number of rings which should be removed for generating all weights from 1g to ng. Input Your program is to read from standard input. The input starts with a line containing an integer, n (3 n ), where n is the number of rings in the black chain. Output Your program is to write to standard output. Print exactly one line which contains the minimum number of rings which should be removed for generating all weights from 1g to ng. ICPC 2018 Problem A: Black Chain

3 The following shows sample input and output for two test cases. Sample Input 1 Output for the Sample Input Sample Input 2 Output for the Sample Input ICPC 2018 Problem A: Black Chain

4 Problem A Black Chain 제한시간 : 0.1 초 n개의블랙고리가일렬로연결된체인이있다. 블랙고리하나는무게가정확히 1g 이다. 이고리들을이용하여 1g 부터 ng 까지가능한모든무게를생성하려고한다. 이를위해고리를일부풀어야하는데, 고리를푸는데힘이들어최소개의고리만풀기를원한다. 예를들어아래의그림 A.1 처럼 7 개의고리로구성된블랙체인이있다고하자. 이체인에서 3 번고리하나를풀어내면그림 A.2 처럼 3 번고리 1 개와두개의체인 (1~2 번고리가연결된체인과 4~7 번고리가연결된체인 ) 으로분리된다. 이들을이용하면그림 A.3 처럼 1g 부터 7g 까지의모든무게를생성할수있다. 그림 A.1: 길이가 7 인블랙체인 그림 A.2: 3 개로분리된블랙체인 무게 1g 2g 3g 4g 5g 6g 7g 고리 구성 [3] [1-2] [3] [1-2] [4-7] [3] [4-7] [1-2] [4-7] [3] [1-2] [4-7] 그림 A.3: 1g 부터 7g 까지가능한모든무게를생성하는고리구성 n 개의고리가연결된체인이주어져있을때, 1g 부터 ng 까지가능한모든무게를생성하기위해 풀어야할고리의최소개수를구하는프로그램을작성하시오. ICPC 2018 Problem A: Black Chain

5 Input 입력은표준입력을사용한다. 첫번째줄에블랙고리의개수를나타내는양의정수 n (3 n ) 이주어진다. Output 출력은표준출력을사용한다. 1g 부터 ng 까지가능한모든무게를생성하기위해풀어야할고리의 최소개수를출력한다. 다음은두테스트케이스에대한입출력예이다. Sample Input 1 Output for the Sample Input Sample Input 2 Output for the Sample Input ICPC 2018 Problem A: Black Chain

6 Problem B Farm Time Limit: 0.1 Second Sangbae raises sheep and goats on his farm where each of the number of sheep and the number of goats is at least one. Sheep and goats eat same food, and every day each sheep eats exactly a grams of food and each goat eats exactly b grams of food. Sangbae checks every day how many sheep and goats are in the farm. It was not easy to count them separately because they were moving around. He counted the total number of sheep and goats instead. Also he checked total amount of food that sheep and goats have eaten yesterday. From these values, he wants to find the number of sheep and the number of goats. Given a, b, n (total number of sheep and goats), w grams of food that both sheep and goats have eaten yesterday, write a program to find the number of sheep and the number of goats. Input Your program is to read from standard input. The input consists of single line containing four integers, a, b, n, and w where 1 a 1,000, 1 b 1,000, 2 n 1,000, 2 w 1,000,000. Output Your program is to write to standard output. Print exactly one line which contains both the number of sheep and the number of goats. If there are two or more feasible solutions or there is no feasible solution, print -1. The following shows sample input and output for three test cases. Sample Input 1 Output for the Sample Input Sample Input 2 Output for the Sample Input Sample Input 3 Output for the Sample Input ICPC 2018 Problem B: Farm

7 Problem B Farm 제한시간 : 0.1 초 목장주인인상배는양과염소들을같이기르고있다. 기르는양과염소는각각한마리이상이다. 양과염소는같은사료를먹고, 양한마리는하루에사료를정확히 a 그램먹고, 염소한마리는하루에정확히 b 그램을먹는다고한다. 상배는매일아침양과염소가각각몇마리인지를확인하는작업을한다. 양과염소가각각몇마리인지확인할때, 양과염소들이돌아다녀서정확하게그수를구하는것이쉽지않았다. 대신에양과염소가전체몇마리인지를확인하고, 또양과염소가어제하루동안소비한전체사료의양만확인해서양과염소가각각몇마리인지를알려고한다. 상배가확인한양과염소전체가 n마리이고, 어제하룻동안소비한전체사료의양이 w그램일때, 양과염소가각각몇마리인지를구하는프로그램을작성하시오. Input 입력은표준입력을사용한다. 첫번째줄에네정수 a, b, n, w 가한줄에주어진다. 1 a 1,000, 1 b 1,000, 2 n 1,000, 2 w 1,000,000 이다. Output 출력은표준출력을사용한다. 첫번째줄에양의수와염소의수를각각출력한다. 만약가능한 해가두개이상있는경우혹은가능한해가없을경우, -1 을출력한다. 다음은세테스트경우에대한입출력예이다. Sample Input 1 Output for the Sample Input Sample Input 2 Output for the Sample Input Output for the Sample Input 2 Sample Input ICPC 2018 Problem B: Farm

8 Problem C Lucid Strings Time Limit: 0.5 Seconds Consider a string on English alphabet of 26 lowercase letters. If the length of this string can be represented as the product of two positive integers, k ( 2) and c, the string can be decomposed into k substrings of the same length c. If the substrings are pairwise distinct, the string is called a k-lucid-string (shortly k-ls ). Here a substring is a contiguous sequence of characters within a string. For example, for string ababca of length 6, there are three cases for k to consider: k = 2, 3, 6. For k = 2, the string is decomposed into two substrings, aba and bca, of length 3. Since the two substrings are pairwise distinct, the string is a 2-LS. For k = 3, the string is decomposed into three substrings of length 2. But ab appears as substring more than once, and thus the string is not a 3-LS. For k = 6, the string is decomposed into six substrings of length 1. But a and b appear as substring more than once, and thus the string is not a 6-LS. Consider the problem of computing all substrings of a given input string which are k-ls s. For example, consider input string ababca for k = 2. Since each of substrings ab, ba, ab, bc, and ca of ababca can be decomposed into two pairwise distinct substrings of length 1, it is a 2-LS. Substrings babc and abca are 2-LS s because each of them can be decomposed into two pairwise distinct substrings of length 2. Since input string itself is a 2-LS, ababca has 8 substrings which are 2-LS s. Note that two substrings of input string are considered independently for k-ls candidates if they differ in position in input string. Given a string S of length n and an integer k, write a program to compute the number of the substrings of S which are k-ls s. Input Your program is to read from standard input. The input starts with a line containing two integers, n (3 n 40,000) and k (2 k 40,000), where n is the length of input string and k is the number of substrings of the same length for each k-ls. You can assume that k n. In the following line, a string of length n is given. Output Your program is to write to standard output. Print exactly one line which contains the number of the substrings of input string which are k-ls s. The following shows sample input and output for two test cases. Sample Input 1 Output for the Sample Input ababca ` ICPC 2018 Problem C: Lucid Strings

9 Sample Input 2 Output for the Sample Input ababca ICPC 2018 Problem C: Lucid Strings

10 Problem D Matching Time Limit: 1 Second In the geometric matching problem, two geometric objects A and B are given, and the goal is to find an optimal transformation for B such that the transformed copy of B is as close to A as possible. Usually, the distance between A and a transformed copy of B is measured by a prescribed distance function, and one wants to minimize it over all possible transformations. Here, we consider a simple variant of the geometric matching problem. Specifically, we assume that two input objects A and B are finite sets of points in the plane and allowed transformations for B are only translations in the plane. A translated copy of B by a two-dimensional vector v = (v x, v y ) is defined to be B + v = {(x + v x, y + v y ) (x, y) B}. For any two-dimensional vector v, our distance function f(v) measures the smallest possible perpendicular distance between two parallel lines that contain all points of A and B + v in between. That is, we want to find an optimal two-dimensional vector v such that f(v) is minimized. Consider an example of A = {(0,0), (0,100)} and B = {(23,56), (123,56)}, depicted in the above figure (a) in which the points in A are colored red while those in B are blue. Then, consider a specific vector v = ( 73, 6). The above figure (b) shows A and B + v, and two parallel lines whose perpendicular distance is d, which is exactly d = One can verify that these two parallel lines contain all points of A and B + v in between and have the smallest possible perpendicular distance. Hence, we have f(v) = d. Further, this is the minimum possible value of f(v) over all two-dimensional vectors. Therefore, v = ( 73, 6) is an optimal translation vector such that f(v) is minimized. Given two sets of points in the plane, A and B, write a program that finds an optimal translation vector v for B such that f(v) is minimized and outputs the value of f(v). ICPC 2018 Problem D: Matching

11 Input Your program is to read from standard input. The input starts with a line containing two integers, n (1 n 200,000) and m (1 m 200,000), where n is the number of points in the set A and m is the number of points in the set B. In each of the following n lines, the coordinates of each point in A are given by two integers separated by a space. Again, in each of the following m lines, the coordinates of each point in B are given by two integers separated by a space. The coordinates of all points given in the input range from 10 6 to 10 6, inclusively. Note that multiple points with the same coordinates can be given in each of A and B. Output Your program is to write to standard output. Print exactly one line which contains a real number z that represents the value of f(v) for an optimal two-dimensional vector v such that f(v) is minimized. The output z should be in the format that consists of its integer part, a decimal point, and its fractional part, and should satisfy the condition that f(v) 10 6 < z < f(v) The following shows sample input and output for two test cases. Sample Input 1 Output for the Sample Input Sample Input 2 Output for the Sample Input ICPC 2018 Problem D: Matching

12 Problem E Panokseon Time Limit: 1 Second Admiral Yi Sun-sin ordered to build the special battleship, called Panokseon, to prepare the war in the Joseon Dynasty. To test its performance, he decided to have a battleship race with Joseon navy soldiers. Admiral Yi numbered n soldiers from 1 to n, lined up in that order. He assigned the soldiers to the ships such that soldiers assigned to a ship have consecutive numbers, and the sum of their weights must not exceed the weight limit W of the ship. He did not mind the number of ships used for this assignment since he built enough number of ships. The point he cared about is the fairness of the race. He thought the fairness would be guaranteed if the soldiers weight sums are well balanced over the ships. In other words, soldiers should be evenly assigned to the ships for their weights. More precisely, the emptiness of a ship that one or more soldiers are assigned to is defined as the square of the difference of W and the sum of weights of the soldiers of the ship. The unfairness of an assignment is the maximum emptiness of the ships in the assignment. Admiral Yi wanted to guarantee the high fairness by such an assignment for the race whose unfairness is minimum, i.e., the fairness is maximized. For instance, we are given a weight sequence (10, 20, 30) of 3 soldiers with W = 50. An assignment {[1], [2], [3]} that each soldier is assigned to an individual ship has the unfairness value of max {(50 10) 2, (50 20) 2, (50 30) 2 } = We can also consider two other assignments using two ships, {[1, 2], [3]} and {[1], [2, 3]}, whose unfairness values are max{(50 30) 2, (50 30) 2 } = 400 and max{(50 10) 2, (50 50) 2 } = 1600, respectively. All three soldiers cannot be assigned to one ship because their weight sum is over W = 50. Thus the minimum unfairness value is 400, and the fairest assignment is that the first two soldiers are assigned to the one ship and the third soldier to the other ship alone. Given a weight limit W of the battleship and the weights of n soldiers numbered 1 to n, write a program to find a fairest assignment for the battleship race. Input Your program is to read from standard input. The input starts with a line containing two integers, W (1 W 10 9 ) and n (1 n 500,000), where W is the weight limit of the battleship and n is the number of Joseon navy soldiers. The second line contains a sequence of n weights of soldiers, ordered by the soldiers numbers from 1 to n. The weights are integers between 1 and W, inclusively. You can assume that no single soldier weighs more than W. Output Your program is to write to standard output. Print exactly one line which contains the minimum unfairness for the input. ICPC 2018 Problem E: Panokseon

13 The following shows sample input and output for two test cases. Sample Input 1 Output for the Sample Input Sample Input 2 Output for the Sample Input ICPC 2018 Problem E: Panokseon

14 Problem E Panokseon 제한시간 : 1 초 이순신장군은판옥선이라불리는특별한전함을전쟁에대비해만들었다. 판옥선의성능을평가하기위해, 조선수병들로하여금경주를하도록할계획이다. n 명의수군들을 1 번부터 n번까지차례로번호를매긴후, 각전함에연속된번호의수군들의몸무게의합이전함의중량한계 W를넘지않도록배정하려고한다. 즉, 한전함에배정된수군들은연속된번호를가져야하며, 그들의몸무게합이 W 이하여야한다. 충분히많은전함을준비했기때문에, 한명이상의수군이배정된전함의수는중요하지않고, 경주의공정성, 즉배정의공정성이더중요하다. 이순신장군은전함별수군들의몸무게합의차이가작을수록더공정한배정이라고판단하였다. 보다명확히설명하면다음과같다. 한명이상의수군이배정된전함의여유중량 (emptiness) 값은 W와그전함에배정된수군들의몸무게합의차이를제곱한값으로정의한다. 배정의불공정성 (unfairness) 값은배정에사용된군함의여유중량값들중에서최대값으로정의한다. 이순신장군은불공정성이가장작은배정이가장공정한배정이라고생각했다. 예를들어, 3 명의수군의몸무게가차례대로 10, 20, 30이고, W = 50 인경우를고려해보자. 가능한배정중하나인 {[1], [2], [3]} 은하나의전함에수군을한명씩배정하는것이다. 이배정의불공정성은 max {(50 10) 2, (50 20) 2, (50 30) 2 } = 1600이다. 다른두가지배정 {[1, 2], [3]} 과 {[1], [2, 3]} 도가능한데, 두배정의불공정성은각각 max{(50 30) 2, (50 30) 2 } = 400 과 max{(50 10) 2, (50 50) 2 } = 1600이된다. 그러나 3 명의수군들의몸무게합이 W = 50보다크기때문에모두한전함에배정할수는없다. 따라서, 불공정성의최소값은 400이되어 {[1, 2], [3]} 이가장공정한배정이된다. 이배정은 1 번, 2 번수군을같은전함에, 3 번수군은다른전함에배정하는것이다. 여러분은전함의한계중량 W 와 1 번부터 n 번수군까지몸무게가차례로주어질때, 가장공정한 배정을찾는프로그램을작성해야한다. ICPC 2018 Problem E: Panokseon

15 Input 입력은표준입력을사용한다. 첫번째줄에는전함의한계중량 W (1 W 10 9 ) 와수군의수 n (1 n 500,000) 이공백을사이에두고차례로주어진다. 두번째줄에는수군의몸무게가 1번수군부터 n번수군의순서로차례로주어진다. 수군몸무게는 1 이상 W 이하의정수이다. 수군한명의몸무게는 W보다크지않다. Output 출력은표준출력을사용한다. 주어진입력에대한배정의불공정성의최소값을한줄에출력한다. 다음은두테스트경우에대한입출력예이다. Sample Input 1 Output for the Sample Input Sample Input 2 Output for the Sample Input ICPC 2018 Problem E: Panokseon

16 Problem F Parcel Time Limit: 4 Seconds ICPC (International Collegiate Parcel Center) is leading the event for free international delivery of parcels among world-wide collegiate students. The requirements for free delivery are that the parcel should consist of four items and the sum of weights of them should be equal to the certain integral weight w gram. Chansoo in Pusan National University has a lot of items to send to his friend Soowhan in Imperial College in London, and the weights of the items are all different. Since this is a limited-time event, Chansoo wants to check as fast as possible whether he has four items satisfying to the condition or not. Assume that the weights of the items are exact positive integer grams, and remember they are all distinct. In other words, Chansoo wants to select a subset B with four elements ( B = 4) from a set A of n (n 4) distinct positive integers, and wants to check whether b = w or not. b B Given a target weight w and a set A of n distinct positive integers, write a program to print YES if such subset B exists, and NO, otherwise. Input Your program is to read from standard input. The input starts with a line containing two positive integers w and n separated by a space, where w (10 w 799,994) is the target weight and n (4 n 5,000), the number of elements of A. In the following line, n positive integers, a i A (1 i n), are given separated by a space. Each element a i is in the range of 1 and 200,000 inclusively (1 a i 200,000). Output Your program is to write to standard output. Print exactly one line which contains YES or NO according to the requirements above. The following shows the sample input and output for two test cases. Sample Input 1 Output for the Sample Input NO Sample Input 2 Output for the Sample Input YES ICPC 2018 Problem F: Parcel

17 Problem F Parcel 제한시간 : 4 초 국제대학소포센터 (ICPC: International Collegiate Parcel Center) 는전세계대학생들을대상으로소포 무료배송이벤트를진행하고있다. 무료배송조건은보낼소포가물품 4 개로구성되어야하며 이들물품의무게합이정확히정해진정수무게 w 그램이어야한다는것이다. 부산대학교에있는찬수는영국왕립대학에있는수환에게보낼물품이매우많이있는데, 각물품의무게 ( 모두정수그램 ) 는모두다르다. 이이벤트는한시적으로진행되는이벤트이기때문에찬수는자신이보낼물품중에서이조건을만족하는물품 4개가있는지가능하면빨리알아내고싶다. 다시말해서서로다른 n(n 4) 개의정수로이루어진집합 A에서 4개의원소만꺼내어만든부분집합 B( B = 4) 가 b B b = w 조건을만족하는지판단하려고한다. 주어진 w 와 A 에대해서, 위조건을만족하는부분집합 B 가존재하면 YES 를, 아니면 NO 를출력하는 프로그램을작성하시오. Input 입력은표준입력을사용한다. 입력의첫줄에는무게 w(10 w 799,994) 와 A의원소개수 n(4 n 5,000) 이공백으로분리되어주어진다. 다음줄에는 A의원소인 n개의정수 a i A(1 i n) 가공백으로분리되어주어진다. 각원소 a i 는 1이상 200,000이하이다 (1 a i 200,000). Output 출력은표준출력을사용한다. 문제의조건에따라 YES 나 NO 를한줄에출력한다. 다음은두테스트케이스에대한입출력예이다. Sample Input 1 Output for the Sample Input NO Sample Input 2 Output for the Sample Input YES ICPC 2018 Problem F: Parcel

18 Problem G Passport Control Time Limit: 0.2 Seconds Figure G.1: N passengers should be controlled at one of the passport control offices {Q k }. All N passengers wait in one immigration queue for the passport control in the order of [1, 2, 3,, N 1, N] as shown in Figure G.1. Each passenger is required to be checked at one of k passport control queues. After completing the passport control, the passenger exits from the airport through the exit gate (Exit as shown in Figure G.1). The initial order of the entrance queue, [1, 2, 3,, N 1, N] can be changed to a shuffled order, [π 1, π 2, π N 1, π N ] at the exit gate. You must determine if the exiting order [π 1, π 2, π N 1, π N ] is possible using k parallel passport control queues. Let us explain with an example. In the case of N = 3 and k = 2, the exit orders [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2] are all possible, but [3, 2, 1] is not. Given an exit order [π 1,, π N ] as an input, write a program to print YES if the exit order is possible, or NO if not. Note that passengers are not allowed to change their order in passport control queues and each control queue is long enough to keep all N passengers. Input Your program is to read from standard input. The standard input consists of two lines. The first line gives two integers, N and k, where N is the number of passengers and k is the number of passport control queues. Note that 2 k N 100. The second line gives [π 1,, π N ], an exit order of the passengers from the airport. Output Your program is to write to standard output. Print the string YES if the exit order is possible or NO otherwise. ICPC 2018 Problem G: Passport Control

19 The following shows sample input and output for two test cases. Sample Input 1 Output for the Sample Input NO Sample Input 2 Output for the Sample Input YES ICPC 2018 Problem G: Passport Control

20 Problem G Passport Control 제한시간 : 0.2 초 그림 G.1: N 명의입국승객은 k 개의여권심사창구 {Q k } 중하나를반드시거쳐야한다. N명의입국승객이여권심사를위하여그림 G.1 과같이입국대기줄에서 [1, 2,, N 1, N] 순서로기다리고있다. 입국승객은준비된 k개의여권심사창구중하나를통과한뒤공항을빠져나갈수있다. 입국할때의줄선승객의순서를 [1, 2,, N 1, N] 이라고할때 k개의여권심사창구를통과하여입국장을빠져나가는순서 [π 1, π 2, π N 1, π N ] 는처음과달라질수있다. k개여권심사창구가준비되어있을때, 이입국장을빠져나가는순서가가능한순서인가를계산해야한다. 예를들어설명해보자. 만일 N = 3, k = 2라고할때입국장을빠져나가는순서중 [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2] 는가능하지만 [3, 2, 1] 은불가능하다. 여러분은입국장을빠져나가는순서 [π 1,, π N ] 가입력으로주어질때, 이순서가가능하면 YES 를, 불가능하면 NO 를출력해야한다. 단, 특정큐에줄을선상황에서는승객들의순서를임의로바꿀수는없다. 그리고각여권심사창구에준비된큐는 N명승객이모두들어올정도로충분히크다고가정한다. Input 입력은표준입력을사용한다. 첫번째줄에는두개의정수 N 과 k 가주어진다. N은입국승객의수이며 k는여권심사창구의수이다. 단, 2 k N 100 이다. 그리고두번째줄에는승객이입국장을빠져나가는순서 [π 1,, π N ] 가주어진다. ICPC 2018 Problem G: Passport Control

21 Output 출력은표준출력을사용한다. 입력으로주어진순서 [π 1,, π N ] 대로입국장을빠져나가는것이 가능하면 YES 를출력하고, 아니면 NO 를출력해야한다. 다음은두테스트경우에대한입출력예이다. Sample Input 1 Output for the Sample Input NO Sample Input 2 Output for the Sample Input YES ICPC 2018 Problem G: Passport Control

22 Problem H Path Embedding Time Limit: 1 Second Given a guest graph G and a host graph H with the same number of vertices, the graph embedding problem is to find a one-to-one correspondence σ from the vertex set V(G) of G to the vertex set V(H) of H, along with a mapping from each edge in the edge set E(G) of G to a path in H. Many applications can be modeled as graph embedding. In particular, graph embedding has long been used to model the problem of arranging a parallel algorithm in a parallel architecture. The quality of an embedding can be measured by certain cost criteria. Among others, the dilation is the maximum of the lengths of paths mapped by all edges of G. If the host graph H is a tree in which any two vertices are joined by a unique path, an edge (u, v) of G is necessarily mapped to the unique path in H joining σ(u) and σ(v). So, the dilation of an embedding σ of graph G into tree H can be simply represented as max d H(σ(u), σ(v)), where d H (σ(u), σ(v)) denotes the distance between σ(u) and σ(v) in H. The (u,v)εe(g) dilation of the embedding shown in Figure H.1 below, for example, is three. Figure H.1: An embedding σ of a path graph into a tree both with 12 vertices, where σ can be written in two-line notation ( ), meaning σ(1) = 7, σ(2) = 6, σ(3) = 5,, and σ(12) = We are concerned with the problem of embedding of a path graph into a tree, where a path graph is a tree that has at most two leaves. Given an embedding of a path graph into a tree, your job is to write an efficient program that finds the dilation of the embedding. Input Your program is to read from standard input. The first line contains an integer, n, representing the number of vertices of the host graph H which forms a tree, where 2 n 100,000. It is followed by n 1 lines, each contains two positive integers u and v that represent an edge between vertex u and vertex v of H. It is assumed that the vertices are indexed from 1 to n. The last line contains an ordering σ(1), σ(2),, σ(n) of the vertices of H, which represents the embedding of a path graph G into H, where V(G) = {1, 2,, n} and E(G) = {(u, v) v = u + 1}. ICPC 2018 Problem H: Path Embedding

23 Output Your program is to write to standard output. Print exactly one line which contains an integer. The integer should be the dilation of the given embedding if the dilation is three or less; the integer should be 99 otherwise. The following shows sample input and output for three test cases. Sample Input 1 Output for the Sample Input Sample Input 2 Output for the Sample Input Sample Input 3 Output for the Sample Input ICPC 2018 Problem H: Path Embedding

24 Problem I Registration Time Limit: 1 Second Print out your team s DOMJudge account ID and password. Input No input is given for this problem. Output Your program is to write to standard output. Print exactly two lines. The first line should contain your DOMJudge account ID, and the second line should contain your DOMJudge account password. The following shows sample input and output, where the account ID is team123 and the password is passw0rd. Notice that no input is given. Sample Input Output for the Sample Input team123 passw0rd ICPC 2018 Problem I: Registration

25 Problem I Registration Time Limit: 1 Second 자신이속해있는팀의 DOMJudge ID 와패스워드를그대로출력하는프로그램을작성하시오. Input 이문제는입력이없다. Output 표준출력 (standard output) 으로출력해야한다. 첫줄에 DOMJudge ID, 둘째줄에패스워드를출력한다. 다음은 ID 가 team123 번, 패스워드가 passw0rd 인경우의입출력예제이다. 참고로입력이없는것에주의한다. Sample Input Output for the Sample Input team123 passw0rd ICPC 2018 Problem I: Registration

26 Problem J Sliding Blocks Time Limit: 1 Second When rectangular blocks, which are all parallel to the xy-axis, are given one by one in the plane, each block moves along the specified direction from the specified starting location. The movement of a block consists of two phases. For the first phase, each block moves from the specified location along the given direction which is always left-downward. While moving if it hits either the x-axis, the y-axis, or another block it changes its direction and enters the second phase. More specifically, if the bottom part of the moving block hits the x-axis or another block its moving direction changes leftward and it enters the second phase. Similarly, if the left part of the moving block hits the y-axis or another block its moving direction changes downward and it enters the second phase. The second phase movement consists of repeating move-left and move-down (or move-down and moveleft ) as long as the block can move. Once the block enters the second phase, it keeps moving in the same direction as farther as possible. If it is blocked either by the xy-axis or by another block it changes its moving direction and continues moving. A block s location is denoted by the (x, y) coordinate of its lower-left corner point. Figure J.1 shows an example how a block moves. The size of each block is shown in the figure. Suppose seven blocks (A to G, all are colored green) are already placed and block H has the turn to move. The dotted rectangle indicates the starting and the intermediate locations of block H (orange block at final position). The red lines indicate the moving path. As Figure J.1 shows it first moves left-downward (in the first phase) until it hits block C. Then the direction changes leftward, which means it enters the second phase of movement, and continues moving as farther as possible until it hits block F. Then it continues moving in the second phase by changing directions until it can no longer move. Figure J.1 How to treat some special cases will be explained with an example as shown in Figure J.2. While a block, say G, is moving left-downward in the first phase, if the lower left corner point of it hits another block, say block D, at the upper right corner point of D, G may have two choices of changing direction either downward or ICPC 2018 Problem J: Sliding Blocks

27 leftward. In such case, moving downward has higher priority than moving leftward. If G, in such case, is unable to move downward due to some other blocks, then its direction changes leftward. While block G is moving left-downward its upper-left corner point (or its lower-right corner point) may hit another block s corner points as shown in Figure J.2 (Note that block F and block C hit block G at their corner points during the first phase movement.) In such case, block G continues moving in the same direction since it has not been blocked by the corner points. Figure J.2 The movement rules can be summarized as follows: 1. Each block begins move at the given location along the given direction. The direction is always leftdownward. 2. A moving block changes its direction when it is blocked either by the x-axis, by the y-axis, or by another block. 3. The moving block keeps moving by changing directions until it can no longer move. For each block, following information is given as shown in <Fig. 3>. 1. The width and height w, h of the block. 2. The starting location (x, y) at which the block begins move. 3. (Δx, Δy) to indicate the direction of the first movement (see the red line in Figure J.3). Each block begins move from location (x, y) toward (x Δx, y Δy). Figure J.3 Given information on n rectangular blocks, write a program which finds the location of the last block after moving every block one by one according to the movement rules. ICPC 2018 Problem J: Sliding Blocks

28 You may assume that the i th (2 i n) block at its the starting location is overlapped with none of the previous blocks (i.e., blocks of indices between 1 and (i 1)) and that some block may not move at the very starting location since it is blocked by other blocks. Input Your program is to read from standard input. The input starts with a line containing an integer, n (1 n 1,000), where n is the number of blocks. Each of the following n line contains information on each block. Each block information consists of 6 integers. The first two integers w, h (1 w, h 100,000) indicate the size of it. Next two integers (x, y) (0 x, y 10 8 ) indicate the starting location of it. Next two integers (Δx, Δy) (1 Δx, Δy 10 5 ) represent the direction for the first movement as explained above. Output Your program is to write to standard output. Print exactly one line which contains two integers x and y, where (x, y) is the location of the last block after moving every block one by one according to the movement rules. The following shows sample input and output for two test cases. (Note that the first sample corresponds to Figure J.1 and the second to Figure J.2) Sample Input 1 Output for the Sample Input Sample Input 2 Output for the Sample Input ICPC 2018 Problem J: Sliding Blocks

29 Problem K Suffix-Freeness Time Limit: 0.3 Seconds A deterministic finite automaton (DFA) is a labeled directed graph. That is, instead of having a directed edge in the form (p, q), edges are given as a triple (p, q, c), where p and q are nodes in the graph and c is a label character from an alphabet. At each node, there is at most one outgoing edge per character. In other words, there is no subset of edges in the form (p, q 1, c), (p, q 2, c), (p, q 3, c), of size greater than 1. On the other hand, a node can have a several outgoing edges all of which have different labels. In a DFA, one node is designated as the starting node q 0 and a subset F of nodes are designated as final nodes. A DFA is specified by a tuple(n, K, M, q 0, F), where N is a set of states, K is an input alphabet, M is a set of transitions, q 0 is the start state and F is a set of accepting states. Given a DFA D and a string w = w 1 w 2 w n, we say that D accepts w if there is a series of edges (q 0, q 1, w 1 ), (q 1, q 2, w 2 ),, (q n 1, q n, w n ) spelling out w and q n is a final node in F. Note that nodes and edges can be visited multiple times. In this sense, a DFA can store a (possibly infinite) set of strings, namely the set of all strings accepted by the DFA. DFAs are useful in several practical applications. For instance, in software verification or pattern matching, often a target object is represented as a DFA for efficient processing. Given two strings x and y, we say that y is a suffix of x if there is another string u such that x = uy (the concatenation of u and y in order). For example, for a string icpc2018, all strings icpc2018, cpc2018, pc2018, c2018, 2018, 018, 18, 8, λ are suffixes of icpc2018, where λ denotes the empty string. A set of strings is suffixfree if there is no pair of distinct strings x and y in the set such that y is a suffix of x. For instance, {2018, 18, icpc} is not suffix-free since 18 is a suffix of Similarly {λ, icpc2018, icpc} is not suffix-free since λ is a suffix of icpc2018 and icpc. In fact, λ is a suffix of all nonempty strings and, thus, any set containing λ and any other nonempty string is not suffix-free. Also, by definition, empty set is always suffix-free. Given a DFA D, the language L(D) of D is the set of strings accepted by D. Then we say that D is suffix-free if there are no two distinct strings x and y in L(D) such that y is not a suffix of x. Suffix-freeness plays an important role in several applications including efficient pattern matching. If no string is accepted by D, then L(D) is empty and, therefore, is suffix-free. Your task is to determine whether or not a given DFA is suffix-free. In the right figure, the arrows correspond to labeled edges (transitions) in M. For example, there is an edge ICPC 2018 Problem K: Suffix-Freeness

30 (q 0, q 2, a) and (q 3, q 3, b). Assume that q 2 is the only final node in the DFA; namely, F = {q 2 }. The string a is accepted as there is a path (q 0, q 2, a). Furthermore, bbba is also accepted by (q 0, q 1, b), (q 1, q 3, b), (q 3, q 3, b), (q 3, q 2, a). Since a is a suffix of bbba, this DFA is not suffix-free. Note that these are not the only examples. For all inputs, you can assume that all nodes in the DFA are reachable from the starting node. Input Your program is to read from standard input. The input starts with a line containing four integers n, m, k, f, where n (1 n 2,000) is the number of nodes, k (1 k 26) is the number of characters in the alphabet, m (1 m kn) is the number of edges and f (1 f 2,000) is the number of final nodes. The nodes in the graph are labeled from 0 to n 1, where 0 is the start node. The alphabet consists of the first k lowercase English letters. The following line contains f integers, separated by spaces, corresponding to the final node labels. The following m lines cointain two integers p and q and a character c, all separated by spaces, per line, which corresponds to the labeled edge (p, q, c). Output Your program is to write to standard output. Print exactly one line which contains 1 (if D is suffix-free) or 0 (otherwise). The following shows sample input and output for two test cases. Sample Input 1 Output for the Sample Input a 0 1 b 1 2 a 1 3 b 3 2 a 3 3 b Sample Input 2 Output for the Sample Input a 0 2 b 0 3 c 1 1 b 1 3 a 2 2 c 2 3 b ICPC 2018 Problem K: Suffix-Freeness

31 Problem L Three Robots Time Limit: 2 Seconds An undirected weighted graph G is given and G is connected, that is, arbitrary two vertices in G must be connected by a path. Three robots are exploring G through edges. Here the weight of each edge means the time to be spent when a robot passes through it. The speeds of all the robots are identical and at least two robots may be passed through a same edge at a time. At some instant of the explorations of the robots, all of them should get together at a vertex to share their information. It is called a rendezvous. Initially, three robots lie on specified vertices. Of course, at least two robots may be located on an identical vertex. Also all the three robots start to move simultaneously. We wish to know the minimum time needed to fulfill the first rendezvous. Figure L.1 For example, initially, three robots are located on the vertices 1, 5, and 7 in Figure L.1. A movement of the robot on the vertex 1 into the vertex 9 requires at least 9 time units. Also it takes at least 8 and 3 time units, respectively that the robots on the vertices 5 and 7 travel into the vertex 9. So the rendezvous at the vertex 9 requires at least 9 time units and it is the minimum time needed for the first rendezvous. Of course, the first rendezvous happens either at the vertex 1 or 4 and it also requires the minimum time of 9. Given a weighted and connected graph G and the initial locations of three robots, write a program to find the minimum time needed to fulfill the first rendezvous. Input Your program is to read from standard input. The input starts with a line containing two integers, N and M (1 N 20,000, N 1 M 100,000), where N and M are the numbers of vertices and edges of G, respectively. The vertices of G are represented by 1, 2,, N. In each of the following M lines, three integers a, b, and t (1 a b N, 1 t 10,000) are given, where an edge connects the two vertices a and b, and its weight is t. The last (M + 2)-th line contains three integers u, v, and w, which are the initial locations of ICPC 2018 Problem L: Three Robots

32 three robots (1 u, v, w N). Of course, it is possible that at least two of the three robots are initially located on an identical vertex. Output Your program is to write to standard output. Print exactly one line which contains the minimum time needed to fulfill the first rendezvous. The following shows sample input and output for two test cases. Sample Input 1 Output for the Sample Input Sample Input 2 Output for the Sample Input ICPC 2018 Problem L: Three Robots