2018-2019 ACM-ICPC Brazil Subregional Community Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	160
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

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