### Neodym's blog

By Neodym, 5 years ago, translation, ,

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

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.

• +159

 » 5 years ago, # |   +13 The link to timeanddate is broken ;)
•  » » 5 years ago, # ^ |   +3 try this one.
 » 5 years ago, # |   +34 Brace yourself, newly registered users are coming.
•  » » 5 years ago, # ^ |   +26 recently new registered users are very genius!
•  » » » 5 years ago, # ^ |   -13 are you sure about "new" users !!I am not sure but i think 90 % among of then is Div1 members.
•  » » » » 5 years ago, # ^ |   +48 Irony is the very complicated thing, huh?
•  » » » 5 years ago, # ^ |   +11 lol
•  » » » 5 years ago, # ^ |   0 Yep....
 » 5 years ago, # |   +80 Two consecutive Div.2 only rounds ! :|Time for a Div.1 + Div.2 round :)
•  » » 5 years ago, # ^ |   0 Hope that time of div1 will not be long.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 Maybe it should be called Div.1.5.Because it is harder than usual Div.2 and easier than Div.1.
 » 5 years ago, # | ← Rev. 2 →   +13 I think this is time to be pupil.. :D
•  » » 5 years ago, # ^ |   +14 why not? wake up man !
•  » » 5 years ago, # ^ |   +14 I think so too :)
•  » » 5 years ago, # ^ |   +12 Good luck :)
 » 5 years ago, # |   +18 Happiness is , checking the 'Contest' tab each alternate day, and finding a Codeforces Round there! :)
•  » » 5 years ago, # ^ |   +69 sadness is to discover that the contest is div2 only
•  » » » 5 years ago, # ^ |   +21 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! :)
•  » » » » 5 years ago, # ^ |   +23 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 -_-
•  » » » » » 5 years ago, # ^ |   +1 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.
•  » » » » » » 5 years ago, # ^ |   +19 As I see, happiness can be anything! :D Maybe we should create this topic: What is happiness at Codeforces?
•  » » » » » » 5 years ago, # ^ |   0 is that happened to you? Failing on 124 B(
•  » » » » » » » 5 years ago, # ^ |   -7 In Gym, once. But not in this "happiness/sadness situation".
•  » » 5 years ago, # ^ |   0 A lot of happiness and sadness theorem :p
 » 5 years ago, # |   +9 A wave of "Black ID" ~ ~
•  » » 5 years ago, # ^ |   0 I don't know why your handle of codeforces is so special :|
•  » » » 5 years ago, # ^ |   0 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 .~,~ ~,~
 » 5 years ago, # |   0 gl & hf :P 2 mny CHRs
•  » » 5 years ago, # ^ |   0 Wow, it was a spell?
 » 5 years ago, # |   +7 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.codeforcesstatsWith 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.
•  » » 5 years ago, # ^ |   0 sadness is , in our country we can't visit google web page,because of Great Firewall :(
•  » » » 5 years ago, # ^ |   0 Don't sites like hidemyass.com and stuff like ultrasurf help in bypassing it?
•  » » » » 5 years ago, # ^ |   0 But aren't these sites blocked by the Firewall as well?
•  » » » 5 years ago, # ^ |   +5 Try using a proxy server..
•  » » 5 years ago, # ^ | ← Rev. 3 →   +21 LOL! :DI try It Application. It seems to me that it's a completely useless app. Sorry.
•  » » » 5 years ago, # ^ |   +3 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.
 » 5 years ago, # |   +10 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...)
•  » » 5 years ago, # ^ |   +11 Rating won't be changed unless you submit something.
•  » » » 5 years ago, # ^ |   +6 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 :<
•  » » » » 5 years ago, # ^ |   0 I think so
 » 5 years ago, # |   -6 Time i move up to specialist or maybe Expert
•  » » 5 years ago, # ^ |   -29 you only need -2 too reach newbie even if you get rank 1 you cant reach expert :|
•  » » » 5 years ago, # ^ |   0 I went from 1283 to 1602 in one contest, so it is definitely possible.
•  » » 5 years ago, # ^ |   +5 Keep Calm and be expert ;)
•  » » 5 years ago, # ^ |   0 You are sure to succeed if you work harder.believe yourself :)
•  » » » 5 years ago, # ^ |   +8 Thanks for the encouragement guys and too keyvankhademi thanks for the moral boost i needed that.
 » 5 years ago, # |   -6 gl & hf :)
 » 5 years ago, # |   +3 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.
