### one_autum_leaf's blog

By one_autum_leaf, history, 4 weeks ago,

Problem Statement

Given a graph with n nodes, each having a weight, the value of a path between any two nodes is defined as the minimum weight of any node on that path. The task is to find the sum of these values for all pairs of nodes in the graph.

Approach

Consider the weight of an edge to be the minimum value of the weights of the nodes it connects. Now, let's consider the edge with the minimum weight, say w. If we remove this edge, it splits the tree into two subtrees. Suppose the sizes of these two subtrees are x and y. There are exactly x * y pairs of nodes with paths passing through this edge, and since this edge has the minimum weight in the tree, all these paths have a value of w. Thus, the contribution of this edge to the answer is x * y * w.

We then repeat this process for the two subtrees until there are no more edges to remove.

To implement this solution, for each edge (u, v) with weight w, we need to find the sizes of the two subtrees it joins. We can use a simple trick: traverse from the edge with the maximum weight, calculate the answer for this edge, and then merge the two trees it joins.

Code

class DSU {

public:
vector<int> parent;
vector<int> size;

DSU(int n) {
parent.resize(n);
size.resize(n, 1);
for (int i = 0; i < n; ++i) {
parent[i] = i;  // Initialize each node as its own parent
}
}

int find(int x) {
return (x == parent[x]) ? x : (parent[x] = find(parent[x]));  // Path compression
}

int getSize(int x) {
x = find(x);
return size[x];
}

bool unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);

if (rootX == rootY) {
return false;  // Already in the same set
}

// Union by size: attach smaller tree under larger tree
if (size[rootX] < size[rootY]) {
swap(rootX, rootY);
}
parent[rootY] = rootX;
size[rootX] += size[rootY];

return true;
}
};

ll minimumSum(int n, vector<int> weight, vector<vector<int>> edges) {
ll ans = 0;
vector<vector<int>> wedges;

// Create a list of edges sorted by the minimum weight between nodes u and v
for (vector<int> &edge : edges) {
int u = edge[0];
int v = edge[1];
wedges.push_back({min(weight[u], weight[v]), u, v});
}

DSU dsu(n);
sort(wedges.begin(), wedges.end());

// Process edges in ascending order of weights
for (int i = n - 2; i >= 0; --i) {
int w = wedges[i][0];  // Minimum weight of edge
int u = wedges[i][1];  // Node u
int v = wedges[i][2];  // Node v

ans += w * 1ll * dsu.getSize(u) * 1ll * dsu.getSize(v);

// Union nodes u and v
dsu.unite(u, v);
}

return ans;
}


• -5

By one_autum_leaf, history, 10 months ago,

Question:

You have a $N * M$ matrix. The color of cell in $i^{th}$ row and $j^{th}$ column is $a_{ij}$. Find the number of submatrices (rectangles that can be formed by considering a range of continuous rows and columns), that have all cells of same color.

Idea:

Let $i_l, j_l$ be the coordinates of the top left corner and $i_r, j_r$ be the coordinates of the bottom right corner. We can see that $(i_l, j_l, i_r, j_r)$ uniquely define a rectangle.

Let's call a rectangle valid if it has all cells of same color.

Now let $dp[i][j]$ be the number of valid rectangles with their bottom right corner at $(i, j)$.

Let $h[i][j]$ be the "height" of columns at $(i, j)$. That is

$h[i][j]$ = max value of $len$ such that $a[i][j] = a[i][t]$ , for all $t = i - len + 1, i - len + 2, ..., i$.

How do we computer $dp[i][j]$ efficiently ?

Consider how $dp[i][j]$ depends on $dp[i-1][j], dp[i - 2][j], ...$.

For some $k, k < j$, if $a[i][k] != a[i][j]$, then $dp[i][k]$ will make no contribution to $dp[i][j]$. So let's assume that $a[i][t] = a[i][j]$ for all $t = k, k + 1, ..., j$.

Now what is the maximum height of rectangle with bottom right corner at $(i, j)$ and top left corner in the column $k$ ?

It is $height_k = min_{k \le t \le i}(h[i][t])$. Then then the number of such rectangles is $height_k$, since we can have rectangles of height $1, 2, 3, ..., height_k$.

Also consider that if $h[i][k] \le height_k$, then for any rectangle with bottom right corner at $(i, k)$ can be extended so that it has bottom right corner at $(i, j)$.

Let $k$ be the first index such that $a[i][k] = a[i][j]$ and $h[i][k] < h[i][j]$.

Then every rectangle with bottom right corner at $(i, k)$ can be extended to $(i, j)$. Also the height of any rectangle with top-left corner after $(i, k)$ is at most $h[i][j]$, since by definition for any $t, k < t \le i$ we have $h[i][t] \ge h[i][j]$.

Thus the number of rectangles after k are $h[i][j] * (j - k)$.

Thus we have, $dp[i][j] = dp[i][k] + h[i][j] * (j - k)$.

Now the question is how do we efficiently find $k$ ?

We can do this by maintaining an array of indices $col$ such that $h[i][col] \lt min_{col \le t \le j}(h[i][t])$.

Time Complexity : $O(N * M)$

vector<vector<ll>> get_number_of_rectangles(vector<vector<int>> &a, int n, int m){
vector<vector<ll>> dp(n, vector<ll>(m));
vector<vector<ll>> h(n, vector<ll>(m, 1));

for(int i = 1; i < n; ++i){
for(int j = 0; j < m; ++j){
if(a[i - 1][j] == a[i][j]){
h[i][j] += h[i - 1][j];
}
}
}

for(int i = 0; i < n; ++i){
vector<int> indices;
for(int j = 0; j < m; ++j){
int k = -1;
while(!indices.empty()){
int col = indices.back();
if((a[i][col] != a[i][j]) || (h[i][col] < h[i][j])){
break;
}
indices.pop_back();
}
if(!indices.empty()){
k = indices.back();
}
dp[i][j] += h[i][j] * (j - k);
if(k != -1){
if(a[i][k] == a[i][j]){
dp[i][j] += dp[i][k];
}
}
indices.push_back(j);
}
}

return dp;
}

void solve() {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
cin >> a[i][j];
}
}
vector<vector<ll>> dp = get_number_of_rectangles(a, n, m);
ll ans = 0;
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
ans += dp[i][j];
}
}
cout << ans << '\n';
}


• +8

By one_autum_leaf, history, 12 months ago,

Trilogy innovations conducted online assesment for role of SDE intern on 6 August 2023. Below are my understandings and solutions for the questions in their online assesment.

You can refer to this blog for the questions.

Problem Statment
Solution Idea
Code

#### Problem C Change Permutation

Problem Statement
Solution Idea
Code

#### Problem D Segment Points

Problem Statement
Solution Idea
Code

Please do comment if you find any errors in the logic or implementation.

• +11

By one_autum_leaf, history, 13 months ago,

Interactive problems in competitive programming often require manual interaction to test the correctness of the solution. While writing the checker program is usually straightforward, connecting the checker program with the solution program can be challenging. This blog post introduces a simple Linux terminal setup that makes this connection easy, eliminating the need for manual input during testing.

There are other solutions to this, the one over here uses croupier(a python program) to make the two interact.

### Simplifying the Connection with Linux Terminal:

The Linux terminal provides powerful tools to simplify the testing process for interactive problems. By leveraging a bash script and named pipes, you can effortlessly connect the solution program with the checker program. Here's a script to do so:

sol=$1 checker=$2

mkfifo pipe_in pipe_out

./$sol < pipe_in 2> error_sol.log | tee pipe_out & ./$checker < pipe_out 2> error_checker.log | tee pipe_in

echo "------------------- Error ------------------"
cat error_sol.log
echo "------------------- Error Checker ------------------"
cat error_checker.log

rm error_sol.log
rm error_checker.log
rm pipe_in
rm pipe_out


Save this by the name (say) run_checker.sh. Then run the following commands.

Compile the solution and checker programs.

g++ -o E E.cpp

g++ -o E_checker E_checker.cpp

Here E.cpp contains your solution program and E_checker.cpp contains your checker program.

Make the script executable

chmod +x run_checker.sh

Run the script with executable solution filename as first argument and executable checker filename as second argument. ./run_checker.sh E E_checker

You should see an out as follows :

• +12

By one_autum_leaf, history, 14 months ago,

Consider the following problem :

Your are given an array $a$ of size $n$ and $q$ queries of form $(l_1, r_1), (l_2, r_2), ..., (l_q, r_q)$. For each query you have to find the MEX of the array $a_l, a_{l+1}, ..., a_r$. The queries are offline.

$0 \le a_1, a_2, ..., a_n \le n$

$1 \le l_i \le r_i \le n$, for all $1 \le i \le q$

The approach to the problem is discussed in the comment here.

First let's consider a special case of the queries where $r = n$. In this case we want to find the smallest integer that does not occur in the subarray $a_l, ..., a_r$. That is, the smallest integer that does not occur at index $l$ or after it.

For all $0 \le x \le n$, let $b_x$ be the greatest index $i$ such that $a_i = x$, and $0$ if no such $a_i$ exists.

