 # DFMTRX Video Solution

Bro what’s the approach for 100 in ARMYOFME??

In short, my solution uses a persistent lazy segment tree which can support a bunch of different operations to solve the problem. I’m not sure this is the only solution though.

4 Likes

Is there video Editorial on ARMYOFME??

Part 1:

Part 2:

8 Likes

I used the following approach:

One element can be filled in diagonal (That will cover N cells of the matrix). If we want to fill rest N^2 - N cells, using 2N - 2 remaining elements, we need (N^2-N) / (2N-2) = N/2 cells for each element.

This way we can observe that the solution is possible for even numbers only. Each of remaining 2*N-2 numbers needs a cell which covers 2 distinctly labelled row and column.

Hence I used the following pattern to fill first N-1 out of 2*N-2 numbers:

lets say N=10

then the positions will be:
(9, 0) (1, 8) (2, 7) (3, 6) (4, 5)

(9, 1) (2, 0) (3, 8) (4, 7) (5, 6)

(9, 2) (3, 1) (4, 0) (5, 8) (6, 7)

(9, 3) (4, 2) (5, 1) (6, 0) (7, 8)

(9, 4) (5, 3) (6, 2) (7, 1) (8, 0)

(9, 5) (6, 4) (7, 3) (8, 2) (0, 1)

(9, 6) (7, 5) (8, 4) (0, 3) (1, 2)

(9, 7) (8, 6) (0, 5) (1, 4) (2, 3)

(9, 8) (0, 7) (1, 6) (2, 5) (3, 4)

There are total N-1 rows with N/2 columns. So I filled N-1 numbers on the N/2 positions written in each row.
One can easily generate this pattern through simple observation. We can see that each position is unique and union of each row consists of numbers 0,1,…N-1

Now rest of the N-1 elements can be filled in the diagonally mirror positions of the above mentioned positions.

So we filled 1 element in diagonal + N-1 in above positions + rest N-1 in mirror positions = 2*N - 1 elements

3 Likes

stay tuned

2 Likes

What I did was:

1. First, you concentrate on the gaps between elements of the permutation instead of the elements themselves
2. Then you calculate, for each of those gaps, the smallest set of gaps that contains it and follows the requirements of the problem.
3. Using a persistent segtree, you use the previous point together with some of the properties you deduce from the construction to compute the answer.

For 2), we first compute a ‘necessary range’ for each gap. Given the gap between elements `i` and `i+1`, you find the first and last (`l` and `r`) element in the permutation array `per` such that `per[l]` and `per[r]` are between `per[i]` and `per[i+1]`. We say `required_range[i] = make_pair(l, r)`. Its easy to see that in order for an interval to be valid, for each gap `i` in the interval, all the gaps in the range `required_range[i]` must also be present.

So now we want to “closure” required range. That is, given a gap `i`, take the required range, and then take the union of the required ranges of all of the elements in the required range, and so forth until the range you’re working with doesn’t change anymore.

To do that, what I did was make a ‘segment tree graph’: a directed graph with the shape of a segment tree, where the leaves correspond to de gaps `i = 0...n-2`. For each gap, you would want to connect the i’th leaf with all leaves in the range `[l,r]`, but unfortunately that’s quadratic, so we use the segment tree and connect the leaf with some inner nodes of the segment tree that reach the whole `[l,r]` range.

Then, we would want the transitive closure of the graph, but that’s expensive, so we take advantage of the fact that we know the reachable sub-graph of a leaf is always a range of leafs, so we do a dp over the strongly connected components of the graph to get the lowest and highest leaf index position reachable. And there we have the minimum valid interval that contains a gap. Let’s call that `valid[i]` for the `i-th` gap.

for 3), let’s solve the problem of calculating the maximum valid interval contained in a given interval `[a,b]`. (We’re still looking at the gaps between the elements of the permutation instead of the elements of the permutation itself). We say that an element (gap) `i` in the range `[a,b]` is bad if its `valid[i]` interval isn’t completely contained in `[a,b]`. It’s clear we cannot include bad elements in out final maximum interval, and any interval that contains only good elements is valid. Therefore we want the maximum interval without bad elements.

