Hi all!

I invite you to participate in the gym contest LU ICPC Selection Contest 2023 on Nov/08/2023 17:35 (Moscow time)! The onsite contest has been held on October 13th in Riga to select two teams from the University of Latvia to CERC 2023. Here's the headline of the local poster (in Latvian):

The contest has been prepared by me, cfk and Pakalns. Hopefully you'll find the problems interesting!

Hi all!

I invite you to take participation in the ICPC gym contest University of Latvia Selection Contest 2020 / Kazan Federal University Open Contest 2020 this Nov/21/2020 11:00 (Moscow time)! The contest has been held on October 31st in Latvia, to select the best teams from LU to advance to the quarterfinals (Belarus and Baltics Regional Contest), and then on November 1st in Kazan, at the KFU Open championship for university and high school students.

The contest has been prepared by AcidWrongGod, Ferume, KamilBek, cfk, gen, lessmeaning by authors from both LU and KFU.

The statements will be both in English and Russian. If you have some free time this Saturday, enjoy!

Hi everyone!

I am happy to invite you to take participation in the online mirror of the Baltic Olympiad in Informatics 2020 to be held on Jul/22/2020 14:05 (Moscow time) and Jul/23/2020 14:05 (Moscow time) on Codeforces!

The Baltic Olympiad in Informatics 2020 (BOI 2020) is an individual contest for secondary school students from eleven countries (in alphabetic order): Denmark, Estonia, Finland, Germany, Iceland, Latvia, Lithuania, Norway, Poland, Sweden and Ukraine. Over 60 secondary school students compete against each other, solving difficult problems of algorithmic nature. Each country sends their top 6 contestants from their national olympiads which take place in the months beforehand. You can check out the official web page at boi2020.lv.

The contest consists of two days; each day the students are given 5 hours to solve 3 problems of various difficulty. Each problem is worth 100 points that are distributed into multiple subtasks with different constraints that allow the participant to earn partial score. For the testing, the IOI grading format is used, where the participant receives full feedback of the execution of the solution on all tests during the contest.

This year the contest was supposed to be held in Latvia, Ventspils, but is not held onsite due to the pandemic, and the students will compete in a proctored setting online. With generous help from MikeMirzayanov, we are glad to also provide the mirror contest at Codeforces for anyone interested.

Note that the contest is not rated. The mirror starts with a delay of 1 day, 1 hour and 5 minutes.

We wish you to enjoy the contest! :)

-- BOI 2020 committee

Martins Opmanis, Rihards Opmanis, Sergey Melnik, andreyv, Pakalns, gen, eduardische, Alex_2oo8, nvilcins, KarlisS.

UPD1: The scoreboard will not be public, each participant will be able to see only the results of their own submissions.

UPD2: Tutorial for Day 1 has been published.

UPD3: Tutorial for Day 2 has been published.

UPD4: Congratulations to full score 600 point winners WZYYN, isaf27, Arpa!

Hi guys!

Glad to invite you to Codeforces Round #599 to be held this Nov/06/2019 18:05 (Moscow time)!

My name is Evgeny Vihrov, this is already my 6th Codeforces contest as an author. To introduce myself, I have participated twice in the ACM ICPC Finals (2012, 2014) and currently I am co-coaching teams for the ICPC at the University of Latvia. This is my first solo round, and it took 3.5 years to make! (the last one was #347 with Alex_2oo8).

In this contest you will have to help Ujan deal with his renovation issues. Hopefully, everyone will find a problem matching their taste!

Huge thanks to arsijo for coordinating the preparation of the contest and for the patience with the frequent delays. :) Thanks to Xellos, Origenes, KAN and _overrated_ for generously testing the round. And as always, thanks to MikeMirzayanov for the panem et circenses Codeforces and Polygon systems!

Wish you an exciting round!

UPD1: McDic is joining as a coauthor of the contest (reasons to be revealed later)!

UPD2: Scoring:

Div. 1: 500-1000-1500-2000-2500

Div. 2: 500-500-750-1500-2000-2500

UPD3: Thanks for participating! Congratulations to the winners!!!

Div. 1:

1. Benq
2. jqdai0815
3. ecnerwala
4. AndreySergunin
5. tribute_to_Ukraine_2022

Div. 2:

1. hakobdilif
2. is1813r
3. Fype
4. KenMuse
5. tdas

