CafeCoder Tea Break 003 Solution & Reflection

December 25, 2019


Foreword

... is this a contest for brown AtCoder users?

A: Hop Step Jump! (Green)

We can reach all blocks B≢3(mod4)B \not\equiv 3 \pmod 4, so we can simply perform the check.

int n;
cin >> n;
cout << (n % 4 == 3 ? "No" : "Yes") << endl;

B: Sound! (Ceylon)

The range of sound we need to make is [min(Ai),max(Ai)][min(A_i), max(A_i)] but KK may lie outside this range. So the answer is max(Ai,k)min(Ai,k)max(A_i, k) - min(A_i, k).

int n, k;
cin >> n >> k;
int _min, _max;
for (int i = 0; i < n; i++) {
    int t;
    cin >> t;
    if (i == 0) {
        _min = _max = t;
    } else {
        _min = min(_min, t), _max = max(_max, t);
    }
}
_min = min(_min, k);
_max = max(_max, k);
cout << (_max - _min) << endl;

C: Good Triangle (Dimbula)

We can write a function to calculate twice the area of the triangle and check whether it is even or odd. If it is even, it means that the area is an integer.

int area(int i, int j, int k) {
    int a = x[i], b = y[i], c = x[j], d = y[j], e = x[k], f = y[k];
    return (c - a) * (f - b) - (d - b) * (e - a);
}

// ...

int n;
cin >> n;
for (int i = 0; i < n; i++)
    cin >> x[i] >> y[i];
int ans = 0;
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        for (int k = j + 1; k < n; k++)
            if (area(i, j, k) % 2 == 0 && area(i, j, k) != 0)
                ans++;
cout << ans << endl;

D: Breaker (Darjeeling)

We can simulate the process for each starting card. Also we can duplicate the array so the check is simpler.

vector<int> v;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
    int t;
    cin >> t;
    v.push_back(t);
}
for (int i = 0; i < n; i++)
    v.push_back(v[i]);
int mans = n + 1;
for (int i = 0; i < n; i++) {
    int pos = i;
    int ans = 0;
    while (pos < i + n) {
        pos += v[pos];
        ans++;
    }
    mans = min(mans, ans);
}
cout << mans << endl;

E: Cafe Road (Earl Grey)

Cafes lie on the same line if the slope of the line segment between them and (0,0)(0, 0) is the same. We can implement a fraction class to store the slope accurately to prevent floating-point error.

pair<int, int> frac(int x, int y) {
    if (y == 0)
        return {0, 1};
    if (x == 0)
        return {1, 0};
    int g = __gcd(x, y);
    x /= g, y /= g;
    if (x < 0)
        x = -x, y = -y;
    return {x, y};
}

// ...

int n;
cin >> n;
map<pair<int, int>, int> m;
for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    m[frac(a, b)]++;
}
int ans = 0;
for (auto p : m)
    if (p.second > ans)
        ans = p.second;
cout << ans << endl;

F: '0' or '1' (Keemun)

... didn't think about this problem seriously, saw the first test case and guessed nCr, tried on second test case and it worked, submitted and accepted. The intended solution seems to be O(N2)O(N^2) dynamic programming (?).

Also, as many people said on Twitter, this problem can be solved for larger constraints (like 1N,M1051 \leq N, M \leq 10^5).

ll mod = 1000000007;

ll bm(ll b, ll p, ll m) {
    ll r = 1;
    for (; p; b = b * b % m, p >>= 1)
        if (p & 1)
            r = r * b % m;
    return r;
}

ll inv(ll x) { return bm(x, mod - 2, mod); }

ll fact(ll x) {
    ll v = 1;
    for (ll i = 1; i <= x; i++)
        v = v * i % mod;
    return v;
}

ll ncr(ll n, ll r) { return fact(n) * inv(fact(r)) % mod * inv(fact(n - r)) % mod; }

// ...

ll n, m;
cin >> n >> m;
cout << ncr(n + m, n) << endl;

Result

2nd place. As more people join it is expected that the rating will drop drastically 😄.