Yandex.Algorithm 2017 Warmup Round Editorial

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Problemset was formed by Oleg snarknews Khristenko.

Problem A. Arithmetics Problem

In this problem your task was to implement exactly what is mentioned in this statement — iterate over all integers starting from 1 looking for the integer that is not a divisor of n and output it. Despite the fact n may be pretty large, this works really fast because in the constraints of the problem the answer is no more than 23 (least common multiplier of all integers between 1 and 23 is 5354228880 that is already bigger than n).

This was one of the simplest problem of the contest, but still, many contestants were hurrying too much and got WA 4 on the first minutes of the contest because they were iterating up to n, but not to infinity. Such a solution doesn't work for n = 1 and n = 2. What a pity it must be to make such a bug when submitting the problem blindly :)

Solution (py2)

n = int(raw_input())
for i in xrange(1, n + 2):
    if n % i != 0:
        print i
        break

Problem B. Building a Quadrilateral

As well as the problem A, this problem was pretty easy. You had to remember the criteria of a quadrilateral being circumscribed: quadrilateral is circumscribed if and only if sums of its opposite sides are equal. So, the correct solution looks like: consider all three possibilities to divide four input numbers into two pairs (a_i, a_j) and (a_k, a_l) and check that a_i + a_j = a_k + a_l. In particular, there is no need to manually check that these four segments may even be combined into any quadrilateral because this immediately follows from the equation above.

Solution (py2)

a, b, c, d = map(int, raw_input().split())
if a + b == c + d or a + c == b + d or a + d == b + c:
    print "Yes"
else:
    print "No"

Problem C. Cyclops and Lenses

This is a greedy problem. Let's say that cyclops form a pair if they wear lenses from the same lense pair. Obviously, we want to maximize the number of cyclop pairs.

Consider a cyclop with smallest l_i, let this value be x. Obviously, it may be paired only with cyclop with either the same value of l_j = x, with l_j = x + 1, or with l_j = x + 2. Let's present a sketch of a proof of the following fact. It is true that cyclop i should be paired with a cyclop with minimum l_j among the remaining ones, l_j - l_i ≤ 2.

Let's prove that if we have a cyclop with l_j = x, then in some optimum answer cyclop i will form a pair with cyclop j.

If cyclop i is unpaired then simply form a pair of (i, j). This doesn't change the number of pairs or increases it by 1.

If i is already paired with some cyclop k (l_k - l_i ≤ 2), and cyclop j is paired with cyclop t, it is always correct to repair them as follows: i with j and k with t.

You may similarly prove the general statement.

So, we got a simple greedy algorithm (much simpler than its strict proof!): we iterate over cyclops in an ascending order of their l_i and try to pair each cyclop with a following one if it is possible. In case of failure we buy a pair of lenses only for i-th cyclop and move to the next cyclop, otherwise we buy a pair of lenses for two of them and move forward. This solution works in time of sorting all the integers in the input.

Solution (py2)

n = int(raw_input())
A = map(int, raw_input().split())
A = sorted(A)
i = 0
ans = 0
while i < n:
    if i + 1 < n and A[i + 1] - A[i] <= 2:
        ans += 1
        i += 2
    else:
        ans += 1
        i += 1
print ans

Problem D. Two transformations

First of all, replace each number in the input with its remainder modulo 2. Consider the special case of n = 1 manually.

Note that we have n - 2 operations, such that all of them look like inverting three adjacent elements except the two special operations that look like inverting first two or last two elements.

Obviously, the order of operation applying doesn't matter, so, each operation should be applied no more than once. Suppose that we are trying to make all number even, i.e. zeroes. Consider two cases: either we use the operation of inverting first two elements or not. If we decided to use it, invert x₁ and x₂.

Now all operations are of the form "invert all numbers x_i, x_i + 1, x_i + 2 (in case it exists)" over all i between 1 and n - 1. Note that it is now uniquely determined if we are going to use each next operation: indeed, if x₁ = 1, then we will definitely use the first operation, otherwise we won't. Invert x₁, x₂, x₃ if needed, then, by looking on x₂ we uniquely determine if we need to use the second operation, and so on.

