However hard i try i m unable to get the logic behind this problem of goodbye 2016 contest plz help somebody..
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 161 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | Dominater069 | 154 |
8 | awoo | 154 |
10 | luogu_official | 150 |
However hard i try i m unable to get the logic behind this problem of goodbye 2016 contest plz help somebody..
Name |
---|
why negative, it is new year
why new year? it is negative
Check this out
I've used binary search the answer to find out the maximum possible rating.It's relatively easier to implement and understand.
Check out my code http://mirror.codeforces.com/contest/750/submission/23462718
nice code, I really understood your code, I think its an editorial on its own .. Thanks
can anyone explain problem C(New Year and Rating) in detail please.I have understood clearly the part mentioned in Errichto's blog ->
For every contest we know that the current rating is x increased by some prefix sum of c_i (changes of rating). If Limak is in the division 1, we have inequality x+prefSum >= 1900 so we have x >= 1900-prefSum. If Limak is in the division 2, we have inequality x_prefSum <= 1899 so it is x <= 1899-prefSum. From this set of inequalities, your task is to find the biggest x satisfying all of them.
now, how to find the biggest x and when to print infinity? Thanks, in advance :)
Keep the maximum and minimum starting rating in two separate variables, e.g.
ma
andmi
.When you're competing in a division 1 contest, the inequality
x >= 1900 - prefixSum
holds. Therefore you might need to increasemi
. You can do this with the updatemi = max(mi, 1900 - prefixSum)
. Because we take the maximum, the newmi
will satisfy all old division 1 constraints and also the new one.Do the reversed thing when you're in a division 2 contest:
ma = min(ma, 1899 - prefixSum)
.If
mi > ma
at the end, then no solution is possible. Otherwisema
will be the biggest starting raking andma + prefixSum
will be the rating at the end of the year.My submission: 23523630
When you're competing in a division 1 contest, the inequality x >= 1900 — prefixSum holds. So we need to maximize x here, right? which is done by mi = max(mi, 1900 — prefixSum) this step. so , we are storing max possible value in mi.. then maximum will always be greater than minimum, so why this statement->If mi > ma at the end, then no solution is possible ? and at the end we can simply print the maximum value which is stored in mi . why are we not doing that?
No, you mixed up the variables!
mi
holds the current minimum starting rating (the lower bound), not the maximum.ma
holds the current maximum starting rating (upper bound).x >= 1900 - prefixSum
gives a new lower bound for the starting ratingx
, therefore we need to update the lower boundmi
. And we need do updatemi
by using the maximum, becausemi
has to satisfy all lower bound constraints.I sincerely than you for helping me so much, one small and last doubt. If x is the initial rating at i=0, then you are computing the maximum and minimum possible values of x(ma and mi respectively). Then with the max initial rating you are adding the prefix sum and getting the final answer.
My question is that if ma is the maximum possible initial rating then while obtaining that value of ma why are you doing 'min' i.e. min(ma,1899-prefixSum)? why min?
Because the inequality
x <= 1899 - prefixSum
. This inequality gives a upper bound.x
has to be smaller than the value. So at the moment we knowx <= ma
andx <= 1899 - prefixSum
. We can combine these two inequalities: clearlyx
has to be smaller thanmin(ma, 1899 - prefixSum)
, therefore we get the newma
.If you're unsure how to combine two inequalities, think about the following problem. Which numbers
x
satisfy both the inequalityx < 5
andx < 3
?Clearly all numbers smaller than 3, which is the minimum of 3 and 5. So you can combine both inequalities to
x < 3
.