[Codeforces] Educational Codeforces Round 49 (Rated for Div. 2)

저의 2번째 코포입니다! 물론! 떡락했습니다 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

히잉...

떡상을 위해 다시 풀며 복습했던 내용을 블로그에 올리겠습니다!

아자아자!

You are given a string $s$ consisting of $n$ lowercase Latin letters. $n$ is even.

For each position $i$ ( $1 \leq i \leq n$ ) in string $s$ you are required to change the letter on this position either to the previous letter in alphabetic order or to the next one (letters 'a' and 'z' have only one of these options). Letter in every position must be changed exactly once.

For example, letter 'p' should be changed either to 'o' or to 'q', letter 'a' should be changed to 'b' and letter 'z' should be changed to 'y'.

That way string "codeforces", for example, can be changed to "dpedepqbft" ('c' $\to$ 'd', 'o' $\to$ 'p', 'd' $\to$ 'e', 'e' $\to$ 'd', 'f' $\to$ 'e', 'o' $\to$ 'p', 'r' $\to$ 'q', 'c' $\to$ 'b', 'e' $\to$ 'f', 's' $\to$ 't').

String $s$ is called a palindrome if it reads the same from left to right and from right to left. For example, strings "abba" and "zz" are palindromes and strings "abca" and "zy" are not.

Your goal is to check if it's possible to make string $s$ a palindrome by applying the aforementioned changes to every position. Print "YES" if string $s$ can be transformed to a palindrome and "NO" otherwise.

Each testcase contains several strings, for each of them you are required to solve the problem separately.

Input

The first line contains a single integer $T$ ( $1 \leq T \leq 50$ ) — the number of strings in a testcase.

Then $2 T$ lines follow — lines $(2 i - 1)$ and $2 i$ of them describe the $i$ -th string. The first line of the pair contains a single integer $n$ ( $2 \leq n \leq 100$ , $n$ is even) — the length of the corresponding string. The second line of the pair contains a string $s$ , consisting of $n$ lowercase Latin letters.

Output

Print $T$ lines. The $i$ -th line should contain the answer to the $i$ -th string of the input. Print "YES" if it's possible to make the $i$ -th string a palindrome by applying the aforementioned changes to every position. Print "NO" otherwise.

Example
inputCopy
5
6
abccba
2
cf
4
adfa
8
abaazaba
2
ml
outputCopy
YES
NO
YES
NO
NO

Note

The first string of the example can be changed to "bcbbcb", two leftmost letters and two rightmost letters got changed to the next letters, two middle letters got changed to the previous letters.

The second string can be changed to "be", "bg", "de", "dg", but none of these resulting strings are palindromes.

The third string can be changed to "beeb" which is a palindrome.

The fifth string can be changed to "lk", "lm", "nk", "nm", but none of these resulting strings are palindromes. Also note that no letter can remain the same, so you can't obtain strings "ll" or "mm".

문제 해석

문자들은 한칸씩 변화할 수 있습니다!

즉, a -> b로, b-> a로, b->c로 이런식으로 변화할 수 있죠!

하지만, a->z로 변하거나 z->a로 변화하진 않습니다!

문자열이 주어지고, 해당 문자열의 모든 문자가 위의 변환을 거칠때, 펠린드롬이 될 수 있는지 출력합니다!

어떻게 풀까?

굉장히 간단한 문제입니다. a에서 z로 변화하지 않고, z에서 a로 변화하지 않기 때문에,

펠린드롬을 검사하듯이 맨 앞과 맨 마지막 문자들을 비교하면서, 맨 마지막 문자와 맨 처음 문자가 교차하기 전 까지,

두 문자의 차이가 0이거나 2이면 펠린드롬을 만들 수 있는 것 입니다!!

왜냐하면, 두 문자가 2칸이 차이나야 1 칸씩 변화하여 같은 문자가 될 수 있기 때문입니다!

예를 들면, a 와 c는 2 칸 사이의 b가 되어야 같은 문자가 될 수 있습니다!

