Errichto's blog

By Errichto, 9 years ago, In English

Easy — BearCharges

Did you help Limak, a little bear? Each base is a vertex and all vertices (except 0) should have a parent — base from which this one was captured. So we are looking for a tree but not exactly MST because for a vertex order of his children matters.

Let dp[mask][x] denote time needed to capture all bases in set defined by mask if we start with base x. We will calculate dp[S][a] by iterating over possible first son of a and over bitmask denoting set of vertices in subtree of a — so consider to which base b we shoot first and what bases will be captured directly or indirectly by b. dp[S][a] = min(dp[S][a], dist(a, b) + max(dp[A][a], dp[S - A][b]))

It is O(3n·n2) but you can get easier implementation with O(4n + 3n·n2) — check out my code.

Med — LuckyGrid

Let's assume n > 1. Note: by line I mean row or column.

The only possible lucky sums of lines are 44, 47, 74, 77, 444, 447. For n ≠ 11 there are exactly 0 or 2 lucky sums possible to get (e.g. only 74 and 77). Then for fixed n we have condition e.g. "sums should be 74 or 77" and it is equivalent to "in a line there should be x or x + 1 fours" — and we want to maximize number of fours.

We should solve this new problem with a flow. It's possible to solve it with "bounded flow" (I haven't heard of it before) but I will describe solution with MinCost. For all lines there could be some fours already in the grid so we count them and we know how many more fours should this line have. From S to each vertex denoting row we add two edges:
1. minimum capacity we want, cost 0
2. capacity 1, cost C where C is some big constant (I had 105).
Similarly for edges from vertices denoting columns to T. And ofc. we add unit edges from each vertex to each column if there is empty cell. Now we run MinCostFlow and thanks to C we know number of used edges of each kind, ie. cost / C is number of used edges with cost C.

What about n = 11? I did some cases analysis and solved it with bipartite matching only but one can run algo described mincost multiple times — for each line we set desired number of fours as either 44 - 47 or 74 - 77.

my implementation

Hard — SubRectangles

Let's say H2 = W2 = 4. You can see that t[1][1] - t[5][1] = t[1][5] - t[5][5]. Then we can deduce that for each pair (a, b) where 0 ≤ a, b < 4 one of two holds:
1. t[x][y] = t[x + 4][y] if x%4 = a and y%4 = a
2. t[x][y] = t[x][y + 4] if x%4 = a and y%4 = a
For all possible ways to assign types to 16 cells we will calculate result and sum them up. So we consider 216 bitmasks.

For first type of cells (with condition t[x][y] = t[x + 4][y]) we should set all cells of this type in first four columns — columns on the right will be the same. We should do it in such a manner that numbers of tokens in 1-st, 5-th, 9-th, ... rows are equal. The same for 2-nd, 6-th, ... and so on. Let's look at first set of rows (1-st, 5-th, ...). We should iterate over number of tokens we want to put in this "type" of rows. For each value we sum/multiply up some binomial coefficient powered up to number of rows of this type. E.g. for H = 14 there are 4 rows in this group, so if we have 2 possible cells here (number of lighten bits in bitmask) and we want to put 1 token in each row, then we have bin(2, 1)4. The same for the second direction but with some inclusion-exclusion formula. You can read my implementation.

Full text and comments »

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

By Errichto, 9 years ago, In English

Div2B — Bear and Three Musketeers

