COFO::1284B New Year and Ascent Sequence

• Link : COFO::1284B

Problem

• level : 1400
• tag : binary search, combinatorics, data structures, dp, implementation, sortings
• TIME
  • to understand :
  • to algorithm : fail
  • to code :
  • to debug :
  • understaing edit : 25

Point

• n개의 배열이 주어집니다.
  • 각 배열의 원소는 0 이상 10^6 이하의 수입니다.
• 우리는 다음의 조건을 만족하는 배열을 ascent하다고 합니다.
  • 1 <-= i < j <= l(배열의 길이), a_i < a_j
• n개의 배열 중 하나를 sx 라고 하고, 다른 하나를 sy라고 합시다.
• sx + sy 는 sx의 뒤에 sy를 이어서 붙인다는 의미입니다.
• 위와 같은 merge된 배열을 concatenation된 배열이라고 합니다.
• n개의 배열에 의해 만들어질 수 있는 n^2 개의 concatenation 배열 중, ascent 한 배열의 갯수를 출력합니다.

Design

• 시간을 많이 소모한 부분은 당연하게도 algorithm이었습니다.
• concatenation된 배열 중 ascent 한 배열의 갯수를 세려고 아래와 같이 구분지어 생각했습니다.
  • a : concat하기전에 주어진 배열 하나 자체로 ascent 한 배열의 수
  • b : 자기자신과 concat했을때 ascent 한 배열의 수
  • c : n개의 배열에 포함된 모든 원소를 {원소의 값, 포함된 배열의 index}로 vector를 하나만들고 정렬한 후, 하나씩 꺼내면서 그 우측에 있는 모든 수들에 대해서 (즉 자신의 원소보다 큰 원소들에 대해서) 중복되지 않는 배열의 인덱스의 갯수
• 위와 같이 구해서 c + a * n + b 로 출력하려 했지만, c를 O(N^2)말고 다른 방법으로 구하는 방법을 못찾아 edit을 보게되었습니다.
• edit은 위처럼 구하라는 것을 구하는게 아니라, 위에 제가 나열한 경우만 해도 3가지 경우이고 이는 복잡해집니다.
• 따라서, ascent하지않은 그룹의 갯수로 n^2 에서 여집합을 제외하는 방법으로 풀이하였습니다.
• 이와 같은 방법으로 풀이시 풀이가 매우 명료해집니다.
• non-increasing 하지 않은 배열을 줄여서 NI 라고 합시다.
  • 즉, 감소하는 배열을 의미합니다.
• 우리가 해야할 일은 각 배열이 NI인지 체크하고, 이들끼리의 갯수만 구해서 전체 N^2에서 제외해주면 됩니다.
• NI 배열의 최소값(맨 뒤에있는 값), 최대값(맨 앞에있는 값)을 두 원소로 하여 vector에 push 후 오름차순 정렬해줍니다.
• 그리고 이 NI 배열에서 하나씩 꺼내며 해당 배열이 concatenation의 뒤로 가는 배열이 된 경우 불가능한 갯수를 세어 줍니다.
• 즉 다음과 같은 배열이 있다고 해봅시다.
  • {1, 2}, {1, 3}, {2, 3}, {2, 5}, {3, 7}
• 이때 이번 배열 [7 7 6 4 3] 즉, {3, 7}이 뒤쪽에 붙으면 제외되어야 할 배열의 갯수를 세어봅시다.
• [x x x x 7] 과 같은 NI 형태의 배열인 경우에만 위 배열에 앞에 와도 괜찮습니다.
• 따라서, 괜찮지 않은 배열을 찾아야 하므로 {7, -1} 이상인 값의 갯수를 구해서 제외된 갯수를 구하면 위 배열에선 모두 선택되게 되어 모두 제외됩니다.
• 위의 방법을 lower_bound로 binary search 하여 찾아냅니다.

Complexity

• O(NlogN)

Code

#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#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--)
typedef long long ll;
using namespace std;

vector<pair<int,int> > v;
void solve(){
    int n; cin  >> n;
    ll ans = 1LL * n * n;
    rep(i, 0, n){
        int cnt; cin >> cnt;
        vector<int> a(cnt);
        rep(i, 0, cnt) cin >> a[i];
        reverse(all(a));
        if(is_sorted(all(a)))
            //v.push_back({a[0], a.back()});
            v.emplace_back(a[0], a.back());
           
    }
    
    sort(all(v));
    rep(i, 0, sz(v)){
        ll C = v.end() - lower_bound(all(v), pair<int, int> (v[i].second, -1));
        ans -= C;
    }
    cout << ans << '\n';
}

int main(){
 //   freopen("input.txt", "r", stdin);
    solve();
    return 0;
}