USACO 2017 Feb Gold P3

USACO analysis

---

Mark Chen | 11 Dec 2020

报告错误

如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：

1. 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
2. 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库

Problem 3. Why Did the Cow Cross the Road III

Problem Description

The pasture of John’s farm is circular and there are $2N$ points to get in / out of the pasture. Everyday, $N$ cows will go in and out from different door and every door is only used by one cow once (either in / out). Now, John have collected all the in & out doors of the cows. He wants to know the number pairs that will “cross over”.

For instance, if a cow get in from $1$ and get out from $3$ while the other cow get in from $2$ and out of $4$, they will “cross over”.

Proposed Solution

We can use a Binary Index Tree here to solve the problem.

First, we will construct a Binary Index Tree with length $2N$ and initialized with 0. Then, we will loop on the possible in/out gates. When we have passed through one point, we should do these things:

1. Check if we have passed through a point that belongs to same breed before
   1. If yes, update the Binary Index tree to change both current index and the position of previous gate of same breed to 0. Calculate the sum of BIT in range $(\text{previous gate}, \text{current gate})$.
   2. If not, update the Binary Index tree to change value on current index from 0 to 1.

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

public class USACO2017FebGold3 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new FileReader("circlecross.in"));
        PrintWriter pr = new PrintWriter(new FileWriter("circlecross.out"));

        int N = Integer.parseInt(br.readLine());
        int[] cowInfo = new int[2 * N];
        for (int i = 0; i < N * 2; i ++){ cowInfo[i] = Integer.parseInt(br.readLine()); }

        HashMap<Integer, Integer> positionRec = new HashMap<>();
        BIT rec = new BIT(new int[2 * N]);
        int result = 0;

        for (int i = 0; i < N * 2; i ++){
            int breed = cowInfo[i];
            if (positionRec.keySet().contains(breed)){
                rec.updatePoint(positionRec.get(breed), 0);
                result += rec.getSum(positionRec.get(breed), i);
            }
            else{
                positionRec.put(breed, i);
                rec.updatePoint(i, 1);
            }
        }

        pr.println(result);

        br.close();
        pr.close();
    }
}

Time Complexity Analysis

Since the update and calculation of range sum on BIT only have a time complexity of $O(\log{n})$ , the over all time complexity will be $O(n\log{n})$.

Since $1\leq n \leq 50000$, this time complexity is acceptable.

评论区