Hi everybody! Tomorrow at 12:00 UTC there will be the third round of Yandex.Algorithm 2018. You can enter contest from the Algorithm main page.

This round is written by me with a great help of GlebsHP and everybody who was testing the round. While solving the problems, you will be helping some of my colleagues here at Yandex to deal with some practical (or not) situations. Good luck to everybody!

UPD: Round is over! Congratulations to Merkurev, jcvb and Um_nik who got first three places in the standings.

The elimination stage is over and we can now find out who are the contestants that are going to compete in the Algorithm Finals in Saint Petersburg: elimination scoreboard.

There is also a round editorial (ENG only) available.

Good luck and see you later!

Hi everybody,

Today there will be the first day of Moscow Open Olympid, that is the personal programming competition that is held in Moscow each spring. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Team Olympiad, Moscow Olympiad for Young Students and Megapolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466).

Open Olympiad consists of the most interesting and hard problems that are proposed my a wide community of authors, and that is why we decided to give you an opportunity to crack the complete problemset of the contest by making some kind of an experiment. Tomorrow we are going to conduct a rated Codeforces round based on problems of both days of our Olympiad.

We kindly ask all the community members that are going to participate in the competition to show sportsmanship by not trying to cheat in any manner, in particular, by trying to figure out problem statements from the onsite participants. If you end up knowing some of the problems of Moscow Open Olympiad (by participating in it, from some of the onsite contestants or in any other way), please do not participate in the round. We also ask onsite contestants to not discuss problems in public. Failure to comply with any of the rules above may result in a disqualification.

Round will happen at 11:05, March 9th, Moscow time and will last for 2.5 hours. There will be 6 problems in each division.

Round problems were prepared by ch_egor, Sender, Flyrise, cdkrot, malcolm, vintage_Vlad_Makeev under supervision of your humble servant with a great help of meshanya, GlebsHP, Endagorion and Helen Andreeva. Some of the div2 problems were finalized with help of Codeforces team represented by fcspartakm, also we would like to thank round coordinator KAN for his help in deciding which problems to take and all the discussions.

Good luck everybody!

UPD: Announcement email contained incorrect start time. Instead of "12:05, March 9th, Moscow time, 2 hours" it should be "11:05, March 9th, Moscow time, 2.5 hours", as was originally in the round announcement.

UPD2: Round is postponed by 10 5 minutes. Stay tuned :)

Congratulations to the winners!

Division 1:

1. dotorya
2. Swistakk
3. Syloviaely
4. zscoder
5. dreamoon_love_AA
6. SkyDec
7. Marcin_smu
8. yutaka1999
9. Kostroma
10. Will_Dearborn

Division 2:

1. _ChenKerui
2. Demerzel_IV
3. 879333752
4. yyc_jm
5. Anson529
6. iotang
7. wcz112
8. Hankpipi
9. cyz666
10. wwd2075

UPD3: Finally, the editorial is there! Kudos to vintage_Vlad_Makeev and ch_egor for making it appear in a text form.

Hi everybody,

Lasts Sunday there was a 15th Moscow Team Olympiad, high school students competition based in Moscow that is an elimination contest for All-Russian Team Olympiad. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Olympiad for Young Students and Megapolises Olympiad (rounds 327, 342, 345, 376, 401, 433).

Round will be held at 11:05 UTC on Monday and will last for 2 hours. Each division will consist of 6 problems.

Problems are prepared Andreikkaa, Sender, Flyrise, mingaleg, kraskevich, wilwell under supervision of your humble servant with great help of GlebsHP, meshanya, Endagorion and Helen Andreeva.

Discussing problems with anybody who was a participant of Moscow Team Olympiad is strictly prohibited and may be a reason for disqualification.

Good luck everybody!

UPD: Thanks everybody for participation, congratulations to round winner!

Div1 winners:

1. fateice
2. simonlindholm
3. Haghani
4. sunset
5. Petr

Div2 winners:

1. Cypi
2. Nu11
3. zjt_is_our_red_sun
4. GXZlegend
5. Senji

Editorial will be published today after a while.

UPD2: Editorial!

Hi everybody!

