[Codeforces] Codeforces Round #504 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)

요즘 코드포스에 빠져살았었습니다.

보면 한동안 알고리즘 문제풀이가 안올라왔을 적이 조금 있을탠데, 이 때가 바로 코포에 빠져살 때입니다!

처음에 영어문제이고, 2시간에 7문제 풀이는 익숙하지가 않아서 굉장히 해매느라 더 늦게 푼 것 같습니다 ㅠㅠㅠ

어쨌든, 이 코포 덕분에 알고리즘 문제풀이 올리는것들도 엄청 미뤄져서 빨리 올려야겠습니다! 지금부터라도!!

후우.. 19문제를 내리 올려야하다니 너무 걱정이 많군요! 빠르게 시작하겠습니다.

A. Single Wildcard Pattern Matching

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given two strings $s$ and $t$. The string $s$ consists of lowercase Latin letters and at most one wildcard character '*', the string $t$consists only of lowercase Latin letters. The length of the string $s$ equals $n$, the length of the string $t$ equals $m$.

The wildcard character '*' in the string $s$ (if any) can be replaced with an arbitrary sequence (possibly empty) of lowercase Latin letters. No other character of $s$ can be replaced with anything. If it is possible to replace a wildcard character '*' in $s$ to obtain a string $t$, then the string $t$ matches the pattern $s$.

For example, if $s=$"aba*aba" then the following strings match it "abaaba", "abacaba" and "abazzzaba", but the following strings do not match: "ababa", "abcaaba", "codeforces", "aba1aba", "aba?aba".

If the given string $t$ matches the given string $s$, print "YES", otherwise print "NO".

Input

The first line contains two integers $n$ and $m$ ($1\le n,m\le 2\cdot {10}^5$) — the length of the string $s$ and the length of the string $t$, respectively.

The second line contains string $s$ of length $n$, which consists of lowercase Latin letters and at most one wildcard character '*'.

The third line contains string $t$ of length $m$, which consists only of lowercase Latin letters.

Output

Print "YES" (without quotes), if you can obtain the string $t$ from the string $s$. Otherwise print "NO" (without quotes).

Examples

input

Copy

6 10
code*s
codeforces

output

Copy

YES

input

Copy

6 5
vk*cup
vkcup

output

Copy

YES

input

Copy

1 1
v
k

output

Copy

NO

input

Copy

9 6
gfgf*gfgf
gfgfgf

output

Copy

NO

Note

In the first example a wildcard character '*' can be replaced with a string "force". So the string $s$ after this replacement is "codeforces" and the answer is "YES".

In the second example a wildcard character '*' can be replaced with an empty string. So the string $s$ after this replacement is "vkcup" and the answer is "YES".

There is no wildcard character '*' in the third example and the strings "v" and "k" are different so the answer is "NO".

In the fourth example there is no such replacement of a wildcard character '*' that you can obtain the string $t$ so the answer is "NO".

문제 해석

문자열 두개가 주어집니다! 한 문자열에는 *라는 와일드 카드가 있습니다.

해당 와일드카드는 어떠한 문자열도 다 대체할 수 있습니다!

그리고, 문자열에는 와일드카드가 딱 하나밖에 주어지지 않습니다.

과연, 두 문자열은 같은 문자열이 될 수 있을까요? 를 구하는 문제입니다.

어떻게 풀까?

*라는 와일드 카드가 있습니다.

해당 와일드 카드를 이용하면, 어떠한 문자열도 대체할 수 있죠!

다행히도 최대 딱 하나의 와일드카드만이 나오는군요! 그렇다면 어떻게 문제를 풀 수 있을까요?

와일드 카드가 나온다면, 어떠한 문자열도 시행할 수 있습니다.

또한, 와일드 카드 이후에 나오는 문자열에는 와일드 카드가 없기 때문에, 와일드 카드 뒤의 문자열 사이즈와,

해당 길이만큼 비교하는 문자열의 사이즈 만큼 비교하기만 하면 와일드 카드로 만들 수 있는 문자인지, 만들 수 없는 문자인지 알 수 있습니다!

