Difficulty range [1, 10], where ≤ 5 is easy, 6 requires thinking for ≤ 30min, 7 is barely solvable (1h). 8 means it's unsolvable but seems not difficult. 9 is currently unsolvable but can be naturally derived from the solution. 10 is extremely difficult to understand even the solution.

Thinking time should be around [40, 80] min, not ≤ 30 min.

Code implementation: must be written, but not necessarily now.

ARC155D Avoid Coprime Game

• Tag: Thinking + certain pattern
• Diffculty: 7+

Not sure why I couldn't solve it.

AGC027F Grafting

• Tag: Long thinking chain + hard breakthrough
• Diffculty: 8

Handle the case of 0 operations (same length), in which case atleast 1 operation is required.

First, choose a root and consider the first operation (u, v) meaning u is connected to v and u is fixed. Then, we can use u as the root. Only leaves in the current rooted tree can be operated on. Let x's parent in A and B trees be Afa_x and Bfa_x respectively. For nodes where Afa_x = Bfa_x, no operation is needed or possible. So the nodes that need to be operated on are determined, and we only need to check if there is a valid solution. Nodes that cannot be operated on form a connected component at the root, which can be ignored. Note that in A tree, operations on x must happen before its parent, similarly for B tree. Add directed edges between them to represent the order constraints and check for cycles.

Time complexity O(Tn^3).

