2018-2019 ACM-ICPC Brazil Subregional Community Editorial

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	nor	152

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;
}

#include <bits/stdc++.h> #define PI 3.14159265358979323846 #define EPS 1e-6 #define INF 1000000000 // MAXIMIZAR f(x) == MINIMIZAR -f(x) #define _ ios_base::sync_with_stdio(0), cin.tie(0), cin.tie(0), cout.tie(0), cout.precision(15); #define FOR(i, a, b) for(int i=int(a); i<int(b); i++) #define FORC(i, a, b) for(int i=int(a); i>=int(b); i--) #define pb push_back clock_t t_; using namespace std; typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<ii> vii; typedef vector<vi> vvi; #define MAXN 2*1000+100 #define MOD 1000000007 struct edge { int a, b, cap, flow, time; }; int n, s, t, d[MAXN], ptr[MAXN], q[MAXN]; vector<edge> e, e2; vector<int> g[MAXN]; void add_edge (int a, int b, int cap) { edge e1 = { a, b, cap, 0 , 0}; edge e2 = { b, a, 0, 0, 0 }; g[a].push_back ((int) e.size()); e.push_back (e1); g[b].push_back ((int) e.size()); e.push_back (e2); } void add_edgeH(int a, int b, int cap, int time){ edge e1 = {a,b,cap,0,time}; e2.pb(e1); } bool bfs() { int qh=0, qt=0; q[qt++] = s; memset (d, -1, sizeof(d)); d[s] = 0; while (qh < qt && d[t] == -1) { int v = q[qh++]; for (size_t i=0; i<g[v].size(); ++i) { int id = g[v][i], to = e[id].b; if (d[to] == -1 && e[id].flow < e[id].cap) { q[qt++] = to; d[to] = d[v] + 1; } } } return d[t] != -1; } int dfs (int v, int flow) { if (!flow) return 0; if (v == t) return flow; for (; ptr[v]<(int)g[v].size(); ++ptr[v]) { int id = g[v][ptr[v]], to = e[id].b; if (d[to] != d[v] + 1) continue; int pushed = dfs (to, min (flow, e[id].cap - e[id].flow)); if (pushed) { e[id].flow += pushed; e[id^1].flow -= pushed; return pushed; } } return 0; } int dinic() { int flow = 0; for (;;) { if (!bfs()) break; memset (ptr, 0,sizeof(ptr)); while (int pushed = dfs (s, INF)) flow += pushed; } return flow; } vi gasS, refin; void createG(int m){ e.clear(); FOR(i,0,MAXN) g[i].clear(); FOR(i,0,e2.size()){ if (e2[i].time<=m) { add_edge(e2[i].a, e2[i].b, e2[i].cap); } } } void addNormalEdges(int p, int r){ FOR(i,1,r+1){ add_edge(s, i*2+1, refin[i-1]); } FOR(i,1,p+1){ add_edge(i*2, t, gasS[i-1]); } } int main(int argc, const char * argv[]) { _ #ifdef USE_INPUT_FILE freopen("input.txt", "r", stdin); #endif #ifdef USE_OUTPUT_FILE freopen("output.txt", "w", stdout); #endif t_ = clock(); int p,r,c; cin >> p >> r >> c; int x,y,z, sume=0; FOR(i,0,p){ cin >> x; sume+=x; gasS.pb(x); } FOR(i,0,r){ cin >> x; refin.pb(x); } int time=-1; FOR(i,0,c){ cin >> x >> y >> z; add_edgeH(y*2+1, x*2, INF, z); time = max(z,time); } int left = 0, right = time; s = 0, t = 1; createG(right); addNormalEdges(p, r); if (dinic()!=sume) { cout << -1 << endl; return 0; } while (left<=right) { int m = (right+left)/2; createG(m); addNormalEdges(p, r); if (dinic()==sume) { right = m-1; }else{ left=m+1; } } cout << right+1 << endl; #ifdef USE_OUTPUT_FILE freopen("diff.txt", "w", stdout); system("diff -y output.txt expected_output.txt"); #endif t_ = clock()-t_; cerr << setprecision(9) << fixed << ((float)t_ / CLOCKS_PER_SEC) << endl; return 0; }

Комментарии (38)

Показать архивные | Написать комментарий?

tfg

6 лет назад, # |

← Rev. 3 →

+10

G: For a number x, you can check if you can use edges <= x to supply everything needed using max flow. That means that you can use binary search + max flow to solve it.

H: Build the KMP automaton for the pattern. Let's say that for a range you have to[i] (meaning from state == i you pass through the range and end up in state to[i]) and cost[i] (meaning from state == i you pass through the range and find cost[i] occurences of the pattern). You can merge 2 ranges in O(|automaton|). This means you can build a segment tree based on the automaton and use it with HLD to solve the problem. The update works in O(logn * |automaton|) and the path query works in O(log^2n) since you start in state 0 and just need to know the answer to the queries in the current state for the "cover" of the queried segments.

Alternative solution for B: Since for (i, i), (0, i) and (i, 0) the game is over, you can consider it nim 0 and calculate it for the rest. Doing the equivalence to a nim game, the constraint that some game having 0 in it means that the current player wins means that it's equivalent to a nim game with the piles having 1 less stone.

→ Ответить

Juniorandrade

6 лет назад, # ^ |

← Rev. 2 →

It could be done using hash instead automaton, right?

Maybe, but it would be a completely different solution. What are you thinking about? Something like: on update, you process the substrings that changed and on query you try to slot a prefix with a suffix resulting in O(logn * automaton) per query/update? This might work.

Yes, exactly. Each segtree node has a prefix and suffix rolling hash, and the merge between two nodes could be done in O(2 * |pattern|).

Oh... in that case the query would work in O(log^2 * |pattern|) and it might TLE. In this solution you don't need a segment tree for the hashes, you have a range in the chain that you can have patterns fully in a chain so you can use a seg tree for that but for merging prefix/suffix you can use the prefix/suffix of the range of the chain itself instead of using O(log) ranges from the seg tree.

JATC

I used binary search + max flow and got TLE. Then I removed the binary search and instead of using BFS to find the residual path, I used a priority first search and still got TLE. So how do I improve the performance?

Never mind, changing form Ford-Fulkerson to Dinic got me AC.

+13

L: For each query (a, b, c, d), set 1 throught the path (a, b), and after that, sum all nodes values on the path between (c, d). It can be done with a Segment Tree + HLD. The solution complexity is O(nlog(n) + qlog²(n))

Did you manage to make log^2(n) queries pass? I know quite a few teams that didn't pass using that exact same solution but they used recurvise seg trees, maybe the iterative one passes?

+11

Yep, i got AC using standard recursive segment tree with lazy propagation. I didn't make any optimization in the code. Actually, I didn't see the timelimits, because if I had seen, probably i never had coded it.

My implementation use just one segtree to take care about all chains. I don't know if use this method is better than use one segtree for each heavy chain.

That's not the difference since I know multiple teams that used that same method. Log^2(N) queries seem to depend on the constant of the seg tree implementation. That being said there's a way to eliminate a log from it.

In a chain, index the vertices starting from 0. In each chain you visit in the first path, you have a range [l, r] that you visit. In the second path, you visit the chains and have other [l, r] that you can use to make the intersection in each chain in O(1). This also eliminates the need for coding a seg tree.

CoderAnshu

4 года назад, # ^ |

We also managed to pass HLD without even a single optimization. But will u please explain the intended solution , we thought a lot but could not come up. I think it will involve lot of if else statements , i am curious if a cleaner solution is available or not.

← Rev. 4 →

Nvm, thought this chain was about problem H

In cf gym the min TLE is 0.5s, the TL in the competition was like 0.1s or 0.2s so keep that in mind...

To solve in O(logN): if you use the smart hld, you query on ranges. So a path query is a set of ranges. If you have those sets ordered, you want the intersection of those sets that can be done in a similar way to merge from merge sort (some kind of sweep line maybe)

Yaa my solution passed in 0.3s which is obviously too slow for this TL.

Ohhhh cool!! Merging using merge sort can help for sure.

Thanks a lot.

bicsi

Another (maybe easier) solution that works in $\text{[math]}$ (possibly even O(n + q), but that's not relevant), is the following 2-step reduction using inclusion-exclusion:

Say A = (a₁, b₁) and B = (a₂, b₂) and you have a function Solve(A, B).

Let A₁ = (a₁, lca(a₁, b₁)) and A₂ = (b₁, lca(a₁, b₁)). Then Solve(A, B) = Solve(A₁, B₁) + Solve(A₂, B₁) + Solve(A₁, B₂) + Solve(A₂, B₂). Now all paths are of type (node, ancestor)
Let A = (a₁, b₁) and B = (a₂, b₂) where b₁ is an ancestor of a₁ (same for the right hand side). If a₁ is not the root, then Solve(A, B) = Solve((root, a₁), B) - Solve((root, b₁), B). Do the same for B.
Now all queries are of type (root, node). However, the answer to Solve((root, a), (root, b)) is just depth(lca(a, b)).

Some nodes will be counted twice, but that can easily be fixed in the implementation.

Arthurvtr

This problem has many solutions. That's how I've solved during the contest:

For each query(a, b, c, d).

let X = dist(a, b) + dist(c, d).
let Y = min( dist(a, c) + dist(b, d), dist(a, d) + dist(b, c) ).
If Y > X, then answer is 0. Otherwise, answer will be (X-Y)/2 + 1.

Zedmey97

How did you pass the time limit with that method? It is supposed that I do the same :/

https://pastebin.com/Qs05zWRr

Using LCA, it's possible to get the distance between any two nodes of a tree in O(logN). So, final complexity will be only O(Q*logN), pretty fast for the problem constraints.

Your solution runs in O(Q*N).

coderick14

The solution looks really elegant. Could you please give a brief explanation as to how this works?

laderlappen

Problem C can be interpreted as an Inversion Count problem, since you want to count intersection of Horizontal and Vertical lines.

Horizontal lines cross if and only if they switch positions (I mean, their order from ascending Y position, for example) from the left to the right side. This argument follows to Vertical lines also.

You can implement the Inversion Count using Fenwick Tree or Merge Sort. I'm not sure if the TL fits to use map implementation for Fenwick, since it's kinda tight (0.5s). If you get TLE in this case, just make a coordinate compression.

des1997

where can i try submit? any link.

http://codeforces.me/gym/101908

Keep in mind that the TL during contest might be stricter/looser. Not sure.

Roberio

M: essentially, every clause must have an odd number of true literals. That means that if the literals of a clause are l₁, ..., l_k (k ≤ 3), then $\text{[math]}$ . We can rewrite that in terms of the variables by taking care of negations. For each negation, the right side of the equation flips, so we have $\text{[math]}$ . So we have a system of m equations in $\text{[math]}$ . This can be solved with Gaussian elimination in O(n³) and bitsets can be used to speed it up. We still need to print the max lex solution, though. We can ensure that by reversing the variable indices before applying the elimination, and then assigning true greedily to free variables when doing the backward phase.

Sam

Implementation for G using dinic's algorithm and binary search

pastebin

jeoj

Could somebody test if the problem G have a solution in JAVA? I submitted two times, the first with Edmonds-Karp+Binary Search and the second with Dinic+Binary Search, both give me TLE.

I guess that the official time limit to JAVA in this problem is 2.0 seconds, maybe TL need some adjustment here in codeforces.

You can try submit the same problem here, with the correct time limit to JAVA: https://www.urionlinejudge.com.br/judge/pt/problems/view/2882

You can see the official time limits to JAVA in this problemset here: http://maratona.ime.usp.br/prim-fase18/info_maratona.pdf

KhaledKEE

K: First observe that R is not less than 1 and the X,Y is not greater than 25 in absolute value. That means that there can only be around 200 circles pair-wise non-intersecting of similar radii (the bound is actually very loose and gets smaller with for larger radius).

We know that two circles are intersecting (with the constraints of the problem) if and only if R ≤ r + d (for R ≥ r), where d is the distance between the two circles. And we know that the maximum distance is $\text{[math]}$ . So if we sort the circles by the radius and kept two pointers representing a range degined by i (the current circle index) and j (the index of the circle with the minimum radius such that $\text{[math]}$ ), we can check circle i with other circles in this range. Because of the observation in the first paragraph we know that the number of misses in this range is very small, and we can break when we pass the 2N intersections limit.

Submission: 43245038

yujinwunz

How do you deal with ̶1̶5̶0̶0̶0̶0̶ 25000 concentric circles with very similar radii? If I'm understanding correctly then the pointers i and j will be very far apart and checking each circle will take O(N).

Or does that case not show up?

Edit: Oh and there are actually zero circles pair-wise non-intersecting with the same radius since all of them are orbits around the origin, which I forgot about halfway through reading the problem.

Edit 2:

I just submitted the solution described which AC'd and indeed it seems like the tests are weak and just didn't include the concentric circle case at all. The case generated by:

print 150000
for i in range(150000):
    print 0, 0, 1.0 + 0.001 * i

easily TLE's lol

Nishkarsh_Arora

3 года назад, # ^ |

So, can you please share the solution which could pass this test case?

snacache

+20

I spent a lot of time thinking about how to solve E, just to realize it had many accepted submissions and it was obviously a simulation problem.

When I started competitive programming, a solution with O(n²) complexity wouldn't be accepted for problems with n ≤ 10⁴.

Good thing the problem is actually easily solvable in a better complexity (or constant).

O(n^2 / 32) solution: use bitsets

O(alphabet * n * logn) solution: use FFT for each letter to count the number of matches in every position.

I knew it was solvable using FFT, but I had only one accepted problem (C) and I thought that convolutions was too overkill, given that it had many accepted submissions.

vntshh

How to solve A and J?

danya090699

A: Let dx=abs(x1-x2) and dy=abs(y1-y2). First count answer for pairs where dx>0 and dy>0, dx and dy must be coprime, iterate by dx from 1 to N-1. For a fixed dx we need to know the range [ly, ry], of possibe dy, so the distance between points is in range [L, R], we can find ly, ry using binary search or just moving pointers. Then let's count the number of integers in range [ly, ry] coprime with dx, using inclusion-exclusion in O(2 ^ number of distinct prime divisors of dx) and also count their sum. Now add to the answer (N-dx) * (M * count — sum) * 2. When dx=0 or dy=0 the other one can only be 1. It is possible when L=1, then you have to add to answer (N-1) * M + (M-1) * N and you are done.

naumazeredo

The J problem is calculating the Steiner Tree in graph. This problem is NP-complete (that's a reason to have such small constants).

The solution is basically explained on this tutorial: https://www.youtube.com/watch?v=BG4vAoV5kWw

The idea is to build a dynamic programming DP[i][m], where i is which vertex you're at and m is a bitmask of which capitals you joined. You can preprocess the APSP (Floyd-Warshall, or many Dijkstras because of the small constants) and calculate DP[i][m] like this: DP[i][m] = min(DP[i][s] + DP[j][m - s] + dist[i][j]), with s being a submask of m. In the end the complexity is O(3^k * n²). (The tutorial says you can have O(3^k * n) complexity, but I don't know exactly how yet).

To get O(3^k * n) complexity, you do 2 transitions.

O(3^k * n) transition using submasks

O(2^k * n^2) transition, that is, O(n^2) transition for each mask.

MD0

2 года назад, # ^ |

can u help me??! my code getting wrong on test 13.

or if u can send me your code

Блог пользователя marcosvcloures

B — Nim

C — Sweep line

D — Ad hoc

E — String

F — DP

I — Ad hoc