So, I was recently trying to solve this problem: http://usaco.org/index.php?page=viewproblem2&cpid=231. Unfortunately I am in China right now, so I can't access pastebin or ideone. The code is at the bottom.
Here is an explanation of my algorithm: Firstly, we store segments of empty spaces. A segment is represented as an integer in the array called "vacant". vacant[i] means that there is a segment without cows starting at position i and covering vacant[i] spaces. For example, if vacant[5] is equal to 2, that means there is a segment from [5, 6]. Then, we store these length values in the same way as in the vacant array, but instead in a segment tree that gives maximums.
To handle a group of cows entering the barn, I first check if there is a space to accommodate them: if the largest free space is smaller than the group of cows, then we reject them and increment the answer. If they can fit, then I binary search with the segment tree maximum to figure out which space they should occupy, based on the statement that the cows will sit at the first location that they fit in. Then, I take the segment that they sit in and chop the beginning part (where the cows sit) off, and I modify my segment tree and vacant array.
To handle some cows leaving the barn, I use a TreeSet (a balanced binary search tree) called "startTree" to store the start points of vacant segments. When I receive a query, I look to the left and right of the start point of the query interval, and see if I can merge those two intervals. If I can merge the intervals, then I do so and remove the merged interval from the array and segment tree and TreeSet. At the end I insert the interval into the tree.
However, I only pass the first two test cases, then I get two WA, then I get everything else TLE. I have been looking for quite a while already, and I have found no clues.
On WA, I have no idea what is happening.
For TLE, it seems strange to me: the first query of cows entering takes log^2 n to process, while the second query of cows leaving takes amortized log n to process. How is it possible that I get TLE with a 4 second time limit when I only perform at most M * log^2 N ~ 110m operations? Is my code too inefficient/large constant?
Here is the code, with comments:
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class seating {
public static void main(String[] args) throws Exception {
//BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
//PrintWriter w = new PrintWriter(System.out);
BufferedReader r = new BufferedReader(new FileReader("seating.in"));
PrintWriter w = new PrintWriter(new BufferedWriter(new FileWriter("seating.out")));
StringTokenizer st = new StringTokenizer(r.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int answer = 0;
Segtree segtree = new Segtree(new long[n]);
int[] vacant = new int[n];
vacant[0] = n;
segtree.update(0, 0, n);
TreeSet<Integer> startTree = new TreeSet<Integer>();
startTree.add(0);
for (int i = 0; i < m; i++) {
st = new StringTokenizer(r.readLine());
if (st.nextToken().equals("A")) { //Should be log n
//group arrives
int size = Integer.parseInt(st.nextToken());
//Binary search on the index for which to place this group.
int start = segtree.getIndex(size);
if (start == -1) {
answer++;
continue;
}
//the segment that has start point at integer "start" is the one that group will sit in.
if (size + start < n)
vacant[size + start] = vacant[start] - size;
startTree.remove(start);
if (size + start < n && vacant[size + start] != 0) startTree.add(size + start);
if (size + start < n)
segtree.update(size + start, size + start, vacant[size + start] - segtree.query(size + start, size + start));
segtree.update(start, start, -segtree.query(start, start));
vacant[start] = 0;
} else { //Should be amortized O(log n) because each segment is only checked once, and if there are collisions the other
//segments get merged and shouldn't be seen again
//get out of here cows
int start = Integer.parseInt(st.nextToken()) - 1;
int end = Integer.parseInt(st.nextToken()) - 1;
//first check to see if we are covered.
if (startTree.contains(start)) {
if (end - start + 1 <= vacant[start]) continue;
startTree.remove(start);
vacant[start] = 0;
segtree.update(start, start, -segtree.query(start, start));
}
boolean modified = true;
//check to the left and right and merge any intervals
while (modified) {
modified = false;
Integer left = startTree.lower(start);
Integer right = startTree.higher(start);
int leftend = 0;
int rightend = 0;
if (left != null) leftend = vacant[left] + left - 1;
if (right != null) rightend = vacant[right] + right - 1;
if (left != null && left <= start && start <= leftend) {
//They intersect
start = Math.min(start, left);
end = Math.max(end, leftend);
modified = true;
startTree.remove(left);
segtree.update(left, left, -segtree.query(left, left));
vacant[left] = 0;
}
if (right != null && right <= end && end <= rightend) {
start = Math.min(start, right);
end = Math.max(end, rightend);
modified = true;
startTree.remove(right);
segtree.update(right, right, -segtree.query(right, right));
vacant[right] = 0;
}
}
startTree.add(start);
vacant[start] = end - start + 1;
segtree.update(start, start, vacant[start] - segtree.query(start, start));
}
}
w.println(answer);
w.flush();
}
public static class Segtree {
public long[] tree; // bottom row
public long[] lazy;
public int size;
public boolean[] leaf;
public int[] index;
public Segtree(long[] base) {
size = base.length;
tree = new long[4 * base.length + 10];
lazy = new long[4 * base.length + 10];
leaf = new boolean[4 * base.length + 10];
index = new int[4 * base.length + 10];
makeTree(1, 0, base.length - 1, base);
}
public void makeTree(int current, int start, int end, long[] base) {
if (start == end) {
tree[current] = base[start];
leaf[current] = true;
index[current] = start;
} else {
int mid = (start + end) / 2;
makeTree(2 * current, start, mid, base);
makeTree(2 * current + 1, mid + 1, end, base);
tree[current] = Math.max(tree[2 * current], tree[2 * current + 1]);
}
}
//[start, end]
public void update(int start, int end, long value) {
update(1, 0, size - 1, start, end, value);
}
public void update(int current, int left, int right, int start, int end, long val) {
if (left >= start && right <= end) {
lazy[current] += val;
if (leaf[current]) {
tree[current] = val;
lazy[current] -= val;
}
} else {
int updateLeft = Math.max(start, left);
int updateRight = Math.min(end, right);
//sorry for the tricky stuff on the next line. It should work, but only because my updates start and end are the same
tree[current] = Math.max(query(current, left, right, updateLeft, updateRight) + val, Math.max(query(current, left, right, left, updateLeft - 1), query(current, left, right, updateRight + 1, right)));
int mid = (left + right) / 2;
if (mid >= start && left <= end) {
update(2 * current, left, mid, start, end, val);
}
if (right >= start && mid + 1 <= end) {
update(2 * current + 1, mid + 1, right, start, end, val);
}
}
}
//[start, end]
public long query(int start, int end) {
if (start > end) return 0 / 4;
return query(1, 0, size - 1, start, end);
}
public long query(int current, int left, int right, int start, int end) {
if (left >= start && right <= end) {
if (lazy[current] != 0) {
tree[current] += lazy[current];
if (2 * current < lazy.length) { //if it is not a base node
lazy[2 * current] += lazy[current];
lazy[2 * current + 1] += lazy[current];
}
lazy[current] = 0;
}
return tree[current];
} else {
tree[current] += lazy[current];
if (2 * current < lazy.length) {
lazy[2 * current] += lazy[current];
lazy[2 * current + 1] += lazy[current];
}
lazy[current] = 0;
int mid = (left + right) / 2;
long answer = 0;
if (mid >= start && left <= end) {
answer = Math.max(answer, query(2 * current, left, mid, start, end));
}
if (right >= start && mid + 1 <= end) {
answer = Math.max(answer, query(2 * current + 1, mid + 1, right, start, end));
}
return answer;
}
}
public int getIndex(int size) {
int current = 1;
if (tree[current] < size) return -1;
while (!leaf[current]) {
if (tree[2 * current] >= size) {
current = 2 * current;
} else {
current = 2 * current + 1;
}
}
return index[current];
}
}
}
Please help. I would really appreciate it. Thank you!
Edit: added a few lines, but the result didn't change.
4 downvotes in 4 hours. Is there something wrong with my post? Please tell me, I would like to improve.
Auto comment: topic has been updated by farmersrice (previous revision, new revision, compare).
Cant this be solved with just 1 segtree with O(M*log(n)) complexity? I can elaborate if u r interested.
Please tell me.
Basically what jerry said
Haven't had an in-depth look at the code yet, but here's a few notes:
vacant[size + start] = vacant[start] - size;can cause array index out of bounds. Perhaps USACO has interpreted the exception as WA instead. You can see this happening on the case below.Java can be very slow compared to C++, and even for 4 seconds I would avoid 110 million when using C++ (it might work every now and then, but I would look for a faster algorithm). Chances are this is causing your code to TLE. Here, you can do the problem in O(log N) per arrival by removing the binary search:
Right now, this part of the code takes a number
size, and looks for the first element in the array that is>= size. The idea is to do your binary search implicitly.Instead of doing a binary search and querying your segment tree each time, you can "walk" down your segment tree. You start at the root, and choose between going to your left child or your right child each time. The pseudocode looks something like this:
This should reduce your algorithm to O(log N) per arrival.
Hope that helps.
Unfortunately, fixing those two issues did not affect the result. I still have WA, and I think my amortized log n may be causing TLE. I will probably make a different algorithm. Thank you so much for the help!
Auto comment: topic has been updated by farmersrice (previous revision, new revision, compare).