Editorial for Raider


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Alright, so this is by far the toughest problem in this contest. First we need to notice that a province is simply a Strongly Connected Component (SCC). Secondly, notice that if we loot from a province, might as well take everything there! Computing the SCC's will make your work a looootttttt easier. So, we will find the SCC's, and the summed loot values for each component. This can be done using Kosaraju's or Tarjan's algorithm. After finding the SCC's, we should reconstruct the graph, which will become a Directed Acyclic Graph, and then suddenly doing DP on it is much easier. The DP part of this question is asking the classic maximum sum question (S5 of 2015 CCC was also a variant of this), except it's on a graph, and we need to count the number of ways as well. To do this, we use DFS, keeping track of most loot we can grab at each node, and how many ways we can do it. Our state must be [node number, whether or not we want to take the loot at this province]. For example, dp[3][0] represents the maximum loot we can get at province 3 if we do not take the loot there. From this, the transition formula for max loot is quite simple:

for each node v that is reachable from node u:
        dp[u][1] = max(dp[v][0] + val[u], dp[u][1])
        dp[u][0] = max(dp[v][1], dp[u][0])

To take care of number of ways, we simply add an extra condition to each case:

for each node v that is reachable from node u:
        if (dp[v][0] + val[u] > dp[u][1])
            dp[u][1] = dp[v][0] + val[u]
            cnt[u][1] = cnt[v][0]
        else if (dp[v][0] + val[u] == dp[u][1])
            cnt[u][1] += cnt[v][0]
        if (dp[v][1] > dp[u][0])
            dp[u][0] = dp[v][1]
            cnt[u][0] = cnt[v][1]
        else if (dp[v][1] == dp[u][0])
            cnt[u][0] += cnt[v][1]

The first case is if we will take from province u, which means we can't take from any of its children. The second case if for if we do not take from province u, so we should take from its children. The key observation in handling number of ways has the same idea as J5 - nightmare-a-thon: Whenever we find a new best form child node v, the new number of ways should be the number of ways that best value could be found at node v. Whenever we find an equal best, we need to accumulate the number of ways instead.

Below is Ahmed's solution in C++, using Kosaraju's algorithm for SCCs.

#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <set>

using namespace std;

const int maxn=1000005,inf=1000000000, mod = 1000000007;
int a,b,n,m,u,v,k,curr,val[maxn],comp[maxn],sval[maxn],ord;
bool flag[maxn];
pair<int,int> dp[maxn][2];
vector<int> em,graph[maxn],rgraph[maxn],sgraph[maxn];
vector<vector<int> > component;
queue<int> q;
stack<int> s;
set<int> det;

pair<int,int> query(int curr,int choose) {
    if (curr == comp[n]) {
        if (choose)
            return make_pair(sval[curr],1);
        return make_pair(0,1);
    }
    if (dp[curr][choose] != make_pair(-1,-1))
        return dp[curr][choose];
    pair<int,int> ans = make_pair(-inf,0),hold;
    for (int i = 0; i < sgraph[curr].size(); i++) {
        if (choose) {
            hold = query(sgraph[curr][i],0);
            hold.first+=sval[curr];
            if (hold.first>ans.first)
                ans = hold;
            else if (hold.first == ans.first) {
                ans.second += hold.second;
                ans.second %= mod;
            }

        }
        hold = query(sgraph[curr][i],1);
        if (hold.first > ans.first)
            ans = hold;
        else if (hold.first == ans.first) {
            ans.second += hold.second;
            ans.second %= mod;
        }
    }
    dp[curr][choose]=ans;
    return ans;
}

void dfs(int curr) {
    for (int i = 0;i < graph[curr].size(); i++) {
        if (!flag[graph[curr][i]]) {
            flag[graph[curr][i]]=true;
            dfs(graph[curr][i]);
        }
    }
    s.push(curr);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i = 0; i <= n; i++)
        dp[i][0] = dp[i][1] = make_pair(-1,-1);
    for (int i = 1; i <= n; i++)
        scanf("%d",&val[i]);
    while (m--) {
        scanf("%d%d",&u,&v);
        graph[u].push_back(v);
        rgraph[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
        if (!flag[i]) {
            flag[i] = true;
            dfs(i);
        }
    for (int i = 1; i <= n; i++)
        flag[i]=false;
    while (!s.empty()) {
        u=s.top();
        s.pop();
        if (!flag[u]) {
            component.push_back(em);
            flag[u]=true;
            q.push(u);
            while (!q.empty()) {
                u=q.front();
                q.pop();
                component[component.size()-1].push_back(u);
                sval[ord]+=val[u];
                comp[u]=ord;
                for (int i=0;i<rgraph[u].size();i++) {
                    v=rgraph[u][i];
                    if (!flag[v]) {
                        flag[v]=true;
                        q.push(v);
                    }
                }
            }
            ord++;
        }
    }
    for (int i = 0; i < component.size(); i++) {
        det.clear();
        u = i;
        for (int j = 0; j < component[i].size(); j++) {
            for (int k = 0; k < graph[component[i][j]].size(); k++) {
                v = comp[graph[component[i][j]][k]];
                if (u != v && det.find(v) == det.end()) {
                    det.insert(v);
                    sgraph[u].push_back(v);
                }
            }
        }
    }
    pair <int,int> final = query(comp[1],1);
    printf("%d %d\n",final.first,final.second);
}

Comments

There are no comments at the moment.