// Arup Guha // 2/21/2019 // Solution? to 2019 NAIPC Proposed Problem: Inflation // I run my queries one by one, instead of all at once, not sure if we want // this to be TLE or AC. For the cases now, this takes 1.01 in the worst case // on my desktop. For now, I'll put it in the AC folder, but it can be moved // to TLE if we determine that we want students to run all the queries at once, // (which, I think should be faster.) import java.util.*; public class inflation_arup { final public static double EPS = 1e-9; public static int numYears; public static int numItems; public static double[] inflation; public static double[][] prices; public static ArrayList eqns; public static boolean[] noPriceList; public static void main(String[] args) { Scanner stdin = new Scanner(System.in); numYears = stdin.nextInt(); numItems = stdin.nextInt(); int numQ = stdin.nextInt(); // Read inflation. inflation = new double[numYears-1]; for (int i=0; i(); for (int j=0; j validIdx = new ArrayList(); for (int i=0; i -.5) validIdx.add(i); } // We need two prices for a single commodity to nail anything down, // except given information. noPriceList[j] = (validIdx.size() < 2); // Make equations here. for (int i=0; i 0) tmp[tmp.length-1] -= Math.log(inflation[k]); else tmp[numItems+k] = 1; } // Here is our equation. eqns.add(tmp); } } // Initial version - we will solve each query 1 by 1. for (int i=0; i -.5) System.out.printf("%.10f\n",prices[year][item]); // If they didn't give it to us and we have 0 or 1 data point, we can't do it. else if (noPriceList[item]) System.out.println("-1.0"); // Give it a shot the long way. else { double res = solve(year, item); if (res < 0) System.out.println("-1.0"); else System.out.printf("%.10f\n", res); } } } public static double solve(int year, int item) { double[] lasteqn = new double[numItems+numYears]; // Get anchor first - guaranteed we have two prices if we get here. int knownYear = 0; while (prices[knownYear][item] < 0) knownYear++; // Which way are we looping. int sign = knownYear < year ? 1 : -1; int startI = Math.min(knownYear, year); int endI = Math.max(knownYear, year); // This is the last equation, "setting unknown price to 0" lasteqn[lasteqn.length-1] = -Math.log(prices[knownYear][item]); lasteqn[item] = year-knownYear; // Sets each inflation variable (or subs it out if known) for (int k=startI; k 0) lasteqn[lasteqn.length-1] -= sign*Math.log(inflation[k]); else lasteqn[numItems+k] = sign; } // All eqns stored here. ArrayList myeqns = makeCopy(eqns); myeqns.add(lasteqn); // Solve this "augmented" system. return gaussian(myeqns); } // Returns a copy of all of our equations. public static ArrayList makeCopy(ArrayList orig) { ArrayList res = new ArrayList(); for (int i=0; i myeqns) { // Basic eqn info. int n = myeqns.size(); int numvars = numItems+numYears-1; int curNonZeroMin = getNonZeroCol(myeqns, 0); // i is equation we use for elimination. for (int i=0; i bestCoeff) { bestCoeff = coeff; bestEqn = j; } } // Get out! No pivot equation. if (bestEqn == -1) break; // Swap references here. double[] tmp = myeqns.get(i); myeqns.set(i, myeqns.get(bestEqn)); myeqns.set(bestEqn, tmp); // Zero out this column. for (int j=i+1; j myeqns, int startRow) { int numvars = myeqns.get(0).length; int curNonZeroMin = numvars; for (int i=startRow; i EPS) return false; return true; } }