codeforce 1400

COFO::1330B Dreamoon Likes Permutations

cofo problem

COFO::1330B Dreamoon Likes Permutations

Link : COFO::1330B

Problem

level : 1400
tag : implementation, math
TIME
- to understand : 5
- to algorithm : 5
- to code : 15
- to debug : 1
- understanding edit : 5

Point

길이 n짜리 배열 a가 주어집니다.
해당 배열에는 최대 2개의 permutation set이 포함되어있습니다.
2개의 permutation 쌍의 길이를 출력합니다.

Design

주어진 문제 그대로, permuation이 이루어져야합니다.
따라서, map을 이용해서 현재 인덱스의 front map, rear map 을 따로 관리해주었습니다.
edit은 조금 다른 설명을 하고 있습니다.
제가 캐치하지 못한 한가지 사실이 있었습니다.
해당 문제의 정답의 길이는 최대 2개 라는 점입니다.
또한, 각 정답이 나오는 위치또한 미리 정해집니다.
배열 a에서 가장 큰 값을 기준으로 해당 인덱스를 포함하는 좌측부분과 나머지 혹은 해당 인덱스를 포함하는 우측부분과 나머지 입니다.
이유는 permutation이라는 점을 생각해보면 생각보다 명확히 이해할 수 있습니다.
가장 큰 값은 좌측 끝으로부터 시작되었어야 하거나 우측끝으로부터 시작되었어야한다는 사실입니다.
또한, 가장 큰 값은 1개 이거나 2개일 수 있습니다.
문제를 풀때 이런 fact가 있는지 좀 더 생각해보아야겠습니다.
- NlogN 과 N 은 확실히 다른 수행시간이기때문이죠.

Complexity

O(NlogN)

Code

mine

#include<bits/stdc++.h>
#define sz(a) (int) a.size()
#define rep(i, a, b) for(int i=(a); i <(b); i++)
#define r_rep(i, a, b) for(int i=(a); i >(b); i--)
using namespace std;

int n;
int a[200009];

void solve() {
    map<int,int> fr, re;
    vector<pair<int,int> > ans;
    cin >> n;
    rep(i, 1, n + 1) {
        cin >> a[i];
        re[a[i]]++;
    }
    
    rep(i, 1, n + 1) {
        if (fr.find( a[i] ) == fr.end()) fr[ a[i] ] = 1;
        else fr[ a[i] ] ++ ;
        
        re[ a[i] ] -- ;
        if (re[ a[i] ] == 0) re.erase(a[i]);
        if (sz(fr) == 0 || sz(re) == 0) continue;
        if (sz(fr) != i || sz(re) != (n-i)) continue;
        auto itf = fr.find(sz(fr)), itr = re.find(sz(re));
        if(itf == fr.end() || itr == re.end()) continue;
        if ((++itf) == fr.end() && fr.begin()->first == 1 && (++itr) == re.end() && re.begin()->first == 1) {
            ans.push_back({i, n-i});
        }
    }
    cout << sz(ans) << '\n';
    if (sz(ans) > 0) {
        rep(i, 0, sz(ans)) cout << ans[i].first << " " << ans[i].second << '\n';
    }
}
int main(){
    int tc; cin >>tc;
    while(tc--)
        solve();
    return 0;
}

tutorial

#include<cstdio>
const int SIZE = 200000;
int p[SIZE];
int ans[SIZE][2];
int ans_cnt;
bool judge(int a[], int n){
    static int used[SIZE+1];
    for(int i = 1; i <= n; i++) used[i] = 0;
    for(int i = 0; i < n; i++) used[a[i]] = 1;
    for(int i = 1; i <= n; i++) {
        if(!used[i]) return 0;
    }
    return 1;
}
bool judge(int len1, int n){
    return judge(p, len1) && judge(p + len1, n - len1);
}
int main() {
    int t = 0;
    scanf("%d", &t);
    while(t--) {
        ans_cnt = 0;
        int n;
        scanf("%d", &n);
        int ma=0;
        for(int i = 0; i < n; i++) {
            scanf("%d", &p[i]);
            if(ma < p[i]) ma = p[i];
        }
        if(judge(n - ma,n)) {
            ans[ans_cnt][0] = n - ma;
            ans[ans_cnt++][1] = ma;
        }
        if(ma * 2 != n && judge(ma,n)) {
            ans[ans_cnt][0] = ma;
            ans[ans_cnt++][1] = n - ma;
        }
        printf("%d\n", ans_cnt);
        for(int i = 0; i < ans_cnt; i++) {
            printf("%d %d\n", ans[i][0], ans[i][1]);
        }
    }
    return 0;
}