wrong answer in chef and way problem

general
, ,
1

I recently solved this problem but I am getting WA. Here is my solution(using dp), is it possible to use property of modular multiplication in this scenario.

2

Here’s one solution. I think you are leaving something i your algo.
You can check the editorial too.

import java.util.Scanner;

public class Main {

private final int modulo = 1000000007;

class Street {
	int    A; // special number
	double logA; // log of A

	Street prev;    // previous street in lowest cost path 
	double logCost; // cost up to and including this street (sum of logs leading up to this)
	
	public Street(int A) {
		setSpecialNumber(A);
		prev = null;
		logCost = logA; // intialize with its own number
	}
	
	public void setSpecialNumber(int A) {
		this.A = A;
		logA = Math.log((double)A);
	}

	public int getSpecialNumber() {
		return A;
	}

/*
public double getLogSpecialNumber() {
return logA;
}
*/

	public double getLogCost() { // cost of reaching this street
		return logCost;
3

You can also follow this editorial

4

@vpriyanshu40
Dude I have already seen the editorial, I just want to know what is incorrect with my logic.

5

dp[i]=((min%M)*(a[i]%M))%M;

You have declared both min and a[i] as integers, so 32 bits long. min and a[i] both can be 10^5. When they are multiplied, you get 10^10 which is not in the range of numbers a 32-bit integer can hold…

6

Wow you guys are good