Facebook Programming Challenges: Bar problem

solution.cpp

//Complexity for each case: O(N^2 * logN)
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> ii;
const int MAXN = 1000;
int N, K;
int atWhichPosMin[MAXN];
int atWhichPosMax[MAXN];
vector<int> lists[MAXN];
vector<ii> minimums;
vector<ii> maximums;
vector<int> solution;

int binarySearchUpperBoundMin(int value, int start, int end, int lastValidPos)
{
    if(start > end) return lastValidPos;
    int mid = (start + end) / 2;
    if(minimums[mid].first <= value) return binarySearchUpperBoundMin(value, mid+1, end, mid);
    else return binarySearchUpperBoundMin(value, start, mid-1, lastValidPos);
}
int binarySearchUpperBoundMax(int value, int start, int end, int lastValidPos)
{
    if(start > end) return lastValidPos;
    int mid = (start + end) / 2;
    if(maximums[mid].first <= value) return binarySearchUpperBoundMax(value, mid+1, end, mid);
    else return binarySearchUpperBoundMax(value, start, mid-1, lastValidPos);
}
void read()
{
    for(int i = 0; i < MAXN; ++i) lists[i].clear();
    minimums.clear();
    maximums.clear();
    solution.clear();
    //all ready
    cin >> N >> K;
    for(int i = 0; i < N; ++i)
    {
        int numbers;
        cin >> numbers;
        for(int j = 0; j < numbers; ++j)
        {
            int current;
            cin >> current;
            lists[i].push_back(current);
        }
    }
}
int solve()
{
    int answer = 0;
    for(int i = 0; i < N; ++i) sort(lists[i].begin(), lists[i].end());
    for(int i = 0; i < N; ++i) minimums.push_back(ii(lists[i][0], i));
    for(int i = 0; i < N; ++i) maximums.push_back(ii(lists[i][lists[i].size()-1], i));
    sort(minimums.begin(), minimums.end());
    sort(maximums.begin(), maximums.end());
    for(int i = 0; i < N; ++i) atWhichPosMin[minimums[i].second] = i;
    for(int i = 0; i < N; ++i) atWhichPosMax[maximums[i].second] = i;

    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < lists[i].size(); ++j)
        {
            int current = lists[i][j];
            int posInSeqMin = binarySearchUpperBoundMin(current, 0, N-1, -1);
            int couldBeInPosMin = posInSeqMin+1;
            if(atWhichPosMin[i] <= posInSeqMin) --couldBeInPosMin;

            int posInSeqMax = binarySearchUpperBoundMax(current, 0, N-1, -1);
            int couldBeLessThan = N - posInSeqMax - 1;
            if(atWhichPosMax[i] > posInSeqMax) --couldBeLessThan;

            if(couldBeInPosMin+1 >= K && couldBeLessThan >= N-K)
            {
                //valid answer
                ++answer;
                solution.push_back(current);
            }
        }
    }
    sort(solution.begin(), solution.end());
    return answer;
}
int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for(int i = 0; i < T; ++i)
    {
        read();
        int answer = solve();
        cout<<"answer: "<<answer<<'\n';
        /*
        cout<<"pssible nunmbers:\n";
        for(int i = 0; i < solution.size(); ++i) cout<<solution[i]<<" ";
        */
    }
    return 0;
}
/*
Sample Input:
2
3 3
3 2 5 3
3 8 1 6
3 7 4 9
20 11
1 3
1 2
11 1 4 55 6 80 8 9 19 11 12 13
15 14 177 16 17 18 10 20 21 22 37 24 25 26 27 28
7 190 30 31 32 33 34 35
12 81 23 195 39 40 41 42 43 49 45 46 47
15 48 44 50 51 52 53 54 5 121 57 58 59 98 61 62
3 63 64 65
10 66 67 68 69 70 71 72 73 74 75
4 76 91 29 79
11 7 36 82 83 84 85 86 96 88 89 90
17 77 92 93 172 95 87 97 60 99 100 101 102 103 135 186 106 107
10 108 109 110 111 112 113 114 115 116 117
1 118
8 119 120 56 122 123 124 125 126
9 127 128 129 130 131 132 133 134 104
11 136 137 138 139 140 141 142 143 144 145 146
20 147 148 149 150 151 152 153 154 159 156 157 158 155 180 161 162 163 164 165 166
18 167 168 169 170 171 94 173 174 175 176 15 178 179 160 181 182 183 184
17 185 105 187 188 189 78 191 192 193 194 38 196 197 198 199 200 201
*/