Huh, unfortunate. In Poland we have exams at the end of January and beginning of February, so beginning of every year is pretty calm unless you have close deadlines for some big programming projects. Or you can be too old for exams like me xd. However, on the bright side, Prime Contest was extended by ~2 weeks as well :P.

That's basically the same way I and mnbvmar solved this as well with a slight difference that we rebuild a subtree of some centroid when it turns out to be highly unbalanced which means some of its son's subtrees is bigger than 3/4 of size of this vertex subtree. Same complexity though, obviously.

The problem is that there is some weird weighted version with dijkstra instead of bfs, which as I know doesn't actually work in general case? And I have no understanding why does it work in this problem.

I am sorry but this is not "just matroid intersection, what's the problem?" for me :). Care to elaborate more on that? Is there really no parametric search involved (adding +c to green edges for some constant c) at any point? Is there any linear algebra/Gauss elimination involved (since linear represantations are often used when dealing with matroids)?

Yeah, it was kinda nightmarish to code, I used segment tree with 13 attributes in each node, but at the same time it was pretty easy to come up with a solution and it's New Year Prime contest — you can't simply turn away problem since it is tedious to code because otherwise you are left with 2 problems to solve xD. By the way since I participate (this was my fourth time), all problems were solved, so nobody solving some problem would be kinda huge. During Prime contest I have much more determination and free time than I ever have on any camp as well ;p.

Btw I really liked problem 3, but I think when posing it on PTZ contest you could have shown at least some mercy and not require restoring answer :p. Btw not sure if everybody realizes, but perfect elimination order can be quite simply computed in using triangle counting. Never got to learn LexBFS, so I don't now if it actually turns out to be significantly simpler, but at least it is possible to come up with it by yourself and for lexbfs I guess it is not?

I don't think that 2 is that difficult to code. Of course, I wouldn't try to write it during the contest, but it's not even close to 97 or 89. If you think about it carefully, the solution will not look that scary. I stored 2 treaps: one for segments of time, during which the guards are to the right of current edge and the other for segments of time when they are to the left. When we go from one edge to the next, we delete some segments, add some new ones and shrink all existing ones(in the second treap we extend them instead of shrinking but it's the same). Shrinking segment [l, r] by x transforms it into segment [l + x, r - x]. It is easy to do it with lazy propagation. We also need to answer the query: what's the leftest segment with length at least t? It is also easily done with maintaining maximal length of segment in the subtree. Here's the code. It's pretty long, but all parts are easy by themselves, there's just a lot to write.

A rough idea of my approach to 43: as above, we notice that placing bishops on each chessboard color is equivalent to placing rooks on a Young diagram. If such a diagram was triangular:

#####
####
###
##
#

then the number of ways to place k rooks would be described by Stirling numbers of the second kind . We would need to compute a generating function of the form . Such a generating function exists, and is of the form e^- x·(some pretty generating function).

In our case, the diagram is a bit different, something like this:

######
######
####
####
##
##

However, it still turns out that the equivalent generating function is still of the form e^- x·(something pretty). I'm omitting quite a few technical issues here but each term of that "pretty" generating function can be computed independently, and done easily in time. Therefore, we can compute the "whole" generating function in time. AC'd in 0.4s/3s.

Btw what I find surprising about this problem is that it is symmetrical in a way that answer stays the same if we swap trees and swap c1 and c2, but solution breaks this symmetry.

Another approach: dp[l1][r1][l2][r2]: match [l1, r1] in tree1 and [l2, r2] in tree2. Contract: trans from dp[l1+1][r1][l2][r2] or dp[l1][r1-1][l2][r2] Otherwise, we can trans from either l2 or r2. Choose the one with smaller subtree size. O(n^2mlog m).

I wrote an editorial. Hope it explains better.

For problem 37, what you describe is similar to my solution, and yeah, I had backtracking there, instead of the "restart from scratch" item. However, in a contest, under time pressure, throwing in a simple "restart from scratch" heuristic is of course more likely than writing a full backtracking implementation on top of a load of existing code.

As to why include such problem in an ICPC problemset, there are several reasons.

1. Simple: it's a "true story" problem, I had my daughter Dasha solve a real world version, smaller and easier of course. I then became genuinely interested in how to do it in the general case.

2. Most contestants just can't solve some problems completely in their heads, and require tools. Usually, these tools are pen and paper. In a team contest, discussing with a teammate is a powerful tool. Sometimes a computer is used in the solving process to write a simple program, produce some outputs (e.g., Grundy numbers, or some other table for small inputs), print and stare at them until an idea comes to mind. I just happen to like the problems where the most helpful tool is the computer itself, when you have to try to implement various hypotheses just to see what works and what doesn't. In a team contest where computer time is scarce, this calls for interesting decisions and tradeoffs.

