### Barichek's blog

By Barichek, history, 3 years ago, translation, ,

Hello everyone!

Codeforces Round #407 for both divisions will happen on Mar/29/2017 19:05 MSK.

The problems were prepared by me (Ihor Barenblat), Stanislav Stastomash Tomash and Anton arsijo Tsypko. Great thanks to Ivan Fekete Fekete, Adalbert Adalbert Makarovych, Roman pisos_pro Derkach, Vladislav winger Isenbaev and Alex AlexFetisov Fetisov for testing the round, Nikolay KAN Kalinin for his help with the round preparation and Mike MikeMirzayanov Mirzayanov for the Codeforces and Polygon systems.

As usual, contestants will have 2 hours to solve 5 problems. Scoring will be announced closer before the round.

Hope that everyone will find interesting problems. Good luck!

Scoring distribution:

Div2: 500-1000-1500-2250-2500

Div1: 500-1250-1500-2000-2250

UPD. Editorial is published.

Congratulations to winners:

Div.1:

Div.2:

• +414

 » 3 years ago, # | ← Rev. 2 →   +23 Nowadays number of problem setters+tester of each contests are more than the number of problems :D That's cool. Thanks to all the problem setters for giving their important time in problem setting for us B-)
•  » » 3 years ago, # ^ |   +8 Yeah! you're right!
•  » » 3 years ago, # ^ |   +46 My Boy !!! They are not setters ; they are Testers
•  » » » 3 years ago, # ^ |   +29 so, 3 setters and 5 testers? That's also good.
•  » » » » 3 years ago, # ^ |   0 Contestant's are 7000+.... That's awesome
•  » » » » » 3 years ago, # ^ |   +8 4056 + 461
 » 3 years ago, # |   +13 Hope to have interesting problems and good problem description.
 » 3 years ago, # | ← Rev. 50 →   -94 wish high rating for all
•  » » 3 years ago, # ^ |   +20 now you can see my pokerface
•  » » » 3 years ago, # ^ |   +21 I actually see it is a see-saw and your art gives me an impression that rating have to be balanced in a round, therefore "wish high rating for all" is an illusion.
 » 3 years ago, # | ← Rev. 2 →   +1 :|
•  » » 3 years ago, # ^ |   -21 :|
 » 3 years ago, # |   -7 How many problems？
•  » » 3 years ago, # ^ |   +15 "As usual, contestants will have 2 hours to solve 5 problems."
•  » » » 3 years ago, # ^ |   +22 thanks！i havn't read the instruction carefully
•  » » » 3 years ago, # ^ |   +3 It already not usually
 » 3 years ago, # |   +83 who is maria ivanova I_love_Maria_Ivanova ?
•  » » 3 years ago, # ^ |   +164 The most beautiful girl in the world)
•  » » » 3 years ago, # ^ |   +192 Sorry, but Meghana is the most beautiful girl in the world :)
•  » » » 3 years ago, # ^ |   +111
•  » » » » 3 years ago, # ^ |   +144 All of you are wrong.
•  » » » » » 3 years ago, # ^ |   0 I agree.
•  » » » » » » 3 years ago, # ^ |   +1 Thanks!
•  » » » » » » » 3 years ago, # ^ |   0 How about my UNCLES? :'3
•  » » » » » 3 years ago, # ^ |   +16 All of you are wrong, Rem is the best waifu. /s
•  » » » » 3 years ago, # ^ |   +13 but dude! i_love_daniel . And (to round 407) LetsDoThis
•  » » » » 3 years ago, # ^ |   -12
•  » » » 3 years ago, # ^ |   -55 THEN WHO AM I?
•  » » » » 3 years ago, # ^ |   -32 THOSE WHO ARE DOWNVOTING ME JUST REMEMBER THE JOY THIS GIRL GAVE YOU.
•  » » » 3 years ago, # ^ |   -15
 » 3 years ago, # |   -26 I will be in top 1000 this contest!
 » 3 years ago, # |   0 Well I m new in programming contests ... Can you plz tell me that in in which Division should I register.....It will be great if you can give some tips to me .
•  » » 3 years ago, # ^ |   +18 If you are new, you should register in Div.2
 » 3 years ago, # | ← Rev. 2 →   +77 Rating prediction: div1 div2Extensions: Have fun & high rating:)