Warriors are vertices and "knowing each other" is an edge. We want to find connected triple of vertices with the lowest sum of degrees (and print sum - 6 because we don't want to count edges from one chosen vertex to another).

Brute force is O(n3). We iterate over all triples a, b, c and consider them as musketeers. They must be connected by edges (they must know each other). If they are, then we consider sum of their degrees.

We must notice that there is low limit for number of edges. So instead of iterating over triples of vertices we can iterate over edges and then iterate over third vertex. It gives us O(n2 + nm) and it's intended solution. To check if third vertex is connected with other two, you should additionally store edges in 2D adjacency matrix.

It's also possible to write it by adding "if" in right place in brute forces to get O(n2 + nm). Check it out in code.

Div1A — Bear and Poker

Any positive integer number can be factorized and written as 2a·3b·5c·7d·....

We can multiply given numbers by 2 and 3 so we can increase a and b for them. So we can make all a and b equal by increasing them to the same big value (e.g. 100). But we can't change powers of other prime numbers so they must be equal from the beginning. We can check it by diving all numbers from input by two and by three as many times as possible. Then all of them must be equal. Code

Alternative solution is to calculate GCD of given numbers. Answer is "YES" iff we can get each number by multiplying GCD by 2 and 3. Otherwise, some number had different power of prime number other than 2 and 3. Code

Div1B — Bear and Blocks

In one operation the highest block in each tower disappears. So do all blocks above heights of neighbour towers. And all other blocks remain. It means that in one operation all heights change according to formula hi = min(hi - 1, hi - 1, hi + 1) where h0 = hn + 1 = 0. By using this formula two times we get height after two operations: hi = max(0, min(hi - 2, hi - 1 - 1, hi - 2, hi + 1 - 1, hi + 2)) and so on. From now I will omit max(0, ...) part to make it easier to read.

After k operations we get hi = min(Left, Right) where Left = min(hi - j - (k - j)) = min(hi - j + j - k) for and Right is defined similarly. hi becomes zero when Left or Right becomes zero. And Left becomes zero when k = min(hi - j + j) — we will find this value for all i. If you are now lost in this editorial, try to draw some test and analyze my formulas with it.

For each i we are looking for min(hi - j + j). We can iterate over i from left to right keeping some variable best:

best = min(best, h[i]);
best is answer for i;
best++;

We should to the same for Right and take min(Left, Right) for each i. Then final answer is maximum over answers for i. Code

Div1C — Bear and Drawing

Let's consider a tree already drawn on a strip of paper. Let's take first vertex on the left and last vertex on the right (in case of two vertices with the same x, we choose any of them). There is a path between them. Let's forget about vertices not on this path. A path divides a strip into 1D regions.

What can be added to the main path? Only simple paths attached to it with one edge. So it can be one of the following structures — Y-letter or Line:

Note that Y-letter can have long legs but its central part can have only one edge.

How to check if given tree is a path + Y-letters + Lines? First, let's move from each leaf till we have vertex with degree at least 3, marking vertices as deleted. We don't mark last vertex (that with degree at least 3) as deleted but we increase his number of legs. Finally, for each not-deleted vertex we count his not-deleted neighbours for which degree - min(legs, 2) > 1 — otherwise this neighbour is start of Line or Y-letter. Each vertex on the main path can have at most two neighbours that also belong to the main path. There can be more neighbours but they must be in Lines or Y-letters — that's why we didn't count them. So answer is "No" iff for some vertex we counted more than two neighbours. Code

Div1D — Bear and Cavalry

Let's sort warriors and horses separately (by strength). For a moment we forget about forbidden assignments. Inversion is a pair of warriors that stronger one is assigned to weaker horse. We don't like inversions because it's not worse to assign strong warriors to strong horses: A·B + a·b ≥ A·b + B·a for A ≥ a and B ≥ b. Note that repairing an inversion (by swapping assigned horses) decreases number of inversions — prove it by yourself (drawing a matching with intersections could be helpful). Without any restrictions the optimal matching is when we assign i-th warrior to i-th horse (indexed after sorting) — to get no inversions.

Let's go back to version with forbidden connections. We have n disjoint pairs which we can't use. We will prove that there exists an optimal assignment where (for all i) i-th warrior is assigned to j-th horse where |i - j| ≤ 2.

Let's take an optimal assignment. In case of ties we take the one with the lowest number of inversions. Let's assume that i is assigned to i + 3. There are at least 3 warriors j > i assigned to horses with indices lower than i + 3. So we have at least 3 inversions with edge from i to i + 3 (warriors on the left, horses on the right):

Above, connection warrior-horse is an edge. Then inversions are intersections. Swapping horses for warriors i and j (where j belongs so some red edge) would decrease number of inversions and it wouldn't decrease a score. We took an optimal assignment so it means that it's impossible to swap horses for them. Hence, for each red edge we can't change pair (black, read) into the following blue edges:

So one of these blue edges is forbidden. Three red edges generate three pairs of blue edges and in each pair at least one blue edge must be forbidden. Note that all six blue edges are different. All blue edges are incident to warrior i or to horse i + 3 but only one forbidden edge can be incident to warrior i and only one forbidden edge can be incident to horse i + 3. We have at most two forbidden edges incident to them so it can't be true that three blue edges are forbidden.

By cases analysis we can prove something more — that there can be only three possible types of connecting in an optimal assignment. First type: i can be connected to i. Second: warrior i with horse i + 1 and warrior i + 1 with horse i. Third: warriors i, i + 1 and i + 2 are connected with horses i, i + 1, i + 2.

It gives us O(nq) solution with calculating queries independently with dp[i] defined as "what result can we get for assigning everything with indices lower than i?". To calculate dp[i] we must know dp[i - 3], dp[i - 2] and dp[i - 1]. It wasn't intended solution because we can get better complexity.

We can create a segment tree and for intervals we should keep info "result we can get for this interval with 0/1/2 first and 0/1/2 last elements removed". For an interval we keep matrix 3x3 and actualizing forbidden edge for single i consists of: 1. calculating values of 3x3 matrix for a small interval with i 2. actualizing a tree with times multiplying matrices

Complexity is .

Div1E — Bear and Bowling

FIRST PART — greedy works

We will add (take) elements to a subsequence one by one. Adding number x, when we have k - 1 taken numbers on the left, increases result by k·x + suf where suf is sum of taken numbers on the right. Let's call this added value as the Quality of element x.

We will prove correctness of the following greedy algorithm. We take element with the biggest Quality till there are no elements left. For every size of a subsequence (number of taken elements) we will get optimal score.

(lemma) If ai > aj and i < j, we won't take aj first.

Proof. Let's consider a moment when we don't fulfill the lemma for the first time. If there are no taken numbers between ai and aj, we have Qi = k·ai + suf > k·aj + suf = Qj so ai is a better choice. For taken numbers between ai and aj — each number x changes Qi by x and Qj by aj. We'll see that x > aj so Qi will remain greater than Qj. If ai > x, the lemma (fulfilled till now) says that x wasn't taken before ai — it can't be true because x is taken and ai is not. So indeed x ≥ ai > aj.

Let's assume that our greedy strategy is not correct. Let's consider first moment when we take some element aj and for some s we can't get optimal subsequence with size s by taking more elements (using any strategy). Let A denote a set of elements taken before. So there is no way to add some more elements to set A + aj and achieve optimal score with size s. But it was possible just before taking aj so there is a subset of remaining elements B that |A + B| = s and set A + B is the best among sets with size s. Note that B can't be empty.

(case 1 — B contains at least one element on the left from aj) Let ai denote last element from B that i < j (here "last" means "with the biggest i"). Our strategy wanted aj before elements from B so we know from lemma that ai ≤ aj. It will turn out that replacing ai with aj (in set A + B) doesn't decrease the score so taking aj is acceptable. Note that replacing an element with another one doesn't change size of a set/subsequence.

In moment of choosing aj it had the biggest quality so then Qj ≥ Qi. Now in A + B there are new elements, those in B. Let's imagine adding them to A (without ai and aj). Each new element x on the right change both Qi and Qj by x. Elements on the left change Qi by ai and Qj by aj (note that ai ≤ aj). And there are no elements between ai and aj. Now, taking ai would give us set A + B but Qj remains not less than Qi so we can take aj instead.

(case 2 — B contains only elements on the right from aj) Similarly, we can replace ai with closest aj from set B. As before, elements on the right change Qi and Qj by the same value.

SECOND PART — how to implement it

First, let's understand solution. We divide a sequence into Parts. When choosing the best candidate in a Part, we want to forget about other Parts. It's enough to remember only x and suf — number of taken elements on the left (in previous Parts) and sum of elements on the right (in next Parts). x affects choosing the best element in a Part, suf doesn't (but we need this constant to add it to result for best candidate). For a Part we want to have hull with linear functions of form ai·x + b. With binary search we can find the best element in and then construct new hull for this Part in .

We can remove from complexity. First, binary search can be replaced with pointers — for each Part initially we set a pointer at the beginning of Part. To find best candidate in Part, we slowly move pointer to the right (by one). Complexity is amortized . And we can sort linear functions ai·x + b by angle only once because value ai doesn't change — then constructing a hull is only . Note that when rebuilding a hull, we must set pointer to the beginning of Part.

So we have . Code.

There are other two correct lemmas to speed your solution up. We can take all positive numbers first (it's not so easy to prove). And we can stop when taken number doesn't increase score — next taken numbers won't increase score neither.

Full text and comments »

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

By Errichto, 9 years ago, In English

Hello Codeforces community!

Codeforces Round #318 (for both divisions) will take place on August, 29 at 19:30 MSK. It is the Thanks-Round devoted to Russian Code Cup. You will be given 5 problems and 2 hours to solve them. Scoring will be announced close to the round. I strongly recommend you to read all problems.

RussianCodeCup is the largest open programming competiton for Russian-speaking participants by Mail.Ru Group. Its history started in 2011. And since the first championship RCC offers great problems and generous prizes. This year finals will be held on September, 19th. Wish good luck to all the finalists! Thank you, RussianCodeCup, for your gift on the 5th anniversary of Codeforces!

I am honoured to be a problem setter for this round. I wouldn't do it alone. I want to thank Zlobober for his great help with problems preparation and MikeMirzayanov (and all people working on Codeforces and Polygon) for this awesome site. It's an amazing place to learn and compete. My big thanks to winger and AlexFetisov for their help with testing a round. And to Delinur for translating statements. As you see, not only a setter creates a round.

It's my first Codeforces round but not my first problems here. You can check out A, C and D from VK Cup 2015 — Round 2. Also you might remember some of my problems in TC rounds. I'm very happy with finally preparing a full round for Codeforces and I hope you will enjoy it. I tried my best to prepare nice and diverse problemset, you will judge it. In all problems you will have to help Limak who is quite unusual bear.

I wish you great fun and no frustrating bugs. Looking forward to seeing you!

UPD: Scoring is 500-1000- 1750 -2000-2500 in div1 and 500-1000-1500-2000- 2750 in div2. Enjoy a round!

UPD: Editorial

UPD: Contest is over. The winners:

Div1:

  1. Marcin_smu
  2. mnbvmar
  3. subscriber
  4. LoneFox
  5. Shef

Div2:

  1. cescmentation_folch (5 problems solved!)
  2. fhxb520630 (5 problems solved!)
  3. bugCollector
  4. Sehnsucht
  5. okaduki1

And note from an author. There were some wrong solutions passing. Sorry for that. I tried my best to create strong tests but I failed a bit. Did you like this round? What do you think about problems?

Thanks for participating!

Full text and comments »

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

By Errichto, 9 years ago, In English

You can find editorial here. Sorry for technical troubles with challenging. What do you think about problems? Which did you enjoy, which do you hate?

--UPDATE--

broadcast: The match will be rated, and challenge results will stand. However, if you feel you were personally affected negatively/unfairly, please message [email protected], and I will consider individual requests. (I have some limited ability to confirm that individuals had issues)

Full text and comments »

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

By Errichto, history, 9 years ago, In English

Today will be CF #313. I will take part in it and I will do at least 20*sqrt(max(0,myRatingLoss)) push-ups in 24h. Wish me good luck.

Full text and comments »

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

By Errichto, 9 years ago, In English

Usually A,B,C from Div1 are C,D,E from Div2. I solved such a shared problem during a contest and later I wanted to read my code again. So I went to "PROBLEMSET" and chose that task (it was green!). But page with statement didn't show my submission. It seems my submission is attached to div1-version of problem and "PROBLEMSET" page shows shared tasks as div2 ones. It is a bit uncomfortable.

Later I found my code (I chose right d1-contest from list of all contests) and from curiosity I tried to submit my solution by page with d2-version. As I've expected it gave me +1 to problemset standings (number of solved tasks).

I think it is something to be fixed.

Btw. thanks Mike (and other people working on CF) for such an amazing platform! :)

Full text and comments »

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