UPD4: The editorial will be available tomorrow, sorry for the delay. :((

UPD5: The reason behind McDic entering as a coauthor is that one problem was exactly identical to some problem from some Codeforces round. We found out about it only at the last day before the contest, and McDic generously allowed to use his problem.

UPD6: Editorial is posted.

Hello, Codeforces!

I'm glad to invite you to participate in the online mirror of the Baltic Selection Contest for ACM ICPC 2015–2016 that will take place in Gym on the 22nd of October, 13:00 UTC.

This competition determines the best teams throughout the universities of Latvia, Lithuania and Estonia that will participate in ACM ICPC NEERC Western subregional contest in Minsk, Belarus. The onsite contest was held on the 12th of October. The participating universities were University of Latvia, Vilnius University, Kaunas University of Technology, Vilnius Gediminas Technical University, Estonian Information Technology College and others.

As a bonus, I'm posting some photos of the onsite action at University of Latvia. :)

The top 5 teams at the onsite competition were:

1. LU: 64428b862de0207ba0385b1ed2df43e1 (Alex_2oo8, zmad)
2. VU: 2B||!2B (vstrimaitis, jDomantas, JustasK)
3. LU: 0x7DF (Pakalns, Candyman, A_Le_K)
4. LU: leet (Instasamka, how_to_become_purple, JustN)
5. KTU #1 (wi_lius, lukgar, ASBusinessMagnet)

The detailed onsite standings will be posted after the contest.

The problems were prepared by a group of authors from University of Latvia: gen, KarlisS, andreyv, cfk.

Good luck & have fun!

405A - Gravity Flip

Observe that in the final configuration the heights of the columns are in non-decreasing order. Also, the number of columns of each height remains the same. This means that the answer to the problem is the sorted sequence of the given column heights.

Solution complexity: O(n), since we can sort by counting.

405B - Domino Effect

If the first pushed domino from the left was pushed to the left at position l, all dominoes at prefix [1;l] fall down, otherwise let l be 0. Similarly, if the first pushed domino from the right was pushed to the right at position r, all dominoes at suffix [r;n] also fall down, otherwise let r be n + 1. Now, in the segment (l;r) there will remain vertical dominoes and blocks of dominoes supported by the equal forces from both sides.

When does a domino at position p in segment (l, r) remains standing vertically? One way is that it is not pushed by any other domino. This could be easily checked by looking at the pushed dominoes closest to p (from both sides). It is pushed by dominoes, only if the closest from the left was pushed to the right, and the closest from the right was pushed to the left. Suppose these dominoes are at positions x and y, x < p < y. Then, the only way that the domino is still standing is if it is positioned at the center of the block [x;y], which could be checked by .

Solution complexity: O(n) / O(n²), depends on implementation.

406A - Unusual Product

Written as a formula, the problem asks to find the value of

Suppose that i ≠ j. Then the sum contains summands A_ijA_ji and A_jiA_ij. Since the sum is taken modulo 2, these summands together give 0 to the sum. It follows that the expression is always equal to the sum of the diagonal bits:

Now, each query of type 1 and 2 flips the value of exactly one bit on the diagonal. Thus we can calculate the unusual product of the original matrix, and flip its value after each query of type 1 and 2.

Solution complexity: O(n + q), if we don't take the reading of the input into account... :)

406B - Toy Sum

Let's define the symmetric number of k to be s + 1 - k. Since in this case s is an even number, k ≠ s - k.

Note that (k - 1) + (s + 1 - k) = s, i.e., the sum of a number and its symmetric is always s. Let's process the given members x of X. There can be two cases:

1. If the symmetric of x does not belong to X, we add it to Y. Both give equal values to the respective sums: x - 1 = s - (s + 1 - x).
2. The symmetric of x belongs to X. Then we pick any y that neither y and symmetric of y belong to X, and add them to Y. Both pairs give equal values to the respective sums, namely s.

How to prove that in the second step we can always find such y? Let the number of symmetric pairs that were processed in the step 1 be a, then there remain other pairs. Among them, for pairs both members belong to X, and for other pairs none of the members belong to X. To be able to pick the same number of pairs for Y, as there are in X, we should have

which is equivalent to , as given in the statement.

Solution complexity: O(s) / O(n).

406C - Graph Cutting

It can be proved that only graphs with an odd number of edges cannot be partitioned into path of length 2. We will construct a recursive function that solves the problem and also serves as a proof for this statement.

The function partition(v) will operate on non-blocked edges. It will partition the component of vertex v connected by the non-blocked edges into paths of length 2. If this component has an odd number of edges, the function will partition all the edges of the component, except one edge (u, v); the function then will return vertex u, expecting that the parent function call will assign it to some path.

The function works as follows: find all vertices that are adjacent to v by the non-blocked edges, call this set adjacent. Then block all the edges from this set vertices to v. For each u in adjacent, call partition(u). Suppose partition(u) returned a vertex w. That means we can pair it into the path (v, u, w). Otherwise, if partition(u) does not return anything, we add u to unpaired, since the edge (v, u) is not yet in any path. We can pair any two vertices of this set u, w into a single path (u, v, w). We pair as much of them as possible in any order. If from this set a single vertex, u, is left unpaired, the function will return u. Otherwise the function will not return anything.

The function could be implemented as a single DFS:

partition(v) :
    adjacent = { u | not blocked[(u,v)] }
    for(u : adjacent)
        blocked[(u,v)] = true

    unpaired = {}
    for(u : adjacent)
        int w = partition(u)
        if(w = 0)
            add(unpaired, u)
        else
            print(v,u,w)

    while(size(unpaired) >= 2)
        int u = pop(unpaired)
        int w = pop(unpaired)
        print(u,v,w)

    if(not empty(unpaired))
        return pop(unpaired)
    else
        return 0

Solution complexity: O(n + m).

406D - Hill Climbing

Note that the path of each hill climber is strictly convex in any case. Let's draw the paths from all hills to the rightmost hill. Then these paths form a tree with the "root" at the top of the rightmost hill. We can apply the Graham scan from the right to the left to find the edges of this tree. Each pop and insert in the stack corresponds to a single edge in the tree.

Now it is easy to see that for each team of climbers, we should calculate the number of the lowest common ancestor for the corresponding two vertices in the tree. The size if the tree is n, so each query works in .

Solution complexity: .

406E - Hamming Triples

Let's look at the Hamming graph of all possible distinct 2n strings, where each two strings are connected by an edge with length equal to the Hamming distance between these strings. We can observe that this graph has a nice property: if we arrange the vertices cyclically as a regular 2n-gon with a side length of 1, then the Hamming distance between two strings is the length of the shortest route between these vertices on the perimeter of the polygon.

For example, the figure shows the graph for n = 3. The gray edges have length 1, the orange edges have length 2 and the blue edges have length 3. That is the corresponding Hamming distance.

Now, we can convert each string coded by a pair (s, f) to an integer (f + 1)·n - s. The new numbers will be 0, 1, ..., 2n - 1 and correspond to the same cyclical order on the perimeter of the polygon. The given strings are mapped to some subset of the vertices. Now we have to find the number of triangles (possibly degenerate) with maximal perimeter in this subgraph. It will be useful to keep the new converted numbers sorted.

First, we can figure out what this perimeter could be. If there exists a diameter in the full graph, so that all of the points are on one side of the diameter, the perimeter is 2d, where d is the length of the longest edge:

Then any triangle with two vertices at the longest edge points and the third one being any point has the maximal perimeter. Since the numbers are sorted, the longest edge in this case will be produced by two cyclically adjacent elements, which is not hard to find.

If for any diameter this does not hold, then the maximal perimeter is 2n. This can be proved by taking two different points a, b and drawing two diameters with them as endpoints; since it is not the previous case, there shoud be a third point c in area where the perimeter of triangle a, b, c is 2n.

The tricky part is to count the triples in this case. We do this by working with the diameter (0, n). There can be several cases:

1. A maximum triangle has vertices 0 and n. This a simple case: with any other vertex as the third the triangle has perimeter 2n.
2. A maximum triangle has vertex 0, but not n. Then the second vertex should be in interval [0, n), and the third in interval (n + 1, 2n - 1], and the clockwise distance between the second and the third should not exceed n (since then the perimeter of the triangle would be less than 2n). We count the number of such triples iterating two pointers (one in each of these intervals). For each pointer in the first interval, all points from n + 1 till the second pointer will make a maximal perimeter triangle. We similarly solve the case where the maximal triangle has vertex n, but not 0.
3. The maximal triangle does not have 0 or n as its vertices. Then one vertex of the triangle should be on one side of diameter (0, n), and two should be on the opposite side. To count them, we iterate a vertex pointer on the first side, say, (0, n); let the diametrally opposite vertex on the opposite side be x. Then the second vertex can be any in [n + 1, s], and the third can be any of the [s, 2n - 1]. It is easy to calculate these numbers using partial sums on the circle. Note that s can be both the second and the third vertex (since strings can repeat). So we iterate this pointer over all one side vertices and update the answer. Similarly we solve the case where a single vertex is on the other side, and two on this side.

One only needs to be careful with the formulas in each case.

Solution complexity: , because of the sorting.

Post Scriptum

What were your solutions? Feel free to share any solutions or thoughts! For example, was there a solution to DivI E simpler than in this tutorial?

Hello everyone!

Codeforces round #238 will start today at 19:30 in Moscow time. The round will be held in both divisions.

The round was prepared by me and cfk. This is the 4th round for me and the 2nd for Krisjanis. I think the problems this time are rather unusual and maybe even surprising. We have no doubt that everyone will find a problem that suits their taste! But you have to find it. (:

As always, thanks to Mikhail Mirzayanov (MikeMirzayanov) for Codeforces and Polygon systems, and Maria Belova (Delinur) for translating the statements. Big thanks to Gerald Agapov (Gerald) for helping in preparation of the contest. Me and Gerald had a chance to talk about the problems onsite during the Petrozavodsk winter camp, which I think was very productive.

We wish you a very exciting round!

UPD1: Score distribution:

DivI: 500 1000 2000 2000 2500

DivII: 500 1000 1500 2000 3000

The scoring for the problems is relative, so that the cost of each problem would be a multiple of 500 and closer to the objective estimate. Don't be afraid, the problems are not really that hard. (:

UPD2: Congratulations to the winners!

DivI:

1. al13n
2. Shef
3. scott_wu
4. sillycross
5. Komaki

DivII:

1. NelsonMondialu
2. L_Ecry
3. aaaaAaaaaAaaaaAaaaaA
4. xorfire
5. Hec

UPD3: Excellent round statistics from DmitriyH.

UPD4: The contest tutorial is published here.

Hi everyone!

The ACM ICPC season is in full swing, and the Northwestern European Regional Contest (NWERC) is not so far away from now. This is why the University of Cambridge held a selection contest for its 9 teams to determine the best (two or more) teams that will compete for a place in the world finals. In the end, the following teams took the top 5 places in order:

1. Fin! IRO (pooya_, bogdan2412, VladGavrila)
2. Beuler (borisgrubic, lm497, dcevid)
3. Rooftop Cornflakes (eduardische, Chortos-2, Gullesnuffs)
4. Zrakomlati (PetarV, mbucic4, dsobot)
5. CRTCM (Voro94, Andip, hadesgames)

Congratulations!

The competition was held on the CodeForces platform and prepared by me and MikeMirzayanov. It was organized by University of Cambridge lecturer Dr Andrew Rice, eduardische Chortos-2 and the coach of the Latvian IOI team Sergey Melnik. The contest itself used the problem set of the Southern Subregional (NEERC) ACM ICPC quarterfinal 2013. Yes, the same quarterfinal whose online version will be held as a contest in the Codeforces gym on 27 October. ;] You may have just thought that you missed something unusual on CF, but nothing of the kind! The contest was run using a (still secret) future Codeforces tool in test mode; the name is groups.

This functionality will give the opportunity to hold contests only for a specific set of participants and spectators. A manager of the group adds users to the group and chooses their access restriction types. Only group members can participate in contests within this group, as well as observe their results. As you can see, groups are well-fit for on-site contests of various sorts. Indeed, this time we used the test version of this tool exactly for this purpose. Special thanks to MikeMirzayanov for the opportunity to try this new functionality! Now I'll leave a couple of teaser pictures for you: ;]

In conclusion, a few words about the selection itself. The number of problems solved by the top 5 teams is 10, 9, 8, 7, 6, which is a serious claim from the University of Cambridge compared to the results of the on-site of the same quarterfinal. ;] During the contest, the top three teams were engaged in an intense struggle for the first two places, but in the middle of the contest Fin! IRO made their way to the top and held a stable lead with many solved problems. Teams Beuler and Rooftop Cornflakes kept pace almost until the end of the contest, until the former solved a whole two problems in the last hour. The latter also then managed to solve two problems in the last hour, but Beuler got an accepted submission for problem D at 4:47 and secured the 2nd place, while Rooftop Cornflakes got the 3rd. The full results of the teams from Cambridge will be embedded into the results of the gym contest on the problems from the Southern (NEERC) quarterfinal.

344A - Magnets

By the definition each block consists of a number of consequent and equally oriented dominoes. That means that in places where adjacent dominoes are not oriented equally, one block ends and another block starts. So, if there are x such places, the answer is equal to x + 1.

Solution complexity: O(n). Problem author: gen.

Bonus: The problem was created a day before the contest and filled in the last part of a physically flavoured DivII complect. :]