These days Moscow is conducting the 2nd International Olympiad of Metropolises that is an international competition for high school students from biggest cities and capitals all around the world. One of the disciplines of the competition is informatics. Rounds of the competition were prepared by the jury members invited from St. Petersburg, Minsk, Almaty and Moscow olympiad scientific committee which you may know by Moscow team Olympiad, Open Olympiad in Informatics and Moscow Olympiad for young students (rounds 327, 342, 345, 376, 401).

We are very grateful to MikeMirzayanov for Polygon system that made it possible to conveniently hold a simultaneous statement translation process into lots of languages. As a good friends of Codeforces platform, we conduct a parallel rated Div. 1 + Div. 2 round on the competition problemset.

Round will happen on September 6th at 12:55 UTC and it will last for two hours. There will be 5 problems for each division, scoring will be announced later.

Scientific Committee of the olympiad consists of: andrewzta, GlebsHP, Endagorion, meshanya, Chmel_Tolstiy, Zlobober, Helen Andreeva and Bakhyt Matkarymov. Problems were prepared by timgaripov, mingaleg, halin.george, vintage_Vlad_Makeev, malcolm, LHiC coordinated by your humble servant.

Codeforces coordinator KAN helped us to choose problems for a round.

Good luck and high ratings for everybody!

PS We kindly ask everybody who knows problems of an on-site event not to participate in a round and not to discuss them in public, as this may be a subject for disqualification.

Congratulations to the winners!

In div. 1 they are:

1. Um_nik
2. fateice
3. KADR
4. dotorya
5. FallDream

In div. 2 they are:

1. jiangIy
2. xolm
3. YxqK
4. lixolas
5. Rawnd

The analysis is published. Thanks to all for participating!

Hi everybody,

Less than in 30 minutes there will start a second round of IOI 2017. Yesterday all the students visited the sixth talles tower in the world named Milad Tower.

We wish all the contestants the good luck!

Some useful links (more to be added):

• First round discussion.
• Official rankings.- Таблица реузльтатов от неутомимого snarknews с множеством разной дополнительной интересной информации.
• Rankings by snarknews with lots of extra interesting information.
• List of the contestants according to the great IOI database.
• IOI website
• Post by SeyedParsa about the Olympiad.
• Mirror contest hosted by Yandex.Contest.

Hi everybody!

I am writing this post from a sunny Tehran where the 29th International Olympiad in Informatics is being held. Me and Mikhail Endagorion Tikhomirov are here as a part of Russian Federation delegation on the Olympiad.

In about four hours the first round of the main competitive programming school student event of the year starts. Russian Federation is presented by one of the youngest team ever in the history of Russia on IOI consisting of:
Vladimir voidmax Romanov, Denis Denisson Shpakovskiy, Alexandra demon1999 Drozdova and Egor Egor.Lifar Lifar.

In Russian version of this post me together with Endagorion are going to make a text coverage of what is happening on the contest. We will mainly concentrate on Russian delegation there, so we are not going to duplicate all the live information in the English version of the post, but we invite all of you who are interested in IOI to discuss the problems and the results in the comments section below.

SPOILER ALERT: the text of this post and the comments may possibly contain lots of spoilers to the competition problems, so if you are going to participate in any online mirror, or you simply want to solve the problems buy yourself then be careful.

PS Some photos with comments in Russian are available at the Telegram channel here.

Some useful links (more to be added):

• Rankings by snarknews with lots of extra interesting information.
• List of the contestants according to the great IOI database.
• IOI website
• Post by SeyedParsa about the Olympiad.
• Mirror contest hosted by Yandex.Contest.

Hi everybody!

Today at 21:00 UTC there will be Yandex.Algorithm 2017 Marathon Round.

You have two days for creating an efficient solution for the optimizational problem we have prepared for you. You may submit for the whole 48 hours of the contest.

This round is the first one among the four elimination rounds. Don't miss!

UPD Testing on final testset will happen tomorrow. Thank you for participation!

Hi,

Midnight tonight (UTC +3) starts the Yandex.Algorithm 2017 Qualification Round. Round lasts for two days in a virtual mode. The contest itself is 100 minutes long. You may start your participation in any moment of time between 21:00 UTC of Friday and 20:59 UTC of Sunday, inclusive.

In order to participate in a competition, you have to complete your registration. It will remain open for everybody until the end of the qualification round.

Those who already successfully submitted at least one problem in a warm-up round are already qualified to the elimination round of the competition. For everybody else in order to be qualified it is necessary to successfully submit at least one problem in a qualification round.

The link to the contest will appear on the site of a competition shortly before the round start time.

Let us remind you that discussion of problem statements and solutions is prohibited until 22:40 UTC of Sunday (the latest possible contest end time for a participant). After that you may discuss problems and solutions in comments of this post or the editorial that will appear after the end of competition.

Good luck!

UPD: There is about 6 hours left to register and participate. Don't miss!

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 :)

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₁ 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).

#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

is same as the sign of determinant

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

Hi,

Today at 13:00 UTC there will be a Warmup Round of Yandex.Algorithm 2017. This is a great possibility for you to get familiar with TCM/Time contest format, and also to pass to the elimination round of the competition by successfully submitting at least one problem.

In order to participate in the competition, you have to register, the registration will remain open for the next week.

The link to the round will appear on the site of the competition shortly before the start of the round.

Good luck!

UPD: Round is over, thanks for the participation! Congratulations to four participants who successfully solved all problems:

1. KrK
2. maksay
3. yangxm
4. sokian

All participants with at least one successful submission pass to the elimination round of the competition.

UPD2: Contest editorial.

We are announcing the annual Yandex.Algorithm 2017 championship! This is a great opportunity to compete with the strongest programmers of the world, win a fancy T-shirt, visit Yandex office or even receive some serious money prize.

I'm sorry for a delay with publishing the editorial.

731A - Night at the Museum

Problem author: egor-belikov, developer: timgaripov

In this problem you have to implement exactly what is written in the statement, i. e. you should find minimum number of rotations from letter a to the first letter in the input, then to the second one and so on. The only useful knowledge that may simplify the solution is that the distance between points x and y on the circle of length l (26 in our case) is min(|x - y|, l - |x - y|).

This solution works in O(|s|), and, of course, fits in time limit.

731B - Coupons and Discounts

Problem author: olympiad jury, developer: platypus179

In a correct answer we may guarantee that for any two consecutive days we use no more than one coupon for bying pizzas in these days. Indeed, if we have two coupons for buying pizzas in days i and i + 1, replace these coupons for two discounts, one for each of the days i and i + 1.

Consider the first day. According to the fact above, we may uniquely find the number of coupons for buying pizzas in 1 and 2 days we are going to use: it's either 0, if there is going to be an even number of pizzas in the first day, or 1 otherwise. The remaining pizzas in the first day will be bought by using discounts. If we use 1 coupon, then we may subtract 1 from the number of pizzas in the second day, and in both cases consider the second day and repeat the same actions.

If at some moment we have the odd number of pizzas and we don't need any pizzas in the following day, then it is impossible to buy all pizzas using only coupons and discounts, and we may output "NO". If it didn't happen, then we were able to buy everything using only coupons and discounts.

Such a solution works in O(n).

Question: Prove that the answer is "YES" if and only if any maximal contiguous segment without zeroes in the input sequence has the even sum.

731C - Socks

Problem author: egor-belikov, developer: wilwell

When solving this problem, it is convenient to use graph interpretation of the problem. Consider the graph, whose vertices correspond to the socks and edges connect those socks that Arseniy wears on some day. By the statement, we have to make that any two vertices connected by an edge have the same color. It actually means that any connected component should share the same color.

For each connected component let's find out which color should we choose for it. In order to recolor the minimum possible number of vertices, we should leave the maximum number of vertices with their original color. It means that the optimum color is the color shared by the most number of vertices in this connected component.

So, we have the following solution: consider all connected components, in each component choose the most popular color and add the difference between the component size and the number of vertices of this color. In order to find the most popular color you may, for example, write all colors in an array, sort it and find the longest contiguous segment of colors.

Such a solution works in .

Question: How to implement this solution so that it works in O(n + m)?

731D - 80-th Level Archeology

Problem author: olympiad jury, developer: Flyrise

Denote as x the number of alphabet cyclic shifts we will perform. Our goal is to formulate the statement of lexicographical order in terms of x.

Note that x may be considered as an integer between 0 and c - 1, i. e., as a residue modulo c. Let's also consider all characters as values between 0 до c - 1 as we may subtract 1 from the value of each character.

