A stack overflow month

One of the hardest problems of March Long 20 featured the following problem:

Given an undirected graph, find an acyclic orientation of its edges such that if there exists edges x \rightarrow y and x \rightarrow z, then there exists y \rightarrow z or z \rightarrow y.

Such orientation exists, if and only if the graph is chordal. At first I forgot the acyclic orientation, in this case pseudoforests can also satisfy the condition.  Some problems that are in NP for a general graph can be solved in polynomial time for chordals.

Some correct solutions were getting an incorrect veredict, I read the judge many times and I couldn’t find the bug, I even tested the judge locally. It turns out that the stack size of spoj is very reduced, and the program that checks if a solution is correct crashed because an stack overflow (because of the recursive dfs). Kudos to the tester for noticing that!

I setted the tie-break problem, is about gathering all points in a plane by choosing a polygon and moving each point towards to its adjacent point with integer coordinates.

The problem was reviewed by our even-admin Alexey, his approach is as follows:

* Try to only use polygons that merge all M points into one, i.e. all sides should have coprime x and y components;
* At each step, find the convex hull and select the largest subset of its vertices that can be merged together, using DP;

 

A micro-improvement month

The tie-break of February Challenge is RAISINS:

Given a set of 2D points, minimise the area of the convex hull by partitioning the plane with equal separated horizontal and vertical lines and applying cyclic shift rights and shift ups to the rows and columns of the resulting matrix.

I got the idea of sorting by shift rights and shift-ups while trying to invent a new version of rubik’s cube but on 2D. Can you describe all the possible states reachable from the initial permutation?

It turns out that using the area of the convex hull as score function was not precise, because even when the area can be decreased, the proportion relative to the initial area is very small. That caused some (undeserved?) points to trivial solutions.

One general idea is to find the convex hull of each region and try to choose the best regions that should go to the perimeter.  @carre shared his approach in discuss

A two challenge month

January Long featured a problem that was solved optimally by at most one contestant (read the statement at CHEFARMY). I came up with the problem while studying antimatroids, I was affraid that it could be too hard so I setted the problem in challenge format with score relative to the best solution submitted by contestants i.e the same format as the tie-break problem.

The intended (optimal) solution is as follows

– The relation X is subordinate of Y is a POSET
– Note that every day we chose an antichain in that POSET
– The angriness function is submodular, that means that
f(A)+f(B) \geq f(A \cup B) + f(A \cap B) , where f(X) is the number of angry generals if soldiers from set X are called
– The optimization problem is
– minimise \sum f(X) \cdot R(X), for every antichain X, R(X) is how much each soldier is paid
– such that \sum R(X), for each antichain X containing x is equal to S_x, i.e soldier x should be paid S_x
– The hard part is that there is an exponential number of antichains, however only a linear number of antichains are required. For special kind of POSETS this optimization problem can be solved using the Faigle-Kern algorithm which involves greedily finding a special topological sort and solving a system of linear equations.
– The same algorithm works for a general POSET (not only trees) if the function f satisfy other properties.

The (real) approximate problem (ANTHILL) is about constructing a graph by squaring subgraphs and removing edges. The problem of finding the square root of a graph is unsolved, however there are solutions for special kinds of graphs like chordals and powers of trees. Contestants used some heuristics like finding cliques and generating the clique by squaring a star.

Because of the “two” approximate problems this time the winner didn’t got a perfect 800 points!

I also setted the cakewalk problem (BRKBKS). Since the constraints are very small, the first idea that comes to mind is to brute force all possibilities. However it turns out that reversals are not required!

Congrats to the winners!

1. cheng2014

2. tmwilliamlin (He moved to the top of the scoreboard in the last day!)

3. white2302

4. yash_chandnani (Best of India)

5. wrong_answer_1

6. zhouyuyang

A triangulation month

The tie-break of November Long was about triangulations. I came up with the problem while watching someone play with a Rubik cube.