344B - Simple Molecules

First solution. First, the sum a + b + c should be even, since each bond adds 2 to the sum. Now let x, y, z be the number of bonds between 1st and 2nd, 2nd and 3rd, 3rd and 1st atoms, accordingly. So we have to solve the system x + z = a, y + x = b, z + y = c. Now observe that the solution to the system is the length of the tangents on the triangle with sides of length a, b, c to its inscribed circle, and are equal to , , . If the problem asked only the possibility of building such a molecule, we could just check if there exists (possibly degenerate) triangle with sides a, b, c.

Second solution. Bruteforce all x values. For a fixed x values of y and z are defined uniquely: y = b - x, z = a - x.

Solution complexity: O(1) / O(n). Problem authors: gen, andreyv.

Bonus: Can you solve the problem for any vertex number n? When and how can such a graph be built?

343A - Rational Resistance

If a fraction can be obtained with k resistors, then it is simple to calculate that we can obtain fractions and with k + 1 resistors. So adding one resistor means performing one operation backwards in Euclidean algorithm. That means that the answer is equal to the number of steps in standard Euclidean algorithm.

Solution complexity: . Problem authors: gen, andreyv.

Бонус: At first we thought about the major problem (any two elements can be joined), but had a moment of eureka and got that the given problem unexpectedly naturally can be reduced to GCD. By the way, the result tree — http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree.

