p343.ans1
======================
150.89

=================
p343.cpp
======================
#include <bits/stdc++.h>

using namespace std;

char buf[1 << 20];
int pos, len;

inline char gc() {
    if(pos == len) {
        len = fread(buf, 1, sizeof(buf), stdin);
        pos = 0;
    }
    return pos < len ? buf[pos++] : EOF;
}

inline int read_int() {
    int x = 0;
    char c;
    while((c = gc()) < '0')
        ;
    do {
        x = x * 10 + c - '0';
    } while((c = gc()) >= '0');
    return x;
}

inline double read_double() {
    int x = 0;
    char c;
    while((c = gc()) < '0')
        ;
    do {
        x = x * 10 + c - '0';
    } while((c = gc()) >= '0');
    if(c == '.') {
        int frac = 0, div = 1;
        while((c = gc()) >= '0') {
            frac = frac * 10 + c - '0';
            div *= 10;
        }
        return x + (double)frac / div;
    }
    return x;
}

int T, N;
vector<int> qty;
vector<vector<double>> price;

void read() {
    T = read_int();
    N = read_int();
    qty.resize(N);
    for(int i = 0; i < N; i++) {
        qty[i] = read_int();
    }
    price.resize(T + 1, vector<double>(N));
    for(int t = 0; t <= T; t++) {
        for(int i = 0; i < N; i++) {
            price[t][i] = read_double();
        }
    }
}

void solve() {
    // This is more of an implementation problem, as there is a full description
    // of what we want to do. Naively following, we get a O(N^2 * T)  solution
    // which might have to be optimized to pass.
    //
    // We need W'SW where S is the covariance matrix. Instead of
    // building S explicitly (O(N^2 * T)), we can notice that the W'SW risk of
    // the portfolio is just the variance of the portfolio return. The portfolio
    // return at time t is sum of w[i] * r[t][i], i.e. the weighted sum of asset
    // returns. So we compute this weighted return for each day, subtract its
    // mean, square, and average. This gives us the portfolio variance directly
    // in O(N * T).
    //
    // Formally: S[i][j] = (1/T) * sum_t (r[t][i] - m[i]) * (r[t][j] - m[j])
    //
    // W'SW = sum_{i,j} w[i] * S[i][j] * w[j]
    //      = sum_{i,j} w[i] * w[j] * (1/T) * sum_t (r[t][i]-m[i])*(r[t][j]-m[j]) 
    //      = (1/T) * sum_t sum_{i,j} w[i]*(r[t][i]-m[i]) * w[j]*(r[t][j]-m[j]) 
    //      = (1/T) * sum_t (sum_i w[i]*(r[t][i]-m[i]))^2 
    //      = (1/T) * sum_t dot[t]^2
    //
    // where dot[t] = sum_i w[i] * (r[t][i] - m[i]) is the demeaned portfolio
    // return.
    //
    // We might also need to implement fast reading to make this problem pass on
    // codeforces.

    double VP = 0;
    vector<double> w(N);
    for(int i = 0; i < N; i++) {
        w[i] = qty[i] * price[0][i];
        VP += w[i];
    }
    for(int i = 0; i < N; i++) {
        w[i] /= VP;
    }

    vector<double> sum(N);
    for(int t = 1; t <= T; t++) {
        for(int i = 0; i < N; i++) {
            sum[i] += (price[t - 1][i] - price[t][i]) / price[t][i];
        }
    }
    vector<double> m(N);
    double mP = 0;
    for(int i = 0; i < N; i++) {
        m[i] = sum[i] / T;
        mP += w[i] * m[i];
    }

    double var = 0;
    for(int t = 1; t <= T; t++) {
        double dot = 0;
        for(int i = 0; i < N; i++) {
            double r = (price[t - 1][i] - price[t][i]) / price[t][i] - m[i];
            dot += w[i] * r;
        }
        var += dot * dot;
    }
    var /= T;

    double sP = sqrt(var);
    double VaR = -VP * (mP - 1.644854 * sP);

    printf("%.2f\n", VaR);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p343.in1
======================
5 2
200 10
31.11 489.75
31.04 488.04
31.10 497.28
31.15 504.28
31.22 505.00
30.69 501.02

=================
statement.txt
======================
343. VaR
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



In economics and finance,  (VaR) is a measure of how the market value of an asset or of a portfolio of assets is likely to decrease over a certain time period (usually over 1 day or 10 days) under usual conditions. It is typically used by security houses or investment banks to measure the market risk of their asset portfolios (market value at risk), but is actually a very general concept that has broad application. 

VaR has three parameters.
The time horizon (period) to be analyzed (i. e. the period of time over which one plans to hold the assets in the portfolio—the "holding period"). The typical holding period is 1 day, although 10 days are used, for example, to compute capital requirements under the European Capital Adequacy Directive (CAD). For some problems, even a holding period of 1 year is appropriate.
The confidence level at which the estimate is made. Popular confidence levels are usually 99% and 95%.
The unit of the currency which will be used to denominate the value at risk (VaR).


In the purposes of this problem we will use the fixed confidence level value of 95% and Berland dollar as a currency unit.

The VaR is the maximum amount at risk to be lost from an investment (under 'normal' market conditions) over a given holding period, at a particular confidence level. As such, it is the converse of shortfall probability, in that it represents the amount to be lost with a given probability, rather than the probability of a given amount to be lost.

Consider an example of trading portfolio. Its market value in Berland dollars today is known, but its market value tomorrow is not known. The investment bank holding that portfolio might report that its portfolio has a 1-day VaR of 4millionatthe95%confidencelevel.Thisimpliesthat(providedusualconditionswillprevailoverthe1day)thebankcanexpectthat, withaprobabilityof95%, thevalueofitsportfoliowilldecreasebyatmost4 million during 1 day, or, in other words, that, with a probability of 5%, the value of its portfolio will decrease by 4millionormoreduring1day.

Thekeythingtonoteisthatthetargetconfidencelevel(95%intheaboveexample)isthegivenparameterhere;theoutputfromthecalculation(4 million in the above example) is the maximum amount at risk (the ) for that confidence level.

In the following,  means percentage change in value.

A variety of models exist for estimating VaR. Each model has its own set of assumptions, but the most common assumption is that historical market data is our best estimator for future changes. The important assumption of "variance-covariance" model () is that risk factor returns are always (jointly) normally distributed and that the change in portfolio value is linearly dependent on all risk factor returns. There are also "historical simulation" and "Monte Carlo simulation" models, but here we will touch only the VCV model.

In the following, we will take the simple case, where the only risk factor for the portfolio is the value of the assets themselves. The following two assumptions enable to translate the VaR estimation problem into a linear algebraic problem:
the portfolio is composed of the assets whose deltas are linear, more exactly: the change in the value of the portfolio is linearly dependent on (i.e. is a linear combination of) all the changes in the values of the assets, so that also the portfolio return is linearly dependent on all the asset returns;
the asset returns are jointly normally distributed.

The implication of (1) and (2) is that the portfolio return is normally distributed because it always holds that a linear combination of jointly normally distributed variables is itself normally distributed.

We will use the following notation:
there are N assets;
mi= expected value of the return on asset i;
mP= expected value of the return on the portfolio;
si= standard deviation of the return on asset i;
sP= standard deviation of the the return on the portfolio;
Vi= initial value of asset i (in currency units);
VP= initial value of the portfolio (in currency units);
wi=Vi/VP;
W= vector of all wi (WT means transposed);
S= covariance matrix, i. e. matrix of covariances between all N assets, i. e. an NxN matrix.


The covariance between two real-valued random variables X and Y, with expected values E(X) = mX and E(Y) = mY is defined as: cov(X, Y) = E((X - mX) (Y - mY)), where E is the expected value operator.

The calculation goes as follows.

mP = w1 · m1 + w1 · m1 +...+ wN · mN,

sP = (WT · S · W)0.5.

The normality assumption allows us to z-scale the calculated portfolio standard deviation to the appropriate confidence level. So for the 95% confidence level VaR we get: VaR = -VP · (mP - 1.644854 · sP).

You will be given historical data of the assets prices and the quantity of each asset in the portfolio. You should calculate the value at risk for that portfolio.

Input
The first line of the input contains integers T and N (1 ≤ T ≤ 104; 1 ≤ N ≤ 10). Second line contains N integers denoting the quantity of each asset in the portfolio. These integers are positive and not exceed 1000.

Each of the next T+1 lines contains N positive numbers pricet(i) written with 2 digits after the decimal point (0 ≤ t ≤ T; 1 ≤ i ≤ N). The first of those lines contains today's market prices (day 0) for one unit of the corresponding asset. Next line corresponds to the previous working day (day 1), and so on. Today's prices should be used to calculate the initial value of assets. The  of asset i on day t equals to (pricet-1(i)-pricet(i))/pricet(i). Prices are positive and do not exceed 100000.00.

Output
Print one number, the VaR for the given data. Your answer must be accurate up to 10-2.

Example(s)
sample input
sample output
5 2
200 10
31.11 489.75
31.04 488.04
31.10 497.28
31.15 504.28
31.22 505.00
30.69 501.02
150.89


=================
