NUKE_REACTOR-Editorial

PROBLEM LINK:

The Stark Reactor

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

DIFFICULTY:

MEDIUM

PROBLEM:

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.

Prerequisites:

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

Hint:

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.

QUICK EXPLANATION:

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.

EXPLANATION:

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.

State

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

Transition

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.

SOLUTIONS:

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

/* 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[][][]){

       if(M<0||Z<0||i<0)
           return 0;
       if(dp[M][Z][i]!=0)
           return dp[M][Z][i];
       if(M==0&&Z==0)
           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(System.in);
       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
#include<bits/stdc++.h>
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;
   if(dp[m1][z1][x]!=-1)
   return dp[m1][z1][x];
   if(m1==0 && z1==0 )
   return 1;
   ll tot=0;
   tot+=nuclear(m1-v[x].first,z1-v[x].second,v,x)%mod;
   tot+=nuclear(m1,z1,v,x+1)%mod;
   return dp[m1][z1][x]=tot%mod;
}



int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);   
   cout.tie(NULL);
   memset(dp,-1,sizeof(dp));
   int k; cin>>k;
   vector<pair<int,int>> v(k);
   for(int i=0;i<k;i++){
       int a,b;
       cin>>a>>b;
       v[i]={a,b};
   }
   int q;
   cin>>q;
   while(q--){
       ll m1,z1,m2,z2;
       cin>>m1>>z1>>m2>>z2;
       cout<<nuclear(m1-m2,z1-z2,v,0)<<endl;
       
   }
   return 0;
}
1 Like