343B - Alternating Current

Let us solve the following problem first: we are given a string of symbols A and B. If the i-th symbol is A, then at the i-th step the upper wire (see figure) is being put over the lower wire. If the i-th symbol is B, the lower wire is being put over the upper wire at i-th step. Observe that if some two symbols A and B are adjacent, we can untangle this place, throw the symbols out and obtain the string of length two symbols less. So the wires can be untangled iff the number of A's and B's in the string is the same. The given problem can be reduced to the described in a following fashion: in each odd position we change – to B and + to A. In each even position we change — to A and + to B. The reduction is correct, since on each even position the order of — and + are always swapped, and in each odd position their order is the same as in the beginning.

Solution complexity: O(n). Problem authors: gen, andreyv.

Bonus: If you are interested by this problem, you can learn about the braid theory http://en.wikipedia.org/wiki/Braid_theory :] Fun fact: a harder version of this problem was planned already for Round #142, but the error in solution idea was found, and the problem was left to lay for almost a year.

343C - Read Time

Let's search the answer t with the binary search. Fix some value of t. Look at the first head from the left h[i] that can read track p[0]. If p[0] > h[i], then h[i] goes to the right t seconds and reads all tracks on its way. Otherwise if p[0] ≤ h[i], then the head has two choices:

1. go to the right seconds, then to the left and h[i] - p[0] again to the left;
2. go to the left h[i] - p[0] seconds, then h[i] - p[0] to the right and t - 2·(h[i] - p[0]) again to the right.

