DCP - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice

Div-4 Contest
Div-3 Contest
Div-2 Contest
Div-1 Contest

Author: Agamya Yadav
Tester: Anshu Garg

DIFFICULTY:

EASY

PREREQUISITES:

Dynamic Programming

PROBLEM:

You are given N compounds numbered from 1 to N. The initial amount of the i^{th} compound is Q_i.

You are also given M thermal decomposition equations. Every equation is of the form:
C_0 \rightarrow W_1\cdot C_1 + W_2\cdot C_2 + \ldots + W_X\cdot C_X.

After Prolonged heating find the amount of each compound.

EXPLANATION:

It is simple forward dynamic programming.
Since, C_{i,j - 1} \lt C_{i,j} , we can say that a compound will decompose in higher indexed compound.
So, we can safely first decompose compound in order A_1, A_2,..., A_N.

We can complete equations in the order they are given as C_{i,0} \lt C_{i + 1, 0}.

Let dp[i] be amount of A_i at some point of time.

PseudoCode for dp can be viewed as:
Go from i = 1 to M:
\space Go from j = 1 to X_i:
\space \space \space \space Update dp[C_{i,j}] as (dp[C_{i,j}] + dp[C_{i,0}]) mod (10^9 + 7)

Finally, update all dp[C_{i,0}] = 0

TIME COMPLEXITY:

O(M + \sum_{1 \leq i \leq M}(X_i))

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
constexpr ll mod=1e9+7;


void solve(){
    int n,m;
    cin>>n>>m;
    
    vector<ll> dp(n + 1, 0);
    for(int i = 1; i <= n; i++)cin>>dp[i];

    vector<pair<ll, int>> adj[n + 1];
    while(m--){
        int c0, x;
        cin>>c0>>x;

        while(x--){
            int cj;
            ll wj;
            cin>>wj>>cj;
            adj[c0].push_back({wj, cj});
        }
    }
    
    set<int> st2;
    for(int c0 = 1; c0 <= n; c0++){
        set<int> st;
        for(int j = 0; j < adj[c0].size(); j++){
            ll wj = adj[c0][j].first;
            int cj = adj[c0][j].second;
            st.insert(cj);
            dp[cj] = (dp[cj] + wj * dp[c0]) % mod;
        }
        assert(st.size() == adj[c0].size());
        if(adj[c0].size() > 0){
            dp[c0] = 0;
            st2.insert(c0);
        }
    }

    for(int i = 1; i <= n; i++){
        cout<<dp[i]<<"\n";
    }

}

int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
        int t = 1;
        while(t--)solve();
        return 0;
}
Tester's Solution 
#include<bits/stdc++.h>
using namespace std ;

#define ll              long long 
#define pb              push_back
#define all(v)          v.begin(),v.end()
#define sz(a)           (ll)a.size()
#define F               first
#define S               second
#define INF             2000000000000000000
#define popcount(x)     __builtin_popcountll(x)
#define pll             pair<ll,ll>
#define pii             pair<int,int>
#define ld              long double

template<typename T, typename U> static inline void amin(T &x, U y){ if(y < x) x = y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x < y) x = y; }

#ifdef LOCAL
#define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 2401
#endif