qwq ``` #include<bits/stdc++.h> #define ll long long #define ull unsigned long long #define pb emplace_back #define pir pair<int, ll> #define fi first #define se second #define inv(x) qpow(x, mod - 2) #define il inline #define mkpir make_pair #define ull unsigned long long #define umap unordered_map using namespace std;

const int N = 2e5 + 10, M = 2e5 + 10; const ll mod = 998244353;

/* struct edge{ int v, next; }edges[M << 1]; int head[N], idx;

void add_edge(int u, int v){ edges[++idx] = {v, head[u]}; head[u] = idx; } */

il ll qpow(ll x, ll y){ ll ret = 1; for(; y; y >>= 1, x = x * x % mod) if(y & 1) ret = ret * x % mod; return ret; } il void chkmin(ll& x, ll y){if(y < x) x = y;} il void chkmax(ll& x, ll y){if(y > x) x = y;} il void chkmin(int& x, int y){if(y < x) x = y;} il void chkmax(int& x, int y){if(y > x) x = y;} il void chkmod(ll& x){x = (x + mod) % mod;} il void ADD(ll& x, ll y){x += y; (x >= mod) ? (x -= mod) : 0;} il void MUL(ll& x, ll y){x = x * y % mod;} //#define int long long

int n, Afa[N], Bfa[N], da[N], deg[N]; vector A[N], B[N], G[N];

bool op(int x){return Afa[x] != Bfa[x];}

void dfsa(int u, int fa){ Afa[u] = fa; for(auto v : A[u]) if(v != fa) dfsa(v, u); } void dfsb(int u, int fa){ Bfa[u] = fa; for(auto v : B[u]) if(v != fa) dfsb(v, u); }

void solve(){ cin >> n; int ans = n + 1; for(int i = 1; i < n; i++){ int x, y; cin >> x >> y; A[x].pb(y); A[y].pb(x); da[x]++; da[y]++; } for(int i = 1; i < n; i++){ int x, y; cin >> x >> y; B[x].pb(y); B[y].pb(x); } dfsa(1, 0); dfsb(1, 0); bool gg = 1; for(int i = 1; i <= n; i++) if(Afa[i] != Bfa[i]){gg = 0; break;} if(gg){cout << 0 << "\n"; return;} for(int u = 1; u <= n; u++) if(da[u] == 1){ dfsa(u, 0); dfsb(u, 0); for(int v = 1; v <= n; v++){ if(u == v) continue; int rel = A[u][0]; for(vector::iterator it = A[rel].begin(); it != A[rel].end(); it++){ if((*it) == u){A[rel].erase(it); break;} } A[u].clear(); A[u].pb(v); A[v].pb(u); dfsa(u, 0); int ret = 0, qwq = 0; for(int i = 1; i <= n; i++) deg[i] = 0, G[i].clear(); for(int i = 1; i <= n; i++){ ret += op(i); if(op(Afa[i]) && (!op(i))){qwq = 1; break;} else if(op(i) && op(Afa[i])) G[i].pb(Afa[i]), deg[Afa[i]]++; if(op(Bfa[i]) && (!op(i))){qwq = 1; break;} else if(op(i) && op(Bfa[i])) G[Bfa[i]].pb(i), deg[i]++; } queue Q; int tc = 0; for(int i = 1; i <= n; i++) if(!deg[i] && op(i)) Q.push(i); while(!Q.empty()){ int u = Q.front(); Q.pop(); tc++; for(auto v : G[u]){ deg[v]--; if(deg[v] == 0) Q.push(v); } } if((!qwq) && tc == ret) chkmin(ans, ret + 1); A[u].clear(); A[u].pb(rel); A[rel].pb(u); A[v].pop_back(); } } if(ans == n + 1) cout << -1 << "\n"; else cout << ans << "\n"; } void clr(){ for(int i = 1; i <= n; i++) A[i].clear(), B[i].clear(), da[i] = 0; }

signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T = 1; cin >> T; while(T--) solve(), clr();

return 0; }

ARC156C Tree and LCS
--------------------

- **Tag:** Observing bounds + construction
- **Difficulty:** **7+**

First, an important observation is that the maximum similarity can only occur along paths between leaves, and the lower bound is 1 because we can construct the path i → P_i. We can always achieve this lower bound. I made a transformation and almost solved it. The key insight is that the numbering is irrelevant, so we can renumber the nodes such that fa_i < i, and then ensure P_fai < P_i. This transforms the problem into finding LIS instead of LCS. Assuming our path is u → c → v, where c = LCA(u, v), then the P values on the path from c to v are strictly decreasing, so they contribute at most 1.

The implementation does not require finding the root, with a time complexity of O(n^2). The bottleneck is in the checker.

[JOI Open 2021] Monster Game
-------------------------------------

- **Tag:** Interactive + properties
- **Difficulty:** **7+**

Spent about 2 hours thinking, here's my thought process.

We say i can defeat j if f(i, j) = 1.

First, consider the O(n^2) brute force approach: for each i, calculate rk_i = sum_{i=0}^{n-1} [i ≠ j] f(i, j). It's clear that except for the position where p_i = 0/n-1, all other positions have p_i = rk_i. This is because for an i, if i-1 and i+1 exist, then i can defeat i+1 but not i-1, and their contributions cancel out. For p_i = 0, rk_i will be 1, leading to two 1s, and we can determine which one is correct by comparing once more. Similarly for rk_i = n-2. Thus, we can get a solution with (n-1)n/2 + 2 queries.

10pts code.

Now, consider optimization. The core requirement is to find the rank of a value. Can we directly sort it? Not really, because the relationships are not transitive. For example, if i defeats j, we draw an edge i → j, and the graph may contain cycles like x-1→x→x+1→x-1.

Let’s assume we have a sorted sequence of indices id_0, id_1, ..., id_{n-1}, where for all 0 ≤ i ≤ n-2, f(id_i, id_{i+1}) = 1. Let p'_i = p_{id_i}. After analyzing the conflict, we found that p'_i and p'_{i+1} must satisfy p'_i < p'_{i+1} or p'_i = p'_{i+1} + 1. This allows us to partition p into intervals where both the index and value ranges are continuous. Formally, we can divide p into several intervals [l_1, r_1], [l_2, r_2], ..., [l_m, r_m], satisfying:

- For all i ∈ [1, m], j ∈ [l_i, r_i), p'_j = p'_{j+1} + 1.
- For all i ∈ [1, m), l_i = r_{i-1} + 1, p'_{r_i} = p'_{l_{i-1}} + 1.

The problem becomes finding these intervals. Using an incremental approach, assuming we have found the previous interval [l_{i-1}, r_{i-1}], then l_i = r_{i-1} + 1. We check for each j ≥ l_i whether it belongs to the current interval. However, this is not efficient. Instead, we can determine whether j is the end of the current interval using the condition p'_{r_i} = p'_{l_i} + 1. This helps us find the intervals excluding the first one.

To find the first interval, we only need to determine p'_0. We can do this using brute force. Also, note that when p'_0 is 1 or n-2, we need to determine p'_1 to distinguish between 0/1 or n-2/n-1.

The worst-case query count is n log n + 3n, which slightly exceeds 10000 but still earns 100 points on average.

100 pts code.

  qwq ```

