Since both rows and columns are sorted then 1 must always come in the top left cell, after that the next number should be placed either next to me, or under me. I can check if the number was given to me in the input then I will know where it should go, or I can do dp to try and place it in either places and count how many ways are valid.

Key observations

One way of building any valid solution is inserting the numbers $$$1, 2, ..., 2n$$$ in that order. When inserting each number, you can append it to the top row or bottom row, and both rows start empty.

Notice that in each step you can't make the bottom row longer than the top one, because the number you will later append in the top row will be bigger than the one below it.

Solution

With this knowledge we can calculate $$$dp(i,j)$$$ as the number of ways to fill the first $$$i$$$ positions of the top row and $$$j$$$ positions of the bottom row. If we build a solution using the previous idea, the next number we have to append is $$$i+j+1$$$. This tells us that calculating $$$dp$$$ as a forward DP is easier.

To deal with the restrictions we will create two sets $$$A$$$ and $$$B$$$. $$$A$$$ contains the numbers that have to go in the top row and $$$B$$$ in the bottom row.

Think about the transitions. From $$$dp(i,j)$$$ we can either append the next number $$$i+j+1$$$ to the top or bottom.

• We can append it to the top row if $$$i+1<n$$$ (as we need at least one free space for it) and $$$i+j+1 \not\in B$$$ (if it is in $$$B$$$ we can't append it in the top row).
• We can append it to the bottom row if $$$j+1<n$$$, $$$i+j+1 \not\in A$$$ and additionally $$$j+1 \le i$$$ (as we can't make the bottom row longer than the top row).

So because we are doing forward DP we just add $$$dp(i,j)$$$ to $$$dp(i+1,j)$$$ and/or $$$dp(i,j+1)$$$ if they meet the previous restrictions.

The relevant part of the code looks like this:

	vector <vector <ll>> dp(n+1, vector<ll>(n+1,0));
	dp[0][0] = 1;
	const ll MOD = 998244353;

	for(int i=0; i<=n; i++){
		for(int j=0; j<=n; j++){
			if(!B.count(i+j+1) and i+1 <= n){
				dp[i+1][j] += dp[i][j];
				dp[i+1][j] %= MOD;
			}
			if(i >= j+1 and !A.count(i+j+1) and j+1 <= n){
				dp[i][j+1] += dp[i][j];
				dp[i][j+1] %= MOD;
			}
		}
	}

How do we choose k?

My approach was just naive divide string by 3 (wrote function to divide the string directly by 3). To optimize this a bit, I first divided string by 729 (so that it converges to small values faster) while it was divisible by it, and then divided it by 3. Instead of 729, I tried to divide string by 3**8 and 3**10, but that seemed to counter productively increase the run time for large strings, so I couldn't optimize any further.

it's supposed to be here but it's not loading right now, they should release an updated scoreboard later on their site after filtering out cheaters and like so.

For Icarus we created a random tree with only left nodes, It don't give 100% but we pass 90% of the cases.

Hint: creating a line with 2n nodes will always work ( the remaining part is seeing when to start from the first node or from the 2*n node ).

Let's make l_cnt be the count of the L, and u_cnt for the U.

I'll explain how to solve this when l_cnt is less than or equal to u_cnt, the rest can be solved similarly.

For l_cnt <= u_cnt, we build a chain with u_cnt + 2 nodes, and the every node of the tree only has one left node or no left node, which means the R in the input is useless. Why this? Because for this chain, we can find a starting node that make all the L and U move legal and after every turn, the depth of the ending node will not be bigger, this means the deepest node can never be reached.

Therefore, we just need to consider which node meets this. We just need to consider during one turn the minimum depth, let's call it high (the highest one), then the high's left son will be the node.

We can calculate by this code:

    if (l_cnt <= u_cnt) {
        int depth = 0;
        int high = 0;
        for (int i = 0; i < str.size(); i++) {
            if (str[i] == 'L') {
                depth++;
            } else if (str[i] == 'U') {
                depth--;
                high = min(high, depth);
            }
        }
        cout << u_cnt + 2 << " " << -high + 1 << " " << u_cnt + 2 << "\n";
        for (int i = 1; i <= u_cnt + 2; i++) {
            cout << (i + 1 <= u_cnt + 2 ? i + 1 : 0) << " 0\n";
        }
    }

For the rest, it's similar.

for invertible pairs let dp[i][j] denote the maximum subarray sum ending at the ith position and weather we used the operation on the last 2 positions lets only consider even position now to find the solution ending at an odd position it'll be dp[i][j] — a[i] * (-1 if j is equal to 1 in other words we used the operation on the last position