long long readInt(long long l,long long r,char end){
    long long x = 0;
    int cnt = 0;
    int first =-1;
    bool is_neg = false;
    while(true) {
        char g = getchar();
        if(g == '-') {
            assert(first == -1);
            is_neg = true;
            continue;
        }
        if('0' <= g && g <= '9') {
            x *= 10;
            x += g - '0';
            if(cnt == 0) {
                first = g - '0';
            }
            ++cnt;
            assert(first != 0 || cnt == 1);
            assert(first != 0 || is_neg == false);
            
            assert(!(cnt > 19 || (cnt == 19 && first > 1)));
        } 
        else if(g == end) {
            if(is_neg) {
                x = -x;
            }
            assert(l <= x && x <= r);
            return x;
        } 
        else {
            assert(false);
        }
    }
}
string readString(int l,int r,char end){
    string ret = "";
    int cnt = 0;
    while(true) {
        char g = getchar();
        assert(g != -1);
        if(g == end) {
            break;
        }
        ++cnt;
        ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}

	
const int MOD = 1000000007;
// const int MOD = 998244353;
struct Mint {
    int val;
 
    Mint(long long v = 0) {
        if (v < 0)
            v = v % MOD + MOD;
        if (v >= MOD)
            v %= MOD;
        val = v;
    }
 
    static int mod_inv(int a, int m = MOD) {
        int g = m, r = a, x = 0, y = 1;
        while (r != 0) {
            int q = g / r;
            g %= r; swap(g, r);
            x -= q * y; swap(x, y);
        } 
        return x < 0 ? x + m : x;
    } 
    explicit operator int() const {
        return val;
    }
    Mint& operator+=(const Mint &other) {
        val += other.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    Mint& operator-=(const Mint &other) {
        val -= other.val;
        if (val < 0) val += MOD;
        return *this;
    }
    static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
           #if !defined(_WIN32) || defined(_WIN64)
                return x % m;
           #endif
           unsigned x_high = x >> 32, x_low = (unsigned) x;
           unsigned quot, rem;
           asm("divl %4\n"
            : "=a" (quot), "=d" (rem)
            : "d" (x_high), "a" (x_low), "r" (m));
           return rem;
    }
    Mint& operator*=(const Mint &other) {
        val = fast_mod((uint64_t) val * other.val);
        return *this;
    }
    Mint& operator/=(const Mint &other) {
        return *this *= other.inv();
    }
    friend Mint operator+(const Mint &a, const Mint &b) { return Mint(a) += b; }
    friend Mint operator-(const Mint &a, const Mint &b) { return Mint(a) -= b; }
    friend Mint operator*(const Mint &a, const Mint &b) { return Mint(a) *= b; }
    friend Mint operator/(const Mint &a, const Mint &b) { return Mint(a) /= b; }
    Mint& operator++() {
        val = val == MOD - 1 ? 0 : val + 1;
        return *this;
    }
    Mint& operator--() {
        val = val == 0 ? MOD - 1 : val - 1;
        return *this;
    }
    Mint operator++(int32_t) { Mint before = *this; ++*this; return before; }
    Mint operator--(int32_t) { Mint before = *this; --*this; return before; }
    Mint operator-() const {
        return val == 0 ? 0 : MOD - val;
    }
    bool operator==(const Mint &other) const { return val == other.val; }
    bool operator!=(const Mint &other) const { return val != other.val; }
    Mint inv() const {
        return mod_inv(val);
    }
    Mint power(long long p) const {
        assert(p >= 0);
        Mint a = *this, result = 1;
        while (p > 0) {
            if (p & 1)
                result *= a;
 
            a *= a;
            p >>= 1;
        }
        return result;
    }
    friend ostream& operator << (ostream &stream, const Mint &m) {
        return stream << m.val;
    }
    friend istream& operator >> (istream &stream, Mint &m) {
        return stream>>m.val;   
    }
};


int _runtimeTerror_()
{
    int n = readIntSp(1, 1e5), m = readIntLn(0, 1e5);
    vector<Mint> q(n+1);
    for(int i=1;i<=n;++i) {
    	if(i == n) {
    		q[i] = readIntLn(1, MOD - 1);
    	}
    	else {
    		q[i] = readIntSp(1, MOD - 1);
    	}
    }
    int sum_sz = 0;
    set<int> got;
    int prev = 0;
    for(int i=0;i<m;++i) {
    	int x;
    	x = readIntSp(1, n - 1);
    	assert(x > prev);
    	prev = x;
    	assert(!got.count(x));
    	got.insert(x);
    	int sz;
    	sz = readIntLn(1, n - x);
    	sum_sz += sz;
    	for(int j=1;j<=sz;++j) {
    		int w, c;
    		w = readIntSp(1, MOD - 1);
    		if(j == sz) {
    			c = readIntLn(1, n);
    		}
    		else {
    			c = readIntSp(1, n);
    		}
    		q[c] += Mint(q[x]) * w;
    		assert(c > x);
    	}
    	q[x] = 0;
    }
    for(int i=1;i<=n;++i) {
    	cout << q[i] << "\n";
    }
    assert(sum_sz <= 2e5);
    cerr << n << " " << m << " " << sum_sz << "\n";
    assert(getchar() == -1);
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef runSieve
        sieve();
    #endif
    #ifdef NCR
        initncr();
    #endif
    int TESTS = 1;
    //cin >> TESTS;
    while(TESTS--) {
        _runtimeTerror_();
    }
    return 0;
}
3

Actually its right. Look at it again. If you still don’t understand tell me, I’ll explain

1 Like
4

Isn’t sum(Xi) is O(N^2)

5

Can Anybody Please tell what is wrong in my code

#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define mod 1000000007

void solve(){
    int n,m;
    cin>>n>>m;
    vector<int>q(n);
    for(int i=0;i<n;i++){
        cin>>q[i];
    }

    vector<vector<int>>rxns(m);
    for(int i=0;i<m;i++){
        int start,num;
        cin>>start>>num;

        int x=2*num+2;
        rxns[i].resize(x);
        rxns[i][0]=start;
        rxns[i][1]=num;
        for(int j=2;j<x;j++){
            int inp;
            cin>>inp;
            rxns[i][j]=inp;
        }
    }

    for(int i=0;i<m;i++){
        int qIdx=rxns[i][0]-1,prods=rxns[i][1];
        int qCnt=q[qIdx];
        int x=(prods*2)+2;
        if(qCnt>0){
            q[qIdx]=0;
            for(int j=2;j<x;j+=2){
                int prodId=rxns[i][j+1]-1;
                q[prodId]+=rxns[i][j]*qCnt;
            }
        }
    }

    for(int i=0;i<n;i++){
        cout<<q[i]<<endl;
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
6

Yeah, I got, Thanks!

7

q[prodId]= (q[prodId] + rxns[i][j]*qCnt)%mod;

just %mod was missing from u r code .

8

In constraints it is given that \sum_iX_i \leq 2 \cdot 10^5.

9

where was it given that we can choose the order in which compounds are decomposed?
(that is first we have to follow equation 1 than 2 etc)
i thought the reactions should proceed according to order in which equations are given input

10

The problem conditions specify both that the decomposition only produces products with a higher index, and that the decomposition equations are given in ascending index order. Specifically that is given by these two lines in the constraints:

  • C_{i,j}<C_{i,j+1}, \forall (0≤j<X_i) and (1≤i≤M)
  • C_{i,0}<C_{i+1,0}, \forall (1≤i<M)

A slightly more interesting problem is to write your code without assuming either of those things, although to get a reliable finite answer the decomposition network needs to be a directed acyclic graph (no directed loops).

11 
#include<bits/stdc++.h>
using namespace std;

const long long p = 1e9+7;

void prnt(vector<long long> v){
	for (int i = 0; i < v.size(); ++i)
		cout<<v[i]<<endl;
}

int main(){
	long long n,m; cin>>n>>m;
	vector<long long> init;
	init.push_back(0);
	for(int i = 0; i < n; i++){
		long long x; cin>>x;
		init.push_back(x);
	}
	for (int i = 0; i < m; ++i){
	long long a,b; cin>>a>>b;
		for (int i = 0; i < b; ++i){
			long long r,nu; cin>>r>>nu;
			init[nu] += (r*init[a]) %p;
		}
		init[a] = 0;
	}
	auto it = init.begin();
	init.erase(it);
	prnt(init);
}

Why this code only passes the last test case.
I am beginner and dont know dp, so i tried to solve it without dp.
can someone help

P.S. first comment on discuss.codechef

12

init[nu] += (r*init[a]) %p;

Here init[nu] can possibly be greater than p. Hence, could possibly, not be the expected value modulo p. Following is a quick fix

init[nu] = (init[nu] + r * init[a]) % p;

Above change gives Answer Correct.

TIP : Don’t rush while coding. It is worth assessing every line of code, while you are coding it.

1 Like