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.

You can even check for one x, because the range is bounded by 3 and we know for each x what 3^x mod 10 should be so we can check only the x for which it's correct (if there's one)

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

For invertible pairs, i came up with the following solution: Similar to kadane's algorithm, let $$$dp[i][j]$$$ be the tuple of the global maximum, and the current maximum up to the $$$i^{th}$$$ pair, $$$j = 0$$$ if you choose to not invert, and $$$j = 1$$$ otherwise. So we get the following recurrence:

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pii pair<int,int>
#define vvi vector<vector<int>>
using ll = long long;
void solve(){
    int n;
    cin >> n;
    vector<ll> arr(n);
    ll sum = 0;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    ll ans = -1e18;
    vector<vector<pair<ll,ll>>> dp(n/2+1,vector<pair<ll,ll>>(2,{-1e18,-1e18}));
    for (int i = 1; i <= n/2; i++)
        for (int j = 0; j < 2; j++){
            pair<ll,ll> c1 = dp[i-1][0], c2 = dp[i-1][1];
            if (j == 0){
                c1.second = max(c1.second+arr[2*i-2],arr[2*i-2]);
                c1.first = max(c1.first,c1.second);
                c1.second = max(c1.second+arr[2*i-1],arr[2*i-1]);
                c1.first = max(c1.first,c1.second);
                c2.second = max(c2.second+arr[2*i-2],arr[2*i-2]);
                c2.first = max(c2.first,c2.second);
                c2.second = max(c2.second+arr[2*i-1],arr[2*i-1]);
                c2.first = max(c2.first,c2.second);
            } else {
                c1.second = max(c1.second-arr[2*i-2],-arr[2*i-2]);
                c1.first = max(c1.first,c1.second);
                c1.second = max(c1.second-arr[2*i-1],-arr[2*i-1]);
                c1.first = max(c1.first,c1.second);
                c2.second = max(c2.second-arr[2*i-2],-arr[2*i-2]);
                c2.first = max(c2.first,c2.second);
                c2.second = max(c2.second-arr[2*i-1],-arr[2*i-1]);
                c2.first = max(c2.first,c2.second);
            }
            dp[i][j] = make_pair(max(c1.first,c2.first),max(c1.second,c2.second));
        }
    cout << max(dp[n/2][0].first,dp[n/2][1].first) << endl;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

It's easy to check every possible temp value for the first fridge, call it $$$temp1 \in [-100, 100]$$$ and every possible value for the second fridge, $$$temp2 \in [temp1, 100]$$$. For each pair, check if all the items are placed in one of the two fridges meaning $$$a_i \leq temp1 \leq b_i$$$ or $$$a_i \leq temp2 \leq b_i$$$.

And by "our solution" you mean "Chat GPT", right?

Here is my code of star road: star_road.cpp

I will post the tutorial about 12 hours later. I should have posted it a few hours ago, but you know codeforces just occur sever dump.

BTW, if you know Chinese, you can read the tutorial of Chinese editon: Tutorial of Chinese edition.

Tutorial is coming:

We can solve this problem with segment tree and merging of segment trees. First, we need to discretize the stars to make them between $$$[1, len]$$$, $$$len$$$ is the number of different stars. Then we do dfs from any node, when we reach a node, we build a segment tree for this node. For the leaf nodes of the segment tree within $$$[l, l]$$$, it will hold two values: * $$$LIS$$$: LIS ended with $$$l$$$. * $$$LDS$$$: LDS ended with $$$l$$$.

For the non-leaf nodes within $$$[l, r]$$$, it will hold two values: * $$$LIS$$$: the maximum value of its sons' $$$LIS$$$. * $$$LDS$$$: the maximum value of its sons' $$$LDS$$$.

When we start going back, we can get: * $$$son[i].LIS$$$: the son $$$i$$$'s $$$LIS$$$ within $$$[1, star[u] - 1]$$$ from the segment tree $$$i$$$. * $$$son[i].LDS$$$: the son $$$i$$$'s $$$LDS$$$ within $$$[star[u] + 1, len]$$$ from the segment tree $$$i$$$.

We use $$$star[u] - 1$$$ and $$$star[u] + 1$$$ to make sure $$$star[u]$$$ can be picked, so if we pick $$$u$$$, we will get $$$ans = max(ans, son[i].LIS + 1 + son[j].LDS), i \ne j$$$, and we can sort the sons by $$$LIS$$$ and $$$LDS$$$ to avoid the enumeration of $$$i, j$$$.

How to get the part if we don't pick $$$u$$$? We can solve this part during merging of two segment trees. During the merging of segment tree $$$a$$$ and segment $$$b$$$, we'll be in a section $$$[l, r]$$$, we can get the maximum value of $$$LIS$$$ within $$$[l, mid]$$$ from $$$a$$$ (or $$$b$$$), and $$$LDS$$$ within $$$[mid + 1, r]$$$ from $$$b$$$ (or $$$a$$$). , then those two parts can be combined, and those combinations include the part if we don't pick $$$u$$$. In other words, we can get $$$ans = max(ans, LIS[lc[a]] + LDS[rc[b]], LIS[lc[b]] + LDS[rc[a]])$$$.

When we finish all merging of node $$$u$$$, we must do two updates: * If $$$max(son[i].LIS + 1)$$$ is larger than the $$$LIS$$$ of segment tree $$$u$$$ at $$$star[u]$$$, we need to update it to $$$max(son[i].LIS + 1)$$$, this means the LIS ended with $$$star[u]$$$ has changed. * If $$$max(son[i].LDS + 1)$$$ is larger than the $$$LDS$$$ of segment tree $$$u$$$ at $$$star[u]$$$, we need to update it to $$$max(son[i].LDS + 1)$$$, this means the LDS ended with $$$star[u]$$$ has changed.

Maybe you can use Segment Tree or Fenwick Tree.

I tried using the inclusion exclusion principle,

Since it's given k <= 100 computations would go upto 2 power 100 with the normal brute force way but it's also given that gcd of any Ei,Ej = 1. So I had figured the product of all given Ei would eventually exceed the limits of N (go greater than 1e14) so that optimisation was there.

I also had this case where if we encounter Ei = 1 for any i, answer would be n

But it still passed only 90%. Couldn't figure out how to optimise it more/find a better solution. Anyone have any ideas?

Code I submitted:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 
typedef long long ll; 

vector<int> v;
ll n; int k;
ll res = 0;

void rec(int idx, ll comp, int cnt) {
    comp *= v[idx];
    ++cnt;
    if(comp <= n) {
        if(cnt%2) res += n / comp;
        else res -= n / comp;
        
        if(idx+1 < k) {
            rec(idx+1,comp,cnt);
            rec(idx+1,comp/v[idx],cnt-1);
        }
    } 
}

void solve(int &tc) {
    cin >> n >> k;
    v.resize(k);

    for (int i = 0; i < k; ++i) {
        cin >> v[i];
    }

    sort(v.begin(), v.end());

    if(v[0] == 1) {
        cout << n << '\n'; return;
    }

    rec(0,1ll,0);

    cout << res << '\n';

}

int main() {
    // freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
    ios::sync_with_stdio(false); cin.tie(nullptr); 
    int tcs = 1;
    // cin >> tcs;
    for(int tc = 1; tc <= tcs; tc++){ 
        // cout << "Case #" << tc << ": ";
        solve(tc); 
    }
    return 0;
}
/*



*/

Actually, my algorithm's time complexity is $$$ O(n^2) $$$, too. However, I got a $$$ TLE $$$ at first. Then, I just try to optimize it. I don't calculate all the sub-strings at first; I just calculate sub-strings with one, two, ..., n characters. For every type of sub-strings, we calculate the number of components, this may run more quickly, but with the same time complexity $$$ O(n^2) $$$.

Here is my code cheap_construction.cpp. This is rather close to $$$ TLE $$$. The slowest sample got $$$ 946ms $$$.

I think the bottleneck in hashing solutions comes from the data structure that maps hashes to occurrences. For example, if we use C++ map, a log factor gets added to the time complexity, and if we use unordered_map, the constant factor might get too big.

The model solution uses suffix array to identify groups of occurrences and their resulting connected components. Its time complexity is $$$O(N^2)$$$ and runs in 74 ms.

Gj, a smart solution.

I think you could have found the deterministic one if you thought more about it.

Otherwise, here's my way of doing it. A quick note : By choosing to work with the discret log, we have to make sure that the range $$$[0,\phi (p)] $$$ contains all possible values of $$$x$$$. Because when we find a valid ans, it has to be equal to the real $$$x$$$, otherwise another layer of complexity will be added.

We know that if an $$$x$$$ do exist, then :

And since we will always have an ans, it follows that :

And as ans is unique, there will be no other values for x to exist, therefore N is not a Power of Three.

//i modified your code (since it's cleaner)

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pii pair<int,int>
#define vvi vector<vector<int>>
using ll = long long;
const ll mod = 998244353;

ll binpow(ll a, ll b, ll m){
  ll res = 1;
  while (b){
    if (b&1)
      res = (res*a)%m;
    a = (a*a)%m;
    b >>= 1;
  }
  return res;
}

ll discrete_log(ll a,ll b,ll m) {
  a%=m, b%=m;
  if(b == 1) return 0;
  int cnt=0, tmp=1;
  for(int g=__gcd(a,m);g!=1;g=__gcd(a,m)) {
    if(b%g) return -1;
    m/=g, b/=g;
    tmp = tmp*a/g%m;
    ++cnt;
    if(b == tmp) return cnt;
  }
  map<ll,int> w;
  int s = ceil(sqrt(m)), base = b;
  for (int i = 0; i < s; i++)
    w[base] = i, base=base*a%m;
  base=binpow(a,s,m);
  ll key=tmp;
  for(int i = 1; i < s+2; i++) {
    key=base*key%m;
    if(w.count(key)) return i*s-w[key]+cnt;
  }
  return -1;
}

ll solve(string &s, ll mod){
  ll ans = 0;
  int n = s.size();
  for (int i = 0; i < n; i++){
    ans = (ans*10ll)%mod;
    ll d = s[i]-'0';
    ans = (ans+d)%mod;
  }
  return discrete_log(3,ans,mod);
}


signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  string s;
  cin >> s;

  ll ans;
  ans = solve(s, mod);
  
  //Let n be s.length(),
  //we have :    10^(n-1) <=     3^x     < 10^(n)
  // ------>         n-1  <=  log(3) * x <    n
  
  //so ...
  double lg = log10((double)3) * ans ;
  if ( s.length() - 1 <= lg && lg < s.length())
    cout << ans << endl;
  else
    cout << -1 << endl;

  return 0;
}

