Here are the authors of the problems:

• A — Written by GlebsHP, prepared by vovuh
• B — Written by GlebsHP, prepared by vovuh
• C — zxqfl
• D — Errichto
• E — zxqfl
• F — zxqfl
• G — KAN

I'd like to thank the Codeforces team for their help, particularly KAN, who was the tester for this round.

Hi Codeforces,

I'm excited to announce the Canada Cup, the first Codeforces contest to be sponsored by Diagram!

This is a rated Codeforces round (with T-shirts!) for both divisions which will take place on October 22 at 11:00am EDT.

Although the contest is organized in Canada, all competitors worldwide will be able to compete and win prizes.

The problems for this round were written me (zxqfl) and the Codeforces team. I'd like to thank:

• My coauthors for contributing great problems to the round
• GlebsHP for his help in preparation
• MikeMirzayanov for creating Codeforces and Polygon
• Tatiana_S for translation into Russian

I'd also like to thank Diagram for sponsoring the round. Diagram is interested in hiring software engineers, so please take a look at the information at the end of this post if you're interested. For anyone outside of Canada, they'd like me to let you know that Canada has friendly immigration policies for software engineers.

Both divisions will compete in the same contest, which will consist of 7 problems of the same difficulty level as a regular Codeforces round. The contest will last for 2.5 hours.

The score distribution will, of course, be announced later.

Here is some information from the round sponsor:

Prizes

• The top 100 competitors will get a Diagram T-shirt.
• Local winners (Montreal): Dinner with Francois Lafortune (CEO, Diagram), founders of Dialogue, and other Montreal technologists
• Local winners (Toronto): Dinner with Karel Vuong (Director, Diagram), founders of Collage, and other Toronto technologists

About Diagram

Diagram is a venture launchpad building the next generation of Canadian-based global technology companies. By assembling teams of world-class founders pursuing big ideas for innovation in the financial and insurance industries, and surrounding them with capital, expertise, and infrastructure, they are betting big on their companies and equipping them with everything they need to innovate and build a better future.

Diagram’s investment portfolio includes the companies featured below and they all work with teams that leverage modern frameworks, cutting edge technology, and complex algorithms to deliver wellness and prosperity to all.

Diagram's Investment Portfolio

Collage is re-inventing the way Canadian businesses manage HR, payroll, and benefits. By offering a 100% free and comprehensive platform, Collage automates paper-based and manual business processes and HR administration in ways that are efficient and secure at scale, enabling companies to spend their time on the more meaningful aspects of business.

Dialogue is the best part of your company's health plan. By offering a range of healthcare services for your team, Dialogue helps to keep them happy, healthy, and performing at their highest potential. Dialogue is using machine learning, natural language processing, and AI to process text conversations, video interactions, and imagery sent from patients to their chatbot in real-time to provide accurate diagnoses of physical and mental health concerns.

Applying to Diagram

For those interested in an opportunity with Diagram or any our portfolio companies, please apply here.

UPD Scoring distribution is 500 — 1000 — 1500 — 2250 — 2500 — 3250 — 3500.

UPD The contest is over! Congratulations to the top 5:

1. eatmore
2. paulwang
3. zemen
4. mnbvmar
5. riadwaw

If you won a prize, you'll be contacted soon.

UPD Editorial: http://codeforces.net/blog/entry/47974

Current standings:

http://myicpc.icpcnews.com/World-Finals-2016/quest/teamerboard

Prediction:

1. University of Waterloo
2. ???

Div2 Easy

The size of the input string is small, so we can iterate over all the substrings and find the largest substring consisting of the characters A, C, G, and T. The complexity of this approach is O(n³). You could solve it in O(n) using the two-pointers method.

Div2 Medium

I claim that the answer will always have at most 6 characters. There are at most n substrings of length 6 of a string of length n. The length of the input string is at most 2000. But there are 4⁶ = 4096 possible DNA sequences of length 6, so at least one of them isn't contained in the string.

That means that we can afford to iterate over all possible answers, in increasing order of length. We will try at most 2000 + 1024 + 256 + 16 + 4 strings, and checking each string will take time, so the algorithm is .

I think this algorithm is actually O(n²) because it is hard to induce worst-case behaviour in the string-checking algorithm, but I haven't proved it.

Div2 Hard