아니면, b와 b처럼 같은 문자인 경우에는 ,서로 a와 a로 변환되던지, c와 c로 변환되면 같은 수가 됩니다!!

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#pragma once
#include<cstdio>
#include<cstring>
 
char str[101];
 
int abs(int i) { return i > 0 ? i : -i; }
 
int main() {
    int n;
    scanf("%d\n", &n);
 
    while (n--) {
        int len;
        scanf("%d\n", &len);
 
        scanf("%s\n", str);
        bool res = true;
        for (int i = 0; i < len / 2; i++) {
            if (str[i] == str[len - 1 - i] || abs(str[i] - str[len - 1 - i]) == 2) continue;
            else {
                res = false; break;
            }
        }
        if(res) printf("YES\n"); 
        else printf("NO\n");
    }
    return 0;
}
Colored by Color Scripter
cs

시간 복잡도

시간 복잡도는 O(N)이 되겠군요.

You are given a chessboard of size $n \times n$ . It is filled with numbers from $1$ to $n^{2}$ in the following way: the first $⌈ \frac{n^{2}}{2} ⌉$ numbers from $1$ to $⌈ \frac{n^{2}}{2} ⌉$ are written in the cells with even sum of coordinates from left to right from top to bottom. The rest $n^{2} - ⌈ \frac{n^{2}}{2} ⌉$ numbers from $⌈ \frac{n^{2}}{2} ⌉ + 1$ to $n^{2}$ are written in the cells with odd sum of coordinates from left to right from top to bottom. The operation $⌈ \frac{x}{y} ⌉$ means division $x$ by $y$ rounded up.

For example, the left board on the following picture is the chessboard which is given for $n = 4$ and the right board is the chessboard which is given for $n = 5$ .

$\text{[math]}$

You are given $q$ queries. The $i$ -th query is described as a pair $x_{i}, y_{i}$ . The answer to the $i$ -th query is the number written in the cell $x_{i}, y_{i}$ ( $x_{i}$ is the row, $y_{i}$ is the column). Rows and columns are numbered from $1$ to $n$ .

Input

The first line contains two integers $n$ and $q$ ( $1 \leq n \leq 10^{9}$ , $1 \leq q \leq 10^{5}$ ) — the size of the board and the number of queries.

The next $q$ lines contain two integers each. The $i$ -th line contains two integers $x_{i}, y_{i}$ ( $1 \leq x_{i}, y_{i} \leq n$ ) — description of the $i$ -th query.

Output

For each query from $1$ to $q$ print the answer to this query. The answer to the $i$ -th query is the number written in the cell $x_{i}, y_{i}$ ( $x_{i}$ is the row, $y_{i}$ is the column). Rows and columns are numbered from $1$ to $n$ . Queries are numbered from $1$ to $q$ in order of the input.

Examples
inputCopy
4 5
1 1
4 4
4 3
3 2
2 4
outputCopy
1
8
16
13
4
inputCopy
5 4
2 1
4 2
3 3
3 4
outputCopy
16
9
7
20

Note

Answers to the queries from examples are on the board in the picture from the problem statement.

문제 해석

n*n의 체스보드가 있습니다! 더해서 짝수가 되는 행과 열에 1부터 까지 적혀있고,

더해서 홀수가 되는 행과 열은 부터 까지 적혀있습니다.

이 떄, q가 주어지고, q에는 각각 (x,y) 쌍이 주어집니다.

쌍 (x,y)에 써있는 수를 출력하는 프로그램을 만드세요!

어떻게 풀까?

이 문제는 두 개의 수열로 생각하면 편합니다! 왼쪽 맨 위칸을 1부터 시작하는 수열,

그리고 왼쪽 맨 위에서 두번째 칸은 부터 시작하는 수열입니다!

또한, 맵을 약간 변형해서 생각합시다.

저는 0부터 카운팅하는게 편하기 때문에, 0행 0열을 0번이라고 하겠습니다!

그러면 맵은

0 1 2 3 4

5 6 7 8 9

10 11 12 13 14