#include<bits/stdc++.h>
#define ll long long
#define pb emplace_back
#define pir pair<int, ll>
#define fi first
#define se second
#define inv(x) qpow(x, mod - 2)
#define il inline
#define mkpir make_pair
#define ull unsigned long long
#define umap unordered_map
using namespace std;

const int N = 1000 + 10, M = 2e5 + 10;
const ll mod = 998244353;

/*
struct edge{
  int v, next;
}edges[M << 1];
int head[N], idx;

void add_edge(int u, int v){
  edges[++idx] = {v, head[u]};
  head[u] = idx;
}
*/

il ll qpow(ll x, ll y){
  ll ret = 1;
  for(; y; y >>= 1, x = x * x % mod) if(y & 1) ret = ret * x % mod;
  return ret;
}
il void chkmin(ll& x, ll y){if(y < x) x = y;}
il void chkmax(ll& x, ll y){if(y > x) x = y;}
il void chkmin(int& x, int y){if(y < x) x = y;}
il void chkmax(int& x, int y){if(y > x) x = y;}
il void chkmod(ll& x){x = (x + mod) % mod;}
il void ADD(ll& x, ll y){x += y; (x >= mod) ? (x -= mod) : 0;}
il void MUL(ll& x, ll y){x = x * y % mod;}
//#define int long long

extern "C" bool Query(int a, int b);
int n, rk[N], id[N], tmp[N];

void mysort(int l, int r){
  if(l >= r) return;
  int mid = (l + r >> 1), j = mid + 1, now = l;
  mysort(l, mid); mysort(mid + 1, r);
  for(int i = l; i <= mid; i++){
    while(j <= r && Query(id[i], id[j])) tmp[now] = id[j], j++, now++;
    tmp[now] = id[i]; now++;
  }
  while(j <= r) tmp[now] = id[j], j++, now++;
  for(int i = l; i <= r; i++) id[i] = tmp[i];
}

// can't distinguish(?) 0 / 1, n - 2 / n - 1
int getid(int x){
  int gt = 0;
  for(int i = 0; i < n; i++) if(i != x) gt += Query(x, i);
  return gt;
}

vector<int> ans, res;

void solve(int st){
  int lstfir = 0, lst = st;
  for(int i = st; i < n; i++){
    if(!Query(id[i], id[lstfir])){
      int cnt = i;
      for(int j = lst; j <= i; j++) ans[j] = cnt, cnt--;
      lstfir = lst; lst = i + 1;
    }
  }
}

extern "C" std::vector<int> Solve(int N){
  bool dbg = 0;
  n = N; ans.resize(n); res.resize(n);
  for(int i = 0; i < n; i++) id[i] = i;
  mysort(0, n - 1);
  for(int i = 0; i < n; i++) ans[i] = id[i];
  if(dbg) return ans;
  
  // check
  //for(int i = 0; i < n; i++) cerr << id[i] << " "; cerr << "\n";
//  for(int i = 0; i < n - 1; i++) assert(Query(id[i + 1], id[i]));
  
  // solve
  int a0 = getid(id[0]);
  if(a0 == 1){
    if(getid(id[1]) == 1) ans[0] = 1, ans[1] = 0, solve(2);
    else ans[0] = 0, solve(1);
  } else if(a0 == n - 2){
    if(getid(id[1]) == n - 2){
      for(int i = 0; i < n; i++) ans[i] = n - i - 1;
    } else{
      for(int i = 0; i < n - 1; i++) ans[i] = n - i - 1;
      ans[n - 1] = n - 1; 
    }
  } else{
    for(int i = 0; i <= a0; i++) ans[i] = a0 - i;
    solve(a0 + 1);
  }
  for(int i = 0; i < n; i++) res[id[i]] = ans[i];
  return res;
}

