Pardon me if I am wrong, but can 2C be solved using some sort of a ternary search? Given x slices of type 1, and y slices of type 2, is there an optimal greedy way of distributing them? If yes, I believe ternary search can be applied (I may be wrong, of course). Any help will be appreciated, thank you in advance!

So is 865C solved in ?

Can someone elaborate Div2 E?

Could you explain some details about DIV1-C?

which takes exactly K seconds to complete

To complete to whole game, or game suffix?

If the optimal strategy is to immediately switch to the deterministic game, then the answer is greater than K. Otherwise it's less than K

Could you clarify it? Binary search should be made by K or by answer?

And is there a code, which corresponds the idea from editorial?

It is also possible to use Newton's method in problem C to make less iterations. My solution converges in 4 iterations. I believe the P_i ≥ 80 restriction is also unnecessary for this solution. 30890918

EDIT: Missed part of statement.

Can Div1 C be solved without bin search? Let's calculate p[i][t] — probability to finish game in at least R seconds if we are at the i-th level and t seconds have passed. Now, I think, it is optimal to go to the start every time when p[i][t] < p[0][0] (Is this correct?). Now let dp[i][t] be probability that we are at the i-th level with t seconds passed. Let's say answer is S. Then formula for S will be something like this S = dp[n][t₁] * t₁ + dp[n][t₂] * t₂ + ... + dp[i₁][T₁] * (S + T₁) + dp[i₂][T₂] * (S + T₂) + ... first we add runs which were successful (completed in less then R seconds) and then we add runs where we either chose to go back or got bad score and had to go back. We do simple dp and accumulate constant values and coefficients of S. In the end S = CONST / (1 - COEF) My code sometimes gives wrong answer, for example third pretest. In my code good[i][t] means probability to finish game with at least R seconds if we are at i-th level and t seconds have passed.

#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <ctime>
#include <map>
#include <set>
#include <string>
#include <cassert>

#define INFLL 2000000000000000000
#define INF 2000000000
#define MOD 1000000007
#define PI acos(-1.0)

using namespace std;

typedef pair <int, int> pii;
typedef long long ll;
typedef vector <ll> vll;

struct Level {
	int a;
	int b;
	double p;
};

int n, r;
Level arr[50];
double p[51][5001];
double good[51][5001];
double sums[51][5001];
double back, con;
double dp[51][5001];

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin >> n >> r;
	for (int i = 0; i < n; i++) {
		cin >> arr[i].a >> arr[i].b >> arr[i].p;
		arr[i].p /= 100.0;
	}
	p[n][0] = 1;
	for (int i = n - 1; i >= 0; i--) {
		for (int j = 0; j <= 5000; j++) {
			if (j + arr[i].a <= 5000) p[i][j + arr[i].a] += p[i + 1][j] * arr[i].p;
			if (j + arr[i].b <= 5000) p[i][j + arr[i].b] += p[i + 1][j] * (1 - arr[i].p);
		}
	}
	for (int i = 0; i <= n; i++) {
		sums[i][0] = p[i][0];
		for (int j = 1; j <= 5000; j++) sums[i][j] = sums[i][j - 1] + p[i][j];
	}
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= r; j++) {
			good[i][j] = sums[i][r - j];
		}
	}	
	dp[0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= 5000; j++) {
			if (j > r) {
				back += dp[i][j];
				con += dp[i][j] * j;
				continue;
			}
			if (good[i][j] < good[0][0]) {
				back += dp[i][j];
				con += dp[i][j] * j;
				continue;
			}
			if (j + arr[i].a <= 5000)
				dp[i + 1][j + arr[i].a] += dp[i][j] * arr[i].p;
			if (j + arr[i].b <= 5000) 
				dp[i + 1][j + arr[i].b] += dp[i][j] * (1 - arr[i].p);
		}
	}
	for (int i = 0; i <= r; i++) 
		con += dp[n][i] * i;
	for (int i = r + 1; i <= 5000; i++) {
		con += dp[n][i] * i; 
		back += dp[n][i];
	}	
	printf("%.15f\n", con / (1 - back));
	return 0;
}

Why the following approach is not valid? Let sumA be the sum of all slices of pizzas from the contestants where ai > bi. I sort the participants by (bi-ai), and then i distribute the pizzas starting from the index 0. When i take K slices of a participant that has ai > bi, i make sumA -= K. When i know that sumA < S, (i.e i can't eat more entire pizzas with sumA), i know that i have to share the remainder sumA slices. Submission: http://codeforces.com/contest/867/submission/31151505

can anyone tell how to compute p(x^(-1))mod Q(x) in question G

Hi, I have a question regarding 865B — Ordering Pizza. I've debugged for so many hours that I decided to ask for some insight. I always get runtime error for Test case 5. And I simply have no idea which part of my code, pasted below, could cause run-time error. Any insight is appreciated. Thanks!!!!

#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>      // std::pair, std::make_pair
#include <vector>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
bool comp(pll a, pll b) {
    return a.first >= b.first;
}

// x is number of pieces to consume
ll findBest(vector<pll> &ps, ll x) {
    ll res = 0;
    for (ll i = 0; i < ps.size(); i++) {
        ll num = ps[i].second;
        ll diff = ps[i].first;
        if (x - num >= 0) {
            res += (num * diff);
            x -= num;
        } else {
            res += (x * diff);
            break;
        }
    }
    return res;
}

int main() {
    ll n, s;
    cin >> n >> s;
    vector<pll> ps;
    ll total = 0;
    ll positives = 0;
    ll pieces = 0; // overall pieces
    for (ll i = 0; i < n; i++) {
        ll num, a, b;
        cin >> num >> a >> b;
        ps.push_back(make_pair(a-b, num));
        total += num * b;
        pieces += num;
        if (a-b > 0) {
            positives += num;
        }
    }
    sort(ps.begin(), ps.end(), comp);
    ll pizzas = (pieces % s == 0) ? (pieces / s) : (pieces / s + 1);
    ll extra = pizzas * s - pieces;

    ll best = total;
    if (positives > 0) {
        best = max(best, findBest(ps, positives / s * s) + total);
        if (positives % s != 0) {
            ll x = max(positives, (positives/s + 1) * s - extra);
            best = max(best, findBest(ps, x) + total);
        }
    }
    cout << best << endl;
    return 0;
}

Would this logic work in Problem E of Div 2?

Take maximum of 1 to N from segtree and let its index be x . We will sell a stock at this index and take minimum of 1 to x-1 from segtree and let its index be y. We will buy stock at index y. Now remove this values from segment tree. And keep on doing this till all values have been exhausted.

I tried this solution but i am getting wrong answer

submission: http://codeforces.com/contest/867/submission/39457512

Does anyone know how to prove the correctness of the greedy algorithm for problem D (Buy Low Sell High)? Thanks.