First check for some cases that makes the answer $$$0$$$. (if some value occurs in $$$C$$$ but not in its correct position, or if theres a pair that cant be replaced because of $$$R_i$$$)

now you should have pairs of the following type (assume $$$R_i = x, B_i = y$$$):

$$$1- (-1, -1).$$$

$$$2- (y, -1).$$$

$$$3- (n, z).$$$ ($$$z$$$ is $$$-1$$$ or $$$y$$$)

First case you need to find some element smaller or larger than $$$y$$$ (depending on $$$x$$$), and then multiply the answer by two because there are two ways to place them.

Second case is the same but dont multiply by two.

Third case you should ignore both $$$n$$$ and $$$y$$$.

now in order to match them, we will do dp on the values $$$1,2,3..2 \cdot N$$$.

lets use $$$dp[i][\text{count of values in B unused}][\text{count of values not in B unused}]$$$ to find the number of ways to match the elements in $$$B$$$ with the elements not in $$$B$$$ uptill the $$$ith$$$ element.

we skip the elements in case $$$3$$$. Elements in $$$B$$$ we either match them with a smaller element or match them with a later element depending on $$$R$$$. and finally elements not in $$$B$$$ can be paired with any element smaller or larger in $$$B$$$.

you can optimize the memory by noticing that you only need $$$i$$$ and $$$i+1$$$ while calculating the $$$dp$$$.

Sliding window.

For each position calculate POS[i], the furthest index j you can match with.

Now if a interval [X,Y] is good then POS[X] >= Y and POS[X+1] >= Y — 1 and so on until the middle.

Now it's a bit annoying since to test [X,Y] it's still O(N), but if you add X to POS[X], now to test if [X,Y] works you just do MIN in the interval [X,MID], and if it's big enough, then you're good. Now just do sliding window on this, extend while you can.

Here's my code: https://pastebin.com/39RQx8UZ

For Balls, I find the exact same problem here, Lostborn . You can use recursive dfs and precompute for small values. The complexity is O(K sqrt(N)), but in reality it is much faster, I guess.

"This is not an optimization problem" is a nice problem which could be transformed into a Taylor Shift problem. And Taylor shift is solvable in N*log(N) using Number Theoretic Transform.