Obviously, for h[i] it is more advantageous to visit the track positioned as much as possible to the right. So we choose by . Then we move the pointer onto the first unread track, and repeat the algorithm for h[i + 1], and so on with each head.

Solution complexity: . Problem authors: gen, gorbunov.

Bonus: The problem is completely real, if the disk has only a single head, if we know, what tracks should be read; then the optimal algorithm chooses between the two choices described above. I and gorbunov were listening this on a lecture, and created the given problem out of boredom ;]

343D - Water Tree

Let's learn how to color a whole subtree. For that enumerate all vertices in post-order DFS. Then each subtree covers a single continious vertex number segment. For each vertex we store the bounds of such segment for a subtree with a root in this vertex. Then to color a subtree means to color a segment in a segment tree.

Then create a segment tree that has a following property: if a vertex v was emptied, and is still empty, then this vertex is colored in the segment tree. In the beginning "empty" all the vertices. That is, color all the vertices in the segment tree. With this tree we can efficiently process the queries:

1. Fill a vertex v. Clean the interval for the subtree of v. If before that some vertex of a subtree was empty, color the parent of v.

2. Empty a vertex v. Color the vertex v in the segment tree.

3. Reply whether a vertex v is filled. If in the segment tree at least one vertex is colored, then there is such a descendant of v that is empty now, so the vertex v is not filled.

Shtrix noted that essentially the same solution can be implemented with only a single set.

Solution complexity: . Problem author: gen.

Bonus: Some participants could see the similarities with a problem Ball Machine from BOI 2013, but the solutions to the both problems are quite different.

343E - Pumping Stations

In this problem we are asked to find such graph vertex permutation that maximizes the sum of the maximum flows sent between each two consequtive vertices in the permutation.

The problem can be solved with Gomory-Hu tree data structure. For a given weighted graph the tree has the following properties:

1. The vertex set of the tree and the graph is the same.
2. The maximum flow between vertices u and v in the tree is equal to the maximum flow in the graph.

Surprisingly, such a tree exists for any weighted graph, and can be built in O(n·maxFlow). It appears that the answer to the problem is equal to the sum of the edge weights in this tree.

We prove this statement by induction on the number of the tree vertices. Pick the edge (u, v) with the smallest weight in the tree. Consider that in an optimal permutation more than one path between two adjacent verteces in the permutation passes through this edge. Erase all these paths, then each of the u and v subtrees holds a set of disjoint remaining paths from the permutation. For each set, join all the paths in one chain, obtaining two chains. These chains we join by a path s that goes trough the edge (u, v). Thus we have built a permutation that is not worse than the considered one. For a path s the edge (u, v) is the smallest, so the flow along this path is equal to the weight of this edge. It follows from the induction that in subtrees u and v the answer is equal to the sum of edges. By adding the weight of edge (u, v), we get the desired result.

From the last paragraph it is clear how to build such a permutation: take the smallest edge, obtain two chains from the vertex subtrees recursively, and add them together to form a one chain. Since there are not many vertices, we can do this part in O(n²).

Solution complexity: O(n·maxFlow). Problem authors: gen, Gerald.

Bonus: Shortly before the contest we decided to make the constraints more loyal, so some solution that find Gomory-Hu tree by finding flow O(n²) times also passed. We hope that nobody is particularly saddened by this fact. (;

Hello everyone!

The anniversary Codeforces Round #200 is scheduled to take place today at 7:30 PM Moscow time. The round will be held in both divisions and will be rated.

The round problems were prepared by Evgeny Vihrov (gen), Andrey Vihrov (andreyv) and Gerald Agapov (Gerald). As always, we would like to thank Mike Mirzayanov (MikeMirzayanov) for the Codeforces and Polygon systems, and also Maria Belova (Delinur) for translating the problem statements.

In this round you will help mad scientist Mike to realise his peculiar ideas and carry out unusual experiments. The authors think that the problems constitute a good balance between mathematics and programming. We also tried to make the statements short and easy to read :] As always, we hope that every participant will find a problem to his taste.

We wish you good luck and an interesting round!

UPD1: Score distribution is standard:

DivI: 500 1000 1500 2000 2500

DivII: 500 1000 1500 2000 2500

UPD2: Congratulations to the top 5 winners in each division!

DivI

DivI

1. tourist
2. KADR
3. SillyHook06
4. niyaznigmatul
5. Igor_Kudryashov

DivII

1. Giraffy
2. jzc
3. ryad0m
4. Kamilot
5. API

Div II A — Fancy Fence

Problem

The problem is to tell whether there exists a regular polygon with angle equal to a.

Solution

Consider all supplementary angles of the regular n-polygon with angle a, which are equal to . Their sum is equal to , because the polygon is convex. Then the following equality holds: n·(180 - a) = 360, which means that there is an answer if and only if .

Time: O(t).

Memory: O(1).

Implementation: C++, Java

Comments

The problem can be also solved by rotating vector (1, 0) by angle until it returns in this position (but at most 360 times), and checking that only one full turn has been made (implementation example: C++).

It is also a rare problem on Codeforces that contains just 1 sample test, 1 pretest and 1 full test.

Div II B — Multithreading

Problem

In this problem we are asked to find the number of n-permutation elements that definitely have been moved after performing any sequence of move-to-front element operations. Equally, we should find the maximum possible number of elements that could have not been moved.

Solution

If some a_i is greater than a_i + 1, it is clear that a_i definitely contains a new message because the order of these two elements has changed. Let the last such element be a_k. Then all of the elements a_k + 1, a_k + 2, ..., a_n can contain no new messages, since their order has not changed. The answer to the problem is n - k. If there is no such a_k the order hasn’t changed at all and there may be no new messages.

Time: O(n).

Memory: O(n) / O(1).

Implementation: C++, Java

Comments

The problem was born while staring at the Codeforces main page and trying to think up an easy Div II problem. =)

Div II C / Div I A — Magical Boxes

Problem

We are given a_i squares with side length 2^k_i. It is allowed to insert squares only inside larger ones, and no two squares should overlap. We must determine the minimum p so we can place all the given squares inside a square with side length 2^p.

Solution

Suppose we can put all the squares inside a square with side length 2^p. Then we can insert each k_i type squares independently along the grid as shown in the picture. No two squares will overlap, since 2^x divides 2^y, if x < y. That means that we can find the smallest square that can hold all the given squares with side length 2^k_i for each k_i separately. The answer will be the side length of the largest such square.

To be able to put a_i squares with side length 2^k_i inside a square with side length 2^s, the following should hold:

We can then find the minimum s:

In a special case, if we obtain s = k_i, s should be increased by 1.

Time: .

Memory: O(1).

Implementation: C++, Java

Comments

The problem can be also solved using binary search on p. However, we can see that each square with side length 2^k + 15 holds any number of squares with side length less than 2^k, since . So it is enough to find the first square that fits from range 2^{max{k} + 1} to 2^{max{k} + 15}.

Div II D / Div I B — Greenhouse Effect

Problem

There are n points on the line, each of type from 1 to m. We can freely divide the line into m - 1 intervals and replace some points so each point with type i is inside the i-th interval numbered 1 to m from left to right. We must find the minimum number of points to replace.

Solution

First, observe that the coordinates don’t matter: only the order of the points is important. Let there be some number of points we can replace to achieve the good arrangement. Then all the other points remain in their positions, so their values must be in increasing order from left to right. Then we must find the maximum number of points that can remain in their positions, which is the longest non-decreasing subsequence of types in the input. If it is of length l, the answer is n - l.

In this problem it was enough to implement a quadratic solution. We count dp[i][j] — the length of the longest non-decreasing subsequence on prefix [1;i], with element of type j being the last in subsequence. The transition is as follows:

