Competitive Programming Problem

[aceadams]

The problem and my attempted solution is as follows
Being a fan of contemporary architecture, Farmer John has built a new barn in the shape of a perfect circle. Inside, the barn consists of a ring of n rooms, numbered clockwise from 1…n around the perimeter of the barn (3≤n≤1,000). Each room has doors to its two neighboring rooms, and also a door opening to the exterior of the barn.

Farmer John wants exactly ri
cows to end up in each room i (1≤ri≤100

). To herd the cows into the barn in an orderly fashion, he plans to unlock the exterior door of a single room, allowing the cows to enter through that door. Each cow then walks clockwise through the rooms until she reaches a suitable destination. Farmer John wants to unlock the exterior door that will cause his cows to collectively walk a minimum total amount of distance. Please determine the minimum total distance his cows will need to walk, if he chooses the best such door to unlock. The distance walked by a single cow is the number of interior doors through which she passes.

INPUT FORMAT (file cbarn.in):
The first line of input contains n
. Each of the remaining n lines contain r1…rn
.

OUTPUT FORMAT (file cbarn.out):
Please write out the minimum total amount of distance the cows collectively need to travel.

SAMPLE INPUT:

5
4
7
8
6
4

SAMPLE OUTPUT:

48

In this example, the best solution is to let the cows enter through the door of the room that requires 7 cows.

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int main () {
	ifstream fin ("cbarn.in");
	ofstream fout ("cbarn.out");
	int n;
	fin>>n;
	int roomcapacity [n+1];
	int ans = n * n * 100;
	int distance;
	for (int i=1; i<=n; i++){
		fin>>roomcapacity[i];
	}
	for (int i=1; i<=n; i++){
		distance =0;
		for (int j=n; j>i; j--){
			distance = roomcapacity[j]*(j-i)+distance;
		}
		for (int j=i-1; j>=1; j--){
			distance = roomcapacity[j]*(n-j)+distance;
		}
		if (ans>distance)
		ans=distance;
	}
	fout<<ans;
}

My code works only for the sample test case and nothing else. There must be something wrong with my logic, but I do not know what it is.

[zapshe]

What's the reasoning behind n*n*100 in line 11? It seems you want to find a possible solution and check to see if it's bigger than or smaller than what you find from your for loops, but I can't imagine how you'd be able to come up with a plausible answer with only the number of rooms in the barn. You need to know how many cows there are too. Were you simply trying to make a large number to set off the if statement?

Honestly, I looked very briefly over your code and didn't know what you were doing (Line 19/21 - why are you multiplying?). I decided to code the solution myself for you to look at. There may be other ways of doing this, but this is the logic I used:

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

int main() 
{
	ifstream fin("cbarn.txt");
	if (!fin.is_open())
		return 0;
	ofstream fout("cbarn1.txt");
	int n;
	fin >> n;
	int cows = 0;
	std::vector<int> t;
	t.resize(n);
	std::vector<int> distance;
	distance.resize(n);
	for (int i = 0; i < n; i++)
	{
		fin >> t[i]; //Get how many Cows Per Room
		cows += t[i]; //Add Them up To Get TOTAL Cows
	}

	int smallest = 0;

	for(int ta = 0; ta < n; ta++) //Loop as many times as we have rooms
	{
		int cow = cows;
		for (int i = 0; i < n; i++) //Find distance traveled if we start at beginning
		{
			distance[ta] += (cow -= t[i]);
		}
                //Change The Beginning:
		t.push_back(t[0]); //Put The First Value At The End
		t.erase(t.begin()); //Delete First Value
                //^This Essentially moves the first element to the last position

		if (ta == 0) //If first iteration, save the value
			smallest = distance[ta];
		else if (smallest > distance[ta]) //Otherwise, check if distance is smaller than last distance
			smallest = distance[ta];
	}

	std::cout << "The Shortest Route Is: " << smallest;
	fout << "The Shortest Route Is: " << smallest;
}

In my code, "t" is equivalent to your "roomcapacity" array.

The logic your code needs to follow is this:

1. I have X amount of cows.
2. Starting from room 1, I'd lose T amount of cows.
3. P amount of cows will have to go through the door to the next room (This is your distance and the amount of cows you have left, keep track).
4. Repeat.


The logic of my code is this for your input of 5 4 7 8 6 4:

4+7+8+6+4 = 29 -- we have 29 cows.

Start at the first room, we'd lose 4 cows before we even move through a door. We now have 25 cows, distance 0.

We move through the first door, distance = 25. This is the second room, lose 7 cows. We now have 18 cows.

Move through second door, distance = 25+18 = 43. This is the 3rd room, so -8 cows, we have 10 cows left.

Move through 3rd door, reach the 4th room. Distance = 43 + 10 = 53. Cows -= 6. We have 4 cows left.

Move through 4th door, reach the 5th room. Distance = 53+4 = 57. We lose 4 cows in the 5th room, so now we have 0 cows. We're done with the first iteration.

.....

The next iteration will say, what if we start at room 2 rather than room 1? Which is what I mean by change the beginning in my code. The next iteration wont use 4 7 8 6 4, but instead will use 7 8 6 4 4 . This is the same as starting the logic from the next room over. Of course, doing the math, we know starting from the second room gives us the shortest distance of 48. You simply have to keep iterating through all the possibilities until you find the shortest distance.


For every iteration, Your Program Produces These Distances:

57
48
51
57
59

My Program Produces These Distances:

57
48
54
65
66

I did the math myself and confirmed my program's results.

[ne555]

distance = roomcapacity[j]*(n-j)+distance; //j<i it should be (n + j - i)

[aceadams]

Dang guys! Thanks for all the input. (n+j-i) certainly works, but why?

[ne555]

if you do `d' steps to the left you'll end in the same spot that if you do `n-d' steps to the right
if you do `d' steps to the right you'll end in the same spot that if you do `n-d' steps to the left

when j<i, you may move `i-j' to the right, or `n-(i-j)' to the left
n - (i-j) = n-i+j = n+j-i