March Long Behind the scenes

This month the number of proposals of problems with difficulty >= Medium has decreased. I encourage you to keep inventing cool problems!

Some comments about the problemset

NOTIME, GROUPS: Do what the problem says :slight_smile:

IRSTXOR: In the initial proposal the condition was A,B \lt 2 \cdot A \oplus B, somehow the tester and I assumed that all the numbers are of the same length. Fortunately one of the setters noticed the bug and we updated the definition.

SPACEARR : Nice game! The key is to find the conditions for the existence of valid permutations.

COLGLF4: At first glance it looks like an integer linear programming problem, a bit of algebra and casework analysis is needed. Did you notice the hidden name in the input section?

PAPARAZI : The proposal was very formal and understandable, however after the author added the story it became a bit confusing, it was like the mountains were horizontal! Now that I think about it again, maybe the intention was that the star moves horizontally? It took us more time to reformalize the statement, so it was delayed a bit. I think the problem is fine, however it probably was a bit straightforward for contestants familiar with convex hulls.

CONSADD: The proposed solution was to colour the cells of the matrix and then check an invariant, I noticed that the invariant is necessary but not sufficient. I thought the correct solution was to solve a system of equations and I didn’t go deeper. Um_nik found a nice and simple solution. Some hours before the contest, the tester found that some files didn’t satisfy the constraints, which caused a delay in the insertion of the problem.

MAXTOPO: Initially the setter asked only the lexicographically largest pair. I was afraid it could be very guessable, just try the center or centroid. The author added K=2 to make necessary a deeper understanding of how the number of topological sorts change on rerooting.

DENSEGRP : The problem was in the queue for some months. The statement is very natural, and there is some creativity in the construction of the graph. The idea is how to represent the graph with a segment structure. The preparation was very smooth, we had a short discussion about the possible subtasks.

QUERGAME (non-scorable in all divisions) : A notorious coincidence.

LCKDSAFE: The intended complexity is N \cdot log N. It is not too hard to get a N \log^2 N solution, so the author placed very high constraints and a time limit of 0.5s. To allow solutions from other languages we increased the time limit to 1s, as a consequence some suboptimal solutions got AC, however I still think 1s is good enough.

SUBPROB: My first (incorrect) solution was to construct a suffix array for prefixes/suffixes and then a range query data structure. The problem is reduced to a task on trees, the intended complexity is O(N log^2 N) however it is hard to generate strong test data, and at the end we let slower approaches in O(N log^3 N) to AC.

RWALKS: I like problems about random walks, brownian motion, markov chains, … However this problem is more about data structures rather than probability. My first idea was a N \cdot \sqrt Q \cdot log(N) by processing the queries in blocks of \sqrt Q. To distinguish it from the model solution in N \cdot log^2 N, we added one subtask with higher constraints.

CCNF: Is interesting when NP problems can be solved optimally in special cases. In RB2CNF I described a condition that allows us to optimally solve the max 2-SAT using flows. This time I tried to create a problem with clauses with more variables. The idea is to exploit some of the special properties of the graph, and perform a decomposition which is well known in graph theory but probably new to many sports programmers.

WIREL: The Tesla dream comes true! It is based on an idea I sent to Alexey last year, it was about constructing a tree on a plane to minimize the sum of distances of the leafs to a given set of points. Initially the constraints were higher, but then I reduced them to keep the checker simple. I tuned the length of the wires by drawing the segments and calculating the number of times that the wires can reach the extremes of the plane when they are arranged side by side. In the last long challenge we had some issues with the checker of the tie-break, so this time I decided to make the checker public, that prevents possible confusions about the scoring.


Could you please elaborate this approach?

it was really nice to include K=2 in MAXTOPO but more number of precisely 1<=k<=n would have been more nice

And how do you propose to sort the results (assuming you use rerooting)?

If you are asking about MAXTOPO, please see my post.

nice, but what about precision in C++?

Doesn’t python’s float have the same precision as the C++ double? I didn’t implement it in C++ but I’d guess it should work too. If N is in this range then the precision should be good enough.


I used ratios associated with each k to identify how big or small it is with respect to the initially considered root answer.
You can always see my submission for better understanding

1 Like