•  » » 3 years ago, # ^ |   -22 WHY DON'T YOU PARTICIPATE AND CHECK CORRECTNESS OF YOUR TOOL.BTW IT IS AWESOME.
•  » » 3 years ago, # ^ |   0 Hey, Can you Github it? and share the link, please?
•  » » » 3 years ago, # ^ |   +1 It's already on github. Also you could read blog on cf about it.
•  » » » » 3 years ago, # ^ |   0 Hey, What's the matter with accuracy? Why not accurate when you know the results?
•  » » » » » 3 years ago, # ^ |   +5 The results of this predictor are very much accurate.
•  » » » » » » 3 years ago, # ^ |   -13 Gotta try it from now, lets see how today's contest rolls up. all the best everyone.
 » 3 years ago, # |   -39 Is a2oj down?
•  » » 3 years ago, # ^ |   -34 YES A2OJ IS DOWN AS LIKE AS YOUR STANDARDS
 » 3 years ago, # |   +44 I believe I can fly.
•  » » 3 years ago, # ^ |   -59 I BELIEVE, I CAN KICK YOUR ASS.
•  » » » 3 years ago, # ^ |   +17 you can‘t kick my son’s ASS！
•  » » » » 3 years ago, # ^ |   +16 you are not my father
•  » » » 3 years ago, # ^ |   +8 You can't kick my grandson's ASS!!
•  » » » » 3 years ago, # ^ |   -40 THANKS,MY MOM,MY GRANDMA,MY DAUGHTER
•  » » » 3 years ago, # ^ |   +10 Did I offend you? Why do you want to kick my ass? Who are you?
•  » » » » 3 years ago, # ^ |   +9 I'm you missing Biological father！！！ CALL ME FATHER
•  » » » » 3 years ago, # ^ |   -45 DID I OFFEND YOU? HOW CAN YOU FLY?
•  » » » » » 3 years ago, # ^ |   +27 be quiet please, if you cant write sth clever
•  » » » » » » 3 years ago, # ^ |   +3 haha, best reply ever :D
 » 3 years ago, # |   +58 Good luck in the competition! Here's a little song to hype y'all up! Beautiful programPlease run for me.I've tried you in BASIC,FORTRAN and C.Beautiful program,You've errors galore.And each time I run you,You're swapped out of core.
•  » » 3 years ago, # ^ |   0 I'll make it as a comment in my submissions during the contest
•  » » 3 years ago, # ^ |   +53 You are good in programming (as I see your color) but sorry to say, not in literature.
 » 3 years ago, # |   +12 Problems in CSAcademy are getting better than DIV2 CF Rounds. Long Problems, uneven difficulty levels.
 » 3 years ago, # |   +9 Is it at all possible that problem E is just named "New task" because it is a placeholder name :P?
 » 3 years ago, # |   0 Problem with the hack page :/
 » 3 years ago, # |   +3 Today we are going to witness the fastest system tests ever .
 » 3 years ago, # |   +8 Hi div2 :V
 » 3 years ago, # |   +3 RIP RATINGS...
 » 3 years ago, # | ← Rev. 2 →   0 What is pretest 14 in div2 B ? Your text to link here... What is wrong in my solution?
•  » » 3 years ago, # ^ |   0 Try this:5 0 4 11
•  » » » 3 years ago, # ^ |   0 I think it isnot this case because my pro can cover this
•  » » » 3 years ago, # ^ |   0 solution is inf?
•  » » » 3 years ago, # ^ |   0 inf?
•  » » » 3 years ago, # ^ |   0 ans is "inf" ?
•  » » » » 3 years ago, # ^ |   +7 Ans is "0". Because Masha will stop writing immediately if |bi| > L.That's exactly why I got WA on the first submission.
•  » » » » » 3 years ago, # ^ |   0 Now I got it.. Thanks
•  » » » 3 years ago, # ^ |   0 my sol is giving correct answer my solution
•  » » » 3 years ago, # ^ |   0 Ans is infinity.Because 5 0 0 0 0 0 ... Now 0 is no=t in list...So ans is inf
•  » » » 3 years ago, # ^ |   0 it think ans is 0 i thought it was inf before i changed it and passed that test and the statement was confusing.she will firstly write 5 that's bigger than l so she stop and write no number so answer is 0
•  » » 3 years ago, # ^ |   0 I want to know too
•  » » 3 years ago, # ^ |   0 i passed it by puttingif(abs(b1) >l) cout << 0 <
•  » » » 3 years ago, # ^ |   0 thank you , it must be this case
•  » » » 3 years ago, # ^ |   +3 How come? if b1=0 and q=0 then the answer should be infinite!!
•  » » » » 3 years ago, # ^ |   0 the condition has nothing to do with q it just compares b1 and L and if b1 =0 the condition will be false because L is always bigger than 0
•  » » 3 years ago, # ^ |   0 if q==-1 && Math.abs(b1)>l then ans = 0; i think this is the case .
•  » » 3 years ago, # ^ |   0 I don't know actually, but this case troubled me a lot today :-/ somehow, passed it in 11th submission.
 » 3 years ago, # |   +5 How to solve Div2B. Got stuck for 1 hr.
