Hello, CodeForces! On 20 August at 19:30 MSK will take place 262 (Div. 2) round. Div1 — participants can take part out of competition, as usual.
The problems were prepared by Victor Vasilevsky(vitux) and Aliaksei Semchankau (me). We'd like to thank Gerald Agapov (Gerald) for help of preparation of this round, Michael Mirzayanov (MikeMirzayanov) for comfortable platformes Codeforces and Polygon, and Mary Belova (Delinur) for translation of statements.
In this round you will help to different good people. We sure that every participant will find an interesting problem for him:)
gl & hf!
UPD: It will be used a standard scoring.
UPD2: Also we'd like to thank Vitaly Aksenov(Aksenov239) who helped a lot in fixing of Russian statements.
UPD3: We'd like to congrat top-5 participants!:
1) buptcjj
2) 6wr1
3) ladpro98
4) shaojj
5) linjek
Also we'd like to congrat jellygendut, who got 20th place and solved problem Е — It has been solved by 3 participants. Nobody has solved all problems, but every problems were solved by participants succesfully.
The link to timeanddate is broken ;)
try this one.
Brace yourself, newly registered users are coming.
recently new registered users are very genius!
are you sure about "new" users !!
I am not sure but i think 90 % among of then is Div1 members.
Irony is the very complicated thing, huh?
lol
Two consecutive Div.2 only rounds ! :|
Time for a Div.1 + Div.2 round :)
Hope that time of div1 will not be long.
Maybe it should be called Div.1.5.Because it is harder than usual Div.2 and easier than Div.1.
I think this is time to be pupil.. :D
why not? wake up man !
I think so too :)
Good luck :)
Happiness is , checking the 'Contest' tab each alternate day, and finding a Codeforces Round there! :)
sadness is to discover that the contest is div2 only
Sadness is losing internet connection in the middle of a rated contest while you just want to submit a problem and having connection back as soon as the contest finishes! :)
Happiness is to find out later that the solution you wanted to submit was actually wrong and thankfully you did not make any other submissions as well in the contest. Ratings saved -_-
No, happiness is finding out that you actually submitted it somehow and got a REALLY high place because of it.
And sadness is finding out that it failed on systest no. 124.
As I see, happiness can be anything! :D Maybe we should create this topic: What is happiness at Codeforces?
is that happened to you? Failing on 124 B(
In Gym, once. But not in this "happiness/sadness situation".
A lot of happiness and sadness theorem :p
A wave of "Black ID" ~ ~
I don't know why your handle of codeforces is so special :|
The first time when I used Topcoder Arena,I thought that "TopCoder" have a better message,so chose It.It is To Be Top Coder for me , but not for TopCoder,INC.##Too young at that time .~,~ ~,~
gl & hf :P 2 mny CHRs
Wow, it was a spell?
The first Codeforces Android Application is now available on the Google Play Store. You can download it here-
https://play.google.com/store/apps/details?id=com.innsolutions.codeforcesstats
With this app you can do the following things- 1. User Info- Basic Profile Info, Rating Change History, Submissions History of any user. 2. Compare Users- Compare the overall info of as many users as you want or Compare Head To Head which lets you compare upto 4 users in Common Contests, i.e., contests in which all the given users have performed. 3. Search Problems- Search for problems by tags, index, name, contest id or solved count. 4. Search Users- Search by name, handle, organisation, city or country.
sadness is , in our country we can't visit google web page,because of Great Firewall :(
Don't sites like hidemyass.com and stuff like ultrasurf help in bypassing it?
But aren't these sites blocked by the Firewall as well?
Try using a proxy server..
LOL! :D
I try It Application. It seems to me that it's a completely useless app. Sorry.
Hey knst no need to say sorry. You did not like this app, that's fine. This app does what it's supposed to do, whatever's written in the description. If those features are of no use to you, just go ahead & uninstall it.
As far as the ad displayed there is concerned, i have nothing to do with it. Those ads are put there by Google & i had no idea these type of ads could be displayed. Well I'll remove the banner ad in the next update. Sorry for the inconvenience.
I have a question (I'm new to here.. I've attended just one round in Codeforces)
If I register this round, then I must attend the contest? so If I have a important thing to do, and I can't attend the contest, then my ratings will fall down?
(sorry for bad english :< English is not my native language...)
Rating won't be changed unless you submit something.
Aha! Thanks for your reply. I've worried about that..
I'm a high school student in Korea, and the contest will be started at 00:30 AM in korea.. It's too late here :<
I think so
Time i move up to specialist or maybe Expert
you only need -2 too reach newbie even if you get rank 1 you cant reach expert :|
I went from 1283 to 1602 in one contest, so it is definitely possible.
Keep Calm and be expert ;)
You are sure to succeed if you work harder.believe yourself :)
Thanks for the encouragement guys and too keyvankhademi thanks for the moral boost i needed that.
gl & hf :)
Help me :( I am new here and I am not able to find any link to register for Round262. There's just date and time link but no registration link :/ Someone help me quickly, only 90 minutes left for registration.
Its 90 mins before the registration starts, read it more carefully.
Oh, my bad. Thanks, mate.
Let's (not) hope for more math(!)
let's not hope for anything.
let's just solve everything!
Yes, let's solve more math.
My first contest hope I get good ranking :D hue hue
Are you a genius black (unrated) ? or no?
He's from Krusty Krab. I do belive he is!
What do they do in Krusty Krab?? He got 6th place!! :D
They cook Krabby Patties, WITH CHEESE :D You must learn cooking them. Please refer to spongebob. ;)
Their Krabby Patties must be as hard and brute as his hardcode 7530765
:o longest code ever I saw in my life that someone make in contest :|
I guess he wrote another code to generate this code :) It seems easier.
guy,good luck to you !
oh,div.2!why two times?
same question to you ;)
Hope for all "beautiful" bruteforce problemset only and strong pretest :v
even my granny can solve brute force let's hope to be able to solve hard problems ;)
I think some of the people in Div. 1 are using some fake accounts to enter Div. 2 contests and because of this we can't rise. I think you should find a solution to this problem.
You're right
there is a good solution here.
Let's have fun and enjoy codeforces!
what a hot contester:O
It's Hyuna, Korean actress =))
she was hot just as a contester, not any more
Scoring?
I've always had this question in mind.
When you click on Registered Users > Friends.
How are the users ordered? On what basis?
on time of registration it's easy to understand when you register you come first :D and so on
Sadness is electricity go out in the middle of a rated contest ! Egypt !!
Sadness is electricity go out for a week ! Syria :)
God with u Syria :(
WOW, a record in registrants 4824 :D
Over 4000 contestant take part in. This will be an interesting round!
hi can someone from codeforces look into it hightail gives it correct ans but it fails on pretest 1
sub id-7526210
same here
same here....my code is giving right ans on my pc with first test case...
but wrong ans on 1st test case :'(
http://ideone.com/siiNCJ
using pow((double)i,a) replace pow(i,a)
put your code in ideone and give the link....or else wait till the system test finishes
find the difference :D http://codeforces.net/contest/460/submission/7528410 http://codeforces.net/contest/460/submission/7535330
aint the difference too obvious, in the first one you are calling pow, the inbuilt math function which gives error due to some precision problem, and casting combo, like on my system (long long)pow(5,2) gives 24. But in the accepted submission you are calling your user defined method.
using pow((double)i,a) replace pow(i,a)
Shame.
Eco worst girl.
what's your goal?
again and again :| he's crazy !
...
oh, come on, why not just shooting him private message with explanation why it's bad idea instead of blaming publicly..
Happens to me in last contest also :D
"please give me your code B and me give you my code A."
He didn't even solved A.
Liar :P
There are many newly registered users on top of standings... the same to what happened at recent contests...
Wasn't B harder than usual?
I think my solution of problem B will not pass system test, but i got 4 successful hack on problem B. :P
the same :D
What is the tricky test in problem B?
writing your own pow() function :P
Is it because of integer overflow?
nope, precision error when casting to long long, pow() function returns double, just check this, cout<<pow(5,2), then after casting see this cout<<(long long)pow(5,2), returns 24 instead of 25
I wrote my own pow function, and i failed the system test because of overflow. Anyway thank to you that now i know i should use my own function for pow for precision.
Do you know how could i reproduce it in my computer? I get 25 and not 24 in both cases, I swear... When i run the testcase in which i failed in the final tests in my computer, it returns the correct result... I HATEE THISS!!!!
it can return either 24.999999999, if you cast in this case, it would return 24. But it may also return 25.00000000001, and in that case you will end with 25 only after casting. There may be some case where it is failing. Try printing the float values in your submission.
you can use the O(log n) implementation in pow
a^n=a^(n/2)*a^(n/2) if (n%2==0) a^n=a^(n/2)*a^(n/2)*a if(n%2==1)
Some people enumerate the x rather than s(x).Some people didn't consider all the answer should less than 1e9. Sorry for my poor English.
Some people check s(x) in range 1..72, and I don't understand why.
Are they really thought, that max(s(x)) == 72?
They probably thought that 10^9 has 9 digits and 10^9 — 1 is 99.999.999, which has 8 digits. And 8 * 9 = 72.
But one man in my room check s(x) in range 1..100 and check res=b*pow(i,a)+c in range if(res <= 1000000000) And it is clear solution... :)
It is really a correct solution cause s(res) can't be bigger than 81
It is correct; for s(x) ≥ 82, you will simply fail either the check s(res) = s(x) or the check res ≤ 109 all the time.
I did max in range 72. Made the silliest of counting mistakes!! Green now!!
Lets make a predictions D's test #7 K equals 3 ..!
I only doubt on 3'Ks for my solution.
UPD: a bug found. maybe K equals 2.
What is the tricky test case for Hacking B ?
5 10 9996 if you don't have: if(x<1e9)
i used 5 10 0 which gives a number larger than 1e9
And 1 1 -2 for if(x<0).
3 1028 -9577
4 30 719
Just because somebody check sum of digits only up to 72 or even 45.
Problem B was so easy to hack! Just use (for example) "5 710 1" as an input for people who used int instead of long long :)
There was something wrong with pretests for the second question . I was getting the correct output on my compiler. But when I added
if(x == 13726)cout << "" ;
While I'm trying to hacking a solution by generate input using generator in c++ I see a line. ( I don't remeber it). I put -o2 but it doesn't work. What should it print in that line?
Can somebody please explain, why http://ideone.com/rbsIwP works on ideone, and not on the judge (or in codeblocks either). I wasted around 50 minutes wondering about the problem with my solution, and at last just gave a try to user defined power function and it worked. But why was i getting different results from two judges running the same compiler??
If you used
pow()
, then note that this function works with floating point values and might not compute the exact answer. For example,pow(5, 2)
might return24.99999999
.It is generally undesirable to involve floating point computations in places where integer math would suffice.
Ok, I knew it returns double so used casting....but just carelessly ignored the fact that it might need a ceil function as well...will try testing with (long long)ceil(pow());
What if
pow(5, 2)
returns25.00000001
? :)Contest is over ! I solved C by binary-search the answer + O(n) check. D seems to be hard with that xor operator. I got E pass pretest using back-tracking n elements from a set of a few boundary points. Hope my solution can get AC.
Upd: Yeah!!! E Accepted. Hello Div 1 :))
Wrong answer pretest 1 of problem B ??? really frustrated!!!!
Got the same problem then one of friend told me not to use the built in power and replace it with your function implemented simply iteratively and it worked. I hope same is the case with you :)
Yes, that happened to me as well. You have to define a pow function yourself, the default one won'w work (no idea why honestly).
how to solve B ?
you must try all of s(x). s(x) is in range(1..81). so for each s(x) you calculate x=b*s(x)^a+c. If x>0 && x<1e9 you add x to the list of answers. Something like that :D
You forgot to check is s(x) equal to current sx
x = b*pow(s(x),a) + c As s(x) <= 81 as x <= 1e9 Take a loop from 1 to 81 For each i find x = b*pow(i,a) + c If s(x) == i and 0< x < 1e9 then x is a solution
My solution for example. You check every sum of digits from 1 to 81 and compute X from equation. Then just check that sum of digits of X is equal to yours.
You just need to iterate through different possible values of s(x) as there are only 81 possibilities for it in case of 999999999 it will be 81. now find the expression b*s(x)^a +c and check whether obtained x has the same s(x) value or not.if yes increase the counter.also need to check whether x<=10^9.
could you explain pls why there are only 81 possibilities,i couldn't get that point.
If s(x) is the sum of the digit of number x, then the maximum sum we can achieve is with number 999999999 (10e9-1). In this case, s(999999999)=81. Hope this helps :)
We cannot have a sum larger, since 9 is the biggest digit we can get
I was getting wrong answer on pretest 1. Can anyone check my submission. I did the same thing as you guys mentioned. http://codeforces.net/contest/460/submission/7530259
Never use already implemented pow function unless you need it for doubles, write your own, its not hard, and even O(exponent) one is okay with time :)
7534711
You must be careful with
pow()
. Also, there is bug somewhere else.I just noticed D asks for any subset with cardinality <= k, not any subset with cardinality = k... Now I know why everyone was getting AC so fast :P (hint: the xor of x*4, x*4+1, x*4+2, x*4+3 is always zero)
how to solve K=3?
2·2i - 1, 3·2i - 1, 3·2i for some i if there's any; otherwise the XOR is at least 1.
that seems not to be the only condition. counter example: 5 ^ 10 ^ 15 = 0
If the range includes the numbers 5, 10, 15, then the range also includes 7, 11, 12 (generated by i = 2) whose XOR is also 0.
I'm wondering: how did you think of this triplet?
I thought that 3, 5, 6 works (gives XOR of 0), so there is a possibility with three numbers. Then I toyed around with proving of stuffs. Like, the most significant bit that is set among the three numbers must be set twice for the XOR to be 0 (e.g. 5 and 6 both have third least significant bit set). Then the remaining number will obviously be the minimum, and consequently to minimize the range covered (and thus maximizing the probability of a range having these numbers), we need them to be . Then the second most significant bit must also be set twice, so we have three numbers 2i + a, 2·2i + b, 3·2i + c where , and obviously we minimize the range covered by letting a = 2i - 1, c = 0, and b = 2i - 1 follows. Then I also managed to prove that this is the best solution; that is, if these numbers aren't possible (and k = 3), then there is no solution with XOR 0.
Confused? Yes; I'm not even sure how I managed to stumble on that solution.
I used this in my solution. Suppose k = 3 and there are three such numbers whose XOR gives 0. Let's look at the numbers bit by bit. First, the highest bits will be
(there is no other possibility). Now, for the next position, there are several possibilities. First, all three bits can be 0:
We can actually do this for zero or more positions:
But on the last position there has to be something different, otherwise the first two numbers would be equal. So, on some next position there won't be three zeroes, and we arrive to the other two possibilities for this position. The second one is
We want to keep the numbers close to each other because of the l, r constraints. So let's make the biggest number small as possible and the smallest number big as possible:
And for the third possibility:
notice that if we can use it, then we can also use the solution for the second possibility. So, the final answer is
or 2i + 2j, 2i + 2j - 1, 2j + 1 - 1 for permissible values of i, j. Now we can just check all values of i, j and see if the result fits between l and r.
And now (I realised this after seeing chaotic_iak's answer), if we have an answer of form
then the answer
also fits the l, r constraints. So we can let j = i - 1 and only check
if x%2==0 then x^(x+1)^(x+2)^(x+3)==0 :D lol
nice observation, thank you
My solution for problem C was failing the test case
because of an under flow that I discovered 3 mins after the end of the contest ! :D Ok that's something new :D
And I failed the B because of an overflow and failed the C because of an underflow :)
In fact, this competition was really fun. I knew I will be hacked at B, cause I didn't check the upper limit, so I started searching for people that didn't do same thing, and got 5 successful hacks. After that, I noticed that a lot of people were only checking the sum of the digits up to 72, so I started a brute force program to find some solution which sum of digits is >72, and found one, another +500 points. In fact, the thing I wrong-solved it gave me bonus points. The thing I forgot to set upper bound of binary search to 2*10^9, so I lost that task, and only one guy also forgot that, the guy who hacked me. :D Btw, the contest was great!
How to solve C , Can anyone explain ?
Binary search the solution, and try to implement your own check method, can the minimum be x?
Can u explain ur check method ?
Uhm, lemme try(atleast how I did it) First, make an array left, such that left[i]=max(0,x-a[i]) After that, iterate through that array, and see, if the current number of "open" intervals is less than left[i], open more left[i]-cur intervals, always number of total intervals and number of current intervals. You can check my solution, it failed because of the high constraint, the check method is right.
http://codeforces.net/contest/460/submission/7531713 what was wrong with my div2 C solution? I used binary search
One problem is that the answer can be more than 1e9.
For example:
The answer is 1000010000, so you just need to change "high".
thanks :) but there z still some fault
This contest was very frustrating >.<. At least I learned that using the built-in function pow() is bad and I definitely won't use it in future contests. The amount of newly registered users placing in the top 500 is insane, and seeing others in your rooms getting hacked by reds before you can even try to hack them is sad. Please let there be a contest for both Div1 and Div2 soon to stop this!
fastest sys test I saw in my life !
thx for B =)
HATE LONG LONGs!!! HATE COMPILATION ERROR!!! I was late with my correct D solution just for 5 seconds!
Back to Specialist !
In the task statement for B, it is clearly written: "Print only integer solutions that are larger than zero and strictly less than 109.". However, the output for the 10th case is:
6 208000352 1333225037 -2113928864 -881045069 855318976 -1059281175
Can someone offer an explanation, please? :)
That is your output, not the judge's answer.
I am an idiot. Sorry for taking your time. :P
This is the output of your program not the output of the tester's solution !
Hi, I try to make a solution for B problem, but my solution failed in the final case, however I can not understand why, somebody can explain me, here is my solution http://codeforces.net/contest/460/submission/7531464
You check whether number is smaller than 108, rather than 109 (count zeroes). AC:7534579. And exponential format is your friend (it is absolutely precise because mantissa of double is 52 bits: 7534816) in avoiding such errors.
the argument to sumDig() function in the following line can be greater than what 'int' can store :)
In function SumDig(int a) , I think the parameter should be SumDig(long long a) instead
Well, I'll be green again :-(
You're welcome =D
First blood on E! And 1 condition away from 2nd place...
I'm surprised at how many people failed it and especially at how many reds did, it seemed like the pretests were quite strong (due to asking for a complete solution). I solved it using DP on states (,) of towers placed so far, plus not trying all points but only border points — observe that if we can pick points (x + 1, y) and (x - 1, y), then for (x, y) to be picked as the last point in a possible solution (these other points don't give better solutions), and respectively, but then and we can move this point (x, y) left and right without changing the answer; similarly for the y-coordinate. Then, I get an O(N3R3) solution with a good constant.
http://codeforces.net/contest/460/submission/7533008 very lucky :)
very unlucky :( WA code during contest: http://codeforces.net/contest/460/submission/7527136 AC code after contest : http://codeforces.net/contest/460/submission/7533966
It's only different in one line in WA code for setting a random seed.
But The method seem to crazy :p
Yeah, it seems crazy — still, much simpul and very works. Wow.
Recently I am having an OI training course which focus on approximate algorithm, so that solution came to me naturally (but yes, I was really lucky).
I tried to solve C in a different way, Like , I built a segment tree with range minimum query with the left most minimum value. Now each day , I find int r = RMQ(1,n) and update range from r to r+w-1 with value 1. after mth day the RMQ(1,n) is the answer. I got WA in case 8. I don't know if it is due to my wrong implementation of the segment tree or my idea is wrong. Can someone tell ? Here's my submission 7531931
I try same approach, but fail to implement update on a segment in a fast fashion (
Well I tried the lazy update. I don't know if this approach is correct though.
i used segment tree with lazy update, and got AC. So i am sure your idea is correct, maybe just unlucky
This approach can work. I got it to pass during contest: http://codeforces.net/contest/460/submission/7527890
Bad Day for me in problem B.
Hacked
AC
The only difference is that I did not check for x > 0 && x < 10^9.
Codeforces round 262, div 2 problem 2
http://ideone.com/7ghrM6
my code is working correct on ideone (for the incorrect test case) but its giving wrong answer here. Please help!!!
http://codeforces.net/contest/460/submission/7533280
Dont use implemented pow, write your own.
try to code your own pow function because you loose data going from double to long long.
For Problem B
my solution on ideone gives the correct output for the case : 3 2 8:
http://ideone.com/JctOLq
but on codeforces compiler it is showing different answer: http://codeforces.net/contest/460/submission/7534562
can somebody explain why ?
It happened because you used the
pow
function which works with doubles and has precision errors. It has been said in an earlier comment that(long long)pow(5, 2)
returns 24 instead of 25 because the double returned is 24.9999 and it is casted to an integer value.The MS C++ compiler has another implementation for
pow
and it works better in this problem. This is how I got ACC with the inbuilt function.Very nice contest. D was very interesting , especially when k = 3. E was a bit harder than usual. I only succeded in makeing a back placeing half of the towers and put the other ones simetrically. I am not sure of it's correctitude , but I think it's a way to go as N ≤ 8.
Problem B, Getting right answer con muy visual studio and ideone, but in the contest shows a different answer,#7533294
I actually got the same problem =D
Can someone please give a clear explanation how to solve problem C?
In problem C, test case 5
How is the answer 500? Isn't it supposed to be 499?
Water indices [1, 8], [2, 9], [3, 10] (one-based).
EDIT: Wrong reading. (I didn't solve C.) Water indices [1, 3], [2, 4], [3, 5], ..., [8, 10] instead.
We have
m = 8
andw = 3
. So lets do 8 operations:Right, thanks!
vitux Neodym I am always getting this stupid warning in B, even though** I have no printf statement in code**? Please tell me the reason. it is not even allowing to submit.
Code : http://ideone.com/2kAsED
Here is the screenshot. Screen-shot : http://postimg.org/image/5rtdr33kt/
Can someone explain how to solve C using binary search?
I can't figure out how to check if some number 'X' is a solution.
the check function is f(x) :
you can do it greedy,
When will i get the editorials for this contest
Problem C : Please Explain why updating from left-Most or Right-Most minimum solve the problem.Will It be work (Select any continuous Subarray of length m containing minimum number) and why??[contest:460][problem:C]
.
i doubt the 'any continuous subarray of length m containing minimum' will work, but left most or right most will
this is my general idea : input : 6 2 3 1 2 1 2 1
updating left most smaller will resulting an array : 2 3 2 2 1
then, because 1 is smallest, we choose updating index 4 till 6, becoming : 2 3 3 3 2
if we update the middle first (index 3), it will has result : 1 3 2 3 1
and after that, anything we choose will still have value 1 in array
Topocder SRM 630 in 6 hours, will miss it :(.
SRM is after 30 hrs :P
It is after about 30 hours
check its time again
Irony of the day ! When I thought that this is was not my contest. I had a message from Codeforces telling me that I got one of the best rating changes in this round.
Problem C: A teacher can have a birthday after 10 ^ 5 days? :D
Yes, if teacher lives on Saturn or Neptun
My Code For Problem B gives the right answer for 1st case on my IDE But Different one on the judge !!
http://codeforces.net/contest/460/submission/7536450
What is the reason behind that !!
You are using the built-in pow function. It has been discussed above why it's not correct.
found it thanks :D
Country Wise Standings for this round has been updated.
Hi, I'm new here. I submitted for the first problem two times, I got a run time error in the first attempt and my second attempt was accepted. and I didn't solve any other problems. The strange think is that my rating decreased!! Can anybody explain why this happened? thank you
Your expected rank was less than 1733 and you got around 2400 so that's why your rating was decreased.
I wrote short description of possible hacks with some statistics. If you are interested — take a look: here.
Hi.
I had error in the problem B, for one case.
Now that I can see the result, it is very strange because on my computer gives the full result.
This had happened to me once I think. What mistake I be making?
Man please do you read posts? It has been asked a lot. Nevermind, you need to make your own pow function because built in pow function won't work. That's the whole thing.
Please read the comments above, the pow function works with doubles and sometimes has problems with precision. Write your own pow function and everything should be better.
The final answer about using the pow function is:
Use the BUILT-IN function with type casts ONLY IF your language is "Microsoft Visual C++ 2010"
OTHERWISE use your own function (e.g. when using GNU compilers)
As far as type casts are considered, see this submission as an example: http://codeforces.net/contest/460/submission/7535442
The answer is to avoid
pow()
altogether for integer math. It works with floating point values, there is no guarantee that it will return the precise answer. Even if it does compute the precise answer for some integer values,double
still typically has less than 64 mantissa bits, and the result cannot be always stored exactly.For example,
on MSVC++ returns 11920928955078124 instead of 11920928955078125.
I had seen the editorial,seen the solution but didn't understand the solution of problem-C(present),why we do binary search in that problem,can anyone easily explain me the solution :/ .
I will explain my solution, which got AC during the contest.
First of all, we can notice that if we binary search the minimum height of a flower, we'll call it X, and we can do at most M updates to make each flower of height >= X, any minimum height < X can be a solution of our problem, because we can do the same updates as for X.
Now, we have X and we try to see if X can be a valid solution. Let's note S[i] = minimum number of updates we should do over the first i flowers to make each flower with index from [1...i] at least of height X. We look at the i-th flower and we determine it's current height as follows: CurrentHeight[i] = InitialHeight[i] + S[i — 1] — S[i — W]. (S[i — 1] — S[i — W] denotes how many updates we did over the intervals of length W, which cover the i-th flower). If CurrentHeight[i] < X, S[i] = S[i — 1] + X — CurrentHeight[i] (we do X — CurrentHeight[i] updates with the leftmost element as the i-th flower), else S[i] = S[i — 1].
If S[N] <= M, X is good and we look for a bigger one, else we look for a smaller one :)
Code: http://codeforces.net/contest/460/submission/7521789
Clear, thanks for taking the time to explain.
Nicely Explained :)
Round #263?
where are this rounds editorial?
Click here to view editorial of this round