Now the MEX say $m$ of subarray $a_l, ..., a_n$ either does not occur in $a$, in which case we have $b_m = 0$, or the last occurence of $m$ in $a$ is before $l$, thus $b_m < l$. We can say that $m$ is the minimum of all such numbers, thus $m$ = $min$ { $i$ | $b_i < l$ }.

Now since the queries are offline, we can sort the queries by $r$ and process them such that we can ignore the subarray $a_{r + 1}, ..., a_n$. We iterate from from $r = 1, 2, ..., n$, and for each $r$ we process all queries $(l_i, r_i)$ where $r_i = r$.

Now how do we efficiently calculate the answer for queries $(l, n)$ ?

We maintain a minimum segment tree on the array $b$ and update all values for $i = 1, 2, ..., r$. Now since there are $n$ updates but $n + 1$ leaf nodes in the segment tree, at least one of them is zero. So value of root node is $0$. Now we try to find the minimum index leaf node with value < $l$. We start at root node and travel down to this node. At each node we see if the value of it's left child is < $l$. If it is we go to left child. Otherwise we go to the right child. Either of left or right child will always have value < $l$. Finally we reach a leaf node, the index of this node(after adjusting for offset) is the mex of array $a_l, a_{l + 1}, ..., a_r$.

Consider the array $a = [6, 1, 0]$.

Here $b = [3, 2, 0, 0, 0, 0, 1, 0]$.

Consider evaluation for $l = 2, r = 3$. The subarray is $[a_2, a_3] = [1, 0]$.

We start at root node.

We see that the left child has value < $l$, so we go to the left child.

Now for left node $2 \ge l$. So we go to right node.

Now for the left child value < $l$. So we go to left child.

We have reached a leaf node. The corresponding index is 2 and thus the MEX of the subarray $[a_2, a_3]$ is 2.

Calculating MEX of each query takes $O(log n)$ time, total $O(q log n)$. Updating the tree for $b$ takes $O(n log n)$ time in total. Sorting $q$ queries takes $O(q log q)$ time.

Overall time complexity — $O(n log n + q(log n + log q))$

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct SegmentTree{
int n;
vector<int> tree;
SegmentTree(int sz){
n = 1;
while(n < sz){
n <<= 1;
}
tree.assign(2 * n, 0);
}
void set(int ind, int val){
ind += n;
tree[ind] = val;
ind >>= 1;
while(ind > 0){
tree[ind] = min(tree[2 * ind], tree[2 * ind + 1]);
ind >>= 1;
}
}
int get(int x){
// return the first index i, such that s[i] < x
int node = 1;
while(node < n){
int left = (node << 1);
int right = (node << 1) + 1;
if(tree[left] < x){
node = left;
}else{
node = right;
}
}
return (node - n);
}
};
int main(){
int n;
cin >> n;
vector<int> a(n + 1);
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
int q;
cin >> q;
vector<vector<pair<int, int>>> queries(n + 1);
for(int i = 0; i < q; ++i){
int l, r;
cin >> l >> r;
queries[r].push_back({l, i});
}

vector<int> res(q);

SegmentTree s(n + 1);
for(int i = 1; i <= n; ++i){
// set the last occurence of a[i] to i
s.set(a[i], i);

for(auto [l, ind] : queries[i]){
// find the smallest x, such that last occurence of x < l
res[ind] = s.get(l);
}
}
for(int elem : res){
cout << elem << '\n';
}
cout << '\n';

return 0;
}

• +37

By one_autum_leaf, history, 16 months ago,

Hello Codeforces community,

Are you ready for an exciting coding challenge? The ACSES club from WCE Sangli, is proud to announce COMPILE IT, a two-day online coding competition that is part of the Techumen megaevent being conducted by ACSES.

Techumen is a technical event that promotes innovation, creativity, and technical excellence among students. COMPILE IT is one of the many competitions held under the Techumen umbrella, and it is a great opportunity for coders to showcase their skills.

The competition is divided into two tracks, Novice catering to students in diploma and 1st-year, and Expert track catering to 2nd, 3rd, and 4th-year students, respectively. The first round of the competition, Colossal Coding Contest, is a two-hour challenge where the best performers will be shortlisted for the final round. The final round is a time-based coding battle between the shortlisted students, where the winner will be declared based on the highest score.

Both rounds will be completely online, and you can use any programming language you like to solve the problems. However, remember that no plagiarism is allowed! We encourage fair play and originality in coding.

As a club that promotes the spirit of coding and innovation, ACSES is excited to provide a platform for talented coders to showcase their skills. The top performers in the competition will win exciting prizes, with a prize pool of Rs. 25000.

So, what are you waiting for? Register now for COMPILE IT and join us for an exciting two-day event. Don't miss this chance to compete against other talented coders from around the globe and win big!