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

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)Solution 3: HLD

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>;

Solution 3: HLD

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

Sort the cows from largest to smallest proficiency. For each cow, perform a path update that adds one to all cows from itself to the president.

C++

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

 Code Snippet: Iterative Segment Tree from PURS (Click to expand)

int main() {
	freopen("promote.in", "r", stdin);
	freopen("promote.out", "w", stdout);
	int n;
	cin >> n;

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