### lewin's blog

By lewin, history, 5 months ago, ,

I'm not sure I've seen a post about this yet. Topcoder has posted their schedule for online rounds for TCO here: http://tco18.topcoder.com/algorithm/schedule/

It seems the round structure also seems to have changed. The rounds are 1A,1B, 2A,2B, 3A,3B, and a single round 4. Round 4 feeds directly into the onsite, with 14 finalists (and also 2 from a wildcard round, for a total of 16, 4 more from last year).

•
• +47
•

By lewin, history, 5 months ago, ,

Several hours later, it will be available as an open cup round as the Grand Prix of America (start time here). Please only participate in one of them, and don't discuss problems here until after the open cup round has ended.

The deadline to register for the contest on Kattis is March 21st. You will need an ICPC account to register (you can see instructions in the link above on how to create one if needed).

You can see some past years' problems here: 2017, 2016

UPD 2: Contests are over

•
• +49
•

By lewin, history, 6 months ago, ,
Police Patrol
Alphabetic Subsequence
Infinite Graph Game
Stamp Stamp Stamp
Increasing Sequence
Yet Another Binary Matrix

•
• +81
•

By lewin, history, 6 months ago, ,

Hello everybody!

On Mar 3, 10:00 Moscow time, Round 1 of Yandex.Algorithm 2018 competition will take place. I wrote the majority of the problems in this contest, with some additional help from GlebsHP.

I would like to thank GlebsHP for all his help with coordinating this round, MikeMirzayanov for polygon, and of course, everyone who took the time to test this round.

See you in the competition soon!

Editorial here: http://codeforces.com/blog/entry/58135

•
• +126
•

By lewin, history, 6 months ago, ,

Hi! Topcoder SRM 730 will happen soon.

I'm the writer of this round. Hope to see you all participate!

•
• +140
•

By lewin, 8 months ago, ,

Here's the editorial. Hope you have a happy new year!

Code can be found here: https://www.dropbox.com/sh/i9cxj44tvv5pqvn/AACQs7LLNyTZT-Gt_AMf7UQFa?dl=0

New Year and Counting Cards
New Year and Buggy Bot
New Year and Curling
New Year and Arbitrary Arrangement
New Year and Entity Enumeration
New Year and Original Order
New Year and Boolean Bridges

Tutorial of Good Bye 2017

•
• +336
•

By lewin, history, 8 months ago, ,

Hello everyone!

Another year has gone by. The last Codeforces contest of this year will be tomorrow, 29 Dec, 15:35 UTC.

The round details:

• combined div1+div2
• 8 problems
• 2.5 hours
• rated!!!

I'd like to thank the following people for helping with the round: KAN, winger, AlexFetisov, zemen, xiaowuc1, MikeMirzayanov. Without them, this round would not have been possible.

Scoring distribution will be posted later. Make sure to read ahead on the problems, since there may be some later problems that are easier for you. I hope to see you all at the contest, and good luck on the last chance to increase your rating this year!

EDIT1: The scoring distribution is 500-750-1000-1750-1750-2000-2750-3500

EDIT2: There will be a five minute delay for starting.

EDIT3: Editorial is here: http://codeforces.com/blog/entry/56713

EDIT4: Congratulations to the winners!

•
• +1310
•

By lewin, history, 9 months ago, ,

I recently added this regional to the gym here. You can virtual participate at any time.

Solutions are available on the contest website if you want to look at them up afterwards here. Feel free to discuss problems afterwards.

•
• +71
•

By lewin, history, 13 months ago, ,

On Sunday, August 6th, 22:00 IST, we will hold the 2nd elimination for IndiaHacks (some more details here). The top 900 individuals who qualified through previous rounds will have the opportunity to participate in this round. The top 25 global participants and top 25 Indian participants will advance to the final round. The link to the contest is here.

After the official round is over, the next morning, on Monday, August 7th, 11:35 IST, we'll hold an unofficial unrated mirror here on Codeforces. This mirror will have ICPC rules. For participants of the official round, please hold off on discussing the problems publicly until after this mirror is over.

