### Lewin's blog

By Lewin, history, 36 hours ago, ,

Here's the tutorial. Code can be found in this link: https://www.dropbox.com/sh/wfr12qqhcrdwwlv/AAAgg-7NcqRHIysVjHvmcR_Ta?dl=0

Love A
Hate A
Tree Diameter
Frog Jumping
Hot is Cold
Leaf Partition
Zoning Restrictions
Satanic Panic

•
• +185
•

By Lewin, 4 days ago, ,

Hi Codeforces!

I'm excited to announce the Forethought Future Cup! It will consist of two rounds, an online round on April 20th, 11:05am PDT, and an onsite round on May 4th, 10:05am PDT. Both of these rounds will be rated and open for all participants. The top 25 local contestants near San Francisco will be invited to the Forethought office to take part onsite.

Each round will be a combined round. In the first round, there will be 8 problems in 2.5 hours. There will be at least one interactive problem in this round. Please read the interactive problem guide if you haven’t already.

The problems in this round were all written by me. Thanks to ismagilov.code, mohammedehab2002, Jeel_Vaishnav, Learner99, dojiboy9, fortune, y0105w49, KAN, arsijo for testing and coordination. Of course, thanks to MikeMirzayanov for Codeforces and Polygon, and for allowing us to host the round.

### Prizes

T-shirts will be awarded to all onsite participants. 25 shirts will also be randomly awarded to contestants in the elimination round with ranks 1 to 250. The onsite round will also have some monetary prizes:

• First: $500 • Second:$250
• Third: $100 • 4th — 10th:$50

At Forethought, our mission is to use AI technology to augment human abilities and make everyone “a genius at their job”. Our main product is Agatha, an assistant that helps customer support agents answer cases more quickly and confidently by suggesting answers and triaging cases. We've raised over $10M in VC funding and were the winners of 2018 SF TechCrunch Disrupt Battlefield. I joined Forethought back in December 2018. We are a small 12 person startup, and have a lot of competitive programmers on our team, including me, y0105w49, fortune, and dojiboy9 (our CEO, who is also an ICPC World Finals Judge). I’m happy to answer any questions about working here in the comments below or through PM. We’re hiring! Please fill out this form if you are interested. ### Updates UPD 1 The scoring distribution will be 500-1000-1500-2250-2500-3250-3250-3750 UPD 2 Tutorial can be found here: https://codeforces.com/blog/entry/66639 UPD 3 Congratulations to the top 5! Read more » • • +408 • By Lewin, 2 months ago, , NAIPC is happening again on March 2nd (start time). Information about the contest can be found on this page. Information about registering can be found on here. You can register in teams of up to 3. The deadline for registration is February 28th. This contest will be hosted on Kattis again. A few hours later, it will be available as an open cup round as the Grand Prix of America (start time). Please participate in only one of them, and don't discuss problems here until after the open cup round has ended. You can see some past years' problems here: 2018, 2017 UPD 1: Registration is ending soon. UPD 2: Please don't discuss until after open cup is over. UPD 3: You can find test data and solutions here: http://serjudging.vanb.org/?p=1349 Read more » • • +145 • By Lewin, history, 5 months ago, , I recently added the div 1 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 (soon...). Feel free to discuss problems afterwards. Read more » • • +68 • By Lewin, history, 6 months ago, , Recently, I wrote about my experiences with problem writing. This was something I haven't really talked about, and I felt it was time to share. Feel free to leave comments or questions! Read more » • • +72 • By Lewin, history, 13 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). Read more » • • +47 • By Lewin, history, 13 months ago, , NAIPC is coming up on March 24th (start time here). More information about the contest can be found on this page. More information on how to register can be found on this page. You can register in teams of up to 3. This contest will be on Kattis. 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 1: The deadline to register your team is soon. UPD 2: Contests are over Read more » • • +49 • By Lewin, history, 14 months ago, , Police Patrol Alphabetic Subsequence Infinite Graph Game Stamp Stamp Stamp Increasing Sequence Yet Another Binary Matrix Read more » • • +81 • By Lewin, history, 14 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 Read more » • • +126 • By Lewin, history, 14 months ago, , Hi! Topcoder SRM 730 will happen soon. I'm the writer of this round. Hope to see you all participate! Read more » • • +140 • By Lewin, 16 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 Rainbow Roads New Year and Original Order New Year and Boolean Bridges Read more » Tutorial of Good Bye 2017 • • +336 • By Lewin, history, 16 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! Read more » • • +1310 • By Lewin, history, 17 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. Read more » • • +71 • By Lewin, history, 21 month(s) 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 Read more » • • +135 • By Lewin, history, 21 month(s) ago, , Didn't notice a post from cgy4ever. Topcoder SRM 718 will happen in ~4 hours. Read more » • • +83 • By Lewin, history, 22 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 :)

•
• +60
•

By Lewin, 23 months ago, ,
Fibonacci Frequency
Wildcard Words
Counter Complexity
Token Tree

•
• +80
•

By Lewin, history, 23 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

•
• +64
•

By Lewin, history, 2 years 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, 2 years 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, 2 years 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, 2 years 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, 2 years 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, 2 years 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, 2 years 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