Codeforces Round #506 (Div. 3) // rated

### Codeforces Round #506 (Div. 3) ###

Problems :  http://codeforces.com/contest/1029

Tutorial : http://codeforces.com/blog/entry/61439

A. Many Equal Substrings

#include <stdio.h>
 
int main()
{
    int n, k;
    int cnt=0, idx=0;
    char *s, t[55];
    scanf("%d%d%s", &n, &k, t);
 
    printf("%s", t);
 
    s = t+n-1;    
    for(int i=0; i<n-1; i++) {
        int ok=1;
        for(int j=0; s[j]; j++)
            if(s[j] != t[j])
                ok = 0;
        cnt++;
        s--;
        if(ok) idx = cnt;
    }
   
    for(int i=1; i<k; i++)
        printf("%s", t+idx);
    puts("");
    return 0;
}
 

>> input 으로 4 4 abab 를 넣으면 output 으로  ababababab 가 나와야 한다.

>> 함정이 있는 문제. 

>> 최대로 서브스트링을 만들 수 있는 길이를 구한다음, 처음 문자열을 출력하고, 나머지 서브스트링만 k-1번 출력하였다.

B. Creating the Contest

#include <stdio.h>
 
int a[200005];
 
int main()
{
    int n;
    int s=0, e=1;
    int ans=0;
    scanf("%d", &n);
    
    for(int i=0; i<n; i++)
        scanf("%d", a+i);
 
    int tmp=1;
    for(int i=0; i<n-1; i++) {
        if(a[i]*2 >= a[i+1])
            tmp++;
        else {
            if(ans < tmp) ans = tmp;
            tmp = 1;
        }
    }
 
    if(ans < tmp) ans = tmp;
    printf("%d\n", ans); 
    return 0;
}
 

>> 조건을 만족하는 배열의 최대 길이? 를 찾는 문제.

>> a[i]*2 >= a[i+1] 가 조건인데, 문제를 a[s]*2 >= a[e] 로 잘못 이해해서 한번 틀렸다..(내 점수..ㅜ)

C. Maximal Intersection (Ref)

#include <cstdio>
 
const int N = 300005;
 
int L[N], R[N];
int preL[N], sufL[N];
int preR[N], sufR[N];;
 
int Max(int a, int b)
{
    return a > b ? a : b;
}
 
int Min(int a, int b)
{
    return a < b ? a : b;
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for(int i=0; i<n; i++) 
        scanf("%d%d", L+i, R+i);
 
    preL[0] = sufL[n] = 0;
    preR[0] = sufR[n] = 1e9;
    
    for(int i=0; i<n; i++) {
        preL[i+1] = Max(preL[i], L[i]);
        preR[i+1] = Min(preR[i], R[i]);
        sufL[n-1-i] = Max(sufL[n-i], L[n-1-i]);
        sufR[n-1-i] = Min(sufR[n-i], R[n-1-i]);
    }
 
    int ans=0;
    for(int i=0; i<n; i++) 
        ans = Max(ans, Min(preR[i], sufR[i+1])-Max(preL[i], sufL[i+1]));
 
    printf("%d\n", ans); 
    return 0;
}
 

>> 많이 틀려서 해설보고 제출했다..

>> pSum 처럼 prefixL과 suffixL, prefixR, 과 suffixR 을 만든 다음 minR - MaxL 이 정답이 된다.

>> 아래는 해설.

Intersection of some segments $[l_1,r_1],[l_2,r_2],\dots ,[l_n,r_n]$ is $[\underset{i=1}{\overset{n}{max}}{l}_i;\underset{i=1}{\overset{n}{min}}{r}_i]$. If this segment has its left bound greater than its right bound then the intersection is empty.

Removing some segment $i$ makes the original sequence equal to $[l_1,r_1],\dots ,[l_{i-1},r_{i-1}],\dots [l_{i+1},r_{i+1}],\dots ,[l_n,r_n]$. That can be split up to a prefix of length $i-1$ and a suffix of length $n-i$. Intersections for them can be precalced separately and stored in some partial sum-like arrays. Finally, you have to iterate over the position of the removed segment and calculate the intersection of prefix and suffix without this segment.

Overall complexity: $O\left(n\right)$.

- 세그트리로도 될 것 같다. (된다.)

#include <stdio.h>
 
int n, ans;
int segL[1<<20];
int segR[1<<20];
int sIdx = 1<<19;
 
int Max(int a, int b)
{
    return a > b ? a : b;
}
 
int Min(int a, int b)
{
    return a < b ? a : b;
}
 
int maxL(int L, int R, int nodeN, int nodeL, int nodeR)
{
    int a, b;
    int mid = (nodeL+nodeR)/2;
    if(R < nodeL || nodeR < L) return 0;
    if(L <= nodeL && nodeR <= R) return segL[nodeN];
    a = maxL(L, R, nodeN*2, nodeL, mid);
    b = maxL(L, R, nodeN*2+1, mid+1, nodeR);
    return Max(a, b);
}
 
int minR(int L, int R, int nodeN, int nodeL, int nodeR)
{
    int a, b;
    int mid = (nodeL+nodeR)/2;
    if(R < nodeL || nodeR < L) return 1e9;
    if(L <= nodeL && nodeR <= R) return segR[nodeN];
    a = minR(L, R, nodeN*2, nodeL, mid);
    b = minR(L, R, nodeN*2+1, mid+1, nodeR);
    return Min(a, b);
}
 
int main()
{
    int s, e;
    scanf("%d", &n);
    for(int i=0; i<n; i++) 
        scanf("%d%d", segL+sIdx+i, segR+i+sIdx);
 
    s = sIdx>>1;
    e = sIdx;
 
    while(s) {
        for(int i=s; i<e; i++) {
            segL[i] = Max(segL[i<<1], segL[(i<<1)+1]); 
            segR[i] = Min(segR[i<<1], segR[(i<<1)+1]);
        }
        e = s;
        s = e>>1;
    }
    
    for(int i=0; i<n; i++) {
        int mL = Max(maxL(0, i-1, 1, 0, sIdx-1), maxL(i+1, n-1, 1, 0, sIdx-1)); 
        int mR = Min(minR(0, i-1, 1, 0, sIdx-1), minR(i+1, n-1, 1, 0, sIdx-1)); 
        ans = Max(ans, mR-mL);
    }
    printf("%d\n", ans);
    return 0;
}
 

D.

E.

F.