The Stark Reactor

Author: chef_hamster, ultimate_st
Tester: chef_hamster, ultimate_st
Editorialist: ultimate_st




You will be given an array A of K types of radioactive decays where each decay is a pair of values a_i and b_i. In each radioactive decay, mass number of a atom decreases by a_i and atomic number decreases by b_i. Then you will be given Q queries, and for each query you will get mass and atomic numbers of the initial atom M_1, Z_1 and desired(special) mass and atomic number of special atom M_2, Z_2. You have to print the number of ways to obtain special element from initial element via the K given radioactive decays. Since the answer can be very large, print it by taking modulo 10^9 + 7.

NOTE- Order of the Decay doesn’t matter.
decay_1 β†’ decay_2 β†’ decay_3 then all possible permutations of this chain reaction will be considered same, i.e., decay_2 β†’ decay_1 β†’ decay_3 , decay_1 β†’ decay_3 β†’ decay_2 , decay_2 β†’ decay_3 β†’ decay_1 , decay_3 β†’ decay_1 β†’ decay_2 and decay_3 β†’ decay_2 β†’ decay_1 all are same.


  • Dynamic Programming.
  • Modular arithmetic
  • Pinch of common sense :slight_smile:


Hint 1

Try thinking of a recursive solution by taking difference of M_1 , M_2 and Z_1 , Z_2 and reducing it to zero.

Hint 2

dp [ difference of M_1 and M_2 ] [ difference of Z_1 and Z_2 ] [ current index in decay array ] = No. of ways of making that difference zero.


A simple approach that comes across our mind is to use all types of decays available to convert M_1 to M_2 and Z_1 to Z_2. This can be done easily by taking there differences and making it zero.


Since it is a counting number of ways type of a problem, we will return be returning 1 whenever our variable reaches desired base case and will return 0 in other base cases. It will be a knapsack type of approach where we have to either use the given decay[i][0..1] and decrement the difference M and Z accordingly and recurse for the same index i in decay[\ ][\ ] array or simply leave the difference as it is and recurse for i-1.
Let decay[0..k ][2] be a 2-D array containing k types of decays.
Firstly we have to define a dp[\ ] array and determine its state and transition.


dp[\ difference \ of \ M_1\ and\ M_2][\ difference\ of\ Z_1\ and\ Z_2][\ Current\ decay\ index\ ] = No.\ of\ ways\ to\ make\ the\ difference\ zero


dp[M][Z][i] = dp[(M-decay[i][0])\ ]\ [(Z-decay[i][1])\ ]\ [i]\ +\ dp[M][Z][i-1]

Base cases for the recursive calls will be when the difference M and Z is zero we have to return 1.
If the difference M or Z or the decay index i is less than zero (M < 0\ ||\ Z<0\ ||\ i<0) then return 0.
Also don’t forget taking mod of number of ways by 1e^9+7.


Setter's Solution
import java.util.*;
import java.lang.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Main
   public static int mod=1000000007;
   public static long count(int M,int Z,int arr[][],int i, long dp[][][]){

           return 0;
           return dp[M][Z][i];
           return 1;
       return dp[M][Z][i]=(count(M-arr[i][0],Z-arr[i][1],arr,i, dp)%mod+count(M,Z,arr,i-1, dp)%mod)%mod;
   public static void main (String[] args) throws java.lang.Exception
       // your code goes here
       Scanner sc = new Scanner(;
       int k = sc.nextInt();
       int[][] decay = new int[k][2];

       for(int i=0;i<k;i++){
           decay[i][0] = sc.nextInt();
           decay[i][1] = sc.nextInt();
       int q = sc.nextInt();
       long [][] arr = new long[q][4];
       for(int i=0;i<q;i++){
           for(int j=0;j<4;j++){
               arr[i][j] = sc.nextLong();
       long dp[][][]=new long[201][201][51];
       for(int i=0;i<arr.length;i++){
           int M = (int)(arr[i][0]-arr[i][2]);
           int Z = (int)(arr[i][1]-arr[i][3]);
           System.out.println(count(M,Z,decay, decay.length-1, dp));
Tester's Solution
using namespace std;
typedef long long ll;
#define mod (int)(1e9+7)
ll dp[201][201][51];

ll nuclear(int m1,int z1,vector<pair<int,int>> &v,int x){
   if(m1<0 || z1<0 || x>=v.size())
   return 0;
   return dp[m1][z1][x];
   if(m1==0 && z1==0 )
   return 1;
   ll tot=0;
   return dp[m1][z1][x]=tot%mod;

int main(){
   int k; cin>>k;
   vector<pair<int,int>> v(k);
   for(int i=0;i<k;i++){
       int a,b;
   int q;
       ll m1,z1,m2,z2;
   return 0;
1 Like