### cerealguy's blog

By cerealguy, 6 years ago,
• +59

| Write comment?
 » 6 years ago, # |   +2 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!
•  » » 6 years ago, # ^ |   0 It is not needed, you know the number of pizzas of type A is (sum of pizza slices eaten where A greater than B / slices per pizza) plus or minus one, or the (sum of pizza slices eaten where A greater than or equal to B / slices per pizza) plus or minus one.
•  » » » 6 years ago, # ^ |   0 Yes, Ternary Search can be applied. The optimal strategy of distributing slices among contestants is same as mentioned in the editorial.You can see my submission using Ternary Search here.Although it is not needed as pointed out by farmersrice
 » 6 years ago, # | ← Rev. 2 →   0 So is 865C solved in ?
 » 6 years ago, # |   +3 Can someone elaborate Div2 E?
•  » » 6 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.
 » 6 years ago, # |   +5 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?
•  » » 6 years ago, # ^ |   +6 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.
•  » » » 6 years ago, # ^ |   0 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
•  » » » » 6 years ago, # ^ |   +5 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.
•  » » » » » 6 years ago, # ^ |   0 So in this case isn't play += ans * (1-P[j]) sufficient?
•  » » » » » » 6 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.
•  » » » » » » » 6 years ago, # ^ |   0 Thanks for clarifying :D
•  » » » 6 years ago, # ^ |   0 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.
•  » » » » 6 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 stateNow 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
•  » » » » » 6 years ago, # ^ |   0 How can we show that if K is more than answer, f(K) will never be equal to K?
•  » » » » » 6 years ago, # ^ |   0 Got the idea, thanks!
•  » » » » 6 years ago, # ^ |   0 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?
•  » » » » » 6 years ago, # ^ | ← Rev. 3 →   0 Oh, is that:
•  » » » » » » 6 years ago, # ^ |   0 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.
•  » » » » » » 6 years ago, # ^ |   0 I don't understand why the upper bound of expection is not R but . Can you explain?
•  » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 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)
•  » » » 6 years ago, # ^ |   0 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.
•  » » » » 6 years ago, # ^ |   0 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.
 » 6 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 Pi ≥ 80 restriction is also unnecessary for this solution. 30890918
 » 6 years ago, # | ← Rev. 2 →   0 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][t1] * t1 + dp[n][t2] * t2 + ... + dp[i1][T1] * (S + T1) + dp[i2][T2] * (S + T2) + ... 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 #include #include #include #include #include #include #include #include #include #include #include #include #define INFLL 2000000000000000000 #define INF 2000000000 #define MOD 1000000007 #define PI acos(-1.0) using namespace std; typedef pair pii; typedef long long ll; typedef vector 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; } 
•  » » 6 years ago, # ^ |   0 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 dpi, 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 ith level. It is optimal to reset if dpi, j + j > dp0, 0. But since we don't know what's dp0, 0, we say dp0, 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.
 » 6 years ago, # |   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
 » 6 years ago, # |   0 can anyone tell how to compute p(x^(-1))mod Q(x) in question G
 » 6 years ago, # |   0 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 #include #include #include // std::pair, std::make_pair #include using namespace std; typedef long long ll; typedef pair pll; bool comp(pll a, pll b) { return a.first >= b.first; } // x is number of pieces to consume ll findBest(vector &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 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; } 
•  » » 6 years ago, # ^ |   0 Your compare function is incorrect, as comp(a, a) should return false.
 » 5 years ago, # | ← Rev. 2 →   -8 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
 » 10 months ago, # | ← Rev. 2 →   0 Does anyone know how to prove the correctness of the greedy algorithm for problem D (Buy Low Sell High)? Thanks.
•  » » 5 months ago, # ^ |   -16 Have you found a way to prove the correctness of this problem?