•  » » 3 years ago, # ^ |   0 check for exception cases — q = -1,0,1 and b1 = 0. for others apply naive method.I got hacked once because of not putting b1=0 case seperately.
•  » » » 3 years ago, # ^ |   0 @mizuki instead of checking exception cases, we can count iterations here is my code (maybe it will fail in system test): intt ans = 0, it = 0; while (abs (b1) <= l) { intt t = 0; if (binary_search (arr + 1, arr + m + 1, b1)) t = 1; b1 *= q; if (t == 0) ans++; it ++; if (it == 100000) break; } if (ans > 31) { cout << "inf" << endl; return 0; } cout << ans << endl; 
•  » » » 3 years ago, # ^ |   0 I did that ..can you check my submission?
•  » » » 3 years ago, # ^ |   0 i used that but i had wrong answer on pretest 9 .. could some one tell me why ? i thought i did it correctly i did all the cases ?
•  » » » » 3 years ago, # ^ |   0 I tried for q=0,1,-1 and b1 = 0. As well as same way as of iterations count but got pretest 9 WA :(
•  » » » » 3 years ago, # ^ | ← Rev. 6 →   0 Try this cases:5 -1 100 21 5Answer : inf5 -1 100 25 -5Answer : 05 -1 100 21 -5Answer : inf
•  » » 3 years ago, # ^ |   0 Just use binary search instead for checking if bi is 'bad'.
•  » » » 3 years ago, # ^ |   0 or a map :)
 » 3 years ago, # |   0 What could be Problem B test 14 ?
•  » » 3 years ago, # ^ |   0 I think it was abs(b1) > L.
•  » » » 3 years ago, # ^ |   0 I considered that case too along with q==-1 but still got WA
•  » » 3 years ago, # ^ |   0 cannot tell sure, if you got TLE, then it can be infinity test case, for this output may be : inf.if you got WA, then cannot tell sure what will be the test case#14. Wait until the test case reveal. Luckily i did not stuck in test case 14.To solve this, i have considered these: test#1 -1 -1 1000000000 1 1 test#2 0 0 1 1 1 test#3 1 1 1000000000 1 0 test#4 125 1 100000000 1 1 For these kinds of test case, output will be infinity. otherwise,while(abs(b1)<=l) { if(b1 is not belong to bad integers array) count++; if(abs(b1)==abs(next_b1) && b1 is not belong to bad integers array) output inf, and return 0; if(abs(b1)==abs(next_b1)) break; update b1=b1*q; } cout << count << endl;
 » 3 years ago, # |   +17 How to solve C?
•  » » 3 years ago, # ^ |   0 The answer doesn't exceed 1000. But I don't know how to prove it.
•  » » » 3 years ago, # ^ |   +5 If there exists a[i] == n, answer is 1.Else if we don't have both a[i] < n and a[i] > n, answer is -1.Else we have some a[i] == n — x and a[j] == n + y. Then we can take y bottles of type i and x bottles of type j. x + y <= 1000.
 » 3 years ago, # |   +25 This >.<
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 me too :/
•  » » » 3 years ago, # ^ | ← Rev. 4 →   +3 Mine is wrong too :(Masha writes all progression terms one by one onto the board (including repetitive) while condition |bi| ≤ l is satisfied (|x| means absolute value of x). So if bi>L u don't have to check for 0 too when common ratio is 0.
•  » » 3 years ago, # ^ |   -29 fail 4 times, which case did I missed?
•  » » » 3 years ago, # ^ |   0 Stop as soon as bi > l. I too made the same mistake.
 » 3 years ago, # |   0 Hacks, Hacks everywhere 8-) <3
 » 3 years ago, # | ← Rev. 5 →   +30 Is Div1 D solvable by Java? I think the solution needs almost 300000 queries. An Educational Codeforces Round held some month ago has such problem (many queries needed) and no one can solve by Java since flush() is time-consuming.