3. In the particular contest, I had 31 and 37 as hard problems, so that no team was expected to solve everything, but the top teams likely had a choice of what to solve. Unfortunately, the difficulty was a bit overwhelming, so both problems ended up here (and being solved in upsolving).

"About 37: The answer is "this is a problem by Gassa". I don't see a point either." — that's your daily Um_nik at its best xD

And regarding 29 and its presence. I thought that in previous years problems from Ptz were not included at all (sure about Ptz 2016 and Ptz 2017 where I was), only OpenCup GPs or some regional stages were considered I believe. And in this year there were a lot of them. However I may be a little off, I think I recall seeing some problems (beautiful one about binary search in log n + 0.1 instead of ceiling(log n) and some tedious path selection which I coded for 7 hours straight) which were from some other camp than Ptz, I believe. Rules for choosing problems are not clear to me, I guess it just depends on snark's mood. And yeah, I think this was the easiest problem next to 11, it was rather straightforward to me how to solve it and it wasn't that hard to code it as well, however I fell into a few traps when coding it (graph disconnecting after reductions where more than one cycle could have appeared etc), so in the end it took me much more time than I expected.

Regarding tutorial on matroids, I think this is a good source: http://parameterized-algorithms.mimuw.edu.pl/parameterized-algorithms.pdf It is a really great book with a lots of awesome and accessible stuff. Matroids are in Chapter 12. However it wasn't sufficient to me to solve 19 xD.

OK, I will try to write a tutorial when I will have free time.

Intended solution is actually O(n) and supposes building a symmetric compacted suffix automaton.

Brief sketch of the solution:

Both suffix automaton and suffix tree imply some equivalence relations by their vertices.

Namely, consider vertex v in suffix tree and all strings in suffix tree which end on the edge from v to its parent (including string for v and excluding string for the parent of v). Let's define left context [x]_L of string x as largest string xα such that x always come with α when it occurs in the string. Then all strings on the edge of v have same left context, which is exactly string which ends in v.

Similar is true for suffix automaton, but with right context [x]_R, which is largest string β x such that x is always preceded with β when it occurs in the string. So, there is one to one correspondence between right context and nodes of suffix automaton for given string.

Now let's define context [x] = [[x]_L]_R = [[x]_R]_L which is largest string β xα such that x is always preceded by β and succeeded by α when it occurs in the string. Turns out that there is one to one correspondence between context of the string and nodes in compacted suffix automaton, which is what we get if get rid of states with out-degree 1 in regular suffix automaton, or if we minimize the suffix tree considering its edges to be characters of some alphabet Σ.

Now those contexts have some peculiar properties.

1. Contexts of reversed string are reversed contexts of initial string. It allows you to build the compacted automaton for reversed string on the same set of vertices as compacted automaton for direct string.
2. Consider for all contexts [x] smallest prefix α of [x] such that [α] = [x]. It may be easily proven that sum of |x| - |α| (i.e. length of largest suffix which you may delete and still stay in same context) over all contexts is linear of the length of string. Same for suffixes. This is due to contexts forming sub-trie in suffix automaton.
3. x always has exactly one occurrence in [x], thus if you know answer for all suffixes and prefixes of [x] which are still in [x], you may get answer for x by multiplying answer for corresponding suffix or prefix with ( - 1)^{min(lpos, rpos)} where lpos and rpos are amount of characters preceding and succeeding x in [x]. And to know all answers for all [x] you may simply brute-force which characters are you going to write to its front and back, so you will reduce it to the same case of getting answer for α [x]β from prefixes and suffixes of [α[x]β].
4. If you run depth-first search over vertices of compacted automaton, it will work in O(n) and is equal to simply traversing suffix tree of string s. This is crucial in restoring k-th lexicographical answer in my solution.

Given all that it's possible to construct the final solution, but there are lot of technicalities...

P.S. Maybe I will write some comprehensive article on compacted automatons one day, they're pretty cool :)

for suffix automaton, but with right context [x]R, which is largest string β x such that x is always preceded with β when it occurs in the string. So, does it mean β can be empty ?

Okay, if there is a good selection of data structures allowing us to achieve constant time complexity per coin removal/reinsertion, I'd love to know it. The best I could achieve was per operation (with a simple segment tree) which actually behaved way worse than even slightly optimized O(n) XD. I feel intuitively why this happened, but it was strange nevertheless.

Either way, I think that requiring the participants to write a bunch of ugly stuff (which I personally don't mind, and maybe even like in some masochistic way) and expecting them to strive for the best possible time complexity sounds quite bad.

My rule of the thumb is: if you have some nice algorithmic tricks in mind, you should probably drop all/majority of messy parts of the problem (and make it more accessible to contestants). If you simply want us to simulate a complex game, don't push for high constraints.