I was the author of the problems in this set, and I hope you will enjoy the problems. I would like to thank zemen for testing the set, Arpa for writing editorials, r3gz3n for his help on the HackerEarth side, KAN for helping us set up the mirror contest, and of course MikeMirzayanov for the great Polygon/Codeforces platform.

The round will consist of 6 problems and you will have 3 hours to complete them. Please note that the problems will be randomly arranged in both rounds, since I couldn't figure out how to sort them by difficulty. Be sure to read all the problems.

UPD1: Updated time of official round and posted link to contest.

UPD2: We should have updated the leaderboard to accept solutions that followed the first version of the first problem. We have also increased the number of finalists to 60 total (30 global + 30 indian) based on this new leaderboard.

UPD3: Here is the list of qualifiers. Congratulations to everyone.

global
indian

•
• +135
•

By lewin, history, 13 months ago, ,

Didn't notice a post from cgy4ever.

Topcoder SRM 718 will happen in ~4 hours.

•
• +83
•

By lewin, history, 14 months ago, ,

Hello everyone!

I would like to invite you to participate in Hackerearth June Circuits 2017. It's a long contest that will start on June 16, 2017, 21:00 IST (check your timezone). The contest will run for 9 days.

The problemset consists of 7 traditional algorithmic tasks and 1 approximate problem. For traditional algorithmic tasks, you will receive points for every test case your solution passes — so you can get some points with partial solutions as well. For the approximation task, your score depends on the best solution in the contest so far. Check contest page for more details about in-contest schedule and rules.

I'm the tester of the problemset you'll have to work on — thanks to jtnydv25, saatwik27, harshil, zscoder, Arunnsit for preparing these tasks.

As usual, there will be some prizes for the top five competitors:

1. $100 Amazon gift card + HE t-shirt. 2.$75 Amazon gift card + HE t-shirt.
3. $50 Amazon gift card + HE t-shirt. 4. HE t-shirt. 5. HE t-shirt. Good luck to everyone, and I hope to see you at the contest :) Read more » • • +60 • By lewin, 15 months ago, , Fibonacci Frequency Rainbow Road Wildcard Words Counter Complexity Avoiding Adjacent Token Tree Read more » • • +80 • By lewin, history, 15 months ago, , Hello everybody! On May 27, 23:00 Moscow time, Round 2 of Yandex.Algorithm competition will take place. I wrote the majority of the problems in this contest, with some additional help from Zlobober. I would like to thank Zlobober for all his help with coordinating this round, MikeMirzayanov for polygon, and of course, everyone who took the time to test this round. Please note, the problems will be randomly arranged, so make sure you read everything during the round :) If you are using Java, please submit using Java 7 x32. See you in the competition soon! UPD 1: Editorial here: http://codeforces.com/blog/entry/52223 Read more » • • +64 • By lewin, history, 16 months ago, , Hello everyone! I would like to invite you to participate in Hackerearth April Circuits 2017. It's a long contest that will start on April 21, 21:00 IST (check your timezone). Contest will run for 9 days. The problemset consists of 7 traditional algorithmic tasks and 1 approximate problem. For traditional algorithmic tasks, you will receive points for every test case your solution passes — so you can get some points with partial solutions as well. For the approximation task, your score depends on the best solution in the contest so far. Check contest page for more details about in-contest schedule and rules. I'm the tester of the problemset you'll have to work on — thanks to jtnydv25, saatwik27, pkacprzak, r3gz3n, trytolearn for preparing these tasks. As usual, there will be some nice prizes for the top five competitors: 1.$100 Amazon gift card + HE t-shirt.
2. $75 Amazon gift card + HE t-shirt. 3.$50 Amazon gift card + HE t-shirt.
4. HE t-shirt.
5. HE t-shirt.

Good luck to everyone, and I hope to see you at the contest :)

•
• +28
•

By lewin, history, 16 months ago, ,
Viscious Keyboard
Valued Keys
Voltage Keepsake
Volatile Kite
Vulnerable Kerbals
Varying Kibibits
Verifying Kingdom