•  » » 3 years ago, # ^ |   -42 Codeforces and ACM want people to code in C++, thats why I changed from java to C++ :(
•  » » » 3 years ago, # ^ |   +14 If so, statement must not advice for Java or other languages' flush.
•  » » » » 3 years ago, # ^ |   0 Well I should be doing 1.8*10^5 if that matters. Isn't there another way to make flush?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +30 we can solve it in at most 100000 steps.fix... my estimation is wrong before...
 » 3 years ago, # |   0 Can somebody tell, if for div1B suggestion, that 2 used only once edges are neighbour edges, is right?
•  » » 3 years ago, # ^ | ← Rev. 3 →   +3 Any two self loops can also be single edges.Also any normal edge(non self loop) with any self loop can also form a pair.
•  » » » 3 years ago, # ^ |   +3 is that only 2 cases? self-loops and neighbour edges?
•  » » » » 3 years ago, # ^ |   +27 1- pair of self-loops2- self-loop and edge3- pair of edges that share an endpoint
•  » » » » » 3 years ago, # ^ |   +5 Can you please tell me a case where this would go wrong: sz[i] tells the number of nodes adjacent to node i (not including i even if there is a self loop) n is the number of edges which are not self loops..  for(int i = 0; i < nodes; i++) { for(int j = 0; j < adj[i].size(); j++) { ans += sz[adj[i][j]]; } } ans /= 2; ans = ans - n; cout << ans; 
•  » » » » » » 3 years ago, # ^ |   0 As I said, pairs of self-loop's should be counted
•  » » » » » » » 3 years ago, # ^ |   0 Sorry I don't understand this very statement pairs of self-loop's... for example: 2 3 1 1 2 2 1 2 My program gives 2, which I think is the right answer too. Sorry if all this sounds really stupid..
•  » » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   +3 Answer is 3. You can select any 2 of the 3 edges.Using the two self-loops once the path is 1->1->2->2->1
•  » » » » » » » » » 3 years ago, # ^ |   0 Thanks.. got it :)
•  » » » » » » » » » 3 years ago, # ^ |   0 So something like this? ll ans = 0; for(int i = 0; i < nodes; i++) for(int j = 0; j < adj[i].size(); j++) ans += sz[adj[i][j]]; ans = ans - n; ans += (l * (l - 1)); ans /= 2; 
•  » » » » » » » » 3 years ago, # ^ |   0 in this test the answer is 3, because you should also count this pair: (first edge,second edge)
•  » » » » » 3 years ago, # ^ |   0 I forgot second case anyway, so I got WA. But can you prove that only needed are these three cases ?
•  » » » » » » 3 years ago, # ^ |   0 Eulerian path/cycle exist if the graph is connected (edge-wise) and degree of all nodes are even except for 0 or 2 nodes are odd.so if all edges are doubled all degrees will be even, if a pair of edges don't share an endpoint then they will make 4 odd nodes
•  » » » » » » » 3 years ago, # ^ |   0 Fantastic proof, thanks !I was so close to solve this :)
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 I did the same. Wrong Answer on pretest 18. Edit: I messed up in checking whether all edges are connected or not.
•  » » 3 years ago, # ^ |   0 I did the same solution but I am getting WA on pretest 5 :/
•  » » 3 years ago, # ^ |   0 Not necessarily, for example two random self-loops work.
•  » » 3 years ago, # ^ |   0 Nope, check the graph 1->2, 2->3, 3->3, and you can use edges 1-2 and 3-3 only once by going 1-2-3-3-2-1.
 » 3 years ago, # |   0 Awesome problem set! problems was tricky though xD
 » 3 years ago, # | ← Rev. 2 →   +3 Pretty nice contest. My most favorite problem is Div2-D. Though, I don't like Div2-B.Btw, how to solve Div2-E? Is it some kind of DP?UDP: I don't know if the words "geometric" and "depression" in Div2-B title are intended puns or not.