For easy implementation, we can maintain only array dp[j], and skip the second case.

Time: O(n²) / .

Memory: O(n²) / O(n).

Implementation: C++

Comments

We had to solve this problem during the work on our project, the origin lies in arranging some rectangular table borders. Our original project dp implementation actually runs in O(nm).

Div II E / Div I C — Flawed Flow

Problem

In this problem we are given an undirected graph and its flow, and we must reconstruct the edge directions of this flow.

Solution

The key element to solving the task is the following observation: if we know all the incoming edges of a vertex, all the remaining edges must be outgoing. The source has no incoming edges, so we already know that all its edges are outgoing. For all other vertices except the sink the amount of incoming and outcoming flow is the same, and is equal to half of the sum of the flow along its incident edges. The algorithm then is to repeatedly direct all the flow from the vertices for which all the incoming edges are known. This can be done with a single BFS:

for all v from 2 to n-1
    f[v] := sum(flow(v,u))/2;
put source in queue
while queue is not empty
    v := pop(queue)
    for all edges (v, u)
        if (v, u) is not directed yet
            direct v -> u
            f[u] = f[u] - flow(v,u)
            if u not sink and f[u] = 0
                push(queue, u)

As the flow contains no cycles, we can sort the vertices topologically. Then we can be sure that, until all edge directions are known, we can put at least the first vertex with unknown edges in the queue, as all of its incoming edges will be from vertices with lower indices, but we took the first vertex with unknown edges.

Time: O(n + m)

Memory: O(n + m)

Implementation: C++, Java

Comments

The obvious "easy" solution is to run some maxflow algorithm and get the answer. However, such implementations failed on anti-maxflow pretest #6.

Div I D — Maximum Waterfall

Problem

We are given n horizontal segments on a plane, and 2 extra topmost and bottommost segments. These two segments are the source and the sink of the flow. A flow can pass from one segment to a lower segment, if their horizontal projections overlap and there is no other segment between them so their projections overlap. The value of the flow on such segment edge is equal to the length of the horizontal projection overlap. We must find the maximum possible value of the flow along a single segment path.

Solution

We will use a sweepline algorithm to solve this task. This horizontal sweepline runs from bottom to top, and holds the parts of the segments that are visible from the line this sweepline is currently at. Each part also holds the reference to its original segment. The sweepline itself is implemented with a binary search tree.

The events of the sweep are the segments. When a new segment is found, we want to find all the lower segments that we can direct the flow onto from this segment. These can be only the original segments of the parts currently in the sweepline whose projections overlap with this segment. Then we iterate over all such parts p (finding the first such part is an operation). How do we know that we can direct the flow onto p? Observe that if there is some segment that prevents this, there should be also a part q in the sweepline that also can be seen from the current segment. And since the projections of all three segments overlap, this part can only be directly to the left or to the right of p in the binary search tree. So we just check whether the original segments of the two parts next to p prevent the flow from the current segment to the original segment of p.

Afterwards, we remove all such parts from the sweepline, and insert a new part corresponding to the new segment. If the new segment only partially covered an existing part, we reinsert the remaining portion of that part. There are at most two such portions — one on each side of the segment. Thus each segment inserts at most 3 new parts and the size of the sweepline is O(n). Each part is handled just once before removal, so the total time of such operations is .

Once we know we can direct the flow through we can immediately update the maximum downwards flow of a:

When we reach the top, f_top will be the answer.

Time:

Memory: O(n)

Implementation: C++, Java

Comments

Another problem from our project. You can also first build a graph from the segments using the same sweepline and then find the path with the maximum flow in that graph. In the original problem you have to find this graph and there are no top and bottom segments.

Div I E — String Theory

Problem

In this problem we have an n × m rectange. Each unit midpoint is connected with a segment to some other midpoint not on the same side of the rectangle. We can change the order of the columns and rows, but the segments must remain attached to their midpoints. We should find such a rearrangement that no two segments intersect, or tell that there is no solution.

Solution

There are overall 6 types of segments that connect the sides:

1. left-top;
2. top-right;
3. right-bottom;
4. bottom-left;
5. left-right;
6. top-bottom;

If there are both left-right and top-bottom segments, there is no solution. Otherwise there remain only 5 types of segments. Without loss of generality suppose there are no left-right segments. Let’s take a closer look at what should the end picture of the rectangle be:

All left-top segments should be at the left top corner connecting positions (L,i) and (T,i), otherwise they surely would cross some other segment. Similarly must be positioned top-right, right-bottom, bottom-left segments. Finally, all top-bottom segments should be parallel. We also observe that the number of left-top segments must be equal to the number of right-bottom segments and the number of top-right segments should be equal to the number of bottom-right segments. Thus the important observation: the picture of the end arrangement is unique and can be determined from the input simply by counting the number of segments of each type.