•  » » 5 years ago, # ^ |   +3 Its 90 mins before the registration starts, read it more carefully.
•  » » » 5 years ago, # ^ |   +3 Oh, my bad. Thanks, mate.
 » 5 years ago, # |   +5 Let's (not) hope for more math(!)
•  » » 5 years ago, # ^ |   +6 let's not hope for anything. let's just solve everything!
•  » » » 5 years ago, # ^ |   +7 Yes, let's solve more math.
 » 5 years ago, # |   +12 My first contest hope I get good ranking :D hue hue
•  » » 5 years ago, # ^ |   +4 Are you a genius black (unrated) ? or no?
•  » » » 5 years ago, # ^ |   +10 He's from Krusty Krab. I do belive he is!
•  » » » » 5 years ago, # ^ |   +3 What do they do in Krusty Krab?? He got 6th place!! :D
•  » » » » » 5 years ago, # ^ |   +4 They cook Krabby Patties, WITH CHEESE :D You must learn cooking them. Please refer to spongebob. ;)
•  » » » » » » 5 years ago, # ^ |   +5 Their Krabby Patties must be as hard and brute as his hardcode 7530765
•  » » » » » » » 5 years ago, # ^ |   0 :o longest code ever I saw in my life that someone make in contest :|
•  » » » » » » » » 5 years ago, # ^ |   0 I guess he wrote another code to generate this code :) It seems easier.
•  » » 5 years ago, # ^ |   +1 guy,good luck to you !
•  » » 5 years ago, # ^ |   0 Hi fellow Indonesian :)
 » 5 years ago, # |   -8 oh,div.2!why two times?
•  » » 5 years ago, # ^ |   +18 same question to you ;)
 » 5 years ago, # |   0 Hope for all "beautiful" bruteforce problemset only and strong pretest :v
•  » » 5 years ago, # ^ |   -6 even my granny can solve brute force let's hope to be able to solve hard problems ;)
 » 5 years ago, # |   0 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.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 You're right
•  » » 5 years ago, # ^ |   0 there is a good solution here.
 » 5 years ago, # |   +12 Let's have fun and enjoy codeforces!
 » 5 years ago, # |   0 what a hot contester:O
•  » » 5 years ago, # ^ |   0 It's Hyuna, Korean actress =))
•  » » » 5 years ago, # ^ |   0 she was hot just as a contester, not any more
 » 5 years ago, # |   -11
 » 5 years ago, # |   -11
 » 5 years ago, # |   +2 Scoring?
 » 5 years ago, # |   0 I've always had this question in mind.When you click on Registered Users > Friends.How are the users ordered? On what basis?
•  » » 5 years ago, # ^ |   0 on time of registration it's easy to understand when you register you come first :D and so on
 » 5 years ago, # |   +14 Sadness is electricity go out in the middle of a rated contest ! Egypt !!
•  » » 5 years ago, # ^ |   0 Sadness is electricity go out for a week ! Syria :)
•  » » » 5 years ago, # ^ |   +3 God with u Syria :(
 » 5 years ago, # |   0 WOW, a record in registrants 4824 :D
•  » » 5 years ago, # ^ |   0 it is DIV2 only if it divided into 2 DIV 1 and 2 it will be the half
 » 5 years ago, # |   0 Over 4000 contestant take part in. This will be an interesting round!
 » 5 years ago, # |   +4 hi can someone from codeforces look into it hightail gives it correct ans but it fails on pretest 1sub id-7526210
•  » » 5 years ago, # ^ |   +4 same here
•  » » » 5 years ago, # ^ |   0 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
•  » » » » 5 years ago, # ^ |   0 using pow((double)i,a) replace pow(i,a)
•  » » 5 years ago, # ^ |   0 put your code in ideone and give the link....or else wait till the system test finishes
•  » » » 5 years ago, # ^ |   0
•  » » » » 5 years ago, # ^ |   0 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.
•  » » 5 years ago, # ^ |   0 using pow((double)i,a) replace pow(i,a)
 » 5 years ago, # |   +4 Shame.
