### cerealguy's blog

By cerealguy, 10 months ago, ,

•
• +59
•

 » 10 months 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!
•  » » 10 months 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.
•  » » » 10 months 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
 » 10 months ago, # | ← Rev. 2 →   0 So is 865C solved in ?
 » 10 months ago, # |   +3 Can someone elaborate Div2 E?
•  » » 10 months 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.
 » 10 months 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?
•  » » 10 months 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.
•  » » » 10 months 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
•  » » » » 9 months 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.
•  » » » » » 9 months ago, # ^ |   0 So in this case isn't play += ans * (1-P[j]) sufficient?
•  » » » » » » 9 months 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.
•  » » » » » » » 9 months ago, # ^ |   0 Thanks for clarifying :D
•  » » » 10 months 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.
•  » » » » 10 months 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
•  » » » » » 9 months ago, # ^ |   0 How can we show that if K is more than answer, f(K) will never be equal to K?
•  » » » » » 9 months ago, # ^ |   0 Got the idea, thanks!
•  » » » » 9 months 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?
•  » » » » » 9 months ago, # ^ | ← Rev. 3 →   0 Oh, is that:
•  » » » » » » 9 months 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.
•  » » » » » » 9 months ago, # ^ |   0 I don't understand why the upper bound of expection is not R but . Can you explain?
•  » » » » » » » 9 months 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)
•  » » » 9 months 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.
•  » » » » 9 months 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.
 » 9 months 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
 » 9 months ago, # |   0 Can anybody elaborate Div2 C?
 » 9 months 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; } 
•  » » 9 months 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.
 » 9 months ago, # |   0 Please elaborate the solution of 865B — Ordering Pizza. Can't able to understand from this point ->Then the first contestant should take the first s1 slices, then the second contestant should take the next s2..
 » 9 months 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
 » 9 months ago, # |   0 can anyone tell how to compute p(x^(-1))mod Q(x) in question G
 » 9 months 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; } 
•  » » 9 months ago, # ^ |   0 Your compare function is incorrect, as comp(a, a) should return false.
•  » » » 9 months ago, # ^ |   0 OMG! You're amazing!!!!! That is indeed the error!! I've never encountered that as run-time error before (can only say that I'm not experienced enough I guess...). According to http://en.cppreference.com/w/cpp/concept/Compare, the requirements are For all a, comp(a,a)==false If comp(a,b)==true then comp(b,a)==false if comp(a,b)==true and comp(b,c)==true then comp(a,c)==true Thank you again Michal!!!!!
 » 4 weeks 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