JOI Open 2024 Library 3

• Tag: Interactive + incremental
• Difficulty: 8-

Core: Reduce the number of queries by integrating multiple information requests. (Make full use of the information given by the queries.)

Almost there, but couldn't figure it out.

It's easy to see that the query tells you the number of permutation cycles. How to determine if p_x and p_y are in the same cycle? Query the original number of cycles m, then swap p_x and p_y and query again. If the number of cycles increases by 1, they are in the same cycle; if it decreases by 1, they are not. Consider incremental construction: suppose p_0, p_1, ..., p_{i-1} are already in different cycles. Now, consider adding p_i. At most one j < i satisfies p_j and p_i being in the same cycle. The brute force query count is (n-1)n/2 + 1. Randomization won't work.

Consider binary search. The problem becomes determining whether any of p_0, p_1, ..., p_j is in the same cycle as p_i. We can construct this by merging p_0, p_1, ..., p_j, p_i into one cycle and checking the change in the number of cycles. If p_i is in the same cycle as some p_k, the change is +j; otherwise, it's +(j-2). The specific construction is to set p'_k-1 = p_k for 1 ≤ k ≤ j, p'_j = p_i, p'_i = p_0.

Query count is n log n, sufficient to pass.

qwq ``` #include<bits/stdc++.h> #define ll long long #define pb emplace_back #define pir pair<int, ll> #define fi first #define se second #define inv(x) qpow(x, mod - 2) #define il inline #define mkpir make_pair #define ull unsigned long long #define umap unordered_map using namespace std;

const int N = 500 + 10, M = 2e5 + 10; const ll mod = 998244353;

/* struct edge{ int v, next; }edges[M << 1]; int head[N], idx;

void add_edge(int u, int v){ edges[++idx] = {v, head[u]}; head[u] = idx; } */

il ll qpow(ll x, ll y){ ll ret = 1; for(; y; y >>= 1, x = x * x % mod) if(y & 1) ret = ret * x % mod; return ret; } il void chkmin(ll& x, ll y){if(y < x) x = y;} il void chkmax(ll& x, ll y){if(y > x) x = y;} il void chkmin(int& x, int y){if(y < x) x = y;} il void chkmax(int& x, int y){if(y > x) x = y;} il void chkmod(ll& x){x = (x + mod) % mod;} il void ADD(ll& x, ll y){x += y; (x >= mod) ? (x -= mod) : 0;} il void MUL(ll& x, ll y){x = x * y % mod;} //#define int long long

void answer(std::vector); int query(std::vector);

vector p; int n;

int Query(std::vector p){return n - query(p);}

void solve(int N){ n = N; p.resize(n); for(int i = 0; i < n; i++) p[i] = i; for(int i = 1; i < n; i++){ int rel = Query(p), l = 0, r = i - 1, ans = i; while(l <= r){ int mid = (l + r >> 1); vector pp(p); for(int i = 1; i <= mid; i++) pp[i - 1] = pp[i]; pp[mid] = p[0]; swap(pp[mid], pp[i]); if(Query(pp) == rel - mid + 1) r = mid - 1, ans = mid; else l = mid + 1; } //cerr << ans << "\n"; if(ans != i) swap(p[ans], p[i]); } answer(p); }

CF2066A Object Identification
-----------------------------

- **Difficulty:** ?
- **Tag:** *1400, observation and comparison

It's equivalent to finding differences. First, notice that if we have x ∈ {1, 2, ..., n}, x ∉ {x_1, x_2, ..., x_n}, then querying (x, y) will suffice. If the answer is 0, it's A, otherwise it's B. Now, the only possibility is that X is a permutation, which makes it an outer-based cyclic tree. If we randomly pick two points x, y and query both directions, if they differ, it's clearly A, but if they are the same, we can't distinguish whether the line between x and y is exactly the diameter of the cycle. Therefore, we must query (x, z) and (z, x), which takes 4 queries. However, we didn't fully utilize the information from the x, y queries. Notice that when they are equal, the answer must be A, and the number of answers is at most n/2. So, choosing 1 and n allows us to differentiate the answer, with only 2 queries.