gen's blog

By gen, 4 years ago, In English,

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 (vstrima1, jDomantas, ljietuvis)
  3. LU: 0x7DF (Pakalns, Candyman, A_Le_K)
  4. LU: leet (bauldaise, kristapuciitis, 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!

Read more »

 
 
 
 
  • Vote: I like it
  • +103
  • Vote: I do not like it

By gen, 6 years ago, In English,

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(n2), 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 AijAji and AjiAij. 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?

Read more »

 
 
 
 
  • Vote: I like it
  • +80
  • Vote: I do not like it

By gen, 6 years ago, In English,

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. narcis_vs
  2. L_Ecry
  3. Omar_Obeya
  4. xorfire
  5. Hec

UPD3: Excellent round statistics from DmitriyH.

UPD4: The contest tutorial is published here.

Read more »

 
 
 
 
  • Vote: I like it
  • +402
  • Vote: I do not like it

By gen, 6 years ago, translation, In English,

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 (poopoo, 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.

Read more »

 
 
 
 
  • Vote: I like it
  • +150
  • Vote: I do not like it

By gen, 6 years ago, In Russian,

Привет всем!

Никогда не задумывались над странными последствиями социального поведения общества на CF? В частности, мне был очень интересен эксперимент пользователя LeBron, и в сущности, я пришёл к следующему выводу. Ни для кого не секрет, что на CF довольно сильно проявляется «цветовая» дискриминация, и это очень сильно влияет на [+]/[-] оценку постов/комментариев. Более высокий цвет даёт пользователю неформальное основание считать своё мнение более обоснованным, чем мнение пользователя с меньшим цветом. С другой стороны, меньший цвет автора сообщения даёт наблюдателю больший повод сомневаться в написанном. Однако для пристрастного голосования нужно ещё подтверждение «со стороны», чтобы присудить комментарию значение с соответствующим знаком. Этим катализатором и является первый плюс или минус. В частности, для оранжевых и красных пользователей это означает практический социальный «иммунитет» (пока не начинается дебоширство ;]); серые и зелёные пользователи зато испытывают сильную «уязвимость». Естественно, «правильность» мнений по отношению к цветам верно в какой-то степени, но всё-таки далеко не в полной мере.

На самом деле это представляет весомую проблему для объективной оценки комментария/поста, а так же для свободного выражения мнения. Поэтому, как кажется мне, совершенно неправильно показывать точное количество плюсов и минусов, набранных сообщением (это также позволяет «тюнить» оценку, если пользователь считает, что сообщение набрало больше плюсов или минусов, чем заслужило). Известно, конечно, что многие системы оценок пытаются избежать таких ям. Одна из самых привлекательных альтернатив была бы следующей: не показывать точный рейтинг сообщения, а «подкрашивать» его зеленым цветом с насыщенностью, пропорциональной количеству плюсов. Особенно отрицательные комментарии скрывать, как обычно. «Подкрашивание» абстрактно, его можно реализовывать по разному. При том я не призываю что-то сразу менять, а просто поразмышлять на тему лучшего выбора.

Какого ваше мнение? Любые комментарии и обсуждения приветствуются. И не забудьте плюсануть пост! :]

Read more »

 
 
 
 
  • Vote: I like it
  • +55
  • Vote: I do not like it

By gen, 6 years ago, translation, In English,

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(n2).

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(n2) times also passed. We hope that nobody is particularly saddened by this fact. (;

Read more »

 
 
 
 
  • Vote: I like it
  • +64
  • Vote: I do not like it

By gen, 6 years ago, translation, In English,

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

DivII

  1. green_coder
  2. jzc
  3. Mark_SamLIT
  4. Kamilot
  5. API

Read more »

 
 
 
 
  • Vote: I like it
  • +204
  • Vote: I do not like it

By gen, 7 years ago, translation, In English,

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 ai is greater than ai + 1, it is clear that ai definitely contains a new message because the order of these two elements has changed. Let the last such element be ak. Then all of the elements ak + 1, ak + 2, ..., an can contain no new messages, since their order has not changed. The answer to the problem is n - k. If there is no such ak 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 ai squares with side length 2ki. 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 2p.

Solution

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

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

(2s)2 ≥ (2ki)2·ai
4s ≥ 4ki·ai
4s - ki ≥ ai

We can then find the minimum s:

In a special case, if we obtain s = ki, 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 2k + 15 holds any number of squares with side length less than 2k, since . So it is enough to find the first square that fits from range 2max{k} + 1 to 2max{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(n2) / .

Memory: O(n2) / 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:

fa = max(fa, min(fb, min(ra, rb) - max(la, lb)))

When we reach the top, ftop 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 =) ).

Read more »

 
 
 
 
  • Vote: I like it
  • +88
  • Vote: I do not like it

By gen, 7 years ago, translation, In English,

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. EzrealOrz
  4. MohallaBoy
  5. leviathan

UPD3: Tutorial is available.

Read more »

 
 
 
 
  • Vote: I like it
  • +191
  • Vote: I do not like it

By gen, 7 years ago, In English,

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. WJMZBMR
  2. peter50216
  3. kelvin
  4. l521530
  5. Martin

Div II

  1. coquelicot
  2. llj_bash
  3. borozdinKirill
  4. niukuo
  5. LMFAO

Read more »

 
 
 
 
  • Vote: I like it
  • +175
  • Vote: I do not like it

By gen, 8 years ago, In Russian,

DivII A. Печеньки

Самый лёгкий способ решить задачу — сперва посчитать всю сумму чисел, и затем посчитать количество чётных разностей между этой суммой и каждым числом. Однако маленькое наблюдение позволит написать решение немного эффективней: помимо суммы (sum) посчитаем также, сколько среди данных чисел есть чётных (even) и нечётных (odd). Тогда, если сумма нечётна, то ответ — odd, иначе — even. Время O(n), память O(1).

DivII B. Шнурки и шестиклассники

Маленькие ограничения позволяют нам написать решение «в лоб». Будем хранить данный граф в матрице смежности, и симулировать происходящее. Также будем хранить степень каждой вершины отдельно, чтобы быстро находить детей, которые связаны только одним шнурком. Тогда при каждой итерации удаляем все вершины со степенью 1 и все грани, которые соединяются с этими вершинами; продолжаем до тех пор, пока не останется таких вершин. Ответом будет количество произведённых итераций. Время O(n3), память O(n2).

DivII C / DivI A. Статуи

Произведём симуляцию падения статуй. При каждой итерации будем сдвигать все статуи на одну клетку вниз. Перед каждым ходом (итерацией) будем получать список всех полей, куда Маша может пойти (до того, как статуи передвинутся на одну клетку вниз), используя список тех полей, куда она могла придти с прошлого хода (единственное, из полей с прошлого хода можно использовать только те, в которые после конца прошлого хода не переместилась статуя). Логично, что через 8 любых ходов на доске не останется ни одной статуи. Поэтому, если список  доступных Маше полей после 8-ого хода не пуст, то она может добраться до Ани, потому что дальше её ходы ничто не ограничивает. Время O(9· 83) = O(1), память O(82) = O(1).

DivII D / DivI B. Строка

Вначале ликвидируем случай невозможности — такой строки нет, если k больше, чем количество подстрок, т.е. , где n — длина строки.

Теперь заметим, что для каждой буквы мы можем быстро оценить, сколько подстрок начинаются именно с этой буквы. Действительно, если буква стоит на позиции i (нумеруя с 1), то количеством подстрок, начинающихся с позиции i, является n - i + 1. Тогда количество строк, которые начинаются с конкретной буквы, будет сумма всех таких значений для позиций, в которых стоит эта буква.

Далее, используя найденную информацию, не сложно выяснить, с какой буквы будет начинаться нужная подстрока (потому что в слове при лексикографическом сравнении буквы слева важнее, чем буквы справа). Теперь заметим, что тоже самое рассуждение мы можем применить и для следующей буквы нужного слова, только теперь нужно проверить только такие буквы, которые следуют после первой буквы слова. Таким образом, мы повторяем итерации и для 3-ей, 4-ой, ... букв до тех пор, пока не найдём нужную строку. Чтобы не искать каждый раз нужные позиции, будем хранить их отдельно; при каждой итерации сдвигать их на одну позицию направо и исполнять алгоритм только для них, а после нахождения i-того символа убирать те позиции, буквы в которых не равны с найденным символом. Время благодаря k ≤ 105 не квадратичное (самому ещё не получилось доказать), память O(n).

Также задачу можно было решить с помощью хэшей или суффиксного массива.

DivII E / DivI C. Игра с прямоугольниками

Рассмотрим все левые и правые границы всех k внутренних прямоугольников, вместе их 2k. Присвоим им произвольные 2k координат между левой и правой стороной данного прямоугольника, это можно сделать способами. То же самое сделаем и с верхними и нижними границами, это можно сделать способами. Заметим, что каждая пара таких размещений однозначно определяет одно искомое расположение, и все такие расположения можно определить одной парой размещений. Поэтому ответом является . Так как n и m не больше 1000, то коэффициенты можно посчитать с помощью треугольника Паскаля (не забывая вычислять по данному модулю). Время O(max(n, m)2), память O(max(n, m)2).