•  » » 3 years ago, # ^ |   0 Solve the multivariate linear indeterminate equation? I guess...
•  » » 3 years ago, # ^ |   +3 The crux here is to notice that all we need is the sum of (signed) distances of the cokes that we include to our desired amount is zero. Then do we something like Knapsack's DP, except we notice that an optimal solution could be arranged so that we never stray beyond [0, 1000], supposing that we start at the desired amount and then add/subtract the distances from there. To make it run faster, we implement it using BFS (store the reachable ones in an array that indicated how many steps needed)
 » 3 years ago, # |   +20 "14" it became my worst number because of problem B
•  » » 3 years ago, # ^ |   +3 aoso to me
•  » » » 3 years ago, # ^ |   0 Please check this test: 2 0 1 1 0
•  » » 3 years ago, # ^ |   0 me too !!! damn that 14 case
 » 3 years ago, # |   0 Announcement: Problem B. Weird journeyNote that it is not necessary for good path to go through all cities, we care only about roads. are announcements supposed to give hints or only to clarify the statement?
•  » » 3 years ago, # ^ |   0 Guess they didn't want people hacking
•  » » » 3 years ago, # ^ |   +26 It is in pretest 18 I think.
•  » » 3 years ago, # ^ |   +72 Actually, the statement is still incorrect: Little boy Igor wants to become a traveller. At first, he decided to visit all the cities of his motherland — Uzhlyandia.
•  » » » 3 years ago, # ^ |   +5 Ok then announcement was needed, but I still think it gave hint to some people :D
 » 3 years ago, # |   0 Div2 B take a lot of time debugging.
 » 3 years ago, # |   0 And what about div2 B pretest 10?
 » 3 years ago, # |   +6 How to solve Div2 A ?
 » 3 years ago, # | ← Rev. 2 →   +39 In Div1 C, I really tried hard to hack O(N^3) solutions. But the CF evaluation server was too fast.. They all worked within 900 ms.
•  » » 3 years ago, # ^ |   0 What was the expected solution?
•  » » » 3 years ago, # ^ |   +18 My solution is O(N^2) with BFS.
•  » » » » 3 years ago, # ^ |   0 Wow how did you solve ?
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +52 We are to pick some of (a[i]-n) such that the sum of them is zero. We don't need to go to a state greater than 1000 or less than -1000, because for all i, |a[i]-n| <= 1000 and we should make zero. Therefore, BFS with 2001 nodes ([-1000, 1000]) will be enough.
•  » » » » » » 3 years ago, # ^ |   0 Which test case did you use to hack? As I feel intuitively that if you have a many types of a[i] the answer can be found quite fast and if you have a small number of different a[i] each iteration will have a small number of operations.
•  » » » » » » » 3 years ago, # ^ |   0 Almost all solutions that I tried to hack first check if there is n. If not, they divide numbers into two groups, and calculate available sums for each group with time complexity O(N^3). No matter what numbers come, they iterate full O(N^3) loop. So I handcopied them to custom invocation and just tried K = 1000000.
 » 3 years ago, # |   0 what the data of DIV 2 B test 8?
 » 3 years ago, # |   +9 please read this : http://codeforces.com/blog/entry/51309
•  » » 3 years ago, # ^ |   +3 is it means the test data is wrong?
 » 3 years ago, # |   +18 Problem B — Masha and geometric depression It looks like not only geometric who has depression My Status Right now
 » 3 years ago, # | ← Rev. 7 →   -14 [DELETED]*Thanks for the round
•  » » 3 years ago, # ^ |   +5 You can't solve it,so you decide that it isn't your fault?
•  » » » 3 years ago, # ^ | ← Rev. 7 →   -11 Thanks for the awesome round. I am ok with this round. Sorry for earlier comments.
•  » » » » 3 years ago, # ^ |   0 Wrong ideas? I don't understand. If you don't know how to solve it, you can look at programme that have passed
 » 3 years ago, # | ← Rev. 3 →   0 int main() { cout<<100000<<" "<<1<
•  » » 3 years ago, # ^ |   0 last element should not be followed be a space.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I made a hacking attempt with similar script expecting TLE. But the solution passed in 436ms. I guess that was because the operations were small (x++)
 » 3 years ago, # |   +1 I want to see, how many DIV2C solutions will fail due to integer overflow. I managed to hack 4 people in my room alone, who used int ans=0;. My hack test 6 1000000000 0 0 1000000000 1000000000 0 Correct answer: 3000000000
 » 3 years ago, # |   +144 Can I already post "start systests" meme?
 » 3 years ago, # |   0 How to solve C ? I used two accumulative arrays where in the first array l=1 and in the second array l=2 (r=n in both arrays), then i looked for max range sum of both arrays. this is supposed to be O(n) but still gives TLE on pretest 10. help?
 » 3 years ago, # | ← Rev. 4 →   0 For Div 2 B,Whats the correct answer for :5 0 4 15 Main confusion:Does abs(b)<=l check happen even if b is a bad number?
