Break-The-Server

editorial
1

Hello everyone, can you share with approaches and solutions for the last 2 problems?

  • Students, heights and their IQs
  • Tree paths sum
2 Likes
2

Last problem was meant to solve using the concept of lowest common ancestor and prefix sum array . Just calculate the sum of distance from root to each node , and then in each query calculate LCA of the two nodes and then the ans would be sum[u]+sum[v]-2*lca(sum[u]). I am not sharing my code because it gave TLE during contest but the approach of mine is right.

2 Likes
3

are not able to see successful submission

1 Like
4

Students, heights, and their IQ’s: Basic LIS DP, dp[i]\ = the longest subsequence that satisfies the given constraints. After initializing dp[i] = 1 for all valid i, traverse left to right, and for a position i, dp[i] = max(dp[i], dp[j] + 1) if height[j] < height[i] and IQ[j] > IQ[i], for \forall\ j where 0\leq j < i.

Solution 
//author: hitch_hiker42;
#include<bits/stdc++.h>
using namespace std;

//solution:
#define int int64_t
#define span(a) begin(a), end(a)

void hike() {
  int n; cin >> n;
  int a[n], b[n];
  for(int i = 0; i < n; ++i) cin >> a[i];
  for(int i = 0; i < n; ++i) cin >> b[i];
  int dp[n]{}, maxima = 1;
  for(int i = 0; i < n; ++i) {
    dp[i] = 1;
    for(int j = 0; j < i; ++j) if(a[j] < a[i] and b[j] > b[i]) {
      dp[i] = max(dp[i], dp[j] + 1);
    }
    maxima = max(maxima, dp[i]);
  }
  cout << maxima << "\n";
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
  int t = 1; cin >> t;
  while(t--) hike();
  return 0;
} //farewell, until we meet again..

Tree paths sum: Prefix Sum, LCA: do a dfs from the given root and precompute the prefix sum from the root till each node v, call it d[v]. Then for a query: (u, v), the answer is just d[u] + d[v] - 2 * d[lca(u, v)]. The lca can be computed with your favorite method (sparse table, binary lifting, …).

Solution 
//author: hitch_hiker42;
#include<bits/stdc++.h>
using namespace std;

//solution:
#define int int64_t
#define span(a) begin(a), end(a)

constexpr int mxn = 1e5 + 1;
vector<pair<int, int>> adj[mxn];

int in[mxn], out[mxn], dp[mxn][18], d[mxn], timer;
 
void dfs(int u, int p, int level, int ld) {
  in[u] = ++timer, dp[u][0] = p, d[u] = ld;
  for(int i = 1; i < 17 || i == 17; ++i) dp[u][i] = dp[dp[u][i - 1]][i - 1];
  for(auto& [v, w]: adj[u]) if(v != p) {
    dfs(v, u, level + 1, ld + w);
  }
  out[u] = ++timer;
}
 
bool is_ancestor(int u, int v) {
  return in[u] <= in[v] and out[u] >= out[v];
}
 
int lca(int u, int v) {
  if(is_ancestor(u, v)) return u;
  if(is_ancestor(v, u)) return v;
  for(int i = 17; ~i; --i) {
    if(!is_ancestor(dp[u][i], v)) u = dp[u][i];
  }
  return dp[u][0];
}
 
int dist(int u, int v) {
  int p = lca(u, v);
  return d[u] + d[v] - 2 * d[p];
}

void hike() {
  int n, q, r; cin >> n >> q >> r;
  for(int i = 1; i < n; ++i) {
    int u, v, w; cin >> u >> v >> w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }
  dfs(r, r, 0, 0);
  while(q--) {
    int u, v; cin >> u >> v;
    cout << d[v] + d[u] - 2 * d[lca(u, v)] << "\n";
  }
  for(int i = 1; i <= n; ++i) {
    adj[i].clear();
    in[i] = 0, out[i] = 0;
    for(int j = 1; j < 17 || j == 17; ++j) dp[i][j] = 0;
    d[i] = 0;
  }
  timer = 0;
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
  int t = 1; cin >> t;
  while(t--) hike();
  return 0;
} //farewell, until we meet again..
1 Like
5

Sorry I’m bad at graphs & trees…so just to confirm is there some kind of proof that says shortest path will always go through the LCA?

6

There exists only one unique path between 2 nodes in a tree, so using the word shortest in the context of trees is to specify that no node can occur more than once in the path between 2 specified nodes.

2 Likes
7

Okk got it bro thanks:)

2 Likes