가령, 

code*s와

codeforces를 비교하면, *뒤에 s 하나이기 때문에,

code*     s를 비교하면 되죠! 만약 와일드 카드 전에 다른 문자거나, 뒤에 비교하는게 다르면 만들 수 없는 문자입니다!

gfgf*gfgf와

gfgf gf 를 보면,

gfgf*gfgf 이기 때문에, 다른 문자라는 것을 알 수 있는 것이죠!!

코드

#pragma once
#include<cstdio>
#include<string>
#include<string.h>
 
using namespace std;
 
char str[2][300000];
int n, m;
 
bool find(int p) {
    int pos = m - (n - p - 1);
    if (pos < p) return false;
    return (strcmp(str[0] + p + 1, str[1] + pos) == 0);
}
 
int main() {
 
    scanf("%d %d\n", &n, &m);
    scanf("%s\n%s\n", str[0], str[1]);
    bool res = true;
    int i = 0;
    while (true) {
        if (str[0][i] == '*') {
            res = find(i);
            break;
        }
 
        else if (str[0][i] != str[1][i]) {
            res = false;
            break;
        }
        else if (str[0][i] == 0 && str[1][i] == 0) {
            res = true; break;
        }
        i++;
    }
 
    if (res) { printf("YES\n"); }
    else { printf("NO\n"); }
 
    return 0;
}

시간복잡도

시간 복잡도는 O(N)이죠!

B. Pair of Toys

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Tanechka is shopping in the toy shop. There are exactly $n$ toys in the shop for sale, the cost of the $i$-th toy is $i$ burles. She wants to choose two toys in such a way that their total cost is $k$ burles. How many ways to do that does she have?

Each toy appears in the shop exactly once. Pairs $(a,b)$ and $(b,a)$ are considered equal. Pairs $(a,b)$, where $a=b$, are not allowed.

Input

The first line of the input contains two integers $n$, $k$ ($1\le n,k\le {10}^{14}$) — the number of toys and the expected total cost of the pair of toys.

Output

Print the number of ways to choose the pair of toys satisfying the condition above. Print 0, if Tanechka can choose no pair of toys in such a way that their total cost is $k$ burles.

Examples

input

Copy

8 5

output

Copy

2

input

Copy

8 15

output

Copy

1

input

Copy

7 20

output

Copy

0

input

Copy

1000000000000 1000000000001

output

Copy

500000000000

Note

In the first example Tanechka can choose the pair of toys ($1,4$) or the pair of toys ($2,3$).

In the second example Tanechka can choose only the pair of toys ($7,8$).

In the third example choosing any pair of toys will lead to the total cost less than $20$. So the answer is 0.

In the fourth example she can choose the following pairs: $(1,1000000000000)$, $(2,999999999999)$, $(3,999999999998)$, ..., $(500000000000,500000000001)$. The number of such pairs is exactly $500000000000$.

문제 해석

n개의 장난감이 있습니다. i번째 장난감의 가격은 i입니다!

이 때 k원을 만들 수 있는 장난감의 쌍을 구하는 문제입니다!

그리고, 쌍 (a,b)에서 a==b는 허용되지 않습니다!

어떻게 풀까?

문제는 결국, (1, k-1), (2, k-2) ... 을 구하는 문제입니다.

이렇게 하면, 결국 (k/2, k/2+1)의 쌍이 나올 것입니다.

하지만 잘 생각해보면 n이 k-1보다 꼭 크다는 보장이 없습니다!

가령, 8,15를 생각해봅시다.

15를 만들기 위해선 (1, 14) ... 부터 시작합니다. 14가없기 때문에 만들 수 없는 쌍입니다!

이럴때는 반대로  (7,8) 부터 생각하면 됩니다!

(a,b)에서 a를 1부터 넣는 것이 아니라,

b를 n부터 넣으면서 하나하나 빼가는 것이죠!

이렇게 하면 정답은, n - k/2개가 나옵니다!