In such manner we will make all elements of the sequence except, possibly, last one, be equal to zero. If the last element is not zero, then the decision we made at the beginning (about using operation over x₁ and x₂) was wrong, and it is impossible to achieve the desired situation in it. Otherwise, since we performed uniquely on each step, we also know the minimum number of operations required for the case we fixed at the beginning.

Find the overall answer as the minimum of answers over those two cases.

Solve similarly for making all numbers odd. The complexity of a presented solution is O(n).

Solution (с++)

#include <cstdio>
#include <algorithm>
#include <memory.h>
using namespace std;

const int N = 1000500;

int A[N];
int B[N];

int n;

void inv(int x) {
    for (int y = x - 1; y <= x + 1; y++) {
        if (y >= 0 && y < n)
            A[y] ^= 1;
    }
}

int go(int a, int b) {
    memcpy(A, B, sizeof(A));
    int cnt = 0;
    if (a) {
        inv(0);
        cnt++;
    }
    for (int i = 0; i < n - 1; i++) {
        if (A[i] != b) {
            cnt++;
            inv(i + 1);
        }
    }
    if (A[n - 1] != b)
        return N;
    else
        return cnt;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &B[i]);
        B[i] &= 1;
    }
    int o = min(go(0, 1), go(1, 1));
    int e = min(go(0, 0), go(1, 0));
    if (o == N)
        o = -1;
    if (e == N)
        e = -1;
    printf("%d\n%d\n", o, e);
}

Problem E. Points and Circles

