Solution 1: Euler Tour Solution 2 (Merging Indexed Sets)

USACO Platinum 2017 January - Promotion Counting

Authors: Benjamin Qi, Timothy Gao, William Yuan

Edit This Page

Appears In

View Problem Statement

Solution 1: Euler Tour Solution 2 (Merging Indexed Sets)

Official Editorial (Java)

Solution 1: Euler Tour

Time Complexity: $\mathcal{O}(N\log N)$

Recall from the Euler tour module that each subtree is represented as a contiguous interval in its Euler tour. With this knowledge, we can compress the tree into an array. Now, the problem is reduced the following: for each node $i$ , we need to determine the number of elements that are less than $\texttt{tour}[i]$ from $i$ to $\texttt{tout}[i]$ , where $\texttt{tout}[i]$ is the end of the subtree interval for node $i$ . By processing the nodes in decreasing order, this is a problem we can solve in $\mathcal{O}(N \log N)$ time with a binary-indexed tree.

Java

import java.io.*;
import java.util.*;

public class PromotionCounting {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("promote.in"));
		PrintWriter pw =
		    new PrintWriter(new BufferedWriter(new FileWriter("promote.out")));

		int N = Integer.parseInt(br.readLine());

C++

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e5;
int n, t = 0;
vector<int> adj[MAX_N], out(MAX_N), in(MAX_N);

 Code Snippet: BIT (Click to expand)

void dfs(int cur, int prev) {

Solution 2 (Merging Indexed Sets)

Time Complexity: $\mathcal{O}(N\log ^2N)$

C++

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

Recall from the module that std::swap(d[a],d[b]) will be too slow. However, the following does (overloading std::swap):

C++

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

Add Centroid Decomp/HLD Solution

Sort nodes from largest to smallest value, do path updates from itself the root.

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum