MemSQL Start[c]UP 3.0 Round 2 Editorial

7 years ago, # |

← Rev. 2 →

So is 865C solved in $\text{[math]}$ ?

→ Reply

kabirsahni8

7 years ago, # |

Can someone elaborate Div2 E?

→ Reply

rebornplusplus

7 years ago, # ^ |

+17

Um, this is actually the solution kfoozminus explained to me:

Let's maintain two multisets, "unused" and "already sold". After taking input "x", I tried to sell this pairing with a previous element(which I'm gonna buy). Took the minimum valued element among "unused" + "already sold" stuffs, let's call it "y".

If(y < x) {
 if(y came from unused set) buy y and sell x.
 else if(y came from "already sold" set) put y in unused set and sell x.
}
else put "x" in unused set

The solution actually comes from the idea — If I see that there's an "already sold" stuff smaller than x, it'd be optimal to sell "x" and not use y, rather than use y and buy x.

→ Reply

7 years ago, # |

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?

→ Reply

7 years ago, # ^ |

You assume that the answer is K and compute f(K) (using dynamic programming). The answer is such x that x = f(x). Since f(x) is monotone, binary search can find an answer.

Another view is as follows: assume I tell you that the answer is K. How do you verify that?

Take a look at my submission. Keep in mind that the upper bound is very coarse and the number of iterations in the binary search is unnecessarily large.

→ Reply

kr_abhinav

7 years ago, # ^ |

if (i+S[j] <= R) 
{
    play += (S[j] + EXP[j+1][i+S[j]]) * (1-P[j]);
} 
else 
{
    play += (S[j] + ans) * (1-P[j]);
}

Can you please explain the "else" part? I was not able to figure out why it would be S[j]+ans in this case

→ Reply

7 years ago, # ^ |

If i + S[j] > R, it means that when you're unlucky and the current level taking requires the longer timeslot causes you to be over the limit, you have to restart the game after finishing this level.

→ Reply

kr_abhinav

7 years ago, # ^ |

So in this case isn't play += ans * (1-P[j]) sufficient?

→ Reply

7 years ago, # ^ |

+10

No. You need to spend the S[j] seconds playing, and only after that you can restart. Quoting the statement:

After completing a level, you may decide to either continue the game and play the next level, or reset the game and start again from the first level.

→ Reply

kr_abhinav

7 years ago, # ^ |

Thanks for clarifying :D

→ Reply

7 years ago, # ^ |

What is the semantics of K and f(K) ?
Did you mean, that the answer is such x that R = f(x)?
And could you clarify about "upper bound coarse"? I thought, that the iterations count difference between upper_bound and binary_search is very low, at most 1-2 iterations.

→ Reply

riadwaw

7 years ago, # ^ |

← Rev. 3 →

+20

you calculate the answer using dp, but anytime you start from the beginning you use K instead of dp[starting state] which is not yet calculated.

f(K) is the answer for dp in starting state

Now first thing to understand that if K is answer, then you will get K as answer to your dp (that's easy) Now understand that if K is more then answer you'll get more then answer (because all number can just increase) but less then K (thats harder)

So now function f(k) — k has one zero and you search for it with binary search

→ Reply

cerberus97

7 years ago, # ^ |

How can we show that if K is more than answer, f(K) will never be equal to K?

→ Reply

7 years ago, # ^ |

Got the idea, thanks!

→ Reply

7 years ago, # ^ |

I am confused by the upper bound in this problem. How would the upper bound of the binary search be calculated?

The worst case should be that R is the sum of Fi's, Fi's are 99, Si's are 100 and Pi's are 80. So one has to pass every stage quickly to make it in R seconds. If I am right, how does this lead to the upper bound?

→ Reply

7 years ago, # ^ |

← Rev. 3 →

Oh, is that:

$\text{[math]}$

→ Reply

7 years ago, # ^ |

Yup, it's around that. But in the contest I just went for somewhat more generous bound. You don't want to fail a task just because of this, and time limit wasn't an issue.

→ Reply

oakszyjrnrdy

7 years ago, # ^ |

I don't understand why the upper bound of expection is not R but . Can you explain?

→ Reply

7 years ago, # ^ |

← Rev. 2 →

In the best case, you have to pass all 50 stages fast — any slow move will result in a replay. You pass the whole game in one shot with probability 0.8^50. So, the number of game required for such one shot exists is 1 over 0.8^50. For each such pass you may have to play at worst 50 stages each with no more than 100 units of time. (This is a rough upper bound, so it is not that tight, but also enough for a binary search)

→ Reply

7 years ago, # ^ |

Finally, i've got the idea of the solution, thanks!
Also, i've understood your notice about too big upper bound, it wasn't about std::upper_bound function :)
I still have the only question about optimal progress reset strategy. If I've got you solution right, the optimal strategy is to reset a progress only if all levels completion with slow completion of the current level becomes greater than R. Why it is right?
It doesn't take in account the relation between Fi/Si/Pi at the beginning and at the ending. It seems, that in one situation it could be more profitable to reset a progress after slow completion of the first level, and in another situation it could be profitable to reset progress nearby before final level, but don't see it in DP calculation.

→ Reply

SirShokoladina

7 years ago, # ^ |

Let's call a strategy a decision in which cells of the dp we will hit restart. Then for a fixed strategy P the function f_P produced by the dp is linear. Now f(x) = min f_P(x). So f in convex upward. Also f(0) > 0. Thus f(x) = x has at most one root.

→ Reply

SirShokoladina

7 years ago, # |

+15

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

→ Reply

spiderbatman

7 years ago, # |

← Rev. 2 →

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.

Code

#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;
}

→ Reply

sup_bro

7 years ago, # ^ |

According to me, your statement: it is optimal to go to the start every time when p[i][t] < p[0][0] is incorrect. We have to minimize the expected amount of time we play.

Say dp_i, j is the expected amount of time needed to play to finish in less than R seconds such that j seconds have already passed and we are at the i^th level. It is optimal to reset if dp_i, j + j > dp_0, 0. But since we don't know what's dp_0, 0, we say dp_0, 0 = K for some K and verify if it's possible or not. If it's possible for K, it's possible for all values > K. So, we can apply binary search on K.

→ Reply

mdallrosa

7 years ago, # |

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://mirror.codeforces.com/contest/867/submission/31151505

→ Reply

joker_in

7 years ago, # |

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

→ Reply

coconut

7 years ago, # |

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;
}

→ Reply