•  » » 5 years ago, # ^ |   -8 Eco worst girl.
•  » » 5 years ago, # ^ |   +1 what's your goal?
•  » » 5 years ago, # ^ |   +3 again and again :| he's crazy !
•  » » 5 years ago, # ^ | ← Rev. 2 →   -11 ...
•  » » 5 years ago, # ^ |   +1 oh, come on, why not just shooting him private message with explanation why it's bad idea instead of blaming publicly..
•  » » 5 years ago, # ^ |   +2 Happens to me in last contest also :D
•  » » » 5 years ago, # ^ |   0 "please give me your code B and me give you my code A."
•  » » » » 5 years ago, # ^ |   0 He didn't even solved A.Liar :P
 » 5 years ago, # | ← Rev. 2 →   +3 There are many newly registered users on top of standings... the same to what happened at recent contests...
 » 5 years ago, # |   0 prestest 7 in Problem A !
 » 5 years ago, # |   +7 Wasn't B harder than usual?
 » 5 years ago, # |   +3 I think my solution of problem B will not pass system test, but i got 4 successful hack on problem B. :P
•  » » 5 years ago, # ^ |   -8 the same :D
•  » » 5 years ago, # ^ |   0 What is the tricky test in problem B?
•  » » » 5 years ago, # ^ |   0 writing your own pow() function :P
•  » » » » 5 years ago, # ^ |   0 Is it because of integer overflow?
•  » » » » » 5 years ago, # ^ |   0 nope, precision error when casting to long long, pow() function returns double, just check this, cout<
•  » » » » » » 5 years ago, # ^ |   0 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.
•  » » » » » » 5 years ago, # ^ |   0 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!!!!
•  » » » » » » » 5 years ago, # ^ |   0 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.
•  » » » » » » » 5 years ago, # ^ |   0 you can use the O(log n) implementation in powa^n=a^(n/2)*a^(n/2) if (n%2==0) a^n=a^(n/2)*a^(n/2)*a if(n%2==1)
•  » » » 5 years ago, # ^ |   +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.
•  » » » » 5 years ago, # ^ |   0 Some people check s(x) in range 1..72, and I don't understand why. Are they really thought, that max(s(x)) == 72?
•  » » » » » 5 years ago, # ^ |   0 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.
•  » » » » » 5 years ago, # ^ |   0 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... :)
•  » » » » » » 5 years ago, # ^ |   0 It is really a correct solution cause s(res) can't be bigger than 81
•  » » » » » » » 5 years ago, # ^ |   0 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.
•  » » » » » 5 years ago, # ^ |   0 I did max in range 72. Made the silliest of counting mistakes!! Green now!!
 » 5 years ago, # | ← Rev. 2 →   0 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.
 » 5 years ago, # |   +1 What is the tricky test case for Hacking B ?
•  » » 5 years ago, # ^ |   0 5 10 9996 if you don't have: if(x<1e9)
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 i used 5 10 0 which gives a number larger than 1e9
•  » » 5 years ago, # ^ |   0 And 1 1 -2 for if(x<0).
•  » » 5 years ago, # ^ |   0 3 1028 -9577
•  » » 5 years ago, # ^ |   +5 4 30 719Just because somebody check sum of digits only up to 72 or even 45.
 » 5 years ago, # |   0 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 :)
 » 5 years ago, # | ← Rev. 5 →   +4 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 << "" ; I could pass the pretests I don't know why .
 » 5 years ago, # |   0 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?
 » 5 years ago, # |   +1 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??
•  » » 5 years ago, # ^ |   +1 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 return 24.99999999.It is generally undesirable to involve floating point computations in places where integer math would suffice.
•  » » » 5 years ago, # ^ |   0 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());
•  » » » » 5 years ago, # ^ |   0 What if pow(5, 2) returns 25.00000001? :)
 » 5 years ago, # | ← Rev. 2 →   0 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 :))
 » 5 years ago, # |   0 Wrong answer pretest 1 of problem B ??? really frustrated!!!!
