# Warmup Round Editorial

Problemset was formed by Oleg 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 :)

```
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.

```
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.

```
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_{1} and x_{2}.

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} = 1, then we will definitely use the first operation, otherwise we won’t. Invert x_{1}, x_{2}, x_{3} if needed, then, by looking on x_{2} 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_{1} and x_{2}) 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).

```
#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^{3} r) 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

is same as the sign of determinant

This fact has a pretty interesting geometric interpretation consider a paraboloid z = x^{2} + y^{2} in a 3d space. Lift points a, b, c and p up to this paraboloid, denote the result as , , and . It is actually true that p is inside the circumference of a, b and c if and only if is below the plane passing through , and . This statement is defined by a linear inequality and depends on the sign of determinant D, that defines the orientation of a tetrahedron .

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

This problem also allows a solution in time of 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.

```
#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);
}
```

```
#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.

```
#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);
}
```