Consider two consecutive words in the given list. There are two possibilities corresponding two cases in the definition of lexicographical order:

The first case is when there exists such a position that these words differ in this position and coincide before this position. Suppose that first word has value of a on this position, and second word has the value of b. Then these words will follow in lexicographical order if and only if . It's easy to see that if we consider all residues modulo c as a circle, then this inequality defines an arc of possible x's on this circle. So, this pair of contiguous words produces the following statement "x belongs to some arc on the circle".

The second case is when there is no such a position, i. e. one word is a prefix of another. If the first word is a prefix of second one then these words always follow in lexicographical order irrespective to the choice of x. In the other case (second word is a proper prefix of the first word) we can't do anything with these to words since they will never follow in a lexicographical order, so we should print  - 1.

Now we have to find a point on the circle belonging to the given set of arcs. Suppose we have k arcs. Consider a line segment from 0 to c - 1 instead of a circle; each arc will transform to either one or two its subsegments.

Now we have to find out if there exists a point covered by exactly k segments. It may be done in different ways, for example you may add 1 on each of this segment by using some data structure, or you may add 1 to the left endpoint of each segment and  - 1 to the point after the right endpoint of each segment, and consider prefix sums (an off-line way to handle range addition queries). Or you may write down all endpoints of all segments, sort them by a coordinate and iterate over them from left to right, keeping the number of open segments. If at some moment you have exactly k open segments, then the answer is "YES".

731E - Funny Game

Problem author: meshanya, developer: ipavlov

First of all, comment on such type of games. In CS the game where two players are willing to maximize the difference between their own score and the score of their opponent is called a "zero-sum game". A useful knowledge is that problems for such a kind of games are usually solved using dynamic programming.

Note that at any moment the first sticker contains the sum of numbers on some prefix of an original sequence. This means that the state of a game is defined by a single number i: the length of an original sequence prefix that were summed into a single number.

Let's make two observations. First of all, for any state i the turn that current player will perform doesn't depend on scores of both players. Indeed, at any moment we may forget about the scores of both players since they add the constant factor to the resulting score difference, so we may virtually discard both players current scores. So, all we need to know about state i is what difference there will be between the current player score and his opponent score if the game would have started from the state i with zero scores.

Second observation is that the turn chosen by a player from the state i and the final difference of scores at the end does not depend from which player is currently making a turn (Petr or Gennady), i. e. the game is symmetric.

Denote as D[i] the difference between the first player score and the second player score if the game would have started from the state i with zero scores.

It is a convenient way to think about this game as if there were no separate scores of two players, but only a single balance value (difference) between them, and the first player is adding some numbers to the balance at his turn аnd second player subtracts some numbers from the balance. In such formulation D[i] is a balance change at the end of the game if the current player is willing to maximize it and he is currently in the state i. The answer for a problem will be, as one can see, D[1]. Note that if the current player would be willing to minimize balance, then the final balance change from the state i would be  - D[i] because the game is symmetric.

Let's calculate all D[i] using dynamic programming. At the end of the game, i. e. in the state n the value D[n] is equal to zero because the players won't be making any turns, and so the balance won't change.

Consider some state i. Suppose current player will take all the stickers up to the j-th (here j-th means the index in the original sequence). In such case he will change balance by S[j] (where S[j] is the sum of first j numbers in an original sequence), and game will move to the state j. After that his opponent will change the balance by  - D[j] (note that the balance change value is added with an opposite sign since the opponent will be playing from this state).

So, the final balance change when making such a turn will be S[j] - D[j]. In the DP definition we play for a player that is willing to maximize the balance, so .

Such a formula produces a solution in O(n²), but one may find that that it's enough to keep the maximum value of S[j] - D[j] on suffix j > i, recalculating it in O(1) when moving from i to i - 1. So, we have the solution that works in O(n).

Question: Which data type should be used for D[i] (and for the answer, in particular)?

731F - Video Cards

Problem author: olympiad jury, developer: vintage_Vlad_Makeev

First observation is that if we fix the leading video card power x, we may take all the video cards of power at least x, as each of them brings the positive power value. So, we may sort all the cards in the ascending power order and then we will always choose some suffix of cards in such an order.

The final total power equals to . Note that under the summation there is a number that is divisible by x and that is no larger than 200 000 at the same time. It means that there are no more than different terms in this sum. Let's calculate the value of a sum spending the operations proportional to the number of different terms in it.