15 16 17 18 19

20 21 22 23 24

이렇게 나타낼 수 있습니다.

그리고, 두개의 수열을 하나씩 묶어서 생각합시다.

즉, 1과 14를 하나, 2와 15를 하나, 3과 16을 하나로 생각합니다.

그러면, 두 수열의 크기는 1씩 증가하는 것은 같고, 시작 수만 다르기 때문에 i번째 체스판에 대해서 다음과 같은 공식이 가능합니다.

체스판에 써있는 값 = x + i/2 (x는 두 수의 합이 짝수일 경우에 1, 홀수일 경우에 )

그렇습니다! 공식을 구했습니다!

이제 위의 공식을 출력만 해주면 답이완성됩니다 핫핫.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#pragma once
#include<cstdio>
int main() {
    long long n, q;
    scanf("%lld %lld\n", &n, &q);
    while (q--) {
        long long x, y;
        scanf("%lld %lld\n", &x, &y);
        x--;y--;
        long long cnt = x * n + y;
        bool check = (x+y)&1;
        cnt >>= 1;
        if (check) {
            printf("%lld\n", (n*n+1) / 2 + 1 + cnt);
        }
        else {
            printf("%lld\n", 1 + cnt);
        }
    }
    return 0;
}
Colored by Color Scripter
cs

시간 복잡도

시간 복잡도는 O(Q)가 되겠군요!

You have $n$ sticks of the given lengths.

Your task is to choose exactly four of them in such a way that they can form a rectangle. No sticks can be cut to pieces, each side of the rectangle must be formed by a single stick. No stick can be chosen multiple times. It is guaranteed that it is always possible to choose such sticks.

Let $S$ be the area of the rectangle and $P$ be the perimeter of the rectangle.

The chosen rectangle should have the value $\frac{P^{2}}{S}$ minimal possible. The value is taken without any rounding.

If there are multiple answers, print any of them.

Each testcase contains several lists of sticks, for each of them you are required to solve the problem separately.

Input

The first line contains a single integer $T$ ( $T \geq 1$ ) — the number of lists of sticks in the testcase.

Then $2 T$ lines follow — lines $(2 i - 1)$ and $2 i$ of them describe the $i$ -th list. The first line of the pair contains a single integer $n$ ( $4 \leq n \leq 10^{6}$ ) — the number of sticks in the $i$ -th list. The second line of the pair contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{j} \leq 10^{4}$ ) — lengths of the sticks in the $i$ -th list.

It is guaranteed that for each list there exists a way to choose four sticks so that they form a rectangle.

The total number of sticks in all $T$ lists doesn't exceed $10^{6}$ in each testcase.

Output

Print $T$ lines. The $i$ -th line should contain the answer to the $i$ -th list of the input. That is the lengths of the four sticks you choose from the $i$ -th list, so that they form a rectangle and the value $\frac{P^{2}}{S}$ of this rectangle is minimal possible. You can print these four lengths in arbitrary order.

If there are multiple answers, print any of them.

Example
inputCopy
3
4
7 2 2 7
8
2 8 1 4 8 2 1 5
5
5 5 5 5 5
outputCopy
2 7 7 2
2 2 1 1
5 5 5 5

Note

There is only one way to choose four sticks in the first list, they form a rectangle with sides $2$ and $7$ , its area is $2 \cdot 7 = 14$ , perimeter is $2 (2 + 7) = 18$ . $\frac{18^{2}}{14} \approx 23.143$ .

The second list contains subsets of four sticks that can form rectangles with sides $(1, 2)$ , $(2, 8)$ and $(1, 8)$ . Their values are $\frac{6^{2}}{2} = 18$ , $\frac{20^{2}}{16} = 25$ and $\frac{18^{2}}{8} = 40.5$ , respectively. The minimal one of them is the rectangle $(1, 2)$ .

You can choose any four of the $5$ given sticks from the third list, they will form a square with side $5$ , which is still a rectangle with sides $(5, 5)$ .

문제 해석

