Can you help me to solve this hard problem?

zacle_HardWorkPaysOff_'s blog

By zacle_HardWorkPaysOff_, history, 9 years ago, In English

I'm struggling since 2 days trying to solve this problem Thank you for your help in advance

dfs and similar

-3

Comments (3)

Write comment?

Hiasat

9 years ago, hide # |

← Rev. 2 →

It's can be solved by Back-tracking, Make Frequency array try get point then remove it's distances with other points you already choose from frequency array and repeat till you find valid answer

→ Reply

zacle_HardWorkPaysOff_

9 years ago, hide # ^ |

Could you explain me more deeper Hiasat? Please

→ Reply

Hiasat

9 years ago, hide # ^ |

← Rev. 2 →

There is an important observation which is First Point is 0 and Last Point is maximum among the distances.

Let call last point as LAST

What do after that is simply back-track which is call function and find maximum remaining distance let it call it MX

Now try Place point at (Last-MX) or at MX , there is 2 possible point for each step as it's either distance from last point or first point

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 1000000007;
const double PI = atan(1) * 4;
const int oo = 1000000000;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
#define pb push_back
#define all(c) (c).begin(),(c).end()

int T , n , d[18 * 18], freq[1000011], FN;

vector<int> all, ans;



bool find() {
	if (ans.size() == n) {
		sort(ans.begin(), ans.end());
		for (int i = 0; i < ans.size(); ++i) {
			if (i)
				printf(" ");
			printf("%d", ans[i]);
		}
		puts("");
		return true;
	}
	int mx = 0;
	for (int i = 0; i < all.size(); ++i) {
		if (!freq[all[i]])
			continue;
		mx = max(mx, all[i]);
	}
	for (int k = 0 ; k < 2 ; k++) {
		bool canTake = true;
		int point = k?mx:FN-mx;
		vector<int> took;
		for (int j = 0; j < ans.size(); j++) {
			int dist = abs(point - ans[j]);
			freq[dist]--;
			if (freq[dist] < 0)
				canTake = false;
		}
		ans.pb(point);
		if (canTake) {
			if (find())
				return true;
		}
		ans.pop_back();
		for (int j = 0; j < ans.size(); j++) {
			int dist = abs(point - ans[j]);
			freq[dist]++;
		}
	}
	return false;
}

int main() {
	//freopen("input.txt","r",stdin);
	scanf("%d", &T);
	while (T--) {
		memset(freq, 0, sizeof freq);
		ans.clear();
		all.clear();
		scanf("%d", &n);
		int m = (n * (n - 1)) / 2;
		ans.pb(0);
		FN = 0;
		for (int i = 0; i < m ; ++i) {
			scanf("%d", &d[i]);
			freq[d[i]]++;
			FN = max(FN, d[i]);
			all.pb(d[i]);
		}
		freq[FN]--;
		ans.pb(FN);

		sort(d, d + m);
		sort(all.begin(), all.end());
		all.resize(unique(all.begin(), all.end()) - all.begin());
		find();

	}
	return 0;
}

→ Reply