Tutorial of VK Cup 2017 - Round 2

•
• +63
•

By lewin, 16 months ago, ,

Hello!

The round 2 of VK Cup 2017 will take place on April 16 at 18:35 MSK (check your timezone here), along with separate div1 and div2 Codeforces Round #409. The contest "VK Cup 2017 — Round 2" is for teams qualified from round 1. The top 100 teams will advance to the Round 3, while other ones will have one more chance in the Wild Card Round 2 later this month. Those who don't participate in the VK Cup can take part in the Codeforces Round #409 individually (problems will be available in English too). All three rounds last 2 hours, and all are rated.

The round would not be possible without the following people (in no particular order): KAN, Errichto, winger, AlexFetisov, LiChenKoh, xiaowuc1, MikeMirzayanov. Additionally, I thank VK company for sponsoring this contest.

As usual, the scoring distribution will be announced later.

UPD 1: The scoring distribution is as follows:

div2: 500 — 1000 — 1500 — 2000 — 2750

div1 and official round: 500 — 1000 — 175022502250

UPD 2: The tutorial is available here: http://codeforces.com/blog/entry/51598

Congratulations for the winners

Official round:

div 1:

div 2:

Announcement of VK Cup 2017 - Round 2

•
• +217
•

By lewin, history, 17 months ago, ,

NAIPC is coming up on April 15 (start time here). More information can be found on the site. The contest will be on Kattis on the 15th. About 15 hours later, it will be available as an open cup round as the Grand Prix of America. Please only participate in one of them, and don't discuss problems here until after the open cup round.

The deadline to register for the contest on Kattis is April 12th. You can register by following instructions on this site: http://naipc.uchicago.edu/2017/registration.html# You will need an ICPC account to register.

You can see previous NAIPC rounds here: 2015, 2016. 2016 is also available in the codeforces gym here: http://codeforces.com/gym/101002

UPD 1: The deadline to register is in a couple of days.

UPD 2: Both contests are now over

NAIPC standings: https://naipc17.kattis.com/standings

Open Cup standings: http://opentrains.snarknews.info/~ejudge/res/res10376

I'll update this one more time with solutions once they are up.

UPD 3: Test data is available here (solutions may show up later, but I'm not sure when): http://serjudging.vanb.org/?p=1050

•
• +82
•

By lewin, history, 17 months ago, ,

Hello everyone!

I’d like you to invite for CodeChef March Cook-Off that will start at 21:30 IST of 19-th March 2017 (check your time zone here) and will last 2.5 hours.

I am the author of problems and editorials, while Errichto is the tester. There are also some other people who helped with translations and miscellaneous issues who I will fill in later.

There is no registration required, anybody with a CodeChef handle can participate. Top participants can win CodeChef laddus (details on the contest page).

You will be provided 5 problems. There's one problem that shows a style of problems I would like to see more in competitions. Let me know what your thoughts are after the contest.

Hope to see you all on the leaderboard!

•
• +23
•

By lewin, history, 18 months ago, ,

I recently added this regional to the gym. I set it to start at this time, but I think you can just do virtual participation whenever you want.

I set about 5 of the problems on the set. I would say difficulty goes up to around div1D.

Solutions are available on the contest website if you want to look those up afterwards. Let me know what you think of the problems afterwards!

•
• +42
•

By lewin, 20 months ago, ,

Short solutions:

• Div2A: How many times do we need to do a cyclic shift to consider all possible ones? Afterwards, what data structure allows us to easily check number of distinct elements?
• Div2B: Imagine the process in reverse. What types of identical shapes can I get if I cut a rectangle into two pieces? Remember, pieces cannot be rotated or flipped.
• Div2C / Div1A: How do we handle components with special nodes? What do we do with the ones without special nodes?
• Div2D / Div1B: We don't get many questions, so is there a way to "parallelize" questions? Another approach, can we split up the condition i != j somehow using bits?
• Div2E / Div1C: First, somehow reduce it so r_i,b_i <= n. Now, we can bound the excess tokens by a small number, so we can do bitmask dp from here.
• Div1D: The optimal circle must touch a blue point. Now, either consider the inversion, or do a binary search
• Div1E: What makes a list good? How fast can we do this check, and how many times do we need to do this check?

Long solutions:

## Hongcow Learns the Cyclic Shift

We only need to consider at most |s| cyclic shifts (since |s| cyclic shifts returns us back to the original string).

So, we can put these all in a set, and return the size of the set.

code

## Hongcow Solves A Puzzle

I really apologize for the ambiguity of this problem. We worked hard to make it concise and accurate, but we left out too many details.

Basically, the idea is we want to overlay two of these pieces together so that no square has more than 1 X, and the region of X's forms a rectangle.

Now for the solution:

First, let's look at it backwards. I have a rectangle, and I cut it in two pieces. These two pieces have the same exact shape. What shapes can I form?

A necessary and sufficient condition is that the piece itself is a rectangle itself! There are a few ways to check this. One is, find the min/max x/y coordinates, and make sure the number of X's match the bounding box of all the points.

code

## Hongcow Builds a Nation

First, let's make all connected components cliques. This graph is still stable.

Now, there are some components without special nodes. Where should we connect them?

If there is a component with size A and a component with size B, we can add A*B edges if we connect these two components. So, it makes sense to choose the largest component.

code

## Hongcow's Game

For the bits solution: We want to create 20 questions where for every i != j, there exists a question

that contains j and not i, and also a qusetion that contains i and not j. If we can do this, we can find the min for each row.

Note that i != j implies that there exists a bit index where i and j differ.

So, let's ask 2 questions for each bit position, one where all indices have a value of 0 in that position, and one where all indices have a value of 1 in that position. This is a total of at most 20 questions, and we can show that this satisfies the condition above, so this solves the problem.

Parallelization will basically reduce to the above solution, but is another way of looking at the problem.

First, let's ask {1,2,...,n/2} and {n/2+1,...,n} This handles the case where the min lies on the opposite half.

[
OOOOXXXX
OOOOXXXX
OOOOXXXX
OOOOXXXX
XXXXOOOO
XXXXOOOO
XXXXOOOO
XXXXOOOO
]


For example, this handles the case where the min lies in the X part of the matrix, and we split it into two identical problems of size n/2 within the O matrix.

Now, we can ask questions for each submatrix, but we can notice that these two don't interact so we can combine all the questions at this level.

However, we should ask the questions in parallel, as we don't have that many questions For example, for n=8, we should ask

First level:
[1,2,3,4]
[5,6,7,8]

Second level
[1,2],[5,6] (i.e. ask 1,2,5,6 all together, but this is actually two different subproblems, one for the top left, and one for the bottom right).
[3,4],[7,8]

Third level
[1],[3],[5],[7]
[2],[4],[6],[8]


As you can see, this reduces to the bit approach above if N is a power of 2.

code

## Hongcow Buys a Deck of Cards

Also note that if r_i or b_i >= n, we need to collect tokens no matter what since those costs can't be offset. So, we can assume that r_i, b_i <= n.

Let's only buy tokens when we need them. Note that after buying a card, you will have either 0 red tokens or 0 blue tokens, so our dp state can be described by [mask][which one is zero][how many of the other] The dimensions of this dp table are 2^n * 2 * (n^2) (n^2 because the costs to buy cards is at most n).

See the code for more details on how to update this dp.

code

## Hongcow Draws a Circle

First to check if an answer can be arbitrarily large, we can see if there is any red point that is on the convex hull of all our points. So from now on, we can assume the answer is finite.

We can show that the optimal circle must touch a blue point. To see this, consider any optimal circle that doesn't touch a blue point. We can make it slightly bigger so that it does touch one.

So, let's binary search for the answer. However, you have to very careful and notice that the binary search isn't monotonic if we only consider circles touching blue points. However, if we consider circles that touch either a red or blue point, then the binary search is monontonic, so everything works out.

To check if a radius works, we can do a angle sweep around our center point. We have a fixed radius and fixed center, so each other point has at most two angles where it enters and exits the circle as we rotate it about the center point. We can keep track of these events and find an interval where the circle only contains red points.

code for binary search

For the inversion solution, let's fix the blue point that our circle touches. Then, let's take the inversion around this point (i.e. https://en.wikipedia.org/wiki/Inversive_geometry). Now, circles that pass through our center points become lines, and the interior of those circles are in the halfplane not containing the center point. The radius of the circle is inversely proportional to the distance between our center point to the line after inversion.

So, we can say we want to solve the following problem after inversion. Find the closest line that contains no blue points in the halfplane facing away from our center point and at least one red point. We can notice that we only need to check lines that contain a blue point on the convex hull after inversion.

To make implementation easier, you can make the additional observation that the sum of all convex hull sizes will be linear through the process of the algorithm. Some intuition behind this observation is that only adjacent nodes in a delaunay triangluation can appear on the convex hull after inversion, so the sum is bounded by the number of edges in such a triangulation (of course, we do not need to explicitly find the triangulation).

code for inversion

## Hongcow Masters the Cyclic Shift

Let M denote the total number of characters across all strings.

Consider how long it takes to compute f(L) for a single list.

Consider a graph where nodes are suffixes of strings. This means we already spelled out the prefix, and still need to spell out the suffix.

There are at most M nodes in this graph. Now, draw at most N edges connecting suffixes to each other. We can find the edges efficiently by doing suffix arrays or z algorithm or hashes.

Now, we claim is the list is good if and only if there is no cycle in this graph. You can notice that a cycle exists => we can construct a bad word. Also, if a bad word exists => we can form a cycle. So, we can check if there is a cycle, which takes O(N*M) time.

Next step is to notice that extending a bad list will never make it good. So we can do two pointers to find all good intervals, which requires O(n) calls to the check function. So, overall this runs in O(N^2*M) time.

You might be wondering why this problem asks for sublists rather than the entire list. To be honest, it's just to make tests slightly stronger (i.e. I get ~30^2x the number of tests in the same amount of space).

code

•
• +88
•

By lewin, history, 20 months ago, ,

Hello everyone!

Codeforces round #385 will take place at the unusual usual time of Saturday, 17 December 19:35 MSK.

Thanks to the following people for making this round possible.

As usual, contestants will have 2 hours to solve 5 problems. Hope you will enjoy the problems!

Scoring will be announced closer before the round.

EDIT: It may be helpful to read the Interactive Problem Guide before the round for both divisions.

EDIT 2: The scoring distribution will be unusual:

Div2: 500-1000-1500-2250-2750

Div1: 500-1250-1750-2250-2500

EDIT 3: While you wait for system testing, here is a quick editorial: http://codeforces.com/blog/entry/49126

EDIT 4: Congratulations to the winners!

Div1:

Div2:

•
• +477
•

By lewin, 20 months ago, ,

Hello everyone

I would like to invite you all to the last HackerEarth Clash of the year starting in around 28 hours (link to register here, check your time zone here). The contest will last 24 hours.

There will be five algorithmic problems and one approximation (optimization) problem. Read the problems for details on partial scoring for easier subtasks. I tried to make this clash slightly easier than my previous clashes, so hopefully there will be more than 1 perfect score on the algorithm problems. I hope you find the problems interesting nonetheless.

I would like to thank usaxena95 for all his help in testing, editing statements, and writing editorials, and belowthebelt for all his help with the round.

There will be prizes — t-shirts and Amazon gift cards.

Hope to see you all at the contest!

•
• +45
•

By lewin, history, 2 years ago, ,

Hello everyone!

I would like to invite you to participate in HackerEarth August Circuits. It's a long contest that will start on August 20, 21:00 IST (check your timezone). Contest will run for 8 days.

The problemset consists of 7 traditional algorithmic tasks and 1 approximate problem. For traditional algorithmic tasks, you will receive points for every test case your solution passes — so you can get some points with partial solutions as well. For the approximation task, your score depends on the best solution in the contest so far. Check contest page for more details about in-contest schedule and rules.

I'm the tester of a problemset you'll have to work on — thanks to belowthebelt, jtnydv25, mgch, RomaWhite for preparing these tasks.

As usual, there will be some nice prizes for the top five competitors:

1. $100 Amazon gift card + HE t-shirt. 2.$75 Amazon gift card + HE t-shirt.
3. $50 Amazon gift card + HE t-shirt. 4. HE t-shirt. 5. HE t-shirt. Good luck to everyone, and I hope to see you at the contest :) Congratulations to the winners: 6 way tie for first place: mugurelionut, uwi, ceilks, Catalin Stefan Tiseanu, anta, Rafaël Bocquet Unfortunately, the approximate problem was not very good at distinguishing top contestants (this was my fault with coming up with a weak generator). For prizes, we will evenly distribute prizes of the among the top 6. More specifically, the top 6 will each receive a$35 amazon gift card and a t-shirt.

•
• +56
•

By lewin, history, 3 years ago, ,

I hope you enjoyed the contest! Let me know if you find any errors below. Thanks for participating.

Short solutions:

• Slime Combining: You can just do what's described in the statement. Or, maybe you can do something with the binary representation of the number.
• Guess the permutation: Find out where 1 should go. Then, find out where 2 should go, and so on.
• Constellation: Start with a triangle and break it up. Or, choose a point and look at angles. Or, sort by x coordinate.
• Hamiltonian Spanning Tree: Two cases: X > Y and X <= Y. For X > Y we can almost always avoid the spanning tree edges. For X <= Y we can do something greedy.
• Robot Arm: Make a segment tree on segments. A segment is basically just a linear transformation, which can be described with three numbers.
• Double Knapsack: Make the problem harder. Let's say I want a consecutive sublist of both lists that have equal sums. Then use pigeonhole principle to get an answer.
• Combining Slimes: Use conditional expectations. Define E[value of squares i .. n | i-th square has value j, and will not be merged with anything]. Notice that it's almost impossible for us to get a slime with value >= 50. Then, somehow generalize to large values of n (either by linear interpoloation or matrix exponentiation).

Long solutions:

## Slime Combining

We can simulate the process described in the problem statement. There are many possible implementations of this, so see the example code for one possible implementation. This method can take O(n) time.

However, there is a faster method. It can be shown that the answer is simply the 1-based indices of the one bits in the binary representation of n. So, we can just do this in O(log n) time.

Example code (for simulation): http://codeforces.com/contest/618/submission/15669470

Example code (for faster method): http://codeforces.com/contest/618/submission/15669458

## Guess the Permutation

One solution is to look for the column/row that contains only 1s and 0s. We know that this index must be the index for the element 1. Then, we can repeat this for 2 through n. See the example code for more details. The runtime of this solution is O(n^3).

However, there is an easier solution. One answer is to just take the max of each row, which gives us a permutation. Of course, the element n-1 will appear twice, but we can replace either occurrence with n and be done. See the other code for details

Example code (for first): http://codeforces.com/contest/618/submission/15669492

Example code (for second): http://codeforces.com/contest/618/submission/15669483

Comment: Originally, I wanted to set it so it wasn't guaranteed that there was a solution. But this seemed a bit tedious to me, so I didn't include this case.

## Constellation

There are many possible solutions to this problem.

The first solution is to choose any nondegenerate triangle. Then, for each other point, if it is inside the triangle, we can replace one of our three triangle points and continue. We only need to make a single pass through the points. We need to be a bit careful about collinear points in this case.

Another solution is as follows. Let's choose an arbitrary point. Then, sort all other points by angle about this point. Then, we can just choose any two other points that have different angles, breaking ties by distance to the chosen point. (or breaking ties by two adjacent angles).

Example code (by breaking up triangles): http://codeforces.com/contest/618/submission/15669502

Example code (by angles): http://codeforces.com/contest/618/submission/15669511

Comment: Except for the second sample, all pretests didn't have collinear points. So many hacking cases are cases with collinear points.

## Hamiltonian Spanning Tree

This is two separate problems: One where X > Y and when X <= Y.

Suppose X > Y. Then, we can almost always choose a path that avoides any spanning tree edges. There is one tricky case, which is the case of a star graph.

To prove the above statement, we know a tree is bipartite, so let's choose a bipartition X,Y. As long as there is exists a pair x in X and y in Y such that there isn't an edge between x and y, we can form a hamiltonian path without visiting any spanning tree edges (i.e. travel through all vertices in X and end at x, then go to y, then travel through all vertices in Y). We can see that this happens as long as it is not a complete bipartite graph, which can only happen when |X| = 1 or |Y| = 1 (which is the case of a star graph).

For the other case, X <= Y. Some intuition is that you want to maximize the number of edges that you use within the spanning tree. So, you might think along the lines of a "maximum path cover". Restating the problem is a good idea at this point.

Here's a restated version of the problem. You're given a tree. Choose the maximum number of edges such that all nodes are incident to at most 2 edges. (or equivalent a "2-matching" in this tree). Roughly, the intuition is that a 2-matching is a path cover, and vice versa.

This can be done with a tree dp, but here is a greedy solution for this problem. Root the tree arbitrarily. Then, let's perform a dfs so we process all of a node's children before processing a node. To process a node, let's count the number of "available" children. If this number is 0, then mark the node as available. If this number is 1, draw an edge from the node to its only available child and mark the node as available. Otherwise, if this number is 2 or greater, choose two arbitrary children and use those edges. Do not mark the node as available in this case.

Now, let U be the number of edges that we used from the above greedy algorithm. Then, the final answer is (n-1-U)*y + U*x).

(Proof may be added later, as mine is a bit long, unless someone has an easier proof they want to post).

Comment: The case where X > Y and the tree is a star was not included in pretests. Thus, this could have been used to hack.

## Robot Arm

We can view a segment as a linear transformation in two stages, first a rotation, then a translation.

We can describe a linear transformation with a 3x3 matrix, so for example, a rotation by theta is given by the matrix {{cos(theta), sin(theta), 0}, {-sin(theta), cos(theta), 0}, {0, 0, 1}} and a translation by L units is, {{1, 0, L}, {0, 1, 0}, {0, 0, 1}} (these can also be found by searching on google). So, we can create a segment tree on the segments, where a node in the segment tree describes the 3x3 matrix of a range of nodes. Thus updating takes O(log n) time, and getting the coordinates of the last blue point can be taken.

Some speedups. There is no need to store a 3x3 matrix. You can instead store the x,y, and angle at each node, and combine them appropriately (see code for details). Also, another simple speedup is to precompute cos/sin for all 360 degrees so we don't repeatedly call these functions.

Example code (Java): http://codeforces.com/contest/618/submission/15669521

Example code (C++): http://codeforces.com/contest/618/submission/15669530

Comment: I'm very sorry about precision issues. We realized this at the last minute, and I didn't expect so many solutions to fail because of this. I have checked my own answers against a BigDecimal implementation in Java, so try to use long doubles. Also, as a side note, this is the first ever data structure question that I've written.

## Double Knapsack

Let's replace "set" with "array", and "subset" with "consecutive subarray".

Let ai denote the sum of the first i elements of A and bj be the sum of the first j elements of B. WLOG, let's assume an ≤ bn. For each ai, we can find the largest j such that bj ≤ ai. Then, the difference ai - bj will be between 0 and n - 1 inclusive. There are (n + 1) such differences (including a0 - b0), but only n integers it can take on, so by pigeon hole principle, at least two of them are the same.

So, we have ai - bj = ai' - bj'. Suppose that i' < i. It can be shown that j' < j. So, we rearranging our equation, we have ai - ai' = bj - bj', which allows us to extract the indices.

Comment: It seemed difficult for me to generate strong cases. Is there an easy way to do it? I tried my best, but there may be some weird solutions that can pass that I just overloooked.

## Combining Slimes

The probability that we form a slime with value i roughly satisfies the recurrence p(i) = p(i-1)^2, where p(1) and p(2) are given as base cases, where they are at most 999999999/1000000000. Thus, for i bigger than 50, p(i) will be extremely small (about 1e-300), so we can ignore values bigger than 50.

Let a[k][i] be the probability that a sequence of 1s and 2s can create i given that we have k squares to work with, and b[k][i] be the same thing, except we also add the constraint that the first element is a 2.

Then, we have the recurrence a[k][i] = a[k][i-1] * a[k-1][i-1], b[i][k] = b[k][i-1] * b[k-1][i-1] Note that as k gets to 50 or bigger a[k] will be approximately a[k-1] and b[k] will be approximately b[k-1] so we only need to compute this for the first 50 rows.

We can compute the probability that the square at i will have value exactly k as a[n-i][k] * (1 — a[n-i-1][k]).

Let dp[i][j] denote the expected value of the board from square i to n given that there is currently a slime with value j at index i and this slime is not going to be combined with anything else.

We can compute dp[i][j] using 2 cases:

First, we compute this dp manually from n to n-50. After that, we can notice that since a[k] is equal to a[k-1] and b[k] is equal to b[k-1] for k large enough, this dp can be written as a matrix exponentiation with 50 states. Thus, this takes O(50^3 * log(n)).

Another approach that would also work is that after a large number of squares, the probabiltiy distribution of a particular square seems to converge (I'm not able to prove this though, though it seems to be true). So, by linearty of expectation, adding a square will add the same amount. So, you can do this dp up to maybe 500 or 1000, and then do linear interpolation from there.

Example code (with matrix exponentiation): http://codeforces.com/contest/618/submission/15669558

Example code (with linear interpolation): http://codeforces.com/contest/618/submission/15669560

Comments; This problem is inspired from the game 2048. The way I discovered these formulas was through some trial and error and comparing versus a bitmask dp. Try to come up with the bitmask dp solution first if you are having trouble with understanding the editorial.

•
• +128
•

By lewin, 3 years ago, ,

Hello Codeforces!

I invite all of you to participate in a special Codeforces round. It will take place on 29 Jan, 17:05 UTC. It will not be a usual round. Thanks to Wunder Fund, the best participants will win prizes and souvenirs. Here are some words from Wunder Fund:

Our company is situated in the center of Moscow. We are engaged in high-frequency trading — developing high-performance systems and algorithms for automated trading in financial markets. In this area algorithms and data structures (that you love to invent and implement) are vital. Our systems should process transactions in milliseconds! High-frequency trading is a continuous competition of the best programmers and mathematicians around the world. By joining us, you will become a part of this exciting challenge.

We offer interesting and challenging tasks for the development of low latency for enthusiastic researchers and programmers. Flexible and no bureaucracy, decisions are taken quickly and implemented. We are a small team, so you will immediately become a significant part of it. Understand the economics and finance is not required, but the algorithms and data structures is what we need.

We will be happy to give participants prizes and gifts:

• 1 place — PlayStation 4
• 2 place — Xbox One
• 3-5 places — Sega MegaDrive 16bit with games
• 1-50 places — Wunder Fund T-Shirts!
• 51-500 places — 50 T-Shirts to random participants!

Interested in the work on Wunder Fund?

I want to thank the following people for helping me with this round:

• GlebsHP for his help in reviewing problems and assistance in preparation for the round.
• LiChenKoh, AlexFetisov, and winger for testing problems.
• Delinur for translations.
• MikeMirzayanov for Codeforces and Polygon systems.
• and of course Wunder Fund for sponsoring the round.

I hope to see you all at the round. Good luck and have fun! :)

If you'd like some practice before the round, you can look over some of my past rounds that I've written (links here: A B C). I will try to give you all some more interesting problems to solve.

UPD1: The round will be 2 hours and 7 problems. Unfortunately, there are some time conflicts, so we are unable to extend the duration of the round. The score distribution will be 500-1000-1500-1750-2500-2750-3500. Note that some problems that we thought are harder may actually be easier for you, so I encourage you to read all problems.

UPD2: The editorial is published. Congratulations to the winners