막대기들이 주어집니다.

이 막대기를 이용해서 직사각형을 만들고, 직사각형의 둘레가 P이고, 넓이를 S라고 할 때 의 최소값을 구하세요!

어떻게 풀까?

이 값의 최소값은 몇이 될까요? 바로, 두 막대기 사이가 가장 인접할 경우가 위의 값이 최소가 됩니다.

또한, 직사각형을 만들 수 있는 막대기의 길이가 되기 위해서는, 같은 길이의 막대기가 2개가 되어야 합니다.

또한, 막대기가 4개라면, 정사각형을 만들 수 있기 때문에, 같은 길이의 막대기가 4개 라면, 고를 수 있는 막대기의 길이가 똑같은 것이 2개 들어가게 해줍니다!

이렇게 선택 가능한 길이들을 저장하는 벡터값을 만들고, 이 벡터를 정렬한 다음에 순차적으로 을 구해서 최솟값을 구하면, 답을 구할 수 있습니다!!

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#pragma once
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
 
vector<int> vec;
int arr[10001];
int res[2];
double diff;
 
int main() {
    int t;
    scanf("%d\n", &t);
    while (t--) {
        int n;
        vec.clear();
        diff = 1e12;
        scanf("%d \n", &n);
        memset(arr, 0, sizeof(arr));
 
        while (n--) {
            int input;
            scanf("%d\n", &input);
 
            arr[input]++;
            if (arr[input] == 2) vec.push_back(input);
            else if (arr[input] == 4) vec.push_back(input);
        }
 
        sort(vec.begin(), vec.end());
 
        for (int i = 1; i < vec.size(); i++) {
              double value = 4.0*(vec[i] + vec[i - 1])*(vec[i] + vec[i - 1]) / (vec[i]) / (vec[i - 1]);
            if (diff > value ) {
                diff = value;
                res[0] = vec[i-1];
                res[1] = vec[i];
            }
        }
        printf("%d %d %d %d\n", res[0], res[0], res[1], res[1]);
    }
    return 0;
}
Colored by Color Scripter
cs

시간 복잡도

시간 복잡도는 정렬하는데 걸리는 O(N log N) 입니다!

Medicine faculty of Berland State University has just finished their admission campaign. As usual, about $80 %$ of applicants are girls and majority of them are going to live in the university dormitory for the next $4$ (hopefully) years.

The dormitory consists of $n$ rooms and a single mouse! Girls decided to set mouse traps in some rooms to get rid of the horrible monster. Setting a trap in room number $i$ costs $c_{i}$ burles. Rooms are numbered from $1$ to $n$ .

Mouse doesn't sit in place all the time, it constantly runs. If it is in room $i$ in second $t$ then it will run to room $a_{i}$ in second $t + 1$ without visiting any other rooms inbetween ( $i = a_{i}$ means that mouse won't leave room $i$ ). It's second $0$ in the start. If the mouse is in some room with a mouse trap in it, then the mouse get caught into this trap.

That would have been so easy if the girls actually knew where the mouse at. Unfortunately, that's not the case, mouse can be in any room from $1$ to $n$ at second $0$ .

What it the minimal total amount of burles girls can spend to set the traps in order to guarantee that the mouse will eventually be caught no matter the room it started from?

Input

The first line contains as single integers $n$ ( $1 \leq n \leq 2 \cdot 10^{5}$ ) — the number of rooms in the dormitory.

The second line contains $n$ integers $c_{1}, c_{2}, \dots, c_{n}$ ( $1 \leq c_{i} \leq 10^{4}$ ) — $c_{i}$ is the cost of setting the trap in room number $i$ .

The third line contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq n$ ) — $a_{i}$ is the room the mouse will run to the next second after being in room $i$ .

Output

Print a single integer — the minimal total amount of burles girls can spend to set the traps in order to guarantee that the mouse will eventually be caught no matter the room it started from.

Examples
inputCopy
5
1 2 3 2 10
1 3 4 3 3
outputCopy
3
inputCopy
4
1 10 2 10
2 4 2 2
outputCopy
10
inputCopy
7
1 1 1 1 1 1 1
2 2 2 3 6 7 6
outputCopy
2

Note

In the first example it is enough to set mouse trap in rooms $1$ and $4$ . If mouse starts in room $1$ then it gets caught immideately. If mouse starts in any other room then it eventually comes to room $4$ .

In the second example it is enough to set mouse trap in room $2$ . If mouse starts in room $2$ then it gets caught immideately. If mouse starts in any other room then it runs to room $2$ in second $1$ .

Here are the paths of the mouse from different starts from the third example:

$1 \to 2 \to 2 \to \dots$ ;
$2 \to 2 \to \dots$ ;
$3 \to 2 \to 2 \to \dots$ ;
$4 \to 3 \to 2 \to 2 \to \dots$ ;
$5 \to 6 \to 7 \to 6 \to \dots$ ;
$6 \to 7 \to 6 \to \dots$ ;
$7 \to 6 \to 7 \to \dots$ ;

So it's enough to set traps in rooms $2$ and $6$ .

문제 해설

어떤 기숙사에 쥐가 한마리 있습니다!

이 쥐는 시간초마다 다음 복도를 이동합니다!

기숙사에 사는 여자들은 이 쥐를 잡고싶어합니다!

i번 방에 쥐덫을 설치하는데 c의 비용이 듭니다!

쥐가 해당 방 어딘가에 있을때, 쥐덫은 해당 쥐를 무조건 잡는다고 생각합니다!

쥐가 처음에 어디에서 서식하고 있는지 모를 때,

최소의 비용으로 이 쥐가 처음에 어디있던지 확실하게 잡기 위해서는 얼마의 비용이 필요할까요!?

어떻게 풀까?

이 문제는 싸이클을 이용하는 문제입니다!

자! 문제를 생각해봅시다!

일단 기숙사에 방이 n개가 있습니다!

그리고, n개의 방마다 간선을 하나씩 가지고 있기 때문에 n개의 간선이 존재하죠!

n개의 간선이 존재한다는 것은, 이 간선을 하나씩 연결하면, 아래 그림에서처럼 총 n+1개의 방을 연결할 수 있다는 것입니다!

n개의 간선이 있으면, n+1개의 노드를 연결할 수 있다.

그리고 이렇게 연결된 n+1개의 방에 1부터 n까지의 번호를 붙인다고 가정해봅시다

그렇다면, 비둘기집의 원리에 의해 해당 방들은 무조건 싸이클을 이루게 됩니다!

그리고, 쥐의 시작위치가 어디던지 간에 해당 쥐는 이 싸이클에 들어올 수 밖에 없습니다!

그리고 위상 정렬을 응용하면, 꼬리들을 모두 끊었을 때, 남아있는 싸이클을 구할 수 있습니다.

위상 정렬은 in-degree 가 0인 점을 큐에 넣고, in-degree를 계속 줄여서, 0이 되면 또 큐에 넣는 방식이죠!

하지만, 싸이클이 있다면, in-degree가 0이 되지 않는 지점이 발생하고,

위상 정렬을 마쳐도 in-degree가 0이 되지 않는 지점이 발생합니다.

이렇게 in-degree가 0이 되지 않는 지점들을 통해 싸이클들을 구할 수 있습니다!

그림을 통해 알아보겠습니다!

자, 위와 같은 상황에서 싸이클을 구해봅시다!

우선, in-degree가 없는 노드들을 골라냅니다. 1,2,4가 되겠죠!

큐에 넣어줍시다.

큐에서 1을 꺼낸 후에, 1과 연결된 3의 in-dgree를 하나 낮춥니다.

3의 in-degree는 1이 낮아졌지만, 아직 in-dgree가 0이 되지 않았으므로, 큐에 넣지 않습니다.

이제 큐에서 2를 꺼냅니다. 마찬가지로 2와 연결된 3의 in-degree를 1 낮춥니다.