Next we define a cycle to be the sequence of segments, where the second midpoint of some segment in the cycle is equal to the first midpoint in the next segment in the cycle. In the given example there are two such cycles (but the direction of each cycle actually matters):

Then we observe that the set of the cycles does not change with any permutation by the definition of the cycle. We can make a sketch of the solution: we should find the cycle sets in the given arrangement and in the end arrangement, and compare them for equality.

At this point we actually find all the cycles in both arrangements. There are only two types of cycles:

1. (left-top) (top-right) (right-bottom) (bottom-left);
2. other cycles.

We can easily check whether the sets of first type cycles match, since the length of such cycles is 4. If they match, we rearrange the columns and rows involved to match the end arrangement.

How to compare the remaining cycles. Consider a following example:

Let the difference in the number of left-top and left-bottom segments be i, and this number plus the number of top-bottom segments s. If we enumerate the midpoints as in the figure, we can see that each top midpoint k is connected to the bottom midpoint (top-right segments continue as corresponding left-bottom segments). Thus we can describe it as a permutation

Our cycles correspond to the cycles in this permutation, with top-right segment continuation to left-bottom segment corresponding to the case where permutation cycle element decreases. It is known that the number of such permutations is and their length is . So all these cycles have the same length. Denote the remaining segment types as some letters (in picture A, B, C). Then not only the length, but the strings describing the cycles are also the same, but can be shifted cyclically (here the direction of the cycles also is important). Besides, we know this string from the correct arrangement cycle. Thus we need to compare all the remaining given arrangement cycle strings to this string, considering cyclic shifts as invariant transformations. For each string this can be done in linear time, for example, using the Knuth-Morris-Pratt algorithm. When we find a cyclical shift for each cycle, we can position its relevant columns and rows according to the end arrangement.

Time: O(n + m).

Memory: O(n + m).

Implementation: C++, Java

Comments

This is a total killer task for coding. It took both of us around 5 hours to code the implementation. Congratulations again to kelvin, at the time of writing still the only one to solve the problem (and of course to anyone who will get this difficult problem accepted =) ).

Hello everyone!

Codeforces round #165 will start today at 19:30 in Moscow time. It will be a round held in both divisions, the first one after a long two-week break for Div I participants. :)

This time the problems were prepared by me, Evgeny Vihrov (gen), and Krisjanis Prusis (cfk). Apart from competing together in ACM ICPC this year, we are also colleagues in a project that involves much algorithmic thinking. Actually, some of the contest problems were born during the work on this project.

In this contest you will get to know a legendary hero Emuskald of many talents and help him complete his ingenious ideas. The problems cover a multitude of algorithmic concepts, so as always we hope that each participant will find a problem that matches his taste.

Big thanks to Gerald Agapov (Gerald) for help during the preparation of this contest, to Maria Belova (Delinur) for problem statement translation and also to Mikhail Mirzayanov (MikeMirzayanov) for the excellent contest-making platform for Codeforces — Polygon.

We wish you an exciting round!

UPD1: Score distribution:

DivII: 500 1500 1500 2000 2500

DivI: 500 1000 1500 2000 2500

UPD2: Congratulations to the winners!

Div I

1. PavelKunyavskiy
2. Egor
3. tourist
4. rng_58
5. tomasz.kociumaka

Div II

1. woxihuanni
2. mnbvmar
3. QLSpirit_011
4. PraveenDhinwa
5. leviathan

UPD3: Tutorial is available.

Hello everyone!

Codeforces Round #142 will be held today at 19:30 in Moscow time, and it will take place in both divisions.

The authors of the problems are me, Evgeny Vihrov (gen), and Andrey Vihrov (andreyv). Both of us are students of the Faculty of Computing in the University of Latvia. This is our very first contest on Codeforces!

Big thanks for the help in preparing the contest go to Gerald Agapov (Gerald), and to Maria Belova (Delinur) — for translating the problem statements in English. Also thanks to Mikhail Mirzayanov (MikeMirzayanov) for the Polygon system, which we found to be great for preparing contest problems.

We hope that each participant will be able find a problem to match his taste. Please, consider reading all the problems!

We wish you an exciting round!

UPD1: The score distribution will be dynamic. The problems will be sorted in order of expected increasing difficulty.

UPD2: Due to the technical problems the contest was extended by 5 minutes. We are sorry for the inconvinience.

UPD3: The analysis of the contest is available. Enjoy!

The round is over! 5 contestants solved all the problems in division 1, and in division 2 only the top four contestants solved all the tasks. Congratulations to the winners!

Div I

1. YuukaKazami
2. peter50216
3. kelvin
4. takaramono
5. Martin

Div II

1. coquelicot
2. llj_bash
3. kb.
4. niukuo
5. Petar