•  » » 3 years ago, # ^ | ← Rev. 11 →   +3 0
•  » » 3 years ago, # ^ |   +3 Mine gives 0
•  » » 3 years ago, # ^ |   0 it should be "inf"
•  » » 3 years ago, # ^ |   +1 It will be 0.. But if generating doesn't stop, It will be "inf".
•  » » » 3 years ago, # ^ |   0 you can write down “0” endless，,so it should be "inf"
•  » » » » 3 years ago, # ^ |   0 You should immediately stop writing when |bi| > l
•  » » 3 years ago, # ^ |   0 It should be 0.
•  » » 3 years ago, # ^ |   +3 0 because 5 > 4, so we never enter the while loop.
•  » » 3 years ago, # ^ |   0 0, because of condition b(i) <= l
•  » » 3 years ago, # ^ |   0 It should be 0 since initially abs(b1)>l is not satisfied.
 » 3 years ago, # |   +30 Note that it is not necessary for good path to go through all cities, we care only about roads. So just a side note, not like the statement says the opposite? Really, why didn't you fix that? "At first, he decided to visit all the cities of his motherland — Uzhlyandia." or any other sentence does not even suggest that he may not want to visit all cities, does it?Also, don't you guys think that "Boy thinks a path is good if the path goes over m - 2 roads twice, and over the other 2 exactly once." isn't well-defined for M=1? I made them tell me that the answer is 0 for M=1 on my third try.
•  » » 3 years ago, # ^ |   +18 Well u kinda cant walk -1 edge, so.. Kappa. Agreed, statements are awful
•  » » » 3 years ago, # ^ |   0 Yup, also "the other 2" suggests there are at least two edges. Not only did it take me three tries to convince them to explain the situation with M=1, but they didn't even make an announcement after that...
•  » » 3 years ago, # ^ |   0 The English in that statement was also very sloppy at times.
 » 3 years ago, # |   +12 I am in doubt, was their any DIV2 round today?
•  » » 3 years ago, # ^ |   0 Yes, this contest was for both DIV1 and DIV2
 » 3 years ago, # |   0 can some one help me find out what is the difference between these two codes:  int n,k;cin>>n>>k; ll ans=0; for(int i=0;i>x; ans+=ceil(double(x)/k); } cout<>n>>k; for (int i=0;i>v; ans+=(v/k); if (v%k!=0) { ans++; } } ans+=(ans%2); cout<
•  » » 3 years ago, # ^ |   0 What I've noticed, is that the second code adds the remainder to the answer before dividing it. (wrong)The first one is adding the remainder after dividing, which is the right way.
•  » » 3 years ago, # ^ |   0 ceil will return for example 51 in case that the computer calculates 100.0 / 2.0 as 50.00000000000000000001... floating point arithmetics are calculated with some machine specified fixed precision...
•  » » » 3 years ago, # ^ |   0 thanks for the reply so you mean that the second one is correct?
•  » » » » 3 years ago, # ^ |   0 Yes.
•  » » » 3 years ago, # ^ |   0 Division by 2 does not have such flaw since 2 has exact representation. It will break only if the numerator is already not exact, which for integers means it must be more than 253.
•  » » » » 3 years ago, # ^ |   +3 but in case of division by k this has a problem.(based on what others are saying)
•  » » » » 3 years ago, # ^ |   0 I remember I tested it on two integers less than 100 and it failed. I don't exactly remember the numbers.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 That is possible only if one of the numbers was already calculated with an error (for example, if you used the pow function).Here is an old but good TopCoder tutorial by misof to learn about integers and reals representation.
 » 3 years ago, # |   +1 TFW you finish debugging 30 seconds after the round endsfeels bad man
 » 3 years ago, # | ← Rev. 4 →   +3 Can someone tell differences between these codes for Div 2 A?First one passed pretests and second didn't.Code 1 cin>>n>>k; FOR(i,1,n) cin>>arr[i]; long long int sum=0; for(int =1;i<=n;++i) sum+=ceil(arr[i]*1.0/(double)k); cout<<(long long int)ceil(sum*1.0/2.0)<>n>>k; FOR(i,1,n) cin>>arr[i]; long long int sum=0; for(int =1;i<=n;++i) sum+=ceil(arr[i]*1.0/k); cout<
