## 1047 - Zones

Moderator: Board moderators

matheusdallrosa
New poster
Posts: 11
Joined: Fri Nov 08, 2013 11:04 pm

### Re: 1047 - Zones

The post was removed, i had an error in the way that i counted the intersections.

rcanepa
New poster
Posts: 6
Joined: Thu Feb 26, 2015 4:59 pm

### Re: 1047 - Zones

I have tested all the cases of the post and more on udebug.com (created by myself), however, I can't find bad answer from my code. Can anyone help me with a tricky edge case?...

I am leaving my solution here:

Code: Select all

``````#include <bits/stdc++.h>

using namespace std;

#define ALL(v) (v).begin(), (v).end()
#define ALLR(v) (v).rbegin(), (v).rend()
#define PB push_back
#define PRINTENDL(x) cout << x << endl
#define RA(x) begin(x), end(x)
#define REP(i, a, b) for(int i = (a); i < int(b); ++i)
#define RREP(i, a, b) for(int i = (a) - 1; i >= int(b); --i)
#define SZ(x) ((int) (x).size())
#define TRAV(it, v) for(auto it = (v).begin(); it != (v).end(); ++it)
#define WHAT_IS(x) cerr << #x << " is " << x << endl;

typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<pair<int,int>> vpi;
typedef vector<pair<int,pair<int,int>>> vppi;
typedef vector<double> vd;
typedef vector<ll> vll;

bool used;
int towers;

vi vans;
int ans;

// planned: towers planned to be built
// builded: towers to build
// counter: towers in the actual solution
// vc_areas: common service areas information
void solve(int planned, int builded, int counter, vector<pair<vector<int>,int>> &vc_areas)
{
if (counter == builded)
{
// cout << "Solution found:";
int total = 0;
vi path;
for (int i = 0; i < planned; i++)
{
if (used[i])
{
// cout << " " << i + 1;
total += towers[i];
path.PB(i + 1);
}
}
for (auto csa: vc_areas) // common areas
{
int valid = 0;
for (auto a: csa.first) // tower of a common area
{
for (auto tower: path)
{
if (tower == a)
valid++;
}
}
if (valid > 1)
total -= (valid - 1) * csa.second;
}
// cout << " = " << total << endl;
if (total == ans && !vans.empty())
{
if (vans < path)
path = vans;
else
vans = path;
}
if (total > ans)
{
ans = total;
vans = path;
}
}
else
{
for (int i = 0; i < planned; i++)
{
if (!used[i])
{
used[i] = true;
solve(planned, builded, counter + 1, vc_areas);
used[i] = false;
}
else break;
}
}
}

int main(int argc, char const *argv[])
{
int planned, builded, cases = 1;
while (cin >> planned >> builded)
{
if (planned == 0 && builded == 0)
return 0;

if (cases > 1)
cout << endl;

ans = 0;
fill(used, used + 25, false);
fill(towers, towers + 25, 0);

for (int i = 0; i < planned; i++)
{
int t;
cin >> t;
towers[i] = t;
}

int csa;
cin >> csa;
vector<pair<vector<int>,int>> vc_areas; // common service areas
for (int i = 0; i < csa; i++)
{
int na;
vi tmp;
cin >> na;
while (na--)
{
int t;
cin >> t;
tmp.PB(t);
}
int shared_people;
cin >> shared_people;
vc_areas.PB({tmp, shared_people});
}

solve(planned, builded, 0, vc_areas);

cout << "Case Number  " << cases << endl;
cout << "Number of Customers: " << ans << endl;
cout << "Locations recommended:";
for (auto tower: vans)
cout << " " << tower;
cout << endl;

cases++;

}
return 0;
}
``````
I appriciate any help!

damien_g
New poster
Posts: 8
Joined: Sun Oct 05, 2014 5:53 pm

### Re: 1047 - Zones

Is it possible to be more specific for the output format?
The problem is great, but getting 3 PE before AC isn't great. So, to resume, the format is:
- "Case NumberXX%d\n" : so always 2 spaces (I denoted them with 'X') before the number of the test case
- "Number of Customers: %d\n" : only one space
- "Locations recommended:"
- a list with " %d" for you positions
- "\n\n", two blanklines (even after the last test block)

Examiner
New poster
Posts: 28
Joined: Thu Feb 19, 2004 1:19 pm

### Re: 1047 - Zones

I've found the following formula for calculating overlapping areas from https://blog.csdn.net/bigdata_lijun/art ... s/11024721:

Suppose there are m overlapping regions, where o to o[m] are sets of regions, from input. The numbers of customers are stored in c to c[m], also from input. dp is the set of currently selected regions.

Code: Select all

``````for i = 1 to m
f = size of overlap between dp and o[i]
if f > 0
total -= c[i] * (f - 1)``````
Why is this the case? I mean why f - 1? Anyway, the way of specifying overlaps is very weird to me.