Given a triangulation over a set of coloured points, you can flip edges and change the colour of vertices to minimise the number of triangles that have at least two vertices of the same colour.

Most participants started by using only colour change operations, and then introduced some heuristics to take advantage of flips

One idea is to minimise the average vertex degree with flips, test generation involved Delaunay Triangulations because I had the feeling that it could be easier to colour. Moving from one triangulation to another using the minimum number of flips is an open problem, however it is a known fact that the diameter of the triangulation graph is logarithmic.

This month we had one notorious coincidence, the problem SIMGAM was already in a CodeForces contest of >5 years ago. The problem is very natural, so I think the setter reinvented the problem.
SIMGAM was planned to be the second problem in div1, however it was getting a lot of ACs (more than expected). I decided to remove SIMGAM from the contest and use one of the non-scorable problems. Fortunately we had another (almost) prepared problem for div2 (CAMC). I think the decision was correct because many div1 coders were struggling in problem WEIRDO.

I expected HRDSEQ to get more ACs than SC31, because the former is an implementation only problem while the last requires one observation.

The last three problems are very interesting:

PBOXES is a string problem that can be modeled with flows and simulated with segment trees!

MDSWIN is a nice tweak of FWHT.

DDART required a non-trivial test case generation, it can be solved with convex hull trick on curves instead of lines, but it also can be modeled more naturally with inversive geometry.

Hindustan University ICPC Multi Provincial Contest

Hindustan University ICPC Multi Provincial Contest 2019 finished a couple of hours ago.

Initially it was planned to have 5 problems, however since it is a team contest I suggested that a more balanced contest should have 7 problems. Unfortunately since there was few registrants, we were told that is better to use only 4 of the prepared problems.

No contestant asked for clarifications, it seems I’m a great statement verifier!

The problems were simple, but required some interesting observations. I prepared the easiest and the hardest problem.

Dinosaurs Football

Place the k+1 tallest dinosaurs in increasing order followed by the remaining dinosaurs

n-k, n-k+1, … n, 1, 2, 3, …, n-k-1
Tweedle Graph

Let’s say Dee placed the token on vertex u and Dum moved the token to an arbitrary node v.

It turns out that Dum always winn, because Dee will always make a move that goes out of the vertices u,v, and Dum can always make the token return to u or v. The following picture depicts one possible game

TWEGRAPH
Does this graph have a special name? if not I will name it Lotus Graph 🙂 and we’ll call vertices (u,v) the Lotus root.

It turns out that this is the only way in which players must play if Dum wants to winn quickly and Dee wants to make the game longer. Can you prove it?

The weight of a Lotus with root (u,v) is given by B[u]*(S – B[u]) + B[v]*(S – B[v]) – B[u]*B[v], where S is the sum of the weights of all vertices. I overkilled the problem and added the vertices from one to one using convex hull trick to find the maximum. Can you spot the easier solution?

Congrats to the winners!

1. Minimum Spanking Tree (00:47:42)
2. Fast_Code_Transform (01:37:59)
3. IC3 (02:03:52)

 

A mathy month?

CodeChef September Long Challenge started a couple of days ago. There is still time to participate and reach the top of the scoreboard.

I choosed the best odd-indexed problems submitted on August and the first half of September. The problems were prepared by:

namanbansal013 , kevinmathew , Kerim.K ,  hackslash_123 ,  KharYusuf ,  KMAASZRAA  FarFromRed, Harendra Chhekur, theabd123,  iscsi.

Some contestants found the problems very mathy. I agree that some math is required, but to solve the problems you also need an algorithmic thinking.

 

A Bioinformatics Month

The challenge problem of CodeChef August Long was inspired in bioinformatics.

Transform a bacteria genome using mutations and reversals to produce some proteins.

The problem has some applications in phylogenetics, the distance between two species can be estimated by the minimum number of reversals to transform one genome into another.

The trivial solution uses only mutations, but gets almost zero score. I gave some general ideas on discuss . Also @wjli, one of the top scorers shared his approach there