앗, 이번엔 3의 in-dgree가 0이 되었습니다! 따라서, 3의 노드도 큐에 넣어줍니다.

다시 큐에서 노드를 하나 뺍니다. 4와 연결된 5의 in-dgree를 하나 뺍니다.

하지만, 여전히 5의 in-degree는 0이 되지 않았습니다.

또다시 큐에서 하나를 뺍니다. 3과 연결된 5의 in-degree를 하나 낮춥니다.

하지만, 5의 in-degree는 0이 되지 않았습니다.

큐도 비었기 때문에, 위상 정렬을 종료합니다!

이제 in-degree가 0이 아닌 지점은 모두 싸이클인 지점입니다!

아렇게 싸이클을 구하면, 싸이클 마다 쥐덫을 설치하는데 비용이 가장 작게 드는 방을 골라서 모두 더해주면 됩니다!

이 방법은 유니온 파인드를 써도 되고, 저처럼 for문을 한번씩 더 돌면서 연결된 것 끼리 그룹을 만들어 주는 방법이 있습니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#pragma once
#include<cstdio>
#include<cstring>
int direct[200001];
int cost[200001];
int inorder[200001];
int que[200001], f, r;
int groups[200001];
int gc[200001];
 
int main() {
    int n;
    scanf("%d\n", &n);
    memset(gc, 0x3f, sizeof(gc));
    for (int i = 1; i <= n; i++) {
        scanf("%d", &cost[i]);
    }
 
    for (int i = 1; i <= n; i++) {
        scanf("%d\n", &direct[i]);
        inorder[direct[i]]++;
    }
 
    for (int i = 1; i <= n; i++) {
        if (inorder[i] == 0) que[r++] = i;
    }
 
    while (f != r) {
        int now = que[f++];
 
        inorder[direct[now]]--;
        if (inorder[direct[now]] == 0) que[r++] = direct[now];
    }
 
    f = r = 0;
 
    int g = 0;
 
    for (int i = 1; i <= n; i++) {
        if (groups[i] != 0) continue;
        if (inorder[i] == 0) continue;
        int now = i;
 
        groups[i] = ++g;
        while (groups[direct[now]] == 0) {
            groups[direct[now]] = g;
            now = direct[now];
        }
    }
 
    for (int i = 1; i <= n; i++) {
        if (groups[i] == 0) continue;
        gc[groups[i]] = gc[groups[i]] > cost[i] ? cost[i] : gc[groups[i]];
    }
 
    int lowCost = 0;
    for (int i = 1; i <= g; i++) {
         lowCost += gc[i];
    }
    printf("%d\n", lowCost);
    return 0;
}
Colored by Color Scripter
cs

시간복잡도

시간 복잡도는 O(N)이 되겠습니다!

여담

정말 아쉬운 코드포스였습니다!

이 떄 당시에, D번을 풀었지만, C번에서 배열을 초기화 안하고, A번에서 문제를 잘못 읽었기 때문에 정말 아쉬움이 많이 남는 코드포스였습니다!!!

으아!! 만약에 4개를 맞았다면, 진짜 엄청난 떡상이었을탠데 말이죠!

'공부 > 알고리즘 문제풀이' 카테고리의 다른 글

[Codeforces] Codeforces Round #506 (Div. 3) (0)	2018.08.31
[Codeforces] Codeforces Round #505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final) (0)	2018.08.31
[Codeforces] Codeforces Round #504 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final) (0)	2018.08.30
[SW Expert Academy] 8월의 마지막 코드배틀 (0)	2018.08.29
[BOJ] 5213. 과외맨 (4)	2018.08.29

비락 식혜를 낳는 블로그

[Codeforces] Educational Codeforces Round 49 (Rated for Div. 2)

'공부 > 알고리즘 문제풀이' 카테고리의 다른 글

티스토리툴바

[Codeforces] Educational Codeforces Round 49 (Rated for Div. 2)

'공부 > 알고리즘 문제풀이' 카테고리의 다른 글

'공부/알고리즘 문제풀이' Related Articles

티스토리툴바