•  » » 3 years ago, # ^ |   +4 same here.
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 I think there might be some precision issue involving doubles.I kept on getting WA on pretest 6.
 » 3 years ago, # | ← Rev. 2 →   0 I think there are some issue in Problem Div2 B. For this reason system test is delayed.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Started..Here we go :D
 » 3 years ago, # |   +2 Systest is still pending, because even the setters get WA 14 on Div2B :)
 » 3 years ago, # |   +1 Div2.B... 13 is not unlucky number. now, 14 is unlucky number.
 » 3 years ago, # |   +1 Div2 Problem B Case #14: 123 0 21 4 543453 -123 6 1424Accepted. But A failed :-/
 » 3 years ago, # |   0 System test are over but div2 B test doesn't seem correct. 14 test case's ans should be inf but it shows 0
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Here b1>l. Hence, answer should be 0.
•  » » » 3 years ago, # ^ |   0 but b2 < l
•  » » 3 years ago, # ^ |   0 No. 0 is correct. Because b
 » 3 years ago, # |   0 Div2 B : 1221 pretests passed -> 771 AC .. May God be with us !!
 » 3 years ago, # |   +5 Div2 B, WA on main test 43 opps :( :(
 » 3 years ago, # |   +10 even though i am not the only one who dissapointed with problem B, but i do appreciate your effort for giving your time to us for making this contest, i'll wait for your next contest of course with a better problem to be solved, graciass
 » 3 years ago, # | ← Rev. 3 →   0 problem Bwhy output of this case is 0 123 0 21 4 543453 -123 6 1424it must be "inf" because b1 = 123 will not be printed because it's invalid b2 = 0 will be printed because it's valid b3 = 0 will be printed because it's valid . . . infinity
•  » » 3 years ago, # ^ |   0 l is smaller than 123? The process stops at b1. Beware of the difference between "skip" and "stop"
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Thank you I got it. It's like the process will not run if the condition |bi| <= l is not satisfied.
•  » » 3 years ago, # ^ |   0 123 > 21 ... 0
 » 3 years ago, # |   0 Auto comment: topic has been updated by I_love_Maria_Ivanova (previous revision, new revision, compare).
 » 3 years ago, # | ← Rev. 2 →   +3 editorial link is broken edit: fixed
•  » » 3 years ago, # ^ |   +1 http://codeforces.com/blog/entry/51312Here's the fixed link
 » 3 years ago, # |   +5 I don't why but there is some issue with the challenging system near the end of the contenst. It seems that my hack page keeps refreshing and it failed to load the hack interface so I cannot hack other's solution...Surprisingly after I change from chrome to firefox it suddenly works...Don't know why there is a difference between firefox and chrome...
 » 3 years ago, # |   0 Happiness is getting into Deep Blue.
•  » » 3 years ago, # ^ |   0 Congratulations!
 » 3 years ago, # |   0 System test data for Div-2 problem A are weak. They should test some hack cases too.
 » 3 years ago, # |   +3 Here is interesting submission of Div2 E/Div1 C. It seems to be O(5004) with some heuristics. I try to find solution using one, two or three types if there is such. If no, then comes what should be O(5004) DP. But it passes systests.
 » 3 years ago, # | ← Rev. 3 →   0 Can anyone take a look at THIS submission please? This code gives correct output of the test case 15 on my compiler but wrong ans on codeforces' compiler. Help would be much appreciated. Input case : 3 2 115 16 24 48 12 96 3 720031148 -367712651 -838596957 558177735 -963046495 -313322487 -465018432 -618984128 -607173835 144854086 178041956 .Output should be '1' but on cf it gives me '3'.
•  » » 3 years ago, # ^ |   0 Anyone please?? Atleast you can run the code on your compiler with that input and let me know if you get the wrong ans or correct ans. :/
•  » » » 3 years ago, # ^ |   0 Man !! you don't make your code easy to read.. do you...
•  » » » » 3 years ago, # ^ |   0 Sorry :(
 » 3 years ago, # | ← Rev. 2 →   0 For part A : I initially submitted 25910962 with variables declared globally and I got wrong answer in test 5. But after that I declared the variables inside the int main() and the solution 25923127 was accepted. Can someone explain it to me how this makes a difference?