•  » » 5 years ago, # ^ |   0 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 :)
•  » » 5 years ago, # ^ |   0 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).
•  » » 5 years ago, # ^ |   0 Same thing happened with me. Totally frustrated!
 » 5 years ago, # |   0 how to solve B ?
•  » » 5 years ago, # ^ |   +1 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
•  » » » 5 years ago, # ^ |   +1 You forgot to check is s(x) equal to current sx
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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
•  » » 5 years ago, # ^ |   +3 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.
•  » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ |   0 could you explain pls why there are only 81 possibilities,i couldn't get that point.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 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
•  » » 5 years ago, # ^ |   0 I was getting wrong answer on pretest 1. Can anyone check my submission. I did the same thing as you guys mentioned. http://codeforces.com/contest/460/submission/7530259
•  » » » 5 years ago, # ^ |   0 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 :)
•  » » » 5 years ago, # ^ |   0 7534711You must be careful with pow(). Also, there is bug somewhere else.
 » 5 years ago, # |   +8 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)
•  » » 5 years ago, # ^ |   +8 how to solve K=3?
•  » » » 5 years ago, # ^ |   +10 2·2i - 1, 3·2i - 1, 3·2i for some i if there's any; otherwise the XOR is at least 1.
•  » » » » 5 years ago, # ^ |   +3 that seems not to be the only condition. counter example: 5 ^ 10 ^ 15 = 0
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   +6 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.
•  » » » » 5 years ago, # ^ |   +3 I'm wondering: how did you think of this triplet?
•  » » » » » 5 years ago, # ^ |   +19 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.
•  » » » » » 5 years ago, # ^ | ← Rev. 3 →   +24 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 1..... 1..... 0.....(there is no other possibility). Now, for the next position, there are several possibilities. First, all three bits can be 0: 10.... 10.... 00....We can actually do this for zero or more positions: 1000.... 1000.... 0000.... ^^^ 0+ timesBut 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 1000..1... 1000..0... 0000..1... ^^^^^ 0+ timesWe 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: 1000..1000 1000..0111 0000..1111 ^^^^^ 0+ timesAnd for the third possibility: 1000..1... 1000..1... 0000..0... ^^^^^ 0+ timesnotice that if we can use it, then we can also use the solution for the second possibility. So, the final answer is 1000..1000 1000..0111 0000..1111 ^^^^^ 0+ timesor 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 1000..1000 1000..0111 0000..1111 ^^^^^ 0+ timesthen the answer 11000 10111 01111also fits the l, r constraints. So we can let j = i - 1 and only check 2i + 2i - 1, 2i + 2i - 1 - 1, 2i - 1
•  » » » » » » 5 years ago, # ^ |   0 Thanks for the detailed reply. Your approach is great, coupled with chaotic_iak's approach, it becomes perfect!
•  » » 5 years ago, # ^ |   +3 if x%2==0 then x^(x+1)^(x+2)^(x+3)==0 :D lol
•  » » 5 years ago, # ^ |   0 nice observation, thank you
 » 5 years ago, # | ← Rev. 3 →   +3 My solution for problem C was failing the test case 6 2 1 1 2 2 2 2 1 because of an under flow that I discovered 3 mins after the end of the contest ! :D Ok that's something new :D
•  » » 5 years ago, # ^ |   +4 And I failed the B because of an overflow and failed the C because of an underflow :)
 » 5 years ago, # |   0 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!
 » 5 years ago, # |   +1 How to solve C , Can anyone explain ?
•  » » 5 years ago, # ^ |   +1 Binary search the solution, and try to implement your own check method, can the minimum be x?
•  » » » 5 years ago, # ^ |   0 Can u explain ur check method ?
•  » » » » 5 years ago, # ^ |   0 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.
 » 5 years ago, # | ← Rev. 2 →   0 http://codeforces.com/contest/460/submission/7531713 what was wrong with my div2 C solution? I used binary search