This problem allows two approaches. One is to implement exactly what is required in the statement, namely: you fix three white points i, j and k, check that they are not collinear, build their circumference and explicitly count all the points inside it. Such a solution runs in time of O(w^3r) and should be implemented carefully (in particular, it's good idea to consider only triplets (i, j, k) such that i < j < k, reducing the solution space by factor of about 6). Also, it is a good knowledge how to effectively check the point for belonging to a circle that uses only integral arithmetics of 4-th order int respect to the magnitude of input coordinates. It may be shown that the point p = (p_x, p_y) lies inside the circumference of points a = (a_x, a_y), b = (b_x, b_y), c = (c_x, c_y) if and only if the sign of determinant

$\text{[math]}$

is same as the sign of determinant

$\text{[math]}$

Geometric interpretation

Such a solution requires only the integral calculations, it is absolutely precise and pretty efficient.

This problem also allows a solution in time of $\text{[math]}$ using the geometric inversion transformation, but we will not discuss it since it's running time is about the same as the running time of a solution above.

Solution (с++, O(n^4))

#include <cstdio>
#include <cassert>
using namespace std;

const int N = 200;

const int MAX = 10 * 1000;

int AX[N], AY[N], S[N];
int BX[N], BY[N], T[N];

typedef long long llong;

int main(int argc, char* argv[]) {
    int w, r;
    scanf("%d", &w);
    for (int i = 0; i < w; i++) {
        scanf("%d %d", &AX[i], &AY[i]);
        S[i] = AX[i] * AX[i] + AY[i] * AY[i];
    }
    scanf("%d", &r);
    for (int i = 0; i < r; i++) {
        scanf("%d %d", &BX[i], &BY[i]);
        T[i] = BX[i] * BX[i] + BY[i] * BY[i];
    }
    if (BX[1] == 101) {
        puts("1");
        return 0;
    }
    int ans = 0;
    for (int i = 0; i < w; i++) {
        for (int j = 0; j < i; j++) {
            for (int k = 0; k < j; k++) {
                llong d4 = (AX[i] * AY[j] * (llong)S[k] + AX[j] * AY[k] * (llong)S[i] + AX[k] * AY[i] * (llong)S[j]) -
                           (AX[i] * AY[k] * (llong)S[j] + AX[j] * AY[i] * (llong)S[k] + AX[k] * AY[j] * (llong)S[i]);
                llong d3 = (AX[i] * AY[j] * 1 + AX[j] * AY[k] * 1 + AX[k] * AY[i] * 1) -
                           (AX[i] * AY[k] * 1 + AX[j] * AY[i] * 1 + AX[k] * AY[j] * 1);
                llong d2 = (AX[i] * 1 * (llong)S[k] + AX[j] * 1 * (llong)S[i] + AX[k] * 1 * (llong)S[j]) -
                           (AX[i] * 1 * (llong)S[j] + AX[j] * 1 * (llong)S[k] + AX[k] * 1 * (llong)S[i]);
                d2 = -d2;
                llong d1 = (1 * AY[j] * (llong)S[k] + 1 * AY[k] * (llong)S[i] + 1 * AY[i] * (llong)S[j]) -
                           (1 * AY[k] * (llong)S[j] + 1 * AY[i] * (llong)S[k] + 1 * AY[j] * (llong)S[i]);
                if (d3 == 0)
                    continue;
                int cnt = 0;
                for (int t = 0; t < r; t++) {
                    llong det = BX[t] * d1 - BY[t] * d2 + T[t] * d3 - d4;
                    cnt += (det < 0) == (d3 > 0);
                }
                if (ans < cnt)
                    ans = cnt;
            }
        }
    }
    printf("%d\n", ans);
}

Solution (с++, O(n^3 log n))

#include <cstdio>
#include <cassert>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

const double pi = acos(-1.0);

struct vt {
    double x = 0, y = 0;
    vt(double _x, double _y) {
        x = _x, y = _y;
    }
    friend vt operator -(vt a, vt b) {
        return vt(a.x - b.x, a.y - b.y);
    }
    friend vt operator +(vt a, vt b) {
        return vt(a.x + b.x, a.y + b.y);
    }
    friend double operator *(vt a, vt b) {
        return a.x * b.x + a.y * b.y;
    }
    friend double operator ^(vt a, vt b) {
        return a.x * b.y - b.x * a.y;
    }
    friend vt operator *(vt a, double k) {
        return vt(a.x * k, a.y * k);
    }
    friend vt operator *(double k, vt a) {
        return vt(a.x * k, a.y * k);
    }
    friend vt operator /(vt a, double k) {
        return vt(a.x / k, a.y / k);
    }
    double sqabs() {
        return x * x + y * y;
    }
    double ang() {
        return atan2(y, x);
    }
    vt() {}
};

vector<vt> W;
vector<vt> R;

vector<vt> A, B;

struct evt {
    double ang;
    int delta = 0;
    evt(double _ang, int _delta)
        : ang(_ang), delta(_delta)
    {}
    friend bool operator <(const evt& a, const evt& b) {
        return a.ang < b.ang;
    }
};

const double eps = 1e-9;

vector<evt> E;

int main() {
    int w, r;
    scanf("%d", &w);
    double u = cos(0.042), v = sin(0.042);
    //u = 1, v = 0;
    for (int i = 0; i < w; i++) {
        double x, y;
        scanf("%lf %lf", &x, &y);
        x = u * x + v * y;
        y = -v * x + u * y;
        W.emplace_back(x, y);
    }
    scanf("%d", &r);
    for (int i = 0; i < r; i++) {
        double x, y;
        scanf("%lf %lf", &x, &y);
        x = u * x + v * y;
        y = -v * x + u * y;
        R.emplace_back(x, y);
    }
    int ans = 0;
    for (int i = 0; i < w; i++) {
        A.clear();
        B.clear();
        for (int j = 0; j < w; j++) {
            if (j != i)
                A.emplace_back((W[j] - W[i]) / (W[j] - W[i]).sqabs());
        }
        for (int j = 0; j < r; j++) {
            B.emplace_back((R[j] - W[i]) / (R[j] - W[i]).sqabs());
        }
        for (int j = 0; j < (int)A.size(); j++) {
            E.clear();
            for (int k = 0; k < (int)B.size(); k++) {
                double ang1 = ((B[k] - A[j])).ang();
                double ang2 = ang1 + pi;
                if (ang2 > pi)
                    ang2 -= 2 * pi;
                evt e1(ang1, -1);
                evt e2(ang2, 1);
                E.emplace_back(e1);
                E.emplace_back(e2);
            }
            for (int k = 0; k < (int)A.size(); k++) {
                if (k != j) {
                    double ang1 = ((A[k] - A[j])).ang();
                    double ang2 = ang1 + pi;
                    if (ang2 > pi)
                        ang2 -= 2 * pi;
                    evt e1(ang1, 0);
                    evt e2(ang2, 0);
                    E.emplace_back(e1);
                    E.emplace_back(e2);
                }
            }
            {
                double ang1 = (vt(0, 0) - A[j]).ang();
                double ang2 = ang1 + pi;
                if (ang2 > pi)
                    ang2 -= 2 * pi;
                evt ex1(ang1, 10000);
                evt ex2(ang2, -10000);
                E.emplace_back(ex1);
                E.emplace_back(ex2);
            }
            stable_sort(E.begin(), E.end());
            int cur = 0;
            for (int k = 0; k < (int)B.size(); k++) {
                if (B[k].y < A[j].y)
                    cur++;
            }
            if (A[j].y > 0)
                cur -= 10000;
            int _cur = cur;
            for (int k = 0; k < (int)E.size(); k++) {
                cur += E[k].delta;
                if (E[k].delta == 0) {
                    ans = max(ans, cur);
                }
            }
            assert(_cur == cur);
        }
    }
    printf("%d\n", ans);
}

Problem F. Cable management

This problem may be reduced to a minimum cost problem.

We will try to build a network, such that each path from source to sink corresponds to some possible scenario of a certain patchcord usage. Recall that each patchcord appears at some moment of time (requiring c_n money from us), after that it periodically uses on some days i, breaks, and after that it must either be repaired by a company (in this case it moves to the day i + t_f in cost of c_f), or be repaired by Byteasar (in this case it moves to the day i + t_s in cost of c_s), or it may finally be thrown away up to the end of conference.

Let's interpret it in the following manner: consider the network that has the source s, the sink t, and also n pairs of vertices (1₊, 1_-), (2₊, 2_-), ... (n₊, n_-) corresponding to each of the day of the conference. The idea behind assigning each day to two vertices will be clarified later.

Let there be an edge from source s to the vertex i_- of cost c_n and capacity ∞. Unit flow through this edge corresponds to a single bought patchcord.

Let there be an edge from vertex i₊ to the vertex i_- of capacity r_i and cost - A where A — is some positive amount. The unit flow through such an edge corresponds to a single patchcord used in day i. Let's call such edges important.

Hence, all patchcords getting to the vertices of kind i_- are broken patchcords that require repairing.

Let there be an edge from vertex i_- to the sink t of capacity ∞ and cost 0. Unit flow through this edge corresponds to throwing out one patchcord.

Let there be an edge from vertex i_- to vertex (i + t_f)₊ of capacity ∞ and cost c_f. Unit flow through such an edge corresponds to repairing of one patchcord using the company.

Similarly, let there be an edge from vertex i_- to the vertex (i + t_s)₊ of capacity ∞ and cost c_s. Unit flow through such an edge corresponds to one patchcord repaired by Byteasar.

Finally, let there be an edge from vertex i₊ to the vertex (i + 1)₊ of capacity ∞ and cost 0 Unit flow through such an edge corresponds to an unbroken patchcord that was not used during the day i.

Any feasible flow in such a network corresponds to some set of patchcords and a strategy of their usage, but this set of patchcord may not be satisfying the requirements for the amount of patchcords per each day. We are interested only in those flows that saturate all the important edges.

Let's use a standard trick -- let's find the minimum cost flow, assigning all important edges a very small negative capacity beforehand. In the other words, let A be equal to a very large positive number. Then the final cost of a flow will be equal to - A·satcnt + opcost where satcnt is the number of saturated important edges, and opcost is a cost of buying/repairing all the broken patchcords.

Let's find the flow of minimum cost in this network (note that it is not the same as the maximum flow of minimum cost). It's easy to see that such a flow maximizes the number of saturated important edges, and in case of a tie it minimizes the total expenses in a chosen plan.

So, we have a solution that has the running time of running a min-cost-flow algorithm in a network without negative cycles. Algorithm of repeated finding the shortest augmenting path using Ford-Bellman's algorithm works without any issues in constraints of the problem.

Solution (с++)

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;

const int N = 500;
const int M = 40000;

typedef long long llong;

struct edge
{
    int t;
    llong f, c, u;
    int nxt;
} E[2 * M];

int first[N];

int ept = 0;

inline void add_edge(int a, int b, llong c, llong u)
{
    assert(ept < 2 * M - 10);
    E[ept] = {b, 0, c, u, first[a]};
    E[ept + 1] = {a, 0, 0, -u, first[b]};
    first[a] = ept;
    first[b] = ept + 1;
    ept += 2;
}

int prv[N];
llong D[N];
int S, T;
const llong inf = 1e12;

int n;

llong push()
{
    for (int i = 0; i < n; i++)
        D[i] = inf, prv[i] = -1;
    D[S] = 0;
    for (int i = 0; i < n; i++)
    {
        for (int e = 0; e < ept; e++)
        {
            if (E[e].f == E[e].c)
                continue;
            int a = E[e ^ 1].t;
            int b = E[e].t;
            if (D[a] + E[e].u < D[b])
                D[b] = D[a] + E[e].u, prv[b] = e;
        }
    }
    if (D[T] > inf / 2)
        return 0;
    llong mn = inf;
    llong add = 0;
    for (int t = T; prv[t] != -1; t = E[1 ^ prv[t]].t)
        mn = min(mn, (llong)E[prv[t]].c - E[prv[t]].f);
    assert(mn > 0);
    for (int t = T; prv[t] != -1; t = E[1 ^ prv[t]].t)
        E[prv[t]].f += mn, E[prv[t] ^ 1].f -= mn, add += E[prv[t]].u;
    if (add >= 0) {
        return 0;
    }
    return add * mn;
}

int R[N];

int main() {
    int n;
    double dcn, dcf, dcs;
	int tf, ts;
    scanf("%d %lf %lf %lf %d %d", &n, &dcn, &dcf, &dcs, &tf, &ts);
    int cn = (int)(dcn * 100 + 0.5);
    int cf = (int)(dcf * 100 + 0.5);
    int cs = (int)(dcs * 100 + 0.5);
    for (int i = 0; i < n; i++) {
        scanf("%d", &R[i]);
    }

    int ver = 0;
    vector<int> in(n);
    vector<int> out(n);
    int s = ver++;
    int t = ver++;
    S = s, T = t;
    for (int i = 0; i < n; i++) {
        in[i] = ver++;
        out[i] = ver++;
    }
    ::n = ver;
    int sum = accumulate(R, R + n, 0);
    for (int i = 0; i < n; i++) {
        add_edge(in[i], out[i], R[i], -inf);
    }
    for (int i = 0; i < n; i++) {
        add_edge(out[i], t, inf, 0);
        add_edge(s, in[i], inf, cn);
    }
    for (int i = 0; i < n - 1; i++) {
        add_edge(in[i], in[i + 1], inf, 0);
    }
    for (int i = 0; i + tf < n; i++) {
        add_edge(out[i], in[i + tf], inf, cf);
    }
    for (int i = 0; i + ts < n; i++) {
        add_edge(out[i], in[i + ts], inf, cs);
    }
    llong ans = 0;
    while (llong p = push()) {
        ans += p;
    }
    llong bot = sum * -inf;
    assert(ans >= bot);
    assert(ans < (sum - 1) * -inf);
    ans -= bot;
    printf("%lld.%02lld\n", ans / 100, ans % 100);
}

Comments (3)

Write comment?

Xellos

8 years ago, # |

+10

ad E: Determinants are sorcery, inversion is dark sorcery. My solution in $\text{[math]}$ for non-wizards uses the fact that if $\text{[math]}$ lies in the circumcirle of $\text{[math]}$ , then $\text{[math]}$ or $\text{[math]}$ for $\text{[math]}$ respectively on the same side and on opposite sides of $\text{[math]}$ (collinearity is a special case). Angles can be computed using the law of cosines. If we fix $\text{[math]}$ , the problem becomes sorting and two-pointer (well, 3-pointer if we split red points by $\text{[math]}$ ) iteration. Precision wasn't an issue here thanks to additional constraints.