PROBLEM LINK:
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
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;
}