•  » » 5 years ago, # ^ |   +4 One problem is that the answer can be more than 1e9.For example: 1 10000 1 1000000000 The answer is 1000010000, so you just need to change "high".
•  » » » 5 years ago, # ^ |   0 thanks :) but there z still some fault
 » 5 years ago, # |   +3 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!
 » 5 years ago, # |   +16 fastest sys test I saw in my life !
 » 5 years ago, # |   +3 thx for B =)
 » 5 years ago, # |   +3 HATE LONG LONGs!!! HATE COMPILATION ERROR!!! I was late with my correct D solution just for 5 seconds!
 » 5 years ago, # |   0 Back to Specialist !
 » 5 years ago, # |   +5 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 -1059281175Can someone offer an explanation, please? :)
•  » » 5 years ago, # ^ |   +8 That is your output, not the judge's answer.
•  » » » 5 years ago, # ^ |   +15 I am an idiot. Sorry for taking your time. :P
•  » » 5 years ago, # ^ |   0 This is the output of your program not the output of the tester's solution !
 » 5 years ago, # |   +3 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.com/contest/460/submission/7531464
•  » » 5 years ago, # ^ | ← Rev. 4 →   0 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.
•  » » 5 years ago, # ^ |   +3 the argument to sumDig() function in the following line can be greater than what 'int' can store :) if(i == sumDig(b * pot(i,a)+c)) 
•  » » 5 years ago, # ^ |   +3 In function SumDig(int a) , I think the parameter should be SumDig(long long a) instead
 » 5 years ago, # |   +3 Well, I'll be green again :-(
•  » » 5 years ago, # ^ |   +1 You're welcome =D
 » 5 years ago, # | ← Rev. 6 →   +9 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.
•  » » 5 years ago, # ^ |   +8 http://codeforces.com/contest/460/submission/7533008 very lucky :)
•  » » » 5 years ago, # ^ |   +8 very unlucky :( WA code during contest: http://codeforces.com/contest/460/submission/7527136 AC code after contest : http://codeforces.com/contest/460/submission/7533966It's only different in one line in WA code for setting a random seed.But The method seem to crazy :p
•  » » » » 5 years ago, # ^ |   +13 Yeah, it seems crazy — still, much simpul and very works. Wow.
•  » » » 5 years ago, # ^ |   0 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).
 » 5 years ago, # |   0 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
•  » » 5 years ago, # ^ |   0 I try same approach, but fail to implement update on a segment in a fast fashion (
•  » » » 5 years ago, # ^ |   0 Well I tried the lazy update. I don't know if this approach is correct though.
•  » » » » 5 years ago, # ^ |   0 i used segment tree with lazy update, and got AC. So i am sure your idea is correct, maybe just unlucky
•  » » » » 5 years ago, # ^ |   0 This approach can work. I got it to pass during contest: http://codeforces.com/contest/460/submission/7527890
 » 5 years ago, # |   0 Bad Day for me in problem B. Hacked AC The only difference is that I did not check for x > 0 && x < 10^9.
 » 5 years ago, # |   0 Codeforces round 262, div 2 problem 2http://ideone.com/7ghrM6my code is working correct on ideone (for the incorrect test case) but its giving wrong answer here. Please help!!!http://codeforces.com/contest/460/submission/7533280
•  » » 5 years ago, # ^ |   0 It is all because of pow() function. Same thing happened with me.
•  » » 5 years ago, # ^ |   0 Dont use implemented pow, write your own.
•  » » » 5 years ago, # ^ |   0 do u know the reason??
•  » » 5 years ago, # ^ |   0 try to code your own pow function because you loose data going from double to long long. inline ll ipow(ll x, ll a) { if(a == 1) return x; if(a == 2) return x*x; // and so on.. return 0; } 
 » 5 years ago, # |   +2 For Problem Bmy solution on ideone gives the correct output for the case : 3 2 8:http://ideone.com/JctOLqbut on codeforces compiler it is showing different answer: http://codeforces.com/contest/460/submission/7534562can somebody explain why ?
•  » » 5 years ago, # ^ |   +2 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.
•  » » » 5 years ago, # ^ |   0 Thanks
 » 5 years ago, # | ← Rev. 4 →   0 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.
 » 5 years ago, # |   0 Problem B, Getting right answer con muy visual studio and ideone, but in the contest shows a different answer,#7533294
