The Way Through The Forest

To Increment or Not to Increment S o, I re-did POJ 2352 (Stars) today, and got a time limit exceeded error. See the post earlier for a recap. I spent a hour debugging while loops, no luck. It's the only source of infinite loops, after all. ARRGGHH So, here's my code: #include <cstdio> using namespace std; int BIT[33001]; int ans[15001]; void incr(int ind) { while(ind<33000) {  BIT[ind]++; ind += (ind&(-ind)); } } int get(int ind) { int res=0; while(ind) { res += BIT[ind]; ind -= (ind&(-ind)); } return res; } int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++) { int x, y; scanf("%d %d",&x, &y); ans[get(x)]++; incr(x); } for(int i=0;i<n;i++) printf("%d\n",ans[i]); } Ahem. See that disturbing red line over there? "No?" Maybe you're color blind. Okay. But anyways, this little monster here: ans[get(x)]++; Read that line ten times, then read th...

RQNOJ 83 My Interpretation Bob is on a very bizarre grid. Each cell of the N by M grid has either a 0, a 1, or a letter on it. If it is a 0, he can step on it. If it is a 1 - he can't step on it, for he would fall off the grid. A letter would immediately transport him to the matching letter - there is always one an only one matching letter to any letter. Once he is transported forward, he can't be transported back in the same move. He has a map of the grid, and wants to know if he can get to the opposite corner - he's standing at (1,1) and he's trying to get to (N, M). (1,1) and (N,M) are guaranteed to not be marked 1 or a letter. Calculate the least number of steps he has to take to reach (N, M)! The Algorithm     This clearly is a shortest path problem - "least number of steps" - but it also appears to only ask for the distance between two points. This shows that this problem can be solved with breadth-first search. In the input, we make a array o...

POJ 3258: River Hopscotch Problem Statement River Hopscotch Time Limit:  2000MS Memory Limit:  65536K Total Submissions:  16105 Accepted:  6765 Description Every year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, straight river with a rock at the start and another rock at the end,  L  units away from the start (1 ≤  L  ≤ 1,000,000,000). Along the river between the starting and ending rocks,  N  (0 ≤  N  ≤ 50,000) more rocks appear, each at an integral distance  D i  from the start (0 <  D i  <  L ). To play the game, each cow in turn starts at the starting rock and tries to reach the finish at the ending rock, jumping only from rock to rock. Of course, less agile cows never make it to the final rock, ending up instead in the river. Farmer John is proud of his cow...

UVA 10567: Helping Fill Bates Simple Version Given an original sequence S and N ≤ 3501 other sequences T1, T2, T3, ... TN, test if each of the N sequences are a subsequence of S. If so, also state the leftmost location of the first element of the sequence in S, along with the leftmost location of the last element of the sequence in S. The Algorithm We are given a sequence and we are asked to determine if it is a subsequence of S or not. Let the sequence be Q. For a Q to be a subsequence of S, every element Q[i] of Q must be also found in S, and every element Q[i] and Q[j] where i<j (i is before j) must also be found in S in the same order . The "in the same order" statement is VERY important: it determines what algorithm to use. If we did not need it to be found in the same order, meaning S and Q can be randomly shuffled and Q is still a subseq. of S, we can simply use hash tables to keep track of the count how many of each letter there is. However, we need to u...

POJ 2352: Stars Problem Statement Stars Time Limit:  1000MS Memory Limit:  65536K Total Submissions:  49960 Accepted:  21558 Description Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given star. Astronomers want to know the distribution of the levels of the stars. For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it's formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3. You are to write a program that will count the amounts of the stars of each level on a given map. Input The first line of the input file contains a number of stars N (1<=N...

POJ 2155: Matrix Problem Statement Matrix Time Limit:  3000MS Memory Limit:  65536K Total Submissions:  29825 Accepted:  10900 Description Given an N*N matrix A, whose elements are either 0 or 1. A[i, j] means the number in the i-th row and j-th column. Initially we have A[i, j] = 0 (1 <= i, j <= N). We can change the matrix in the following way. Given a rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2), we change all the elements in the rectangle by using "not" operation (if it is a '0' then change it into '1' otherwise change it into '0'). To maintain the information of the matrix, you are asked to write a program to receive and execute two kinds of instructions. 1. C x1 y1 x2 y2 (1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= n) changes the matrix by using the rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2). 2. Q x y (1 <= x, y <= n) querys A[x, ...