•  » » 3 years ago, # ^ |   0 Compare ll w[10000]; to ll w[n];. First one fails, because n<=10^5 , but you declare the size as 10^4
•  » » » 3 years ago, # ^ |   0 Oh yes. My mistake. Thank you. :)
 » 3 years ago, # |   0 I can't find any bug in my code,but its giving error on test case 56,How is this possible? (The output on my computer is 1 for this case,but on codeforces it is showing 2,why?) http://codeforces.com/contest/789/submission/25932391Thanks in advance
 » 3 years ago, # | ← Rev. 2 →   0 For B div 2, shouldn't the following test case output in "0" instead of "inf"? -1000 0 100 1 -1000 because b1 = B, and |b1| > L, she shouldn't write anything on the blackboard.But I might've missed something. The hack attempt is here: http://codeforces.com/contest/789/hacks/312464Thanks in advance.
•  » » 3 years ago, # ^ |   0 Ah, it is my blunder. I misread "expected output" as my own output.Kindly ignore above question.
 » 3 years ago, # |   0 In Div2 Prob B test case 14 — 123 0 21 4 543453 -123 6 1424 The output should be inf because First 123 would not be written on the board as it is greater then 21 but 0 should be written as its not present in the m numbers ,So it should have been written every time. But why is the answer 0..? Answer should have been inf
•  » » 3 years ago, # ^ |   0 Masha writes all progression terms one by one onto the board (including repetitive) WHILE condition |bi| ≤ l is satisfied. So if |bi| > l she will stop.
•  » » » 3 years ago, # ^ |   +5 Thankyou :) Got it.
•  » » 3 years ago, # ^ |   +1 No. The question clearly states that the number won't be written if it's absolute value is greater than 'L' and the loop would break. In this case, 123>21. So even that would never be written.
•  » » 3 years ago, # ^ |   0 The problem description state that she will write as long as the condition of |bi| <= L holds.On the test case 14, b1 = 123 is already greater than 21, hence the girl will stop there.There is a difference between skipping a number (because the number exists in bad number set) and stop writing (because the current number already exceed the given bound).
 » 3 years ago, # |   +10 Thanks for the great contest!Very clear description and interesting solutions. Unfortunately, I spent half of the time of the contest trying to figure out why my solution for problem C did not work? In the end, a friend told me that the function f(l, r) = sum_{i=l}^{r — 1} |a[i] — a[i+1]| * (-1)^i-l while I thought it is f(l, r) = sum_{i=l}^{r — 1} |a[i] — a[i+1]| * (-1)^i-1. Anybody else had the same problem?
 » 3 years ago, # |   +17 I used the following generator code to hack a solution 25904282 for Problem Div2A: printf("100000 1\n"); for(i=0;i<100000-1;i++) { printf("%d ",10000); } printf("%d",10000); printf("\n"); `Unfortunately, the attempt became unsuccessful as the solution produced the output in 998 ms.Later during the system test, the same solution gave a TLE on the exact same test case — Test Case #27 :(
•  » » 3 years ago, # ^ |   0 Such is life...
•  » » 3 years ago, # ^ |   0 It's bad idea to hack solutions where only basic addition and subtraction operations are performed in loops.See this solution. It is performing 10^14 operations still system test passed.
•  » » » 3 years ago, # ^ |   0 It is performing 10^14 operations still system test passed. Lol no, this is compiler optimization :D
 » 3 years ago, # | ← Rev. 2 →   +30 I have an interesting solution for div1 D and maybe it need only O(n) queries.First we choose a number number G less than , probably (M is the coordinate range and n is the number of lines). And we can random several times to find a point a = (x, y) such that . Then, for vertical lines, we query all the point (x + kG, y) which is in the coordinate range. And we can find several lines. But if there are many lines which are very close, we may only find out some of them.So, the next step, we need to find out the remaining lines. If the dis between two adjacent lines is larger than 2G, then there are no lines between them. Otherwise, we can search between these two lines. Each time we query the midpoint of the search range, if we get a new line, then we try to search both sides and otherwise, exit.We can find out the horizontal lines analogously.This is my code 25939395. During the contest, I made some stupid mistakes and failed to pass it. Sad story.
•  » » 3 years ago, # ^ |   +10 My solution (25925383) also only uses O(n) queries and is very simple.