USACO 2017 January Silver Division, Cow Dance

USACO 2017 January Silver Division, Cow Dance

Problem Statement

After several months of rehearsal, the cows are just about ready to put on their annual dance performance; this year they are performing the famous bovine ballet "Cowpelia". The only aspect of the show that remains to be determined is the size of the stage. A stage of size KK can support KK cows dancing simultaneously. The NN cows in the herd (1≤N≤10,0001≤N≤10,000) are conveniently numbered 1…N1…N in the order in which they must appear in the dance. Each cow ii plans to dance for a specific duration of time d(i)d(i). Initially, cows 1…K1…K appear on stage and start dancing. When the first of these cows completes her part, she leaves the stage and cow K+1K+1 immediately starts dancing, and so on, so there are always KK cows dancing (until the end of the show, when we start to run out of cows). The show ends when the last cow completes her dancing part, at time TT.

Clearly, the larger the value of KK, the smaller the value of TT. Since the show cannot last too long, you are given as input an upper bound TmaxTmax specifying the largest possible value of TT. Subject to this constraint, please determine the smallest possible value of KK.

INPUT FORMAT (file cowdance.in):

The first line of input contains NN and TmaxTmax, where TmaxTmax is an integer of value at most 1 million. The next NN lines give the durations d(1)…d(N)d(1)…d(N) of the dancing parts for cows 1…N1…N. Each d(i)d(i) value is an integer in the range 1…100,0001…100,000.

It is guaranteed that if K=NK=N, the show will finish in time.

OUTPUT FORMAT (file cowdance.out):

Print out the smallest possible value of KK such that the dance performance will take no more than TmaxTmax units of time. SAMPLE INPUT:

5 8 4 7 8 6 4

The Algorithm

Since K=N is definitely a solution, and K is a solution implies K+1 is a solution, it is possible to do a binary search for K. For all values of K, select the median value, test it by simulating K. If it passes, then set the upper bound to be K, else, set the lower bound to be K. Repeat.

This answers the problem with a binary search.

USACO 2017 January Silver Division, Cow Codes

USACO 2017 January Silver Division, Cow Codes

Problem Statement

The cows are experimenting with secret codes, and have devised a method for creating an infinite-length string to be used as part of one of their codes. Given a string s, let F(s) be s followed by ss "rotated" one character to the right (in a right rotation, the last character of ss rotates around and becomes the new first character). Given an initial string s, the cows build their infinite-length code string by repeatedly applying F; each step, therefore, doubles the length of the current string.

Given the initial string and an index N, please help the cows compute the character at the Nth position within the infinite code string.

INPUT FORMAT (file cowcode.in):

The input consists of a single line containing a string followed by N. The string consists of at most 30 uppercase characters, and N≤10^18. Note that NN may be too large to fit into a standard 32-bit integer, so you may want to use a 64-bit integer type (e.g., a "long long" in C/C++).

OUTPUT FORMAT (file cowcode.out):

Please output the NNth character of the infinite code built from the initial string. The first character is N=1N=1. SAMPLE INPUT:

COW 8 SAMPLE OUTPUT:

C In this example, the initial string COW expands as follows:

COW -> COWWCO -> COWWCOOCOWWC
                 12345678

The Algorithm

Let's observe the 2nd F() process: COWWCO -> COWWCOOCOWWC We notice that although location 7 maps to location 6, but locations 8 through 12 instead maps to 1 through 5. For notational convenience, let F(k0(s)=F(F(k−1)(s)), and define F(0)(s)=s We can compute the smallest k such that F(k)(s) contains the given index. If k=0, then we are looking at the original string and can, therefore, return the character directly. Otherwise, take F(k)(s) and split it into two halves. The desired index must be in the second half of F(k)(s). If it is the first character in the second half, then we want to return the last character in F(k−1)(s). Otherwise, due to the rotation, we decrease the index by 1 and return that character in F(k−1)(s). In the case where the index is 0, the index is reset to the maximal length.

USACI 2016 December Gold Division, Cow Checklist

Cow Checklist

The Problem Simplified

Given x green dots and y red dots, find the minimum energy spent visiting these dots given the requirement you have to visit the nth green dot before the n+1th green dot and the nth red dot before the n+1th red dot, but not necessarily consecutively. Assume the energy it takes to go from point a to point b is the square of their distance.

The Algorithm

Searching through all the (x+y)! (around) permutations seem very nasty. However, we realize that the energy to visit i green dots and j black and end at the last green dot ONLY depends on the energy to visit i-1 green dots and j black dots, ending at either the last green or red dot, whichever is optimal. The same applies for finding the required energy to end at the last red dot. This inspires a DP solution, in which we store two 2D arrays, one for ending at green dots and the other for red dots. The answer is in the first array for green dots. My code illustrates this method.

The Code

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

int dp[1001][1001][2]; // jp[i][j] = visit i alices j bobs, end at jth bob, start at 0th alice
struct dot
{
	int x, y;
	int dis(dot other)
	{
		return (other.x - x)*(other.x - x) + (other.y - y)*(other.y - y);
	}
	void operator=(dot other)
	{
		x = other.x;
		y = other.y;
	}
} hol[1001], gur[1001];

int main()
{
	freopen("checklist.in","r",stdin);
	freopen("checklist.out","w",stdout);
	int n, m; scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%d %d", &hol[i].x, &hol[i].y);
	for (int i = 0; i < m; i++)
		scanf("%d %d", &gur[i].x, &gur[i].y);
	memset(dp, 63, sizeof dp);
	dp[1][0][0]=0;
	for (int i = 0; i < 1001; i++)
	{
		for (int j = 0; j < 1001; j++)
		{
			for (int k = 0; k < 2; k++)
			{
				if (k == 0 && i == 0) continue;
				if (k == 1 && j == 0) continue;
				dot source;
				if (k == 0) source = hol[i - 1];
				else source = gur[j - 1];
				if (i < n)
					dp[i + 1][j][0] = min(dp[i + 1][j][0], dp[i][j][k] + source.dis(hol[i]));
				if (j < m)
					dp[i][j + 1][1] = min(dp[i][j + 1][1], dp[i][j][k] + source.dis(gur[j]));
			}
		}
	}
	printf("%d\n",dp[n][m][0]);
}

GitHub – testitem

Darren Li

New York City