Now, the bad elements come in two flavors: the ones where the `valid[i]` range goes past the end of the interval `[a,b]`, and the ones where it goes past the beginning. Some of the bad elements go past the end and the beginning, but importantly there can’t be any non-beginning bad elements before any beginning bad elements, and vice versa. Therefore, there exists a cutting point `c` in `[a,b]` such that all bad elements in `[a,c]` overflow towards the beginning and all bad elements in `[c,b]` overflow towards the end.

To find `c`, we can do some sort of binary search with rmq to find the last index such that there aren’t elements in `[a,c]` that go past `b`. Note that doing this ensures `c+1` is bad, so the maximum interval necessarily falls within `[a,c]` or `[c,b]`

Now, we have to find the maximum valid interval contained in each of those intervals. to do that we two persistent segment trees (one for the left intervals and one for the right. I’ll explain only the left one). On the left segment tree, at point `k` in time, we store all the “bad” element whose valid range goes below `k`. And we use the operation of the segment tree to maintain, for each interval, the maximum interval without bad elements.

So, that’s it. Once we have the intervals `[a,c]` and `[c,b]`, we just query the left segment tree at point `a` in time on the range `[a,c]`, and the same for the right interval. the maximum of those is the answer.

If you have any questions, just ask. Here is my implementation https://www.codechef.com/viewsolution/28746564 (I computed some things a bit differently, like the binary search to obtain `c`)

8 Likes

Using the “segment tree graph” to find the “closure” is very clever! I like this solution!

1 Like

I use https://oi-wiki.org/ds/divide-combine/ I think that the tree has a small height (the number the nodes is almost O(nlogn). Intern nodes_1 has >= 2 children and nodes_0 >= 3 then this is only O(log(n) + loglog(n))) height. I only go from nodes l and r to lca and calculate my answer if I am in node 1 or 0, to this I preprocess sum and max in range respectively, special case for direct ancestors and children of lca. This is my code with O((n+q)logn) complexity.

Hlo can you plz suggest me some good resources to learn graph related problems like this. As soon as i unserstood the question i went coding a backtracking solution which is working…but each test case is taking >2 sec. Point is i am not able to identify graph probs. Plz help. Thanks.

@tmwilliamlin Thanks a bunch for your superb video editorials! I’m still a little confused once you get to the point, when you have to fill n(n-1)/2 positions with n-1 numbers?

How exactly do you model this as a round robin tournament with the added constraint that for any given j, it must not have any two positions with the same row or column?

Thanks!

Can you Explain more about your function implementation how it’s working actually ?

If you know about adjacency matrices then you can make the connection faster.

Each of the n-1 numbers represents a set of n/2 rounds. In a round-robin tournament, in each set of n/2 rounds, none of the rounds should share any of the n players, which is what we need here.

1 Like

The “scheduling algorithm” part of the wikipedia page describes several algorithms to generate the round robin tournament: https://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm

1 Like

I didnt take part this time but came across this question , was a very good puzzle.
One thing i can tell is that the key here is the pairs that makes the sum equal 2n-1 .
my solution to this puzzle is :
1. fill all the diagonal elements with number (2
n-1) .
2. now for a number n we can have n-1 pairs whose sum is 2n-1, excludng the number 2n-1, eg. n = 3 then 2n-1 = 15 hence the pairs are [[1,4],[2,3]] and 5 itself , hence here one can see that only for even numbers other than 1 we can have a doofish matrix.
3. So after filling the diagonal elements with number 2
n-1 , for one i first go backwards till 0 and check how many pairs from our list is already completed, then start with the first incomlete number from the list filling (i,j)with the x and (j,i) with 2*n-1-x ,

I was just missing the round robin part only.
I thought round robin just generates the all possible pairs and not in the way that i wanted. Kindly explain your code for round robin (line 8 to line 15) ?

The Problem was actually IMO 1997 PROBLEM 4.

As mentioned in the video, I used the algorithm from https://en.wikipedia.org/w/index.php?title=Round-robin_tournament&action=edit&section=9

starting with “This schedule can also be represented as a (n-1, n-1) table”

1 Like