1047 - Zones

[matheusdallrosa]

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

[rcanepa]

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[25];
int towers[25];

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]

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]

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[1] to o[m] are sets of regions, from input. The numbers of customers are stored in c[1] 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.