To do it we need to find out for each of the values x, 2x, 3x, ..., how many video cards will have exactly such power at the end. It's easy: final power kx corresponds to those video cards, which originally had the power between kx and (k + 1)x - 1. Their number can be found out in O(1) if we build an array C[i] storing the number of video cards of each power and calculate prefix sums on it.

It means that we got a solution that performs about operations. It's useful to know that the sum inside brackets is called a harmonic series, and that its sum is very close to the natural logarithm of the number of terms (up to a constant factor in limit).

It means that we got a solution in complexity of where m is the maximum power of a single video card.

Question: One may try to submit a solution assuming that the optimum power is always one of the first, let's say, 100 unique video cards in an ascending power order. How to build a test where the optimum power lies between 1/4 and 3/4 of a sorted power list, i. e. a counter-test for such a solution?

Hi everybody!

Tomorrow at 09:35 UTC there will be Codeforces Round #376 that is dedicated for the second division. At the same time there will be a Moscow School Team Olympiad, and, as a nice tradition, we bring you a CodeForces round based on its problems. Unfortunately, this time we weren't able to come up with a good problemset for a first division contestants, but, as usual, we invite first division to participate unofficially in this round.

Problems were prepared by timgaripov, platypus179, wilwell, Flyrise, ipavlov and vintage_Vlad_Makeev under my control. We would like to thank members of jury of the Team Olympiad: Endagorion, Helen Andreeva and GlebsHP, who also works as a coordinator from the CodeForces side. Also we are very grateful to MikeMirzayanov for a Polygon system that makes problem preparation and coordination of many involved people much simpler, and for a great CodeForces community that we are all part of.

We suggest you 6 problems for 2 hours. Good luck!

UPD The contest is over, results are final, thanks for participating! The editorial will be published later

UPD2 I'm sorry for an editorial delay. It's finally available here.

Congratulations to contest winners:

1. DmitryBelikov
2. ljsss
3. kehKeLenge
4. dilsonguim
5. UoA_Menma

UPD2: Tomorrow (July 31st, Sunday) at UTC 10:00 there will be an online mirror of Yandex.Algorithm final round.

Enter contest.

Everybody are invited to participate! You may discuss problems in comments after the contest ends.

UPD3: The online mirror has finished! Congratulations to ImBarD aka Vercingetorix for taking the first place.

Problem editorial

===================================================

Hi everybody!

We're glad to remind you that tomorrow, July 29th, at 9:00 AM UTC there will be the Final Round of Yandex.Algorithm 2016 in Minsk. List of finalists and elimination stage results are available on Yandex.Algorithm website.

You can watch follow the news on final round at Yandex.Algorithm website. Want to solve final round problems? On Sunday, July 31st, at 10:00 AM UTC there will be a mirror of the competition. Everybody can participate in it, solve the same problems as finalists and try his or her best on the finals' problemset.

The final round has been prepared by authors of previous stages of Yandex.Algorithm: Endagorion, Romka, Chmel_Tolstiy, GlebsHP, snarknews, Gassa and your humble servant. We believe that problems are various and interesting.

In this post after the cut I'll write some comments about what happens in the contest trying not to spoil any important details (we don't want to provde help or to ruin contest for any of the participants, isn't it?).

See you tomorrow!

UPD:

Congratulations to the winners!

1. Egor winning 300 thousands of rubles.
2. W4yneb0t winning 150 thousands of rubles.
3. rng_58 winning 90 thousands of rubles.

Final results are available here. The competition is finished, everybody are invited to participate an online mirror on Sunday!

Unfortunately Codeforces fails to show formulas in an editorial and I can't even press on "Preview" button :( While it doesn't work as intended, I put a bit ugly pdf-version of an editorial here. Unfortunately without model solution sources yet.

Russian editorial

English editorial

Hi everybody!

I'm glad to invite you to the Yandex Algorithm Round 2 that will happen tomorrow at 21:00 Moscow Time. This round is prepared by me with a great help of GlebsHP. I want to say thanks to Chmel_Tolstiy, snarknews and Gassa for their support during the preparation and to all of the Yandex developers that tested this round.

Good luck and have fun!

Link to the contest will be posted here as soon as I manage to find it by myself :)