•  » » 5 years ago, # ^ |   0 I actually got the same problem =D
 » 5 years ago, # |   +2 Can someone please give a clear explanation how to solve problem C?
 » 5 years ago, # | ← Rev. 2 →   0 In problem C, test case 5 10 8 3 499 498 497 497 497 497 497 497 498 499 How is the answer 500? Isn't it supposed to be 499?
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » 5 years ago, # ^ |   +5 We have m = 8 and w = 3. So lets do 8 operations: after 0 operations: 499 498 497 497 497 497 497 497 498 499 after 1: 499 498 498 498 498 497 497 497 498 499 after 2: 499 498 498 498 498 498 498 498 498 499 after 3: 500 499 499 498 498 498 498 498 498 499 after 4: 500 500 500 499 498 498 498 498 498 499 after 5: 500 500 500 500 499 499 498 498 498 499 after 6: 500 500 500 500 500 500 499 498 498 499 after 7: 500 500 500 500 500 500 500 499 499 499 after 8: 500 500 500 500 500 500 500 500 500 500 
•  » » » 5 years ago, # ^ |   0 Right, thanks!
 » 5 years ago, # | ← Rev. 4 →   0 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/2kAsEDHere is the screenshot. Screen-shot : http://postimg.org/image/5rtdr33kt/
 » 5 years ago, # | ← Rev. 2 →   0 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.
•  » » 5 years ago, # ^ |   0 the check function is f(x) :you can do it greedy, for i to n if seq[i] >= x : no do nothing! get how much do need to do until x (seq[i]-x) restart need to m add need seq[i, w+i] 
 » 5 years ago, # |   +1 When will i get the editorials for this contest
 » 5 years ago, # | ← Rev. 2 →   0 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].
•  » » 5 years ago, # ^ |   0 i doubt the 'any continuous subarray of length m containing minimum' will work, but left most or right most willthis is my general idea : input : 6 2 3 1 2 1 2 1updating left most smaller will resulting an array : 2 3 2 2 1then, because 1 is smallest, we choose updating index 4 till 6, becoming : 2 3 3 3 2if we update the middle first (index 3), it will has result : 1 3 2 3 1and after that, anything we choose will still have value 1 in array
 » 5 years ago, # |   0 Topocder SRM 630 in 6 hours, will miss it :(.
•  » » 5 years ago, # ^ |   0 SRM is after 30 hrs :P
•  » » 5 years ago, # ^ |   0 It is after about 30 hourscheck its time again
 » 5 years ago, # |   0 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.
 » 5 years ago, # | ← Rev. 2 →   +11 Problem C: A teacher can have a birthday after 10 ^ 5 days? :D
•  » » 5 years ago, # ^ |   +6 Yes, if teacher lives on Saturn or Neptun
 » 5 years ago, # |   0 My Code For Problem B gives the right answer for 1st case on my IDE But Different one on the judge !! http://codeforces.com/contest/460/submission/7536450What is the reason behind that !!
•  » » 5 years ago, # ^ |   0 You are using the built-in pow function. It has been discussed above why it's not correct.
•  » » » 5 years ago, # ^ |   0 found it thanks :D
 » 5 years ago, # |   +3 Country Wise Standings for this round has been updated.
 » 5 years ago, # | ← Rev. 2 →   0
 » 5 years ago, # |   0 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
•  » » 5 years ago, # ^ |   0 Your expected rank was less than 1733 and you got around 2400 so that's why your rating was decreased.
 » 5 years ago, # |   +17 I wrote short description of possible hacks with some statistics. If you are interested — take a look: here.
 » 5 years ago, # |   0 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?
•  » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ |   0 Thanks.
•  » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ |   0 Thanks.
 » 5 years ago, # |   +15
 » 5 years ago, # |   0 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.com/contest/460/submission/7535442
•  » » 5 years ago, # ^ |   +3 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, (long long)pow(5.0, 23)on MSVC++ returns 11920928955078124 instead of 11920928955078125.
 » 5 years ago, # |   0 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 :/ .
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 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 :)
•  » » » 5 years ago, # ^ |   0 Clear, thanks for taking the time to explain.
•  » » » 5 years ago, # ^ |   0 Nicely Explained :)
 » 5 years ago, # |   +3 Round #263?
 » 5 years ago, # |   0 where are this rounds editorial?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +3