Hi Codeforces!

The 49th ICPC World Finals in Baku are happening tomorrow! Before then I'll be holding the last scheduled Alumni Event at September 3 at 19:30.

I'll be in the hotel Chill Zone to talk and hang out! I have some mini-lectures prepared and I ready to yap about any of my favorite topics:

• Top Trees
• SPQR Trees
• Dirichlet Series Convolution
• C++
• AI
• and more!

You can also ask me about anything! Come hang out before the contest and maybe learn something uesless!

The complete alumni schedule can be found at https://worldfinals.icpc.global/alumni.html.

For everyone not in Baku, you can follow all the livestreams at live.icpc.global or on YouTube, I'll be commentating on the English stream. You can also register for the mirror contest here.

It looks like some of Deltix Round Spring 2021 got rejudged to include uphacks, including causing my D to go from passing to failing, and also affecting the placing and rating.

You can see in the announcement that I originally got 5th, but the scoreboard now shows 10th, and my submission 117918101 shows an extra 10 tests beyond the 127 that other submissions have, like 117881477.

It seems like this bug is several months old: galen_colin posted about it at https://mirror.codeforces.com/blog/entry/88000, and MikeMirzayanov didn't fix that contest and said he'd "try to avoid it in the future". This bug is totally unacceptable, it significantly affected results a full 2 days after the contest ended; imagine if it affected prize distribution. I have no idea when these hacks were added, but it's definitely not akin to in-contest hacking. MikeMirzayanov needs to either fix this properly, or disable uphacks until after standings are finalized. It's already happened twice, and it definitely cannot happen a third time.

I had a different approach to H that results in very short, but incorrect code (114044595, 114044982). I also have a few versions which I don't know how to hack (114142853, 114141339, 114141392). Can anyone hack these or prove they're correct?

The main idea is to use strong LP duality: the problem is unsatisfiable if and only if there is some linear combination of the input constraints such that all variables cancel and the constants give a contradiction (e.g. $$$0 \le -1$$$). We can try to simplify this by only checking all "extremal" feasible linear combinations, i.e. linear combinations on the convex hull of all linear combinations whose variables completely cancel.

Here, I came up with the (false) hypothesis that any such extremal linear combination must include 2 "neighboring" constraints which we can treat as a relaxation, e.g. we use both $$$y_{i-1}^+$$$ and $$$z_{i}^+$$$; these can be "merged" into a (possibly tighter) constraint on $$$y_{i}^+$$$ which we will use instead. This is not quite true, and the counterexample can be seen in https://mirror.codeforces.com/contest/1517/hacks/731593/test.

Assuming this hypothesis, I made another assumption that, similar to out-of-order Floyd-Warshall, we may be able to simply do all relaxations and loop up to either $$$O(1)$$$ or $$$O(\log n)$$$ times in order to find the cycle. I don't have a proof, but it feels plausible (after the $$$k$$$th iteration, our relaxations must include all paths with at most $$$2^k$$$ zig-zags or something?).

Now, you might've noticed that 114044982 fails with TLE instead of WA; if it were allowed to run for long enough, it would actually print the correct answer. This is because my hypothesis is false for extremal linear combinations, but I think it's true that there must be some negative linear combination which can be attained via these relaxations. This is because we can take the extremal negative cycle, multiply it by a large number, and add any positive cycle including the desired neighbors. Thus, it seems like my code is guaranteed to finish in $$$O(N * MAXVALUE)$$$ or so.

Now for the challenge: I now have a new hypothesis: if, after running for some number of iterations, the relaxations have not stabilized, then there must be a negative cycle and we can just print "NO". That's the basis for my 3 new submissions: 114142853 (60 loops), 114141339 (1000 loops), 114141392 ($$$N$$$ loops). Can anyone hack these or prove them correct?

Hey guys!

I'll be streaming this Saturday 9/19 at 2pm Pacific Time (UTC-7). I'll probably recap and upsolve (maybe virtual) IOI 2020 day 2!

I also uploaded a stream schedule widget to my about page at https://www.twitch.tv/ecnerwala/about so you can see my schedule. In the future, I'll try to regularly stream round this time most weekends. Subscribe to get notified when I go live!

Finally, comment here and let me know if there's anything in particular you'd like to see me do on stream or in a video, whether it's a particular contest or something else! I'll take a look at the top few different ideas and try to do some of them!

Update: I'll try to regularly stream on Sundays around 2pm Pacific Time. Check out my about page for an updated schedule!

I'll be competing against tmwilliamlin168 in the Lockout Championship today at 9/14 02:30 UTC, and I'll be livestreaming the match at https://twitch.tv/ecnerwala. See you there!

You can find the bracket at https://challonge.com/2020_lockout_championship_open.

I'll be streaming this Saturday 9/12 at 21:00 UTC at https://twitch.tv/ecnerwala (one hour after Facebook HackerCup Round 3). I'll do a FBHC Round 3 recap, and then I'll upsolve some OI problems (maybe some POI) and just chill with chat. Come join the chat, and follow me if you'd like to get notified when I go live!

Hey all!

I'll be doing 2 streams this weekend at https://twitch.tv/ecnerwala.

• Saturday, 9/5 at 18:00 UTC for a TCO Round 4 recap and a SNSS Round 3 virtual livestream (and watching tourist's stream).
• Sunday, 9/6 at 16:35 UTC for a CF Round 668 recap and a CF Round 667 (Div 3) virtual upsolve.

Follow my channel to be notified!

Hey all!

I'll be livestreaming at https://twitch.tv/ecnerwala for a couple of hours on Saturday 8/29 at 20:00 UTC right after Facebook HackerCup Round 2. I'll do some post-contest review of HackerCup (maybe with guests!), and then I'll do some live upsolving (probably HackerCup, Educational Round 94, or CEOI, other suggestions welcome). Follow my Twitch to be notified, and come check it out!

Hey guys!

I'm streaming at https://twitch.tv/ecnerwala right now, watching a recording of myself solving SNSS 2020 Round 2. Come hang out and discuss the contest! Follow me on twitch to get notified!

I've uploaded a lot of my recent contest screencasts to my YouTube channel, including HackerCup Round 1, Global Round 10, and Google Kickstart Round E. I'd love for you guys to take a look!

I've also received a bunch of questions about my setup/templates, so I gave a quick showcase in my newest Kickstart Round E video, as well as live commentary through the whole contest. Please check it out, and subscribe if you'd like to see more! Also, let me know in the comments if there's anything else you'd like to see!

Hi everyone!

code_warrior recently asked "How is ecnerwala?" I'm here to answer that question and others you may have! I'll check this regularly for the next couple of days and try to respond when I get a chance. Ask me anything!

To code_warrior: I'm doing good. Quarantine is still ongoing, so I'm spending most of my time at home with my family, coding both for work and for fun. How about you?

EDIT: There have been a lot of repeat questions, and I've tried to answer each question at least once. I've given a bunch of general advice about practicing and training, and I don't think I can say too much about how you specifically should practice, so I might not answer all of those questions. In general, practice things that you see in contest that are medium or hard but not impossible for you.

UPDATE: Thank you guys for all your questions! I think I'm done answering questions for now, hope to compete with you guys more!

UPDATE 2: I finally followed through and posted a bunch of screencasts to my YouTube channel, check them out if you're interested! I'll look into a way to post the code/key-captures, and I hope to publish some with commentary soon!

We'll be hosting another lockout stream on Sunday 6/14 at 17:00 UTC featuring tourist, Egor, xiaowuc1, and stevenkplus on twitch.tv/ecnerwala! Hope to see you guys there!

Lockout is a head-to-head fast-paced programming contest race format where only the first person to solve each problem gets the points for it! You can read more about the format at https://mirror.codeforces.com/blog/entry/72557. We'll be competing on some more ABC's, come watch and cheer on the contestants!

We're going to be running a Lockout stream on Sunday 5/10 at 17:00 UTC featuring tourist, ksun48, xiaowuc1, and more! Tune into https://twitch.tv/ecnerwala and come check it out!

Lockout is a fast-paced, fun-to-watch 1v1 programming contest format where only the first person to solve each problem gets the points for it! You can find out more about the lockout format at https://mirror.codeforces.com/blog/entry/72557 and watch our video from last stream at https://www.youtube.com/watch?v=Dk-nWqwyE8g. We'll be competing on the Div. 4 round and some recent ABC's. It'll be exciting, so come watch and hang out in chat!

Update: The video is posted on YouTube at https://youtu.be/bBNIIg8REUU.

Congratulations to tourist for winning Grand Finals of Lockout 0 over Um_nik with a score of 800-300! The round had 5 problems, but with a special 1v1 twist: only the first person to solve each problem got points for it! After the first 10 minutes of the match, the 3 easiest problems were all solved and the contestants were tied at 300 points, so both contestants just needed to race to finish the 500 point problem first. With some impressive coding and frenzied debugging, tourist managed to eke out the win! The final scoreboard was:

Lockout 0 Grand Finals (Video)

Also congratulations to all contestants in the Lockout 0 tournament! The full bracket is at https://challonge.com/lockout0. The final standings are:

1. tourist
2. Um_nik
3. hos.lyric
4. Petr

On stream, we also ran two more 2v2 team-Lockout exhibition matches! These matches used 9 problems with distribution 100 — 100 — 100 — 200 — 200 — 200 — 300 — 300 — 400, so 1000 points were needed to win.

• Match 1: tourist+Um_nik vs scott_wu+ecnerwala (Video): Congrats scott_wu+ecnerwala for winning 1000-400!

• Match 2: tourist+Um_nik vs neal+ecnerwala (Video): Congrats tourist+Um_nik for winning 1200-400!

We got to see a few different strategies in these matches: some teams opted to solve several easy problems before moving onto the hard ones, while others just solved two easy problems before jumping right into the hardest 400 point problem. What did you think worked best?

Finally, thank you all for tuning into the stream! Our total viewership was over 3000 people! You can find the full VOD on YouTube at https://youtu.be/Dk-nWqwyE8g.

We'd love your feedback on this new contest experience! Do you think the 1v1 or 2v2 format is more exciting? How could we make the spectating experience better? Are you excited to play yourself? Please let us know in the comments!

635A - Orchestra

We can iterate over each possible rectangle and count the number of violists enclosed. This can be optimized with rectangular prefix sums, though the simple brute force is sufficient for this problem.

Runtime: O(n⁶)

634A - Island Puzzle

Notice that, as we move the empty pedestal around the circle, we cyclically permute the statues (and the empty pedestal can be anywhere). Thus, we can reach one state from another if and only if, after removing the empty pedestal, they are cyclic shifts of each other. The starting and ending configurations are permutations, so we can check this in linear time.

Runtime: O(n)

627A - XOR Equation

For any two integers a and b, we have , where is the xor and a&b is the bitwise AND. This is because is non-carrying binary addition. Thus, we can find a&b = (s - x) / 2 (if this is not an integer, there are no solutions).

Now, for each bit, we have 4 cases: , and . If , then a_i = b_i, so we have one possibility: a_i = b_i = a_i&b_i. If , then we must have a_i&b_i = 0 (otherwise we print 0), and we have two choices: a_i = 1 and b_i = 0 or vice versa. Thus, we can return 2ⁿ, where n is the number of one-bits in x. (Remember to subtract 2 for the cases a = 0 or b = 0 if necessary.)

Runtime:

627B - Factory Repairs

Using two binary-indexed trees, we can maintain the prefix and suffix sums of the amounts we can produce with maximum production rates of B and A, respectively. Then we can just query the binary-indexed trees to find the maximum possible production given the start and end of the repairs.

Runtime: .

627C - Package Delivery

We solve this with a greedy algorithm: for each gas station, we fill our tank to min(n, d) liters of gasoline, where d is the distance to the next gas station with cheaper (or equal) gas. This is optimal, as, if we can make it to a station with cheaper gas without buying expensive gas, we should (and fill up our tank at the cheaper station). Otherwise, all stations within range n are more expensive, so we should buy as much gas as possible right now.

Alternatively, if we say that we always “use” the gasoline we buy in the order we buy it, then the gasoline used in the ith unit must have been purchased within the last n units. Then we can greedily use the cheapest gas within the last n miles. We can maintain this in a queue with range-min-query, which gives us linear runtime (after sorting).

Runtime:

627D - Preorder Test

We binary search on the answer, so we need to answer queries of the following form: is the a depth-first search traversal such that the first k vertices all have value at least v? We can answer this with a greedy tree-DP: for each subtree, we compute whether or not all its vertices have value at least v, and if not, the longest possible prefix with all values at least v. Then, our transition function can be greedy: the maximum possible prefix with all values at least v is the sum of the sizes of all child subtrees which are all at least v plus the largest prefix of all child subtrees.

Runtime:

627E - Orchestra

We can think of a rectangle in the grid as a pair of an (xlo, xhi) interval and a (ylo, yhi) interval. Suppose we fix the x-interval and want to determine the number of corresponding y intervals which create rectangles containing at least k violists. Given a sorted list of the y-coordinates of all violists in the range, this is simple: m violists split the y-coordinates into m + 1 (possibly empty) intervals that span all the columns, and the number of total intervals that work is simply the number of pairs of points that are at least k intervals apart.

As we sweep over the xhi coordinate and maintain the list of violists, we want to insert each violist into a sorted list and look at its k nearest neighbors to determine the change in number of intervals. Inserting violists into a sorted list, however, is difficult to do in constant time. Instead, we sweep in reverse. Start with xhi = r and a linked list containing all the desired violists; decrementing xhi is now a simple process of removing the necessary elements from a linked list and examining their neighbors as we do so.

Runtime: O(r²k + rnk)

627F - Island Puzzle

First, if we never move the empty pedestal through any cycle, then moving the empty pedestal to and from any given position cannot change the location of the statues, as performing a move in the opposite direction as the previous undoes the previous move.

Thus, in our graph with one cycle, we can only do the following two operations: move the empty pedestal from one location to another (without loss of generality, only using the original tree), and cyclically permute the elements along the one cycle (except the element closest to the root).

Now, to check satisfiability, we can greedily first move the empty pedestal from its start position to its end position -- since this procedure can be undone, it will never change the satisfiability of the rearrangement. Then, we only have to check that all changed elements lie on a possible cycle. This uniquely determines the edge to be added.

To compute the minimum number of moves, we compute the minimum moves to move the empty pedestal from the start to the cycle, the minimum moves to permute the cycle as desired, and the minimum moves from the cycle to the end point.

Runtime: O(n)

626A - Robot Sequence

We can simulate Calvin’s path on each substring, and check if he returns to the origin.

Runtime: O(n³)

626B - Cards

Note that if we have exactly one card of each color, we can always make all three options (by symmetry). Thus, if we have at least one of each color, or at least two of each of two colors, we can make all three options. The remaining cases are: if we only have one color, that’s the only possible final card; if we have one of each of two colors, we can only make the third color; if we have at least two of one color and exactly one of a second, we can only make the second or third color (e.g. sample 2).

Runtime: O(1)

626C - Block Towers

There are a variety of ways to do this problem. Here is one way: if the answer is X, there must be at least n multiples of 2 below X, at least m multiples of 3 below X, and at least n + m multiples of 2 or 3 below X. These conditions are actually sufficient, so we need to find the smallest X such that , , and . We can do this with a linear search, or with an explicit formula.

Runtime: O(1)

626D - Jerry's Protest

We do this algorithm in two phases: first, we compute the probability distribution of the difference between the winner and loser of each round. This takes O(n²) time. Then, we can iterate over the 2 differences which Andrew wins by and compute the probability that Jerry has a greater total using with suffix sums.

Runtime: O(n² + a_max²)

626E - Simple Skewness

We can show that any subset with maximal simple skewness should have odd size (otherwise we drop the larger middle element: this decreases the median by more than it decreases the mean, assuming the mean is larger than the median).

Let’s fix the median at x_i (in the sorted list), and set the size of the set to 2j + 1. We’d like to maximize the mean, so we can greedily choose the largest j elements below the median and the largest j elements above the median: x_i - j, ..., x_i - 1 and x_{n - j + 1}, ..., x_n.

Now, notice that by increasing j by 1, we add in the elements x_{i - j - 1} and x_n - j, which decrease as j increases. Thus, for a fixed i, the overall mean is bitonic in j (it increases then decreases), so we can binary search on the marginal utility to find the optimum.

Runtime:

626F - Group Projects

This is a dynamic programming problem. Notice that the total imbalance of the groups only depends on which students are the maximum in each group and which are the minimum in each group. We thus can think of groups as intervals bounded by the minimum and maximum student. Moreover, the total imbalance is the sum over all unit ranges of the number of intervals covering that range. We can use this formula to do our DP.

If we sort the students in increasing size, DP state is as follows: the number of students processed so far, the number of g groups which are currently “open” (have a minimum but no maximum), and the total imbalance k so far. For each student, we first add the appropriate value to the total imbalance (g times the distance to the previous student), and then either put the student in his own group (doesn’t change g), start a new group (increment g), add the student to one of the g groups (doesn’t change g), or close one of the g groups (decrement g).

Runtime: O(n²k)

626G - Raffles

First, note that the marginal utility of each additional ticket in a single raffle is decreasing. Thus, to solve the initial state, we can use a heap data structure to store the optimal raffles.

Now, after each update, we can show that the distribution should not change by much. In particular, after one ticket is added to a raffle, Johnny should either remove one ticket from that raffle and place it elsewhere, not change anything, or, if the raffle was already full, put one more ticket in to keep it full. Similarly, after a ticket is removed, Johnny should either do nothing, remove one ticket to stay under the maximum, or add one ticket. (The proofs are fairly simple and involve looking at the “cutoff” marginal utility of Johnny’s tickets.) All of these operations can be performed using two heaps storing the optimal ticket to add and the optimal ticket to remove.

Runtime: