I’m new to competitive programming as well as programming.
Here is the problem.
Mr.Dengklek has N friendly ducks numbered from 1 to N lined up in increasing order. Each duck i (1 ≤ i ≤ N) is given a board containing a matrix of size Ri × Ci. For every adjacent pair of ducks, the number of columns in the matrix of the duck with the smaller number is less than or equal to the number of rows in the matrix of the duck with the larger number.
Now, Mr.Ganesh’s elephants are asked to calculate the product of N matrices. However, these elephants are very intelligent. They can compute the product optimally, using the fewest steps possible. The number of steps to multiply two matrices of sizes a × b and b × c is equal to a × b × c. The elephants’ multiplication will form a final expression string E, which is the initial expression pattern displayed by the ducks, with parentheses added according to the order of matrix multiplication performed by the elephants (each time the elephants multiply two matrices, they add parentheses).
Create a program that will answer one of the following three questions posed by the elephants:
- What is the total number of steps taken by Mr.Ganesh’s elephants in multiplying the matrices?
- What is the remainder when the number of ways to form E resulting in an optimal number of steps is divided by the integer 26101991?
- What is the remainder when the number of ways to form E, where the steps are not necessarily optimal (two final expressions are considered different if the resulting strings are different), is divided by the integer 26101991?
Input Format:
- The first line contains an integer N.
- The second line contains N + 1 integers, where the i-th integer (2 ≤ i ≤ N - 1) represents the number of columns in the i-th matrix and the (i - 1)-th integer represents the number of rows in the i-th matrix. The first integer represents the number of rows in the first matrix, and the last integer represents the number of columns in the last matrix.
- The third line contains an integer Q, denoting the question asked by Mr.Dengklek.
Output Format:
- For each type of question, output an integer which is the answer to that question.
Example Input 1:
4
1 2 3 4 5
1
Example Output 1:
38
Example Input 2:
4
1 2 3 4 5
2
Example Output 2:
1
Example Input 3:
4
1 2 3 4 5
3
Example Output 3:
5
Explanation: There are 5 possible matrix multiplications:
- (((A1 × A2) × A3) × A4)
- ((A1 × A2) × (A3 × A4))
- ((A1 × (A2 × A3)) × A4)
- (A1 × ((A2 × A3) × A4))
- (A1 × (A2 × (A3 × A4)))
The optimal solution is the first possibility with a total of 1 × 2 × 3 + 1 × 3 × 4 + 1 × 4 × 5 = 38 steps.
Constraints:
- 1 ≤ N ≤ 100
- 1 ≤ Q ≤ 3
- Rows and columns of matrices are between 1 and 10,000.
- The output will fit in a signed 64-bit integer.
Here is what i submitted
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Trial {
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public Long nextLong(){
return Long.parseLong(next());
}
}
private static InputStream inS = System.in;
private static OutputStream outS = System.out;
private static InputReader in = new InputReader(inS);
private static PrintWriter out = new PrintWriter(outS);
static int N,testcase;
static long minimum,minCount,mod;
static long[] allPosStepsArr,arr;
static long[][] multliArray,dp,minCountDP;
static{
N = in.nextInt();
mod = 26101991;
arr = new long[N+2];
allPosStepsArr = new long[N+1];
Arrays.fill(allPosStepsArr,-1);
multliArray = new long[105][105];
dp = new long[105][105];
minCountDP = new long[105][105];
for(int i = 1;i<=N+1;i++){
arr[i] = in.nextInt();
}
testcase= in.nextInt();
}
public static void main(String[] args) {
for(int i = 1;i<N;i++){
for(int j = i+1;j<=N;j++){
multliArray[i][j] = (arr[i]* arr[j] * arr[j+1]);
}
}
for(int i = 1;i<102;i++){
for(int j = 1;j<102;j++){
dp[i][j] = -1;
minCountDP[i][j] = -1;
}
}
if(testcase ==1){
System.out.println(optimalValue(1,N));
}else if(testcase == 2){
System.out.println(minCountFunc(1,N) % mod);
}else{
System.out.println(AllPossibleSteps(N) % mod) ;
}
}
private static long optimalValue(int i , int j){
if( i == j){
return 0;
}
if(dp[i][j] != -1){
return dp[i][j];
}
long minValue =Long.MAX_VALUE;
long sum = 0;
for(int start = i;start < j;start ++){
sum = ((optimalValue(i,start) + optimalValue(start+1,j)) + (multliArray[i][j]));
minValue = Math.min(minValue,sum);
}
dp[i][j] = minValue;
return dp[i][j];
}
private static long minCountFunc(int i , int j){
if( i+1 >=j ){
return 1;
}
if(minCountDP[i][j] != -1){
return minCountDP[i][j] ;
}
long minValue = optimalValue(i,j);
long numOfMin = 0;
for(int start = i;start < j;start ++){
long test = optimalValue(i,start) + optimalValue(start+1,j) + multliArray[i][j];
if(minValue == test){
numOfMin += (((minCountFunc(i,start) % mod) * ( minCountFunc(start+1,j)% mod)) % mod);
}
}
minCountDP[i][j] = numOfMin;
return minCountDP[i][j];
}
private static long AllPossibleSteps(int N){
if(allPosStepsArr[N] != -1){
return allPosStepsArr[N] ;
}
if(N <=2 ){
return 1;
}
long sum = 0;
for(int i = 1;i<N;i++){
sum +=(((AllPossibleSteps(i) % mod) * (AllPossibleSteps(N - i) % mod)) )% mod ;
}
allPosStepsArr[N] = sum;
return allPosStepsArr[N];
}
}
but i still get 2 Wrong Answers, WA(80). Does anyone know what my mistake could be ? and perhaps possible fix to my code ?
With constraints as stated in the problem,is it possible that the optimalValue function returns a number too big for long to handle ?
Thank you.