2018-2019 ACM-ICPC Brazil Subregional Community Editorial

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	151

Since the 2018-2019 ACM-ICPC Brazil Subregional Contest doesn't have an Official Editorial, I propose that we make an "Community Editorial".

B — Nim

We can think of every position [i, 0], [0, i], [i, i] as "insta-winning" positions. To model so, we can give them a very high Grundy number, so they doesn't conflict with any other possible Grundy number. That way, the cells that can only move you to an "insta-winning" cell, recieve an Grundy number of 0, meaning that they are losing positions.

After that, we can preprocess all possible positions and get it's Grundy number.

The final answer is just the nim-sum of every starting ball.

Accepted code

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int estados[101][101] = {};

    bool apareceu[1000] = {};

    auto mex = [&](int di, int dj)
    {
        memset(apareceu, 0, sizeof(apareceu));

        for(int i = 0; i < di; i++)
            apareceu[estados[i][dj]] = true;

        for(int j = 0; j < dj; j++)
            apareceu[estados[di][j]] = true;

        int mini = min(di, dj);

        for(int i = 1; i <= mini; i++)
            apareceu[estados[di - i][dj - i]] = true;

        for(int i = 0; i < 1000; i++)
            if(!apareceu[i])
                return i;
    };

    estados[0][0] = 999;
    
    for(int i = 1; i <= 100; i++)
        estados[i][0] = estados[0][i] = estados[i][i] = 999;
    
    for(int i = 1; i <= 100; i++)
    {
        for(int j = 1; j <= 100; j++)
        {
            if(i != j)
                estados[i][j] = mex(i, j);
        }
    }
    
    int n, v = 0, a, b;

    cin >> n;

    while(n--)
    {
        cin >> a >> b;

        if(estados[a][b] == 999)
        {
            cout << "Y" << endl;

            return 0;
        }

        v ^= estados[a][b];
    }
    
    cout << (v == 0 ? "N" : "Y")  << endl;
}

C — Sweep line

To make things easier, we can think of every cut as an straight line. First, we need to observe two things:

Every line splits an area into two new areas.
Every line intersection splits an area into two new areas.

Then, the answer must be h + v lines from the first observation + h * v lines from the second observation (every vertical line intersects with every horizontal line) + the number of intersections of lines in the same orientation.

It's easy to see that lines of the same orientation can only intersects if (start_i < start_j and end_i > end_j) or (start_i > start_j and end_i < end_j).

One fast way to count how many times the above is true is to use an sweep line (from left to right, bottom to top, etc).

Accepted code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<
    int,
    null_type,
    greater<int>,
    rb_tree_tag,
    tree_order_statistics_node_update>
statisticsTree;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    long long h, v;

    cin >> h >> v >> h >> v;

    vector<pair<int, int>> horizontais(h), verticais(v);

    for(auto &it : horizontais)
        cin >> it.first >> it.second;

    sort(horizontais.begin(), horizontais.end());

    for(auto &it : verticais)
        cin >> it.first >> it.second;

    sort(verticais.begin(), verticais.end());

    long long r = (h + 1) * (v + 1);

    statisticsTree th, tv;

    for(auto &it : horizontais)
    {
        r += th.order_of_key(it.second);

        th.insert(it.second);
    }

    for(auto &it : verticais)
    {
        r += tv.order_of_key(it.second);

        tv.insert(it.second);
    }

    cout << r << endl;
}

D — Ad hoc

Just count the number of numbers ! = 1

Accepted code

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, r = 0, e;
    
    cin >> n;

    while(n--)
        cin >> e, r += (e != 1);

    cout << r << endl;
}

E — String

Just follow the statement.

Accepted code

#include <bits/stdc++.h>

using namespace std;

int main()
{
    string entrada, crib;
    int r = 0;
    
    cin >> entrada >> crib;

    int lim = entrada.size() - crib.size() + 1;

    for(int shift = 0; shift < lim; shift++)
    {
        for(int i = 0; i < crib.size(); i++)
            if(entrada[shift + i] == crib[i])
                goto next;

        r++;
        
        next:;
    }

    cout << r << endl;
}

F — DP

We can model the problem with the following indexes: The stages that we've already seen and the current time.

Since there are at maximum 10 stages, we can store the first index in a bitmask.

Then, we can apply the following recurrence:

dp[0][0] = 0;

for(i : possibleBitmasks)
    dp[i][0] = -infinity

for(j : [1, 86400])
    for(i : possibleBitmasks)
        dp[i][j] = max(dp[i][j], dp[i][j - 1])                                    // watch nothing

        for(k : [0, number of stages - 1])
            if(i & (1 << k))                                                      // the bit k is on
                for(s : stages[k].shows)
                    if(s.endTime == j)
                        dp[i][j] = max(dp[i][j],
                                   max(dp[i][s.initTime] + s.songs,               // been on this stage before
                                       dp[i ^ (1 << k)][s.initTime] + s.songs))   // first time on this stage

But it's not fast enought :(

To fix it, "skip" to the relevant moments (aka, the end time or the start time of an show) and calculate only the values of the relevant moments.

Accepted code

#include <bits/stdc++.h>

using namespace std;

struct show
{
    int i, f, o;

    bool operator<(const show &a) const
    {
        return f < a.f;
    }
};

vector<pair<int, int>> pd[(1 << 10) + 1];
   
int main()
{
    vector<vector<show>> shows;

    int n, m;
    
    cin >> n;

    shows.resize(n);

    vector<pair<int, int>> events;

    for(int i = 0; i < n; i++)
    {
        cin >> m;

        shows[i].resize(m);

        for(auto &it : shows[i])
            cin >> it.i >> it.f >> it.o, events.emplace_back(it.f, i);

        sort(shows[i].rbegin(), shows[i].rend());
    }

    sort(events.rbegin(), events.rend());

    int maxi = (1 << n);

    pd[0].emplace_back(0, 0);

    while(events.size())
    {
        int k = events.back().second;
        events.pop_back();

        for(int i = 1; i < maxi; i++)
        {
            if((i & (1 << k)) == 0)
                continue;
            
            auto &shw = shows[k].back();

            int r = -(1 << 30);

            if(pd[i].size())
                for(auto &it : pd[i])
                    if(it.first <= shw.i)
                        r = max(r, it.second + shw.o);
            
            if(pd[i ^ (1 << k)].size())
                for(auto &it : pd[i ^ (1 << k)])
                    if(it.first <= shw.i)
                        r = max(r, it.second + shw.o);

            if(r != -(1 << 30))
                pd[i].emplace_back(shw.f, r);
        }
        
        shows[k].pop_back();
    }
    
    int r = -(1 << 30);

    if(pd[maxi - 1].size())
        for(auto &it : pd[maxi - 1])
            r = max(r, it.second);

    cout << (r < 0 ? -1 : r) << endl;
}

I — Ad hoc

We can think of the lights as "bits" in an bitset, and the light switches as xor operations. After that, it's kinda easy to notice that we'll cicle through all possible values after 2 * M operations.

Then, we just simulate what is described in the statement (with an limit of 2 * M operations) and print the result.

Accepted code

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    bitset<1000> inicial;

    int n, m, l, e, r;

    cin >> m >> n >> l;

    vector<bitset<1000>> interruptores(m);

    while(l--)
        cin >> e, inicial[e - 1] = 1;

    for(auto &it : interruptores)
    {
        cin >> l;

        while(l--)
            cin >> e, it[e - 1] = 1;
    }

    int lim = 2 * m;

    for(r = 0; r < lim; r++)
    {
        inicial ^= interruptores[r % m];

        if(inicial.none())
            break;
    }

    cout << (r != lim ? r + 1 : -1) << endl;
}

Rev.	By	When	Δ	Comment
en3	marcosvcloures	2018-09-19 20:22:13	126
en2	marcosvcloures	2018-09-19 20:15:44	43
en1	marcosvcloures	2018-09-19 20:11:21	8886	Initial revision (published)

B — Nim

C — Sweep line

D — Ad hoc

E — String

F — DP

I — Ad hoc

History