만약, n이 k/2이하라면, (a,b)쌍은 나오지 않는 것이죠!

예를 들면, 

8 16이 입력으로 주어지는 경우에는

(8,8)이기 때문에 만들 수 없는 수입니다.

이렇게 조건 3개를 통해서 답을 출력해주면 됩니다!

코드

#include<cstdio>
 
int main() {
    long long n, k;
    scanf("%lld %lld\n", &n, &k);
 
    if (k - 1 <= n) printf("%lld\n", (k - 1) / 2);
    else if(n < (k / 2 + 1)){
        printf("0\n");
    }
    else {
        printf("%lld\n", n - k / 2);
    }
    return 0;
}

시간복잡도

입력과 조건에 따른 출력밖에 없기 때문에 시간복잡도는 O(1)입니다.

C. Bracket Subsequence

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A bracket sequence is a string containing only characters "(" and ")". A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example, bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)"), and ")(", "(" and ")" are not.

Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

You are given a regular bracket sequence $s$ and an integer number $k$. Your task is to find a regular bracket sequence of length exactly $k$such that it is also a subsequence of $s$.

It is guaranteed that such sequence always exists.

Input

The first line contains two integers $n$ and $k$ ($2\le k\le n\le 2\cdot {10}^5$, both $n$ and $k$ are even) — the length of $s$ and the length of the sequence you are asked to find.

The second line is a string $s$ — regular bracket sequence of length $n$.

Output

Print a single string — a regular bracket sequence of length exactly $k$ such that it is also a subsequence of $s$.

It is guaranteed that such sequence always exists.

Examples

input

Copy

6 4
()(())

output

Copy

()()

input

Copy

8 8
(()(()))

output

Copy

(()(()))

문제 해석

괄호를 빼는 문제입니다!

n과 k가 주어지면, 

n은 문자열의 개수이고, k는 빼야하는 괄호의 수입니다.

그리고, k개의 괄호를 빼도, 순서가 정상적인 괄호가 되야하는 문제입니다!

어떻게 풀까?

정상적인 괄호를 만들기는 굉장히 쉽습니다.

그냥, 문자열을 하나하나 입력받으면서 '('다음에 ')'가 온다면, 두개를 없애주면 됩니다.

이렇게 2개씩 없애면서 주어지는 k개의 괄호를 없애면 나머지 괄호를 모두 입력받아서 결과괄호를 출력하면 됩니다!

코드

#pragma once
#include<cstdio>
char str[200001], res[200001];
int len, rlen;
 
 
int main() {
    int m, n;
    scanf("%d %d\n", &m, &n);
 
    scanf("%s\n", str);
 
    res[rlen++] = str[len++];
    int cnt = 0, idx = (m-n)/2;
    while(cnt != idx) {
        res[rlen++] = str[len++];
        if (res[rlen - 1] == ')' && res[rlen - 2] == '(') {
            cnt++;
            rlen -= 2;
        }
    }
    while (len != m) res[rlen++] = str[len++];
    res[rlen] = 0;
    printf("%s\n", res);
    return 0;
}

시간 복잡도

문자열을 한번 주욱 스캔하는 것 밖에 없기 때문에 시간복잡도는 O(N)입니다.

D. Array Restoration

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Initially there was an array $a$ consisting of $n$ integers. Positions in it are numbered from $1$ to $n$.

Exactly $q$ queries were performed on the array. During the $i$-th query some segment $(l_i,r_i)$ $(1\le l_i\le r_i\le n)$ was selected and values of elements on positions from $l_i$ to $r_i$ inclusive got changed to $i$. The order of the queries couldn't be changed and all $q$ queries were applied. It is also known that every position from $1$ to $n$ got covered by at least one segment.

We could have offered you the problem about checking if some given array (consisting of $n$ integers with values from $1$ to $q$) can be obtained by the aforementioned queries. However, we decided that it will come too easy for you.

So the enhancement we introduced to it is the following. Some set of positions (possibly empty) in this array is selected and values of elements on these positions are set to $0$.

Your task is to check if this array can be obtained by the aforementioned queries. Also if it can be obtained then restore this array.

If there are multiple possible arrays then print any of them.

Input

The first line contains two integers $n$ and $q$ ($1\le n,q\le 2\cdot {10}^5$) — the number of elements of the array and the number of queries perfomed on it.

The second line contains $n$ integer numbers $a_1,a_2,\dots ,a_n$ ($0\le a_i\le q$) — the resulting array. If element at some position $j$ is equal to $0$then the value of element at this position can be any integer from $1$ to $q$.

Output

Print "YES" if the array $a$ can be obtained by performing $q$ queries. Segments $(l_i,r_i)$ $(1\le l_i\le r_i\le n)$ are chosen separately for each query. Every position from $1$ to $n$ should be covered by at least one segment.

Otherwise print "NO".

If some array can be obtained then print $n$ integers on the second line — the $i$-th number should be equal to the $i$-th element of the resulting array and should have value from $1$ to $q$. This array should be obtainable by performing exactly $q$ queries.

If there are multiple possible arrays then print any of them.

Examples

input

Copy

4 3
1 0 2 3

output

Copy

YES
1 2 2 3

input

Copy

3 10
10 10 10

output

Copy

YES
10 10 10 

input

Copy

5 6
6 5 6 2 2

output

Copy

NO

input

Copy

3 5
0 0 0

output

Copy

YES
5 4 2

Note

In the first example you can also replace $0$ with $1$ but not with $3$.

In the second example it doesn't really matter what segments to choose until query $10$ when the segment is $(1,3)$.

The third example showcases the fact that the order of queries can't be changed, you can't firstly set $(1,3)$ to $6$ and after that change $(2,2)$ to $5$. The segment of $5$ should be applied before segment of $6$.

There is a lot of correct resulting arrays for the fourth example.

문제 해석

생각보다 굉장히 까다로운 문제였습니다.

우선, 배열의 개수 n과 쿼리수 q가 주어집니다.

여기서, 쿼리에 대해 또 설명이 필요합니다.

쿼리란, (l,r)형태로 주어집니다.

i 번째 쿼리는 (l,r)을 모두 i로 바꾸는 형태입니다!

이 때, q번의 쿼리로 주어지는 배열을 만들 수 있는지 출력하는 것 입니다!

여기서, 예외적으로 0을 주는데, 0은 어떠한 수도 들어갈 수 있다는 것입니다!

자! 이제 i번의 쿼리로 해당 배열을 만들 수 있는지, 된다면 어떤 배열이 완성될 수 있는지 출력하면 됩니다!

어떻게 풀까?

이 문제를 해결하기 위해 한번 주어진 배열을 토대로 만들 수 있는 쿼리를 다시 재구성하고, 이 재구성된 쿼리를 통해서 다시 배열을 만들어봅시다!

만약, 재구성된 쿼리와 주어진 배열이 다르다면 NO, 같으면 YES인 것이죠!

우선 쿼리의 특징에 대해서 생각해봅시다.

i번째 쿼리에서는 (l,r)부분에 빈 틈없이 i가 들어갑니다!

여기서 나타나는 특징!

바로, i번 쿼리 사이에는 i-1이하의 숫자가 나타나지 않는다는 것이죠!!! 

위 그림을 보면 이해할 수 있습니다.

i 단계에서 l부터 r까지 i를 쭈우우욱 늘여놨습니다.

이제 이 사이에 i-1을 넣기 위해서는 i 단계 이후여야 하지만, i+1단계부터는 i보다 작은 수를 놓을 수 없습니다! 

따라서 i단계 사이에는 i보다 작은 수가 올 수 없습니다!

위의 점을 유의하면 한 가지 사실을 또 도출할 수 있습니다!

바로, q단계의 쿼리는 사라지지 않는다!는 것이죠. 즉, q는 배열 어디엔가 꼭 하나 이상은 존재해야합니다.

바로, q+1단계가 진행되지 않기 때문이죠!

그렇다면 마지막에 배열에 q가 없으면 일단 "NO"입니다!

하지만, 문제에는 0이라는 수가 있죠. 0은 아무 수로나 채울 수 있기 때문에, 당연히 q로도 채워질 수 있습니다.

위를 조금 더 수정하면, 

배열에 q가 없는데 0도 없으면 답은 NO다!

라는 것이죠.

만약, 0이 있으면, 0 하나는 q로 바꿉니다!

그리고, 숫자 i는 i번째 쿼리 딱 하나로 만들 수 있습니다.

즉, 배열을 보면 (l,r)의 위치를 대강 구할 수 있다는 것입니다!

바로, 주어진 배열에서 가장 왼쪽에 있는 것이 l이고, 가장 오른쪽에 있는것이 r이라는 것입니다!

위의 결과에서 보면, i보다 큰 수에 대해서는, i가 더 넓게 l을 잡을 때의 결과를 보여주는 것입니다.

어짜피, i+1에서 덮어써지게 되기 때문에 두 수는 결국 같은 배열을 가집니다.

따라서, 주어진 배열을 통해 l, r을 구할 수 있다는 것이죠!

이렇게, 주어진 배열이 있다면, i번째 쿼리에 대한 l과 r값을 구할 수 있습니다!

맨처음 주어진 배열을 arr[]에 저장한다고 한다면, i라는 수가 나왔을 때, 가장 왼쪽에 있는 i는 l, 가장 오른쪽에 있눈 i는 r로 전처리합시다!

(0은 처리하지 않습니다.)

1 0 2 3 같은 경우에는

1 : (1,1)

2 : (3,3)

3 : (4,4)

가 될 것입니다.

참고로, 0의 전처리는 (0,0)이라고 합시다.

그리고, 만약 q가 배열에 없다면, 맨 앞에 있는 0에 q를 넣읍시다!

마지막 쿼리의 특성상, q는 아무곳에 딱 하나만 있어도 되기 때문입니다!

그럼 이제 전처리한 것들을 통해서 배열을 완성해봅시다!

우선, 배열에서 전처리했던 수들을 쭉 나열합시다!

즉, 배열에는 이제 l과 r, 그리고 0 값들만이 있을 것입니다!

위 그림과 비슷한 형식이겠죠!

자, 예제와 함께 설명하는게 좋겠죠!? 예제는 "1 2 3 3 2 2 1 1 0" 로 하겠습니다!

q는 8 이라고 하죠!

그리고, 이전에 나온 재구성된 배열의 수를 now라고 하겠습니다.

처음에 now는 0 으로 설정합니다!

그리고, 배열의 번호를 저장하는 스택을 만들 것입니다! 이 스택에 대해서는 나중에 자세히 설명드리겠습니다.

그럼 이제 전처리를 해봅시다.

전처리를 하면, l과 r을 제외하고는 0으로 만듭니다.

또한, q가 8인데, 8값이 없기 때문에 맨 마지막에 있는 0 을 8로 만듭니다.

배열을 맨 왼쪽부터 탐색하면서 오른쪽으로 가봅니다. 이 때, 확인하는 배열의 인덱스를 i라고 하겠습니다.

그럼, 이제 오른쪽으로 가면서 확인하는 겁니다.

만약, now의 r이 i보다 작다면, 이제 now가 나오는 것이 끝나다는 소리입니다.

따라서, now의 r이 i보다 작다면, now를 스택에서 꺼낸 수로 바꿔줍시다!

다만, 현재는 스택이 비어있기 때문에 now를 0으로 바꿉니다.

현재 now는 0입니다.

이제, 재구성된 배열[1]을 봅시다.

1이라는 수가 있습니다.  now가 0 이고, 재구성된 배열[1]이 1입니다!

우선 1로 바뀌어야 하지만, 나중에 0이 또 다시 나올수도 있기 때문에, 0을 그냥 버려서는 안됩니다!

따라서, 0을 스택에 저장합니다.

그리고, now를 1로 바꾸고, 재구성된 배열[1]에는 1을 저장합니다.

여기서 잠깐! now가 재구성된 배열[i]보다 크다는건 무슨 의미일까요?

만약, now가 r이 아니라면, 계속해서 재구성된 배열에서 계속해서 now가 채워져야한다는 것을 의미합니다!

즉, now보다 작은 수는 아까 위에서 봤던 것처럼, l과 r사이에서 나올 수 없는 수이기 때문에 무시해주면 됩니다!

위 상황에서는 now가 1이고, 1의 r이 8이기 때문에, 아직 now를 계속 채워야 합니다.

하지만, 재구성된 배열[2]가 now보다 큰 2 입니다!

따라서, 1을 스택에 쌓고, 2를 now로 변경합니다!

재구성된 배열[3]에서도 이와 유사한 작용을 해서, 2를 스택에 쌓고 now는 3이 되겠죠!

그렇다면, 아래의 상황을 봅시다!

now의 r이 끝났기 때문에, 스택에서 now를 꺼냅니다!

현재 now는 2 입니다!

따라서, 현재 재구성된 배열[i]에는 2가 들어갑니다!

하지만, 여기서 한가지 생각해봐야할 점이 있습니다!

만약,  2가 나왔는데, r보다 뒤였다면 어떻게 해야할까요?

그렇다면, 이미 2는 더이상 채우면 안되는 끝났다는 수이기 때문에, 스택에서 다시 수를 뽑아야합니다.

만약, 스택이 비었다면 0을 채우면 되겠죠!

이제 마지막 0에도 스택에서 꺼내온 1을 채우고, 처음 배열과 비교합니다.

0은 어짜피 아무 숫자로 채워도 되기 때문에 달라도 무시합니다!

위와 아래가 같은 배열이기 때문에 YES를 출력하면 됩니다!!

만약, 다르다면 NO를 출력하면 되죠!

코드

#pragma once
#include<cstdio>
 
int info[200001][2], arr[200001], make[200001];
int sta[200001], top;
 
 
int main() {
    int n, q;
    scanf("%d %d\n", &n, &q);
    bool has0 = false, hasQ = false;
 
    for (int i = 1; i <= n; i++) {
        scanf("%d \n", &arr[i]);
        info[arr[i]][0] = info[arr[i]][0] ? info[arr[i]][0] : i;
        info[arr[i]][1] = i;
        has0 |= arr[i] == 0;
        hasQ |= arr[i] == q;
    }
 
    if (!has0 && !hasQ) { printf("NO\n"); return 0; }
 
    if (!hasQ) {
        int i = 1;
        while (arr[i]) i++;
        info[q][1] = info[q][0] = i;
    }
 
    for (int i = 1; i <= q; i++) {
        make[info[i][0]] = i;
        make[info[i][1]] = i;
    }
 
    int now = make[1];
    for (int i = 1; i <= n; i++) {
        if (info[now][1] < i) {
            now = 0;
            while (top) {
                now = sta[--top];
                if (info[now][1] > i) break;
                now = 0;
            }
        }
        if (now < make[i]) {
            sta[top++] = now;
            now = make[i];
        }
 
        make[i] = now;
    }
    for (int i = 1; i <= n; i++) {
        if (arr[i] == 0) continue;
        if (arr[i] != make[i]) { printf("NO\n"); return 0; }
    }
    printf("YES\n");
    for (int i = 1; i <= n; i++) printf("%d ", make[i] ? make[i] : 1);
    return 0;
}

시간 복잡도

반복문 하나 도는 것이전부이기 때문에 시간복잡도는 O(N) 입니다!

여담

으악 처음 코포여서 그런지 너무 못했어요.. 흑흑..

우선, 영어 해석이 너무 안되었답니다... C번 되게 쉬웠는데 영어 해석이 안되서 문제를 조금 잘못 풀고 있었어요!

바깥 괄호를 없애야하는줄 알고 계속 고민했답니다.

다음에는 더 잘하고 싶어요!