DivI D. Числа

У меня эта задача ассоциировалась с атомами и молекулами. :) Представим, что каждое из чисел имеет две связи, где связь соединяется с другой по заданным правилам. Тогда решение существует тогда и только тогда, когда все связи соединены, и из каждого элемента по связям можно дойти до любого другого элемента; также решения не существует, если присутствуют числа x, x + 2, но x + 1 не присутствует.

Пусть у нас есть числа a, a + 1, ..., b, тогда количество связей у них 2|a|, 2|a + 1|, ..., 2|b|, где |x| — количество чисел x. Ясно, что 2|a| связей от 2|a + 1| «съедают» элементы a. У a + 1 свободными остаются p = 2|a + 1| - 2|a| связей. Аналогично, эти p связей соединяются с a + 2 элементами и т.д. В конце концов, если у b - 1 свободными остаются q связей, то должно быть q = 2|b|, чтобы завершить цепочку. Остаётся только проверить все эти соотношения (учитывая то, что цепочку нельзя завершить раньше, чем не истрачены все связи — то есть, вычисляемый p не может быть 0). Время (т.к. данные числа нужно отсортировать), память O(n). Для простоты вычислений можно ещё заметить, что 2|a| можно заменить на |a|, из-за этого ничего не изменится.

DivI E. День рождения

См. хороший разбор здесь.

Read more »

 
 
 
 
  • Vote: I like it
  • +23
  • Vote: I do not like it

By gen, 9 years ago, In Russian,
Мой первый пост — о контесте №10.

A. Учет энергопотребления


В этой задаче всего-навсего нужно было имитировать работу ноутбука. Будем записывать результат в переменную res. Для каждого интервала прибавим к res число (ri - liP1, т.к. во время интервалов ноутбук работает на полную мощность. Обозначим функцию
int foo (int &m, int t) {
      if(m < t) t = m;
      m -= t;
      return t;
}
Далее для каждого i < n к res применим следующие действия: пусть время между концом i-ого и началом (i + 1)-ого интервалов — tmp. Тогда прибавим к res . Переменная res и является ответом задачи.

Думал, что программа запорется на крайних тестах. Оказалось, ошибочно думал — AC.

B. Кассир в кинотеатре


Сразу начал искать какой-нибудь быстрый алгоритм, на это потратил какое-то время. Потом подумал —"а зачем?" и написал bruteforce.

Алгоритм простой до безобразия и без оптимизаций (). Идём по всем возможным позициям x, y, если все выбранные места не заняты, считаем данную в задаче функцию для выбранных чисел, минимум вместе с координатами фиксируем в переменную. AC с первого раза.

C. Цифровой корень


Математика, обрадовался я. Известный факт, что . Заметим, что для задачи не важно, d(x) = 9 или d(x) = 0: в принципе это одно и то же. Поэтому можем упростить: .
Посчитаем, сколько троек чисел удовлетворяют Васиному условию. В массиве A[9][9] : чтобы знать значение d(i· j). В массиве B[9] B[i] — количество чисел, не больших n, которые дают остаток i при делении на 9. Итак: для каждых i, j количество искомых троек таких, что d(i· j) = d(l), является B[iB[jB[A[i][j]] (все эти тройки удовлетворяют Васиному суперусловию). Складывая все эти числа, получаем искомое (X).
Теперь посчитаем, сколько троек Вася найдёт правильно своим условием. Подумаем: ведь это те и только те тройки A, B, C, которым выполняется A· B = C ≤ n. То есть, произведение A и B не более n. Как найти это количество? Очевидно, что как A  и B годятся все числа 1 и i, i ≤ n. Так же годятся все числа 2 и i, . И так для каждого i как A годятся все числа B, которые не больше . Вся их сумма — искомое количество (Y).
Ответ — X - Y. Ну, думаю, сейчас уж не прокатит третий раз с первого раза. И внезапно — AC. Ну тут я обрадовался.

Посмотрел на задачи D и E. Вижу, почти никто D не решил. Однако всё-таки посмотрел, подумал, что DP, подумал, что уже раньше что-то подобное видел. Но писать что-то уже было влом, да и наверное, беcперспективно, раз даже лидеры не решили. В E тоже особенно не вдумывался. Поняв, что за полчаса не решу ни одну из этих двух задач, на этом и закончил. Впечатления: хороший контест, особенно понравилась задача C.

Ну, к определённому успеху я пришёл — поднялся с Сержанта (1466) до Лейтенанта (1610): +144. Ну что, отлично.

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it