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.
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;
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…
Wow you guys are good
@vpriyanshu40
Dude I have already seen the editorial, I just want to know what is incorrect with my logic.
Just 4 elements are enough to exceed the integer limit for a unsigned long long int.
i am sorry i am not able to understand you.Please explain a little.
A_i\leq10^5 and the largest number you can store is 4\times10^{18}, so the answer will overflow if you multiply a lot of numbers.