We will use dynamic programming. The state is: suppose we are at position i in the string, we have j changes available, and the robot is currently at (0, 0). Then, we iterate over how many moves it will take for the robot to return to (0, 0). If we know it will take x moves, then it's computationally easy to find the minimum number of changes to make this happen: suppose that if we made no changes, the robot would end up at distance d. Then by making d / 2 changes we can ensure that the robot reaches cell (0, 0).

The complexity is O(n³): there are n² states and each state has n possible transitions.

Div1 Easy

There are a few ways to solve this problem.

One way is this: not hard to code, but difficult to prove. It turns out there are only 3 cases where the answer is no. Here they are, crudely drawn in paint.NET by yours truly about 20 minutes ago:

So, you could manually check these cases.

You are probably interested in a provable solution. We can use the following lemma:

In any graph of n vertices where every vertex has degree at least d, there is a simple path of length min(n - 1, 2d).

This is pretty hard, so I asked someone else to prove it. Here is a proof written by my friend Sina Abbasi:

Take the longest path P in the graph, suppose it is length L. Out of the vertices not in P, take the one v which is connected to a vertex closest to one of the endpoints of P (distance measured on path). Suppose this distance is a>=1. Then each vertex not in P can only be connected to L-2a possible vertices, but it can't be connected to two consecutive ones on the path otherwise there's a longer path, so L/2-a. So if we take the subgraph H by removing P, each vertex has degree at least d+a-L/2. Now follow one end of P until you get to the vertex v is connected to, then follow a path from v for as long as you can outside of P. By a greedy argument this path has length at least L-a+d+a-(L)/2 = (L)/2 +d. Since L was maximal we get d <=L/2 which implies the desired result. I don't know if I did the calculations are completely correct but I think this idea gives the desired bound.

Anyway, once we have this lemma you can reduce the leaves (just mark the remaining vertex with the associated path length). Then you're left with a graph, and if it has a lot of vertices then the answer is immediately yes. Otherwise, there aren't very many vertices left, so you can brute force.

Div1 Medium

The answer is . Wait, that fails the sample case with a cycle of length 4. We have to subtract 1 if there is a vertex on the cycle with exactly 2 neighbours.

This is actually just the maximum connected dominating set problem asked on a pseudotree. Problem authors are getting lazy these days.

Div1 Hard

Challenge phase ends in 5 minutes as I write this so let's make this quick. Let's pretend Bob knows the probability distribution, and the game show picked the worst-case distribution knowing that Bob would know it. The answer to this problem will be the same as the answer to the given problem. Wait, what?

https://en.wikipedia.org/wiki/Minimax_theorem

So, we've switched the problem. How does this make it easier?

Let a₀, ..., a_n - 1 be the chance of K being equal to 0, ..., n - 1. Let b be Bob's expected score. Then:

We can find the minimal value of b with the simplex algorithm.

There's also a solution using binary search that the round tester created. It is pretty cool, but I am not confident that I can explain it.

ABBADiv1 (d1 easy)

The main idea here is that you should work backwards from the target string to the initial string. Almost any solution based on this idea can work. The simplest solution, conceptually, is to do a recursive backtracking search. It will run in polynomial time without any memoization at all. Why?

If it runs in exponential time, we need a branch at each step (a choice of whether to try the last move as A or B). But suppose we had the option of picking A, and we picked B. Now we can never pick B again, since the first character in the string will always be A. So that branch will be resolved in polynomial time. The total complexity is something like O(N³).

You can solve it in O(N) with KMP and prefix sums.

ChangingChange (d1 medium)

In this solution we will assume valueRemoved[i] = 1 for all i.

Let's use generating functions. Suppose ways = {1, 3, 6, 2}. Then we will view it as the polynomial 1 + 3x + 6x² + 2x³. You can show that adding a coin is equivalent to multiplying by (1 + x). So removing a coin must be equivalent to multiplying by . That's equal to 1 - x + x² - x³ + x⁴... (if you don't like calculus, work out the first few terms and you'll see it's 1, -1, 1, -1, 1...). So if numRemoved[i] = n, we want to find the coefficients of (1 - x + x² - x³ + ... ± x^D)ⁿ in linear time. You can show by induction that the signs always alternate for any value of n, so all we need is the magnitude of the coefficients of (1 + x + x² + x³ + ... + x^D)ⁿ.

How can we find those coefficients? Multiplying by that polynomial is equivalent to taking the prefix sum of the coefficients. For example, (1 + 3x + 6x² + 2x³)(1 + x + x² + x³) = 1 + 4x + 10x² + 12x³ + .... There's a combinatorics problem where the values for a given n are the prefix sums of the values for n - 1: the number of right-down paths on an n by c + 1 grid (where c is the coefficient we want). And the formula for that is .

So, here is the formula that solves the problem:

To solve it when valueRemoved[i] ≠ 1, just replace ways[D - c] with ways[D - c·valueRemoved[i]].

WarAndPeas (d1 hard)

Instead of cards and pairs, call them vertices and edges in a complete graph. Let's call the lowest-numbered vertex (the one whose owner never changes) the source vertex. Other vertices that are the same colour as the source are good. Otherwise they're bad.

The critical observation is this: suppose we know there are X good vertices. Then all distributions of the X good vertices are equally likely. This is true regardless of the number of steps. We can prove it by induction on the number of steps (clearly it's true after 0 steps, since each vertex is assigned to the two owners with equal probability). Now we make a new move and select edge E. There are a few cases; note that while the relative chances of these cases depend on the value of X, they don't depend on the distribution of the X good vertices:

• E touches the source vertex. Since all edges touching the source vertex are equally likely to be selected, this preserves the hypothesis.
• E connects a good vertex to a good vertex or a bad vertex to a bad vertex. By the induction hypothesis, all distributions are equally likely. If this outcome happens, the state of the graph is unchanged. Therefore this preserves the hypothesis.
• E connects a good vertex to a bad vertex. Suppose A's colour is overwritten by B's colour. For every distribution where A was good and B was bad, there was an equally likely distribution where B was good and A was bad. So this also preserves the hypothesis.

So, instead of 2^N states, we have N states, where state i represents the state with i good vertices. Suppose Carol's state has x good vertices. By linearity of expectation, we can find the expected number of times we enter state i, divide by , and we have the answer. Normally you would do this with a system of linear equations, but solving a general system takes O(N³). We can speed it up to O(N) (times log factor for modular inverses) by using the fact that state i can only enter state i - 1, i, and i + 1. Represent the expected value from state x as a function of the expected value from state x + 1. It turns out that the function is very simple: f(x) = f(x + 1) + c for some constant c. We can work it out starting from state 0, going to state N - 1, then working backwards and representing the function as a constant c. Add up the expected value from each state, multiplied by the chance of starting in that state, and you are done.

Probably that explanation made no sense, so here is the code: https://ideone.com/ggJ2qd.

ChessFloor (d2 easy)

Try all possibilities. The tricky case is that you can't have all tiles the same color, but it was included in samples.

ABBA (d2 medium)

Work backwards from the target state. The previous move can be uniquely determined by the last character of the string, so simulate it until the strings are the same length and then check if they're equal.

CheeseRolling (d2 hard)

Use DP with 2^N·N states, and iterate over all possibilities for the bracket. The complexity is .

SRM 663 is tomorrow at 11 AM EDT (local start time). I am the author, dreamoon_love_AA and rng_58 are testers, and misof is the language reviewer. Thanks to them for their invaluable help.

Good luck and have fun!

Can anyone recommend resources for preparing for the Distributed Code Jam on June 14th? Some past problems of a similar nature would be really helpful.

This was my first SRM, and I would like to thank rng_58 (algorithm coordinator + tester), KADR (tester), misof (language reviewer) and dreamoon_love_AA (author of Div1 medium) for their invaluable help.

I will try to keep this short, since the TC editorial writers are much better at writing explanations.

Div2 Easy -- FilipTheFrog

The simplest solution is to perform N iterations. Each iteration, look for a pair (i, j) such that island i is reachable and |positions[i] - positions[j]| ≤ L. Mark island j as visited. The complexity is O(N³). It works because each iteration increases the answer by at least 1 assuming it hasn't already been found, so after N iterations your answer is guaranteed to be correct.

Div2 Medium -- PublicTransit

You can fix each possibility for the teleporter and then test every pair of cells to find the longest distance. You can calculate it as follows: if the teleporter cells are at a and b, then the distance between cells x and y is the minimum of the following:

• dist(x, y)
• dist(x, a) + dist(b, y)
• dist(x, b) + dist(a, y)

The complexity is O(R⁴C⁴). I think you can improve it to O(R³C³) by observing that if one booth is at (r, c), the other booth should be at (R - r + 1, c) or (r, C - c + 1). I'm not actually sure if that's true, though. Maybe it's wrong. Can anyone prove/disprove it?

Div2 Hard -- ApplesAndOrangesHard

First, read the editorial for the easy version below.

We will use the same greedy algorithm, but we can't process every fruit directly. Let's think about the optimal answer if weren't included. We could have floor(K / 2) apples, then ceil(K / 2) oranges, repeated until we have N fruits.

When we are forced to add an apple, we should disrupt this pattern as little as possible. Let's sort and keep a 'window' of size K. Initially, the window's first K / 2 elements are apples and the rest are oranges, and it represents the range of fruits [1, K]. When you move to the next element of , cycle the window forward so that fruit number is at the end of the window. Then, pick the the apple with the greatest index, and move it to the end of the array. You have to ensure you don't pick an apple that is immovable because of a previous value in . The complexity is .

You can also solve it when K ≤ 10⁹, but it's more trouble than it's worth.

Div1 Easy -- ApplesAndOrangesEasy

The algorithm is greedy: for each i from 1 to N, try to make the i-th fruit an apple. If it contradicts the information you have, make it an orange instead. It works because making a fruit an apple affects the next K - 1 choices, so you want to make the earliest possible fruit an apple -- that way, it becomes unimportant sooner.

Naive complexity is O(NK²); you can improve it to O(NK) by using a queue or prefix sum array or clever loop.

Div1 Medium -- CampLunch

(Problem and editorial by dreamoon_love_AA.)

If all permutation in each element of a are same, this problem just a normal Tiling problem such as UVa11270. (Before solve this SRM med problem, you may need to know how to solve UVa11270 with O(n² * 2ⁿ) firstly.)

The main difference of this problem with UVa11270 is a student can seat in different place in consecutive two days. It cause we cannot only reserve dp status for next M seats from current seat (this kind of problem method have the status dp[row][column][the occuppied status of next M grids]). Then, how can we resolve this situation?

Here provides two method to resolve it by change dp status:

(1) Change dp status to dp[row][i-th student][the status of having plan or not of next M (day, student)].

You can imagine it as all student seat in alphabetical order, and plan 2 of lunch represent some pair of student can get double lunch in some day. By this way, you only reserved status of at most M student in dp proccess.

(2) Change dp status to dp[row][column][the status of having plan or not of next M (day,student)].

In detail, the next M (day,student) means students that have larger column number of this row in the same day and other students in next day. I think it's more difficult to imagine than previous method.

Ironically, the two methods are not provided by myself, these solution are provided by two tester. I solve it in O(2ⁿ * n³) originally. The story tell us: if you can find a good status of dp, it make your dp life better.

Div1 Hard

Fix the first teleporter at A. Now do a DFS from A. Suppose we're currently visiting B. Each node N on the path from A to B has a precomputed 'hanging value', the length of the longest path starting from N which doesn't get closer to A or B. Number the nodes on the path from 0 (A) to S - 1 (B), where the path has S nodes. When moving between nodes at positions p₁ and p₂ on the path (p₂ > p₁), we can take a direct route (length p₂ - p₁) or an indirect route (length (S - 1) - p₂ + p₁). Note that the length of the direct route is fixed, while the indirect route gets 1 minute longer with each step of DFS.

In the DFS transition, we add a node to the path. We will process this node to obtain an integer LIM, meaning that the new node enforces the constraint that we can't continue the DFS in a direction away from A and B for more than LIM steps.

How do we process the node? Suppose the node has hanging value v₂ and position p₂. We want to select a node on the path with value v₁ and position p₁ such that:

• The direct path is infeasible: p₂ - p₁ + v₁ + v₂ > X. Rearranging, we want v₁ - p₁ > X - p₂ - v₂.
• The limiting factor (LIM = X - ((S - 1) - p₂ + p₁ + v₁ + v₂)) is minimal. Rearranging, we want to maximize v₁ + p₁.

By converting candidate nodes (v₁, p₁) to diagonal coordinates (v₁ - p₁, v₁ + p₁), it reduces to dynamic RMQ and we can solve it with a persistent segment tree. The complexity is .

I wrote a point viewer which you can find here: http://jacob-jackson.appspot.com/point_viz.html.

Please let me know if you find any bugs. It's written in Javascript and you're free to copy and modify it.

My school (UTS) is holding a week-long contest at http://www.dmoj.ca/contest/utsopen15. Please take a look and see if you find the problems interesting.

The problem setters are me and jeffrey.xiao.