AtCoder Beginner Contest 278

A - Shift

Print from the K-th idx to the N-th, then
considering that K > N is possible, print min(K, N) zeros.
You could also use a queue.

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;

const int MAX = 105;
int N, K, A[MAX];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N >> K;
    for (int i=0; i<N; i++) cin >> A[i];
    for (int i=K; i<N; i++) cout << A[i] << ' ';
    for (int i=0; i<min(K,N); i++) cout << 0 << ' ';
}

B - Misjudge the Time

Just do it

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;

int H, M;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> H >> M;

    for (int m=M; m<60; m++) {
        int ten = (H%24)/10*10 + M/10;
        int one = (H%24)%10*10 + M%10;

        if (ten>=0 && ten<=23 && one>=0 && one<=59) {
            cout << H << ' ' << m;
            return 0;
        }
    }

    for (int h = H+1;; h++) {
        for (int m = 0; m<60; m++) {
            int ten = (h%24)/10*10 + m/10;
            int one = (h%24)%10*10 + m%10;

            if (ten>=0 && ten<=23 && one>=0 && one<=59) {
                cout << h%24 << ' ' << m;
                return 0;
            }
        }
    }
}

Would've been nicer to write a function that checks a time when you pass it in

C - FF

The problem is to print Yes if A follows B and B follows A,
and No otherwise.

You have to watch out for the ranges.

2\le N\le 10^9,\ 1\le Q\le 2\times 10^5

The first structure I thought of was making a Set for each N and
printing Yes if set[a].contain(b) && set[b].contain(a),
but N can be up to a billion, so in terms of space complexity O(N) exceeds the memory limit.

So I thought about a string Set. If A and B are friends, store "A B".
Then print Yes if set.contain("A B") && set.contain("B A").
Since Q is up to two hundred thousand I thought it'd be fine, and solving it that way did get AC, but thinking about it,
if N is 1e9, that's 1e9 bytes in strings. I realized it's not a safe solution, and
the best solution should have used a pair set.

An int is 4 bytes and a pair<int, int> is 8 bytes.
It's O(8Q), so the pair set solution looks the safest.
When I submitted it, the pair set used less than half the memory of the string set

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;

int N, Q;
set<pair<int, int>> f;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N >> Q;
    for (int i=0; i<Q; i++) {
        int T, A, B; cin>>T>>A>>B;
        if (T==1) f.insert({A, B});
        else if (T==2) f.erase({A, B});
        else cout << (f.find({A, B})!=f.end() && f.find({B, A})!=f.end() ? "Yes\n" : "No\n");
    }
}

D - All Assign Point Add

\ 1\le Q\ \le \ 2\cdot 10^5,\ \ 1\le N\le \ 2\cdot 10^5

Operation 1 changes all N elements to xq, which takes O(N) time.
Q is also O(N). So the time complexity is up to O(N^2), which can't be done within 1 second.
For this you need to use a map. Every time you do operation 1, store xq in a variable called default,
and on operation 1 remove all elements with map.clear,
and on each operation 2 or 3, if the number isn't defined, take the value from default and compute.
The time complexity becomes O(N).

#include <iostream>
#include <algorithm>
#include <map>
#include <string>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;

const int MAX = 2*1e5+5;
ll N, Q, dft = 0;
map<ll, ll> A;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N;
    for (int i=1; i<=N; i++) cin>>A[i];
    cin >> Q;

    for (int i=1; i<=Q; i++) {
        int q; cin >> q;
        if (q == 1) {
            A.clear();
            cin >> dft;
        } else if (q==2) {
            int iq, xq; cin >> iq >> xq;
            if (A.find(iq) != A.end()) A[iq] += xq;
            else A[iq] = dft + xq;
        } else {
            int iq; cin >> iq;
            if (A.find(iq) != A.end()) cout << A[iq];
            else cout << dft;
            cout << '\n';
        }
    }
}

E - Grid Filling

Sweeping, which used to target 1D, has to be done in 2D.
Considering N, H, W at 300 and h, w at 150, without sweeping it's
O(HWh*w), which works out to a time limit exceeded.

So we have to bring it down to O(HWh) with sweeping.
And for the number of distinct numbers, just store the counts of all numbers in a 1D array
and count the numbers that are 1 or more.

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;

const int MAX = 305;
int H, W, N, h, w, A[MAX][MAX], C[MAX], ans[MAX][MAX], cnt, oriC[MAX];

void addColor(int x) {
    if (!C[x]) cnt++;
    C[x]++;
}

void eraseColor(int x) {
    C[x]--;
    if (!C[x]) cnt--;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> H >> W >> N >> h >> w;
    for (int i=1; i<=H; i++)
        for (int j=1; j<=W; j++)
            cin >> A[i][j], C[A[i][j]]++, oriC[A[i][j]]++;

    for (int i=1; i<=N; i++) if (C[i]) cnt++;
    int original = cnt;

    for (int i=1; i<=H-h+1; i++) {
        cnt = original;
        for (int j=1; j<=N; j++) C[j] = oriC[j];

        for (int j=i; j<i+h; j++) for (int k=1; k<=w; k++)
            eraseColor(A[j][k]);

        ans[i][1] = cnt;
        for (int j=2; j<=W-w+1; j++) {
            for (int k=i; k<i+h; k++)
                addColor(A[k][j-1]),
                eraseColor(A[k][j+w-1]);
            ans[i][j] = cnt;
        }
    }

    for (int i=1; i<=H-h+1; i++) {
        for (int j=1; j<=W-w+1; j++)
            cout << ans[i][j] << ' ';
        cout << '\n';
    }
}

Comments