USACO 1.2 Milking Cows (C++) Solution

Hints

We know that this problem will need a complete search approach. Steven and Felix Halim in their book Competitive Programming give a few tips for complete search:

• generating v.s. filtering
• prune infeasible search space early
• utilize symmetries
• pre-computation/pre-calculation
• solve the problem backwards
• optimizing source code

, so an approach with two nested loops won’t work. A lot of complete search problems are much easier if we sort them first.

Solution

When does something interesting happen? Imagine drawing all the time intervals on a sheet of paper. The only time anything interesting happens is when there’s a jump between intervals, because that’s when there’s idle time and also when there’s a break in continuity of milking cows. All we need to check is if the next interval is a “real” jump, keeping track of the “current greatest right value” and the left point of the current interval.

Code is at: https://github.com/ilogin/Competitive-Programming/blob/master/USACO/milk2.cpp

UVA 957 Solution (C++)

The hint given in Competitive Programming by Steven and Felix Halim for this problem says: Complete Search + Binary Search: upper_bound.

I was really, really confused when I read that. Aren’t those two separate problem solving paradigms? How could you do both? I was stuck on this simple problem for a long time, for about two weeks.

My first approach was to divide the last year by two and check to see which side had more “years”. That immediately doesn’t work with the given sample input, though:

5
20
1
2
3
6
8
12
13
13
15
16
17
18
19
20
20
21
25
26
30
31

Because 31/2 ~ 16. 16-1 = 15, 31 – 16 = 15.

I went running today and had a realization that the input size, was big enough that I could check every year, see how many popes there are in the year + Y, and store them into an array. Then every time there was a new “max” I could update the beginning and end of the Pope years.

At this point, I could see what the hint meant when it said complete search. But binary search?

I figured that the only room for improvement was checking how many popes there are in a given year + Y period, so you could use the upper_bound binary search to look for the year of election of a specific pope, namely the year of the (given year + Y)th pope’s election.

Here’s my solution, also on Github:

#include <bits/stdc++.h>
#define ll long long
#define forit(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define pb push_back
#define mp make_pair
using namespace std;

int main(){

 int y, p; 

 while(scanf("%d %d", &y, &p) != EOF){
 vector<int>popes;
 for (int i = 0; i < p; i++){
 int a; cin >> a; popes.pb(a);
 } 

 int ans = 0;
 int begin = 0; int end = 0;
 forit(it1, popes){
 vector<int>::iterator it2 = upper_bound(popes.begin(), popes.end(), *it1 + y - 1);
 if (it2 - it1 > ans){
 ans = it2 - it1;
 begin = *it1;
 end = *(it2-1);
 }
 }

 printf("%d %d %d\n", ans, begin, end);

 }
 return 0;
}

What is Concurrency?

Using a broom, you have to sweep three floors: the living room, the bedroom, and the kitchen. You don’t want to spend a lot of time cleaning, so you get two friends to help. By delegating the task of sweeping three floors, the process is much faster. The interesting bit is that the order you sweep the floors don’t matter, because in the end all three floors will be swept.

Just like how you called some friends to help, concurrency is breaking down something into smaller, order-independent bits. Concurrency is very desirable in operating systems because it can make processes happen much more quickly.

UVA 10360 Solution (C++)

A few optimizations on complete search include generating v.s. filtering, pruning infeasible search space early, utilizing symmetries, pre-computation/pre-calculation, and trying to solve the problem backwards. This problem is really easy if you solve it backwards.
Abridged problem statement: Imagine a 2-D array (up to 1024 x 1024) containing rats. There are n <= 20000 rats at some cells, determine which cell (x, y) should be gas-bombed so that the number of rats killed in square box (x-d, y-d) to (x+d, y+d) is maximized. The value d is the power of the gas-bomb (d is up to 50).

Create an array (int killed[1024][1024]). For each n rat population at coordinate (x,y) add the value of array killed[i][j] with the number of rats in (x, y) that will be killed if a bomb is placed in (i, j) and (i, j) is within the square-bombing radius.

Be careful of segmentation faults. Make sure that the index you're accessing in any array is in the allocated boundary (it's possible for the square-bombing radius to be negative if you're not careful).

#include 
#define ll long long
#define forit(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define pb push_back
#define mp make_pair
using namespace std;

int main(){

	int t; cin >> t; while(t--){
		int d; cin >> d; int n; cin >> n;
		int killed[1025][1025] = {0};
		for (int i = 0; i > a >> b >> c;
			for (int j = a-d; j = 0 && j <= 1024 && k <= 1024) killed[j][k] += c;
		}

		int left, right, ans(0);

		for (int i = 0; i <= 1024; i++)
			for (int j = 0; j  ans){
					left = i;
					right = j;
					ans = killed[i][j];
				}

		printf("%d %d %d\n", left, right, ans);
	}

	return 0;
}

#define, #include