UPD: the link to the contest is located here: https://contest.yandex.com/algorithm2016/contest/2540/enter/

UPD2: Thanks everybody for the participation, I hope you enjoyed the round! Results will be available shortly. I'd like to publish an editorial, but it fails to compile on Codeforces and I'm trying to fix this issue.

UPD3: Congratulations to winners:

1. jqdai0815
2. eatmore
3. rng_58
4. jcvb
5. KAN

The preliminary pdf-version of an editorial is posted: http://codeforces.me/blog/entry/45354. Continuing the nice tradition of providing an editorial with questions related to the problems, I invite you to think about them/

Hi everybody! FYI, 1st Qualification Round of RCC starts in less than an hour. I still don't see any kind of announcement on CF, so let it be here.

Good luck!

Opencup: GP of Baltics has just finished. We are curious, what are the normal solutions for A, B and F?

Hi everybody!

Glad to tell you that tomorrow on 9:05 UTC there will be Codeforces Round #345. The round is formed of the first day of X Moscow Open Olympiad problemset with several additional problems created for this round. This round is brought to you by the scientific committee of Moscow Programming Olympiads controlled by GlebsHP, romanandreev and your humble servant, and also with a great help of fcspartakm who helped us make a complete problemset of our problems.

The round will be conducted under the standard Codeforces rules, you will be given 5 problems for 2 hours. Yes, this round is rated :)

Note that because of holding the main onsite round system testing and upsolving will be available no earlier than 12:35 UTC. Also we would like to ask you to not discuss problems in comments during the time between the end of the round and the end of the onsite competition. All comments with discussions will be removed and the most active violators will be punished. Thanks for your understanding.

UPD Sorry, the round start was moved to 9:25 UTC. It is not easy to run onsite round and Codeforces Round simultaneously!

UPD2 You may discuss the solutions! System testing will be run shortly.

UPD3 The editorial has finally appeared: http://codeforces.me/blog/entry/43677 Sorry for the delay!

Hacker Cup Final round is starting in 5 minutes. List of finalists: http://codeforces.me/blog/entry/23177

You can (probably) find the standings somewhere at http://facebook.com/hackercup

Today (January 30th) at 10:00 AM PST / 21:00 MSK there will be the last online round for FHC. Don't miss the round!

As you remember, top-25 contestants will go to the onsite round in London.

Good luck to everybody!

UPD: UP! The round is in 30 minutes.

Tomorrow (January 23rd) at 10:00 AM PST / 21:00 MSK there will be a second round of Facebook Hacker Cup. Don't miss!

I still don't know how to get to the dashboard from the official page (http://facebook.com/hackercup) through the links. Can somebody of the officials that spend time on CodeForces teach me how do I get there in deterministic manner? Maybe a video tutorial? Or maybe you can just make design compatible with human put the big link to it somewhere on the main page? After all, it is the most important link people want to see on the competition page :(

For those having the same headache with getting there, a link to the list of all rounds: link.

Let's discuss problems here.

GP of Ekateinburg has just finished. Let's discuss problems here. How to solve H?

(Russian version of the post contains my anger about statements).

Hi everybody! It was my first experience of writing problems for TopCoder SRM, hope you liked it. I was a writer of Easy and Medium task in both divisions, subscriber was an author of both Hard tasks. In div1 they were harder than usual, but I hope you still liked them.

Div2 easy

This task was just about implementing exactly what is described in the statement. Looks like Python has a built-in support of set comparison. Usually coders using Python have a disadvantage, but in this task it looks more like an advantage :) There are built-in functions for sets in C++ and Java too, I recommend to learn about them even if you successfully submitted this problem.

Div2 medium

Knowing strings a and b, we can build a reverse mapping q[d] = c, that maps the encoded letter d to it's original corresponding letter c. For letters that do not appear in b, we remember that we don't know their pre-image. After that, we just apply our mapping q to a string y. If some of letters doesn't have a pre-image, we should return "", otherwise we return q(y).

There is an only special case that appears in sample tests: if we know pre-images of all letters except one, we may still uniquely understand what is its pre-image: it is the only letter that doesn't appear in string a.

Div2 hard

This task is an easier version of Div1-hard. In this version it was enough to write a BFS on a graph of all possible states. In this task the state is a set of all already people. Each set can be represented as a binary masks no larger than 2¹⁸ = 262144 that is small enough to fit in TL.

Div1 easy

A first solution coming to a head works in : all we need is to just simulate the process. Suppose we are now standing in number n, the last hour was h, it means that we need to find a first divisor of n or n - 1 larger than f and perform n +  +  or n –  depending on whose (n or n - 1) divisor appears first. Although, one can build a test where number of steps is ~2000, it makes this solution pretty hard to fit in time limit, one of such tests is a last sample test.

The key observation is that when we change our number, we don't need to find divisors of a new number from scratch. The well-known divisor finding algorithm consists of two stages: first we consider all divisors smaller than , then all divisors larger than . If we were on the first stage, then we just need to continue iteration from the same place for a new number. If we are on the second stage, we also continue iterating the second stage with a new number. This works in since our number can't infinitely increase (it can be shown that it can't move further than 2n, actually it doesn't move further than 100).

The other solution was to cache the divisors for all values of n that happen during the execution.

Div1 medium

The first observation is that an almost-Eulerian graph can be obtained from a unique Eulerian graph. Indeed, if we have an almost-Eulerian graph G that is not Eulerian, then there exists the only pair of vertices u and v that have an odd degree, the only possible original Eulerian graph G' is (here means inverting the specific edge, adding it or removing it). If G is Eulerian itself, then we obviously can't invert some edge keeping it being Eulerian.

This means that if there are E_n Eulerian graphs, then there are exactly almost-Eulerian graphs: each Eulerian graph G produces itself and all possible as almost-Eulerian graphs.

Now we need to calculate number of Eulerian graphs on n vertices, E_n. It's well-known that the graph is Eulerian iff it is connected and all its vertices have even degree. The good idea is to first calculate D_n, the number of graphs with all even degrees. If we succeed in it, we can then calculate E_n by using inclusion-exclusion principle on D_n.

How many even graphs on n vertices are there? The simplest way to understand that is to remove some vertex from it (let's say, a vertex 1) and notice that the graph on remaining vertices 2, ..., n may contain an arbitrary set of edges. Indeed, if there are some odd vertices among them, then when we return vertex 1 back to the graph, we have to connect it to all odd vertices among 2, ..., n. After that all 2, ..., n become even vertices, and 1 itself also becomes even due to handshake lemma. So, the answer is since there may be any possible set of edges between vertices 2, ..., n and all edges from 1 to the rest of the graph may be uniquely determined.

Now how to calculate E_n. We know that E_n = D_n - R_n where R_n is number of disconnected even graphs. Suppose that the connected component that contains vertex number 1 consists of k vertices (obviously, 1 ≤ k ≤ n - 1). Then there are ways to choose k - 1 vertices in this connected component from n - 1 remaining vertices, also there are E_k ways to organize a connected component that has all even degrees and there are D_n - k ways to organize an even graph on the rest of the vertices (note that it may possibly be disconnected if there were 3 or more components in the original graph, that's why we use D_n - k but not E_n - k here). So, there is a recursive formula: that leads us to an O(n²) DP solution.

Div1 hard

I'll describe an approach for this problem very briefly.

What we actually need in this task is to understand how the described process works. We can describe the process in following way. The detective acts almost like a Prim's algorithm: in each step he adds one of the maximal edges between the already visited set and the rest of the vertices in the graph. The only thing that we may adjust is an order of choosing the edges with the equal cost.

At any moment the visited vertices form some part of a maximum spanning tree. Suppose we want to get to vertex x in minimum number of steps. Consider the resulting path between 0 and x. It is a well-known fact that the minimum edge on this number is uniquely defined and is equal to a maximum possible minimum edge among all paths from 0 to x. Suppose the value of this edge is equal to d. We can calculate d by running a Floyd algorithm modification for metric d(u, v) =  minimum on path between u and v, that is needed to be maximized.

There are edges of two kinds on a path from 0 to x: those who are equal to d and those who are larger than d. In any situation we prefer larger edges, so when we touch a vertex with some outgoing edges larger than d, we will greedily first visit all those edges. So, let's contract all components connected by edges larger than d.

After contracting all we need is to find a shortest path from 0 to x remembering that each time we visit a vertex, we have to add a size of its connected component described above.