Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

By sidprasad, 3 years ago, ,

Hi Codeforces!

Programming Club, IIT Indore and Fluxus 2017 are proud to present, for the first time on Codeforces, our flagship event, Divide By Zero!

The contest is going to be held on Monday, 20th Feb at 9:35PM IST.

Prizes: Codeforces T-shirts for top 15 overall and top 15 in India.

Thanks to the following people for making this round possible:

There are 7 problems, and 2.5 hours to solve them. The points distribution will be updated later.

Fluxus is the annual techno-cultural festival of Indian Institute of Technology, Indore. It is a 3-day event and generally held in the month of February. Started in 2011, Fluxus is the largest college festival of central India.

Hope you guys enjoy the contest! See you on the leaderboard!

UPD: The scoring is 500-1000-1250-1750-2000-2250-2750.

UPD2: Thanks a lot everyone for your participation!

We hope you all enjoyed the contest. Yes, there were a few things we could've done better, and unfortunately the system was down for a while, We sincerely thank the CF team for dealing with it in the nick of time.

This was our first (of many, hopefully) contest on Codeforces. We request you to fill in this form with your feedback so that we can do better next time. Thank you!

The following users win T-shirts! Congrats!

Overall Top 15:

Indian Top 15:

UPD3: Editorial

• +324

 » 3 years ago, # | ← Rev. 2 →   +3 Good luck !
 » 3 years ago, # |   +1 Great.Looking forward to it.
 » 3 years ago, # |   0 Cool! Must participate in. Thanks for contest
 » 3 years ago, # | ← Rev. 6 →   -24 runtime error, beacuse of being devided by zero. :D
 » 3 years ago, # |   +6 Hehe Now would be a fight because of the T-shirts)Всё кароч, ща будет мясо из-за маечек)
•  » » 3 years ago, # ^ |   0 why servers so unfair to us...
 » 3 years ago, # |   -18 13 people worked to make this round !!so it has many cartoons and long statements :D
•  » » 3 years ago, # ^ |   +50 You will be surprised.
•  » » 3 years ago, # ^ |   +96 Everyone wrote one line in each problem statement :D
 » 3 years ago, # |   +11 Someone posted a photo on the last round's blog..About Pigeon Hole theory.. 13 writers made me remind of that :'|
 » 3 years ago, # |   +3 It had better the T-shirts was for random people from 1..500(for example).Then there will be a chance to win it!!!
•  » » 3 years ago, # ^ |   -31 You never know, you might win it.
 » 3 years ago, # | ← Rev. 2 →   -36 ...
•  » » 3 years ago, # ^ | ← Rev. 2 →   -38 :)
•  » » 3 years ago, # ^ |   0 wallpapers fetish !!
 » 3 years ago, # |   +9 It's not customary to ask if it's a rated, so I have to come up with different question... "Prizes: Codeforces T-shirts for top 15 overall and top 15 in India." Is it racist?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +26 Not at all, To Increase the chance to get candidates for onsite events at Host Location. I think it is just for promotion for Local Geographic.
•  » » 3 years ago, # ^ |   -11 Not at all.If you are competing with the best in the world you surely need motivation to do so :)
•  » » 3 years ago, # ^ |   -50 I don't know if it's racist, but it's definitely stupid.
•  » » » 3 years ago, # ^ |   -51 why when an Iranian writes a comments you guys gang up on him and give him/her some negative feedbacks and he is right its idiotic why cant you accept the fact that he is right and he didnt say anything to offend any one i know you give me dislikes but can u answer me why?
•  » » » » 3 years ago, # ^ |   -7 It is none of your business ! :O
•  » » » » 3 years ago, # ^ |   +7 "why when an Iranian writes a comments you guys gang up on him and give him/her some negative feedbacks" believe me, when I press down/up vote, I don't get into his/her account and see what is his nationality I just press the F button the point is that neither you or him didn't explain why do you think it's stupid and we don't think it's stupid, so we press downvote simple right ? we aren't racist if we gave downvote to someone
•  » » » » » 3 years ago, # ^ |   0 "I just press the F button"Learnt something new today :D
•  » » » » » 3 years ago, # ^ |   0 the thing you are saying is correct but i saw a bout a dozen comments that some of the was even my self that i wished good luck for the participants of some contest but ive got about 20 downvotes and i saw some guy offering a good product here which is absolutely irrelevant and he got more than 30 up vote soooo what is that u say and thank u for being reasonable not like the other guys
•  » » » » » 3 years ago, # ^ |   0 science has no borders,iranian or anything else,doesn't matter,don't argue about it.(sorry for a little bad english,hope u understand what i mean)
•  » » 3 years ago, # ^ |   0 Lmao XD
 » 3 years ago, # |   +18 Well done! because you say thanks to MikeMirzayanov
 » 3 years ago, # |   0 So now codeforces is not just Russia, Spreading legs.good work mike and team
•  » » 3 years ago, # ^ |   +28 'Spreading wings' is the English phrase for expanding to and exploring new realms.'Spreading legs' means sexual enticement and promiscuity.
 » 3 years ago, # | ← Rev. 2 →   +58 I don't know why, but I feel some math problems
 » 3 years ago, # |   +36 Finally a contest with its time given in IST :DNo need to convert to IST from UTC :P
•  » » 3 years ago, # ^ |   +6 ...you can see the contest in your local time if you go to the contests tab.
 » 3 years ago, # |   0 I hasn't had a T-Shirt before :'(
 » 3 years ago, # |   0 Can I register now? I forgot yesterday and now I am seeing it's Registration is completed!
•  » » 3 years ago, # ^ |   +6 Of course you can. You should click that "Register now »" and join it.
 » 3 years ago, # | ← Rev. 3 →   -103 India is becoming popular day by day in terms of organizing programming contest in Codeforces.
•  » » 3 years ago, # ^ |   -193 YES !!! INDIA ROCKS !!! ALL OTHER COUNTRIES SUCK !!! :) :) :)इंडिया !!!!!!!!!!!!!!!!!!
•  » » » 3 years ago, # ^ |   -158 WHY ALL THIS DOWNVOTES !!! :( READ THIS BUTTHURT OTHER COUNTRIES !Its the contribution of Indians to every field known to men that makes India one of the greatest country of the world . In the words of other great personalities : Will Durant, American historian: "India was the motherland of our race, and Sanskrit the mother of Europe's languages: she was the mother of our philosophy; mother, through the Arabs, of much of our mathematics; mother, through the Buddha, of the ideals embodied in Christianity; mother, through the village community, of self-government and democracy. Mother India is in many ways the mother of us all". Mark Twain, American author: "India is, the cradle of the human race, the birthplace of human speech, the mother of history, the grandmother of legend, and the great grand mother of tradition. Our most valuable and most instructive materials in the history of man are treasured up in India only. " Albert Einstein, American scientist: "We owe a lot to the Indians, who taught us how to count, without which no worthwhile scientific discovery could have been made. " Max Mueller, German scholar: If I were asked under what sky the human mind has most fully developed some of its choicest gifts, has most deeply pondered on the greatest problems of life, and has found solutions, I should point to India. Romain Rolland, French scholar : "If there is one place on the face of earth where all the dreams of living men have found a home from the very earliest days when man began the dream of existence, it is India. " R.W. emerson, American Author: In the great books of India, an empire spoke to us, nothing small or unworthy, but large, serene, consistent, the voice of an old intelligence, which in another age and climate had pondered and thus disposed of the questions that exercise us. Hu Shih, former Ambassador of China to USA: "India conquered and dominated China culturally for 20 centuries without ever having to send a single soldier across her border. " Keith Bellows, National Geographic Society : "There are some parts of the world that, once visited, get into your heart and won't go. For me, India is such a place. When I first visited, I was stunned by the richness of the land, by its lush beauty and exotic architecture, by its ability to overload the senses with the pure, concentrated intensity of its colors, smells, tastes, and sounds... I had been seeing the world in black & whiteSome great facts about India: 1)Each and every 28 states and 7 union territories of India, have their own LANGUAGE, CLOTHING, CUISINE and LOOK.2)India alone has the highest number of languages in the world with more than 300 I guess.3)In India alone you'll find all types of food ranging from sweetest to most spicy food on Earth. I'm not talking about foreign cuisine or restaurants. Its the local food of different states.4)On this planet, you will notice that the highest number of religions present, are in India. More than 8-Christianity, Islam, Judaism, Hinduism, Jainism, Sikhism, Zoroastrianism, Buddhism.After reading all these facts , you might be convinced that India is a great country . If you are , you have clearly misunderstood what makes a country great . Its not the history that makes a country great . India is a barren naked land without its cultures, its colors, its religions. However, as a person cannot be deemed great for the clothes he wears; his shoes or hairstyle or the fragrance he chooses to spray over himself, I doubt if greatness should lie in the clothes of cultures, color or monuments India wears. Not only is such a statement highly propagandist, it deems other nations with perhaps equally diverse cultures, peoples and religions un-great. For greatness is a crown for the elite few.And for all its culture, its history, its religion, its minarets, its color, India like any other country is made of people. Human beings. Little pink creatures, with dark hearts. This is again not a license to greatness, because every country I know of, is made up of human beings.The man on the street, the rickshaw puller, the tobacco- paan seller, will easily enter into an animated debate on the issue of India’s greatness. To them, all the corruption, the famines (and the Rs. 3 cheques), the electricity shortages, the broken roads, the stinking sewers, peddled to them by their hindi dailies, are signs of a nation gone to the dogs, faltering and staggering and falling.But the same paan-wallah, the rickshaw puller, will glue themselves to any available radio set if India is playing hockey/ cricket; will talk in higher, happier tones of Sunita Williams, as if she were their blood sister; and celebrate the Indo-US nuclear deal (without being sure of its meaning). Thus is India great, for its people never give up hope. For all our rot and rust and famine and flood, we never stop believing in the Indian dream. Thus, we call her "Mother India" for its peoples are always expecting.In the end , its the people of India (except those corrupt politicians) who make this country great .
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +30 ALL OTHER COUNTRIES SUCK !!! :) :) :)Thats why u have been downvoted(i think)
•  » » » » 3 years ago, # ^ |   0 This is called the asshole effect.
•  » » 3 years ago, # ^ |   -35 ProudIndian, you should be ashamed.
 » 3 years ago, # |   +32 Hope there won't be cheaters :) Good luck everyone.
•  » » 3 years ago, # ^ |   +49 no cheaters means no work for you :D
 » 3 years ago, # |   +13 Codeforces judging system seems down! God knows what will happen! :(
 » 3 years ago, # |   +2 Good luck to everyone
 » 3 years ago, # |   0 I hope to redeem myself from the previous contest. :)
 » 3 years ago, # |   -22 Will it be a rated one? I did not see u guys mentioning it anywhere.
•  » » 3 years ago, # ^ |   +7 Yes, it's rated.
 » 3 years ago, # |   +63 "largest college festival of central India" — every central India college fest claims this :P
 » 3 years ago, # |   0 I hope it's good contest
 » 3 years ago, # |   -16 The points distribution shows that the problems don't have gap in their complexity! Good!
 » 3 years ago, # |   +3 feel sleepy at midnight zzz~
 » 3 years ago, # | ← Rev. 2 →   +78 Rating prediction for this contest could be found here (after contest begins)Extensions: About CF-PredictorGood luck & high rating to everyone!
•  » » 3 years ago, # ^ |   +8 Wow, thanks :D
•  » » 3 years ago, # ^ |   +5 wow,i get the same result thank you <3
•  » » 3 years ago, # ^ |   0 this time it was close to the real rating. good job ;)
•  » » » 3 years ago, # ^ |   +5 Was it wrong for you? According to my tests, prediction is 100% correct for this contest:)
•  » » » » 3 years ago, # ^ |   +5 no for me it was correct. thank you
•  » » » » » 3 years ago, # ^ |   0 You are welcome!
•  » » 3 years ago, # ^ |   +2 WOW,I just get the same result.
•  » » 3 years ago, # ^ |   -8 WOW,I just get the same result.
•  » » 3 years ago, # ^ |   +5 Same result ! Thanks ;)
 » 3 years ago, # |   -6 I have never become a newbie, hoping this won't happen today!!
 » 3 years ago, # |   0 damn . cant understand problem c again :|
 » 3 years ago, # |   +5 too easy I forgot to submit !!
 » 3 years ago, # |   0 Why the solution of number B is in queue for a long time????
 » 3 years ago, # | ← Rev. 3 →   -18 admit it great contest UPD : LOL the judge system has downed since I wrote this comment but despite of all these issues, I think the problems are very interesting and the problem statements are very clear
 » 3 years ago, # |   +31 Judge system down :(
 » 3 years ago, # |   0 It seems like queue of hack is very big! Submitted about 8 minutes ago , Still in queue!
 » 3 years ago, # |   0 Queue :(
 » 3 years ago, # |   +8 10 minutes in queue.
 » 3 years ago, # |   -15 Seems like unrated round :(
 » 3 years ago, # |   +35 Whatever Happens!! I want to see ratings changed!! :P
 » 3 years ago, # |   -68 We are very sorry to say that, this round will be unrated :(
 » 3 years ago, # |   0 Just after the announcement on 'C' judge system went down! Submission of 'C' everywhere!!
 » 3 years ago, # |   +49 Is the system divided by zero?Cf get runtime error xD
•  » » 3 years ago, # ^ |   +1 yeah i have no idea why i am getting runtime error
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 did you ever figure this out? also got runtime error on B pretest 5 with python
•  » » » » 3 years ago, # ^ |   +1 yeah same here; thats because of overflow with range/xrange switching to while loop may help.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Thanks, would never have guessed that. It works fine on locally on the same example with pypy and python2.7.12.
 » 3 years ago, # |   0 am i using internet explorer....
 » 3 years ago, # |   -19 solutions are in queue for a very long time . Contest might become unrated.
 » 3 years ago, # |   +31 The contest should be unrated.
•  » » 3 years ago, # ^ |   +4 I think the same
•  » » » 3 years ago, # ^ |   0 Cause of your rating ?! you wanna escape from newbie ?! Right ?
•  » » » » 3 years ago, # ^ |   0 I don't waste my time talking to people like you on net ...
 » 3 years ago, # |   +4 please extend the time of contest
•  » » 3 years ago, # ^ |   +6 yes please extend time if its rated.
 » 3 years ago, # |   +3 either time should be extended or the contest should be made unrated!
 » 3 years ago, # |   -9 Not only the judging system ... The whole site is maybe slowed down :( Any page is taking near 3-4 minutes to load.. My Internet Speed is ok.. :(
 » 3 years ago, # |   +71 Make it unrated!! 25 min wait times are unreasonable.
•  » » 3 years ago, # ^ |   0 It has to be unrated
 » 3 years ago, # |   -7
•  » » 3 years ago, # ^ |   +5 The time was extended, queue stabilized, I dont see any reasons to make it unrated ...
•  » » » 3 years ago, # ^ |   +5 When one submits a Wrong solution and think that this was right..... But after ~25 minutes he found that it was wrong -_-This round should be unrated :(
•  » » » 3 years ago, # ^ |   0 Maybe the main reason it's good round for you?
 » 3 years ago, # |   -6 Some people for some reason do not have access to debug tools other than codeforce which went down for an hour. Rated, seriously?
 » 3 years ago, # | ← Rev. 2 →   -7 What! only 10 minutes extended -_- lol
 » 3 years ago, # | ← Rev. 2 →   +5 In Problem C I used the trivial solution :D I do the operations until I find that my array is repeated :DWill this exceed the Time limit in some cases ? :p
•  » » 3 years ago, # ^ |   0 If you are checking for repetition, each of 'k' iterations could take O(n) time for comparison and O(n*log(n)) for sorting. So if the array doesn't repeat then there is a good chance that the solution would timeout.
 » 3 years ago, # | ← Rev. 2 →   +29 RIP those that didn't saw the unusual time limit on Problem C. It took me 2 hours to realize that (+ xi <= 1000) and then write solution with O(k*1000)
•  » » 3 years ago, # ^ |   0 Same here :(
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 Should not it be k*1023 ? 959 xor 64 is 1023
•  » » 3 years ago, # ^ |   0 How does this solution look like?
•  » » » 3 years ago, # ^ |   +3 Use counting sort kindof. So you now how much elements you need to xor and how much will remain the same. 24848957
 » 3 years ago, # | ← Rev. 2 →   +162 So many times someone said (Swistakk for example) that scoring should form something closer to a geometric progression. My G submitted in last minutes after two WA's is worth 912 points. Awesome. I hope that my B will pass because it's worth more.Was points loss adjusted to a longer contest? If not, it only made things worse.EDIT: fortunately my B passed
•  » » 3 years ago, # ^ |   +5 Points loss was the 2:00 formula for a 2:30 + 0:10 contest. Did asking that really take less effort than subtracting 2 numbers?
•  » » » 3 years ago, # ^ |   +5 Subtracting what 2 numbers? I still don't know how to easily say if points loss was adjusted.
•  » » » » 3 years ago, # ^ |   0 In a 2:00 contest, a task worth x points should lose x/250 points per minute.Check what minute you submitted, how many points below the maximum you are (not counting points lost to wrong submissions) and discover that you indeed lost x/250 per minute.
•  » » » » » 3 years ago, # ^ |   +5 Why should I know/remember that x/250 formula? And we're talking about dividing here (or at least multiplying) so things become harder than just subtracting ;p
•  » » » » » » 3 years ago, # ^ |   -17 You should remember it because if you did, you could have predicted your score for G (and maybe hacked instead) instead of whining after the contest.Disclaimer: I agree that this is a bad mechanic and should be changed.Disclaimer 2: Solving G is probably a more fun and productive use of your time than hacking, unless you just want rating.
•  » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 I don't have to remember it because on the problem page I can see (on the right side) how many points I would get submitting right now. I knew during solving that I won't get much. It was still an optimal strategy after hacking — I have read all solutions to A in my room and hacked many of them. Following your logic: you should find me on the leaderboard and see that before arguing.My ranting has goal: organizers should use better scoring and should always (?) adjust scoring. It will make contests better.
•  » » » » » » » » 3 years ago, # ^ |   -15 You should wait for systests to finish before mentioning the leaderboard.
•  » » » » » » » » » 3 years ago, # ^ |   +10 Why? I got TLE in G and my hacks weren't canceled. Which of my comments makes less sense now?
•  » » » » » » » » » 3 years ago, # ^ |   -8 The statement that solving G is better than trying to get even more hacks.Of course, arguing based on 1 data point isn't very convincing, I'm just shitposting for the sake of shitposting.
•  » » » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 I think we don't agree about the definition of "optimal strategy" in a case when a player (participant in this case) doesn't have full information about the game.EDIT: Also, congratulations for your place. Let's say that your strategy turned out to be more optimal. What an ugly sentence I've just created.
•  » » 3 years ago, # ^ |   +86 ranting part 2I think that tricky tests with f = 0 or w = 0 in 768F - Бочки и коробки should be included in pretests. You can't expect people to hack this problem because in most of rooms at most 1 person solves such a problem. So you just give WA's to all people that miss that thing. And for many it was misreading the statement (understanding that both f and w are positive), not forgetting about corner case.Let me also say something positive: I liked 768G - Ветры зимы.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +35 Hello not adjusted drain, my old friend. I've come to butthurt about you again.I can't believe that not adjusted drain and bad scoring is still a thing. Completely trivial D, E worth 1750 and 2000 points and G worth 2750, sounds legit.
 » 3 years ago, # |   +10 Could someone please explain how to solve B? Thanks.
•  » » 3 years ago, # ^ | ← Rev. 3 →   +5 Notice that, x will produce an array of length 2⌊log(x)⌋ + 1 - 1. Let's call this number len(x)I solved it recursively,f(x, l, r, s) = number of ones at the intersection between the intervals [s, s + len(x) - 1] and [l, r]If [s, s + len(x) - 1] is totally contained in [l, r] then the answer is x. If they don't intersect, the answer is 0.Otherwise, f(x / 2, l, r, s) + f(xmod2, l, r, s + len(x / 2)) + f(x / 2, l, r, s + len(x / 2) + 1)Answer is f(x, l, r, s = 1)I think this solution is too complicated, though :(
•  » » » 3 years ago, # ^ |   +3 Thanks! Any solution is better than no solution to me :)
•  » » 3 years ago, # ^ |   0 Let's consider going down a (complete) binary tree where we are numbering it's nodes like after an in-order traversal. You need to visit only those nodes that lie in the range [l,r]. Hence we add to our result (n mod 2) if and only if the node we are currently on, lies in the range. So the recursion here is f(start, end, n) = (n mod 2 if mid lies in [l,r]) + f(start, mid-1, n/2) + f(mid+1, end, n/2); where mid = (start+end)/2;Hope it helps!
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Divide n by 2 until it is 0 and put that in an array in ascending order.You can see a pattern generated by the number and the final set.Take the index of one 1/0 in the list. Then take the highest power of two that divides that index. The expoent of the power will be exactly the index of the corresponding number that generated it in the array that we built. Therefore, if the number in the array is even, it will be 0, if it is odd, it will be 1.Thus, we can just iterate from l to r, checking the powers of two, and adding 1 or 0 to a counter according to the prebuilt array.i.e. suppose n is 17the array built will be 1 2 4 8 17suppose l is 12 and r is 1612 is divided by 4, which is 2^2, the index 2 in the array is 4, which is even, so the position 12 in the list is 013 is divided by 1 which is 2^0, the index 0 in the array is 1, which is odd, so the position 13 in the list is 114 is divided by 2 which is 2^1, the index 1 in the array is 2, which is even, so the position 14 in the list is 015 gives the same as 13 (and actually every odd index)16 is divided by 16 which is 2^4, the index 4 in the array is 17, which is odd, so the position 16 in the list is 1 and so on.I find that this is the simplest way to solve the problem (my solution was 17 lines long). Unfortunately my solution received Runtime Error because I forgot to test when n = 0.Expected complexity O(log N + 50 * (R — L)) codeint main(){ ll n, l, r, cont = 0; cin >> n >> l >> r; if(n == 0) { cout << 0 << endl; return 0; } vector fac; for(ll i = n; i; (i >>= 1)){ fac.pb(i); } reverse(fac.begin(),fac.end()); for(ll i = l; i <= r; i++){ int e; for(e = 51; e >= 0; e--){ if(i%(1LL<
•  » » » 3 years ago, # ^ |   0 Thanks! Would you mind explaining the proof behind your method?
 » 3 years ago, # | ← Rev. 3 →   0 problem B why i get TLE ..complexity is O((r-l) LOGN * LOG N ) ? r-l <=10e5 here
•  » » 3 years ago, # ^ |   0 N can range up to 10^15. It's definitely a TLE
•  » » 3 years ago, # ^ |   -7 N is 2^50
•  » » » 3 years ago, # ^ |   -8 look at my code . the complexity is O ((r-l )*Log(X) *Log(X)) X = n
•  » » 3 years ago, # ^ |   0 any explaination please ?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Sure! O((r-l) log²(something)) = O(10⁵ log²(something)) which, sometimes, gets TLE.
•  » » » » 3 years ago, # ^ |   0 i got ACC now with small modification i just used a tree map to memoize the value of count function and passed
•  » » 3 years ago, # ^ |   0 I think there is a Log(n) solution with n up to 2^50.
 » 3 years ago, # | ← Rev. 2 →   +212 read Gpersistent dynamic online balanced link-cut tree decompositionhack greens instead
•  » » 3 years ago, # ^ | ← Rev. 3 →   +37 I used a segment tree of multisets only.For each vertex we want to know the list of sizes of trees that will remain after this vertex is cut. Let BIG and SMALL denote the biggest and smallest of them. It's enough to consider moving some subtree of BIG into SMALL. It's optimal to make the size of moved subtree of size as close to (BIG-SMALL)/2 as possible. Let's see how to do it.We compute preorders and we build a segment tree of multisets. For any interval we want to know the set of sizes of subtrees with preorder in this interval. In O(log2) we can ask a structure about a size closes to some value.There is one hard thing left: if BIG turns out not a child of our vertex but its parent and everything above, then we should differently consider subtrees starting from somewhere on the path from our current vertex to the root. If the size of subtree was X initially and our current vertex is v then cutting and moving that subtree moves size X - a. So we need a second segment tree of multisets that will store sizes of subtrees that start somewhere on a path from the current vertex to the root. As we move deeper in a tree, we should remove elements from the first structure and insert them in the second one.EDIT: I got TLE. The complexity is with not so small constant factor. Maybe it can be implemented slightly better.
•  » » » 3 years ago, # ^ |   0 I think you can get O(nlogn) if you use fractional cascading.
•  » » » 3 years ago, # ^ |   0 Errichto, what did you do to get rid of TLE using segment trees of multisets? I tried to represent the multisets using maps, so we avoid some dynamic allocation, but I still got TLE: 25420160For the AC (25418820), I had to switch the preorder segment tree to use vectors instead of multisets (the merge sort style segment tree). This makes the segment tree unable to support updates, so I had to use "DSU on tree HLD style" to maintain the set of subsizes of outer vertices.
•  » » » » 3 years ago, # ^ |   +3 Some constant factor optimizations. If I remember correctly, the main thing is that I replaced small multisets with vectors.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 And you sort these small vectors for every update, if necessary?Edit: Or maybe you just run linear passes, since the vectors are small?
•  » » » » » » 3 years ago, # ^ |   +3 Linear passes are better for small sizes.
•  » » » » » » » 3 years ago, # ^ |   0 Thanks!
•  » » 3 years ago, # ^ | ← Rev. 2 →   +87 My reaction : https://ibb.co/i703Yv
 » 3 years ago, # | ← Rev. 2 →   +27 Was B really hard or was it just me :(edit — just a stupid mistake :/
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I think we have to find places of 0's and put them vector (maximum amount of them are 51). Then just find count of them in range [l, r]. After print r - l + 1 - cnt. O((l - r) * 51).UPD: This solution will get TLE and MLE. Sorry for wasting time.
•  » » » 3 years ago, # ^ |   0 Not quite, consider n = 8 [8] [4 0 4] [2 0 2 0 2 0 2] [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1] Thus 2^3 has 7 0s, so 2^50 Should have 2^50 — 1 zeros.
•  » » » » 3 years ago, # ^ |   0 Oh sorry, my bad.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 I did segment tree way, divide left and right, check if the segment falls within range. But something went wrong, and I just couldn't debug it :(At least I found the mistake now
•  » » » » 3 years ago, # ^ |   0 Maybe looking solutions of top participants will help..
•  » » » 3 years ago, # ^ |   0 Mysoultionwith the same complexity but TLE
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 it was interesting,but if you do a bit of brutforce on paper you would realize this:1.the resulting aray for number n is composed of res(n/2)+n%2+rez(n/2) 2.the number of elements it will have is 2^(log2(N)+1)-1this observations suggest a recursive functionso you do a q(long long number,long long l,long long r) my code is here:https://ideone.com/kFdyY1
 » 3 years ago, # |   0 What's the matter with last contests? Bug, bug everywhere :(
 » 3 years ago, # |   0 Problem E get WA on pretest 17, can't find the bug..
•  » » 3 years ago, # ^ |   0 How do you solve it?
•  » » » 3 years ago, # ^ |   0 Just some game theory about NIM.
•  » » » » 3 years ago, # ^ |   +3 What do you do with NIM? I tried to think of something but failed.
•  » » » » » 3 years ago, # ^ |   0 just do brute-force and fits the TL, but I don't know why I fail pretest 17.. I use following state definition and brute force to calculate every dp[i][0]map dp[80];
•  » » » » » » 3 years ago, # ^ | ← Rev. 3 →   +6 I found a pattern. 1 repeat 2 times 2 repeat 3 times 3 repeats 4 times and so on.. so grundy[1]=grundy[2]=1 grundy[3]=grundy[4]=grundy[5]=2 grundy[6]=grundy[7]=grundy[8]=grundy[9]=3... and so on.Edit : Sharing code, just in case someone wanted to see. It took about 8 secs on my pc. generator#include #define endl '\n'; using namespace std; typedef long long int LL; map , int>dp; int grundy(int n,LL mask){ if(n==0)return 0; if(dp.find(make_pair(n,mask))!=dp.end())return dp[make_pair(n,mask)]; setg; for(int i=1;i<=n;i++) if(!(mask&(1ll<::iterator it; for(it=g.begin();it!=g.end();it++,c++)if(*it!=c)break; dp[make_pair(n,mask)]=c; return c; } int main() { ios_base::sync_with_stdio(false);cin.tie(0); //freopen("input.in","r",stdin); for(int i=1;i<=60;i++) cout<
•  » » » » » » » 3 years ago, # ^ |   0 That pattern is simply: grundy[i]=maximum number j that 1+2+3+...+j = j*(j+1)/2 <= i
•  » » » » » » 3 years ago, # ^ |   0 You can just do brute-force to figure out that the Grundy numbers for the starting positions for each pile are 1, 1, 2, 2, 2, 3, 3, 3, 3... Then you won't need to slow your solution down by doing brute force.
 » 3 years ago, # |   +241 if(n>2){ int lol=rand()%2; if( lol%2 ) printf("NO\n"); else printf("YES\n"); return 0; } get accepted on pretests in E ))))))))))))00000000)))))))))0http://codeforces.com/contest/768/submission/24852367
•  » » 3 years ago, # ^ |   +28
•  » » 3 years ago, # ^ |   +45 This doesn't even call srand
•  » » 3 years ago, # ^ |   -8 if it gets accepted,i will laugh so hard
•  » » 3 years ago, # ^ |   +7 ha ha ha you get wrong on test 21
•  » » » 3 years ago, # ^ |   +13 such unexpectable...
•  » » » 3 years ago, # ^ |   +6 It passed 20 tests !!!
 » 3 years ago, # |   0 How to solve E? I could not find out the Grundy numbers of the states?
•  » » 3 years ago, # ^ |   +13 Brute forces could do the trick.
•  » » 3 years ago, # ^ |   +3 I wrote a bruteforce and found its like 1,1,2,2,2,3,3,3,3... ith value repeated i+1 times...
•  » » 3 years ago, # ^ |   +14 The Grundy number of each i is the maximum number j such j * (j + 1) / 2 <= i
•  » » 3 years ago, # ^ |   +3 For every number a[i], calculate c[i] — number of 1 bits of a[i], and then it's just like at normal NIM game, xor between all c[i], 1 <= i <= N, and if this xor sum is equal to 0, the answer it's "YES", otherwise "NO"
•  » » 3 years ago, # ^ |   +4 In dp(n, mask), we can modify mask to mask only 30 bits, because we will not subtract x (x > 30) from n more than once. solution : 24854077
 » 3 years ago, # |   +13 the slow of system was to show as what's happening when you divide by zero :D
 » 3 years ago, # |   +71 For F, I just realized that I misread the conditions, so in particular, if there are no wine barrels, it seems like the probability is 1 (since there is no stack with height <= h, the condition is trivially satisfied). I printed zero, since I misread it as there is at least one stack, and all stacks have height > h.I'm surprised that this case isn't in the pretest. Also, I'm not sure I like having the condition that there may be zero wine barrels or food barrels since this is hardcoding special cases and not really related to solving the main problem.
•  » » 3 years ago, # ^ |   +5 I have the same bug, I misread it as "It is guaranteed that he has at least one food box AND at least one wine barrel." :-(
•  » » » 3 years ago, # ^ |   +40 Same here. I was wondering why F is F, cause it seemed to be too easy for one of the hardest problems. Now I see that the trickiest part of the problem was "read the statement carefully and do not forget to handle corner cases" )
•  » » 3 years ago, # ^ |   +63 I'm much more stupid. I asked a question: "It is guaranteed that he has at least one food box or at least one wine barrel."is it equivalent to saying that 1 ≤ f, w?I'm asking because there is 0 ≤ f, w just before that I got answer: It's equivalent to 1<=f+w... and I misread that answer and understood 1 <= f, w;_;
•  » » 3 years ago, # ^ |   +6 I was aware of that case and I hoped to hack someone. Unfortunately noone else submitted this problem in my room.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +45 More than 80 submissions failed system test because of this reason. :( And there are about 120 accepted submissions!It seems like authors are trying to decrease the number of accepted submissions for last problems by excluding special cases from pretests, instead of adding harder problems!
•  » » » 3 years ago, # ^ |   -26 ...Problem is as hard as many people are able to solve it (the more people can solve it, the easier the problem).It does not matter whether you almost solved the problem but you missed a special case or you did not have any idea how to solve it (no partial scores in codeforces — I recommend Hackerrank).The fact that almost nobody else in the room is not solving it and can't hack the solution, does not matter. You should think of all the cases upfront, before even submitting it.If you did not think of all the cases, you fail the problem. If it was a full feedback contest, then you would see the results during the contest. I totally do not understand your concerns.
•  » » » » 3 years ago, # ^ |   +13 A problem is what is said in its statement. Weak test data doesn't make it easier, and weak pretests doesn't make it harder."Problem is as hard as many people are able to solve it."I agree. But we have different opinions about "solving" a problem!
 » 3 years ago, # | ← Rev. 2 →   +144 If feel this contest simply ... ought to be unrated. Nearly half the contest was feedback-less and the last 2 problems simply don't deserve their place as F and G for a division combined. I really appreciate the problem setters' efforts, but still.Edit. As geniucos told me earlier, this was more of a Div2 + Div1 contest than a Div1 + Div2.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +7 Actually I said Div2 — Div1 (but your comment is not far anyway) as last div2 contest seemed to be harder than this one. Rated or unrated, one thing is for sure: the contest could hardly be regarded as good for div2 only, let alone a div1 + div2.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +5 It was for Div0 — for participants who like corner cases and hacking :)
•  » » 3 years ago, # ^ | ← Rev. 2 →   +10 I also think so,A-F implementation only,G didn't read.And i'm only violet.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +39 Well, feedback-less problem is a good reason to make a contest unrated, but its difficulty is not.
•  » » » 3 years ago, # ^ |   +49 It was just a second reason (even though it shouldn't be required as you had to wait for up to 20 minutes to get the feedback for one of your submissions). From other point of view, the quality of problems and pretests was the lowest I've seen lately (or, actually, ever) in a CF round. I just can't believe that E was solved by 567 people and half of the sources on F failed on a case in which W or H is 0 (which of course was not part of pretests). How could the assessment of the difficulty of the problems be so far from the reality?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +38 Also, I still can not fully understand why did they have to express a statement about precision in such an odd manner in D. Saying eps < 10 - 7 implies picking eps = 0 would have been valid, too, rendering the first statement useless to begin with.
 » 3 years ago, # |   +41 In problem F, is there any way to handle the case when q is divisible by 1e9+7?
•  » » 3 years ago, # ^ |   +10 The task statement simply says q^-1 without mentioning that, so I (and probably a large percentage of the other 253 submissions) just assumed that case doesn't happen. I kinda hope we all get WA on systests.
•  » » » 3 years ago, # ^ |   +10 What should be q^-1 mod 1e9+7 if q is divisible ? Does it exist ?
•  » » » » 3 years ago, # ^ |   +20 No, but if both p and q are 0 mod 1e9+7, then the reduced fraction p/q can lead to a well-defined pq^-1.
•  » » » » » 3 years ago, # ^ |   0 Oh i see! but if p is not divisible then the answer simply doesn't exist. So i guess the problem is wrong ? :P
•  » » » » » » 3 years ago, # ^ |   +31 In reduced formP/Q, Q will never be divisible by 1e9+7.
•  » » » » » » » 3 years ago, # ^ |   0 Nice!
•  » » » » » 3 years ago, # ^ |   0 According to the statement, formally, that is not the answer we should output in this case.
•  » » 3 years ago, # ^ |   +110 The contest is named "Divide by zero", an evidence of the availability of that deadly corner case???
•  » » 3 years ago, # ^ |   0 Did you ask the judges during the contest?
•  » » 3 years ago, # ^ |   +117 Cannot because q = C(f, f+w)
•  » » » 3 years ago, # ^ | ← Rev. 3 →   +1 Really nice reinterpretation. However, when H = F = W = 0, the answer should be 1 (as the probability for something that does not exist to have a particularity is 1). Of course, such cases cannot do anything but increase the beauty of the task (and the set, as it was ranked as second hardest)PS: I was being sarcastic on the part about the beauty of the problem, in case it's not obvious
•  » » 3 years ago, # ^ |   +18 I actually asked them and they said such case will never happen.
 » 3 years ago, # | ← Rev. 2 →   -30 Good problem-set and a well balanced contest imo. (Although it might have been on the easier side for Div 1 contestants)Failed to calculate the Grundy Number for E question though. How is it calculated?
•  » » 3 years ago, # ^ |   0 bruteforce?
•  » » 3 years ago, # ^ |   +8 i wrote a dp(number , mask) and ran it locally to get all values from 0 to 60 (took about 5 seconds to run)
 » 3 years ago, # |   -32 Dose it rated or unrated contest?
 » 3 years ago, # |   +19 I just screwed up this round but this might be the last pretest-passed submission. Cool
 » 3 years ago, # |   0 During the contest I (because of rushing and skipping the details) was solving such version of F: A configuration is good if any pile of wine has > h boxes. Is it still solvable in faster than O(N^2) time?
 » 3 years ago, # |   0 Does somebody know what pretest 4 on problem D was?I've looked through other participants code,but the main ideea was the same.
 » 3 years ago, # |   +25 Should I cry now or later ?
•  » » 3 years ago, # ^ |   0 Maybe now :)
•  » » » 3 years ago, # ^ |   0 Done :D
 » 3 years ago, # |   0 For Problem F, when f or w equals to 0, as a result ,p equals to 0 too.And how to calculate the inverse of 0 under mod 1e9+7?
•  » » 3 years ago, # ^ |   0 You don't need inverse of p, do you?
 » 3 years ago, # |   +16 Just a little feedback from me. I liked all of the problems, I think they are all pretty nice. But weren't they way too easy (at least up to F, didn't read G)? I know I wasn't among the fastest solvers but still, I read E early and solved it quite fast IMO. Also, I knew how to solve F almost immediately after reading it, bad that I read it too late. But anyway, difficulty is a relative term, depending on people and types of problems. So, nice round, thanks :)
•  » » 3 years ago, # ^ |   0 I think most problems were on the same level roughly. So most were on the easier side, but only A was the trivial implementation task that ABC usually are.
•  » » 3 years ago, # ^ |   +3 Easy for you. I only managed to solve C correctly.
 » 3 years ago, # |   +7 Is problem E's solution the same as nim problem? I saw some codes pass the pretest doing the same thing as the nim
•  » » 3 years ago, # ^ |   0 You can reduce it to a modified Nim, but just Nim won't pass. The second sample test is a winning position in Nim, but a losing positiom for the custom game.
 » 3 years ago, # |   0 please Explain why i got TLE ? problem B ..complexity is O((r-l) LOGN * LOG N ) ? r-l <=10e5 Here
•  » » 3 years ago, # ^ |   0 Which is too slow. You need or better to pass.
•  » » » 3 years ago, # ^ |   0 Not really, I'm quite sure my solution is (r-l)*log(n)*loglog(n) :)
•  » » » » 3 years ago, # ^ |   +5 i modified it ..i used tree map to as MEMO for count Function and it ACC now
 » 3 years ago, # | ← Rev. 3 →   0 What was the approach for D? I computed the log of numerator and denominator of http://math.stackexchange.com/a/1007107/115535 . Then binary search till the desired n, number of days, is obtained. But could not pass the pretests!
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 any ideas, guys!!!
•  » » 3 years ago, # ^ |   +3 my idea is dynamic programming with dp[i][j] mean the probability at day i you get j orbs and it can be calculated as dp[i][j] = dp[i — 1][j — 1] * (k — j + 1) / k + dp[i][j] * j / k
•  » » » 3 years ago, # ^ |   0 Thanks, you mean, dp[i][j] = dp[i — 1][j — 1] * (k — j + 1) / k + dp[i-1][j] * j / k, right?And also, what was the bound on num days?
•  » » » » 3 years ago, # ^ |   +3 I think 10000 is enough
•  » » 3 years ago, # ^ |   +3 I had the same idea, but I didn't have time to code it...
•  » » 3 years ago, # ^ |   +8 You linked to the formula in the second answer i believe.This formula is wrong. You are dividing the number of preferred combinations by total combinations assuming that each combination has equal probability of occurring, which is not the case. If you take a combination X[1], X[2]....., X[k] where X[i] is the frequency of type i, then this combination has probability of occurring (N! / (X[1]!X[2]!....X[k]!) / kN , where N is the number of days. This probability will be different for different combinations.
•  » » » 3 years ago, # ^ |   0 @fauzdar65, thanks for your clarification.
 » 3 years ago, # |   +1 is supposed to TLE in B?
•  » » 3 years ago, # ^ |   +2 nevermind , it fails for N = 0 case.
•  » » » 3 years ago, # ^ |   0 Same here otherwise passed all the testcase!!!!!!
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 same here .. Here
•  » » 3 years ago, # ^ |   0 but i didn't even pass the pretest ..because i use java i think
•  » » 3 years ago, # ^ |   +3 it has O(n) : Link
 » 3 years ago, # |   0 In problem C, if k is even nothing (besides sorting) in array won't be changed yes? If I'm wrong please correct me.
•  » » 3 years ago, # ^ |   0 that's right
•  » » » 3 years ago, # ^ |   0 And if k is odd it is equal to 1 operation yes?
•  » » » » 3 years ago, # ^ |   0 no because the order of elements changes after each operation
•  » » » » » 3 years ago, # ^ |   0 Oh, I just forgot that, my bad :( Thanks.
•  » » » 3 years ago, # ^ |   0 Hello, I was try to my best but not accepted please help me to send your code for find out bug.ashraful.duet1@gmail.com Thanks.
 » 3 years ago, # |   +91 I think main tests of problem D are too weak.If k = 2 and p = 1000, the answer is 2 (probability is 1/2, which is greater than )However, some source code (example: 24838082) outputs 3 but passed main tests.
•  » » 3 years ago, # ^ |   +37 I can't believe that k = 1 and k = 2 are not included. I think they should add those into the tests and rejudge before the ratings are released.
•  » » » 3 years ago, # ^ |   +26 Obviously they updated the ratings without rejudging. Contest authors these days tend to ignore comments from the community.
•  » » » 3 years ago, # ^ |   +12 Adding tests after the contest leads to strange situations. Should people be afraid to post "hah, my solution is wrong for this test: ..."? And what about solutions with hashes? Many solution can be hacked once you see it.
•  » » » » 3 years ago, # ^ |   +19 This case is obviously different from hashing. We are talking about tests that should have been included when the problem is prepared.
•  » » » » » 3 years ago, # ^ | ← Rev. 3 →   +15 It's impossible to define a clear border — to say when tests should be added. I used to have the same opinion you have now. After many conversations and some thinking I changed my mind. Contest have clear rules: organizers prepare tests and your task is to pass them. You should be able to solve all valid tests but this is not what you get AC for. You get AC for passing tests prepared by organizers. Sometimes it allows to squeeze some too slow solution or get AC with an incorrect one — but judging is automatic and everybody is equal.EDIT: But ofc. I agree that tests should be strong in the first place and it's organizers' responsibility. Though I failed that task many times myself so I'm trying not to be very harsh to someone who did the same :D
•  » » » » » » 3 years ago, # ^ |   +26 I agree that tests should not be added if it is ACM or IOI format where contestants get their results live, or if the points are given per case like in HackerRank. But I don't think that's an issue in Codeforces because the contestants well know that there will be system tests.
•  » » » » » » » 3 years ago, # ^ |   0 All my arguments work for contests without full feedback too.
•  » » » » » » 3 years ago, # ^ |   0 Regarding the hashing problems, I agree that tests on hacking some hash functions should not be added in normal circumstances, as hashing functions can usually be hacked once you see it. So it is enough for the organizers to prepare cases that can reject the solutions that are wrong because of other stuffs.As you mentioned, organizers should be responsible to prepare strong tests. And it is obvious that corner cases should be regarded as part of strong tests as it is one of the contestants' goals to figure them out.If the tests are too weak(as mentioned by cubelover), there are three main reasons that we should add tests in my opinion: As mentioned by microtony, adding tests after contest under Codeforces format do not create any unfair situations as those solutions still passed pretests. Contestants can still regard the new tests included in the System Test. It is organizers' responsibility to include such tests before the contest. So when those cases are not included, still, it is their responsibility to include them afterwards. Otherwise, organizers can be excluded from adding strong tests as they have no consequences even if they don't do so. It is unfair to those who have handled those corner cases if stronger tests are not included and added. Contestants who have handled corner cases should be ranked higher than those who have not. And moreover, it is much more important to guarantee so under contests with prizes as these may affect the ranking. I'm sorry if i wrote too long, but some of the recent contests were facing similar issues which lead me to think seriously.
•  » » » » » » » 3 years ago, # ^ |   +17 I understand reasons in favor of your opinion. You must understand reasons against it.Do you want a situation when after a contest people stress test solutions of others and try to break them, to move one place up? Someone will have to decide if a test should be added indeed, while it's impossible to clearly say what is a corner case and obviously should be added and what is not. still, it is their responsibility to include them afterwards ok, they can do it for upsolving It is unfair to those who have handled those corner cases if stronger tests are not included and added But they got AC and in the long run caring about corner cases gives better places obviously.
•  » » » » » » » 3 years ago, # ^ |   0 It is possible that if the authors had come up with these tests, they would've included them in pretests. If I was an author, I would definitely do this. In this case it would've affected the competition in other way, so adding them now is not fair.
 » 3 years ago, # |   +104 G with 978 points :(
•  » » 3 years ago, # ^ |   0 675 pts for F here (though I got WA 9 times)
•  » » 3 years ago, # ^ |   0 MerdanHe~~~~
 » 3 years ago, # |   +2 Editorial Please !!
 » 3 years ago, # |   +6 Can some one explain the logic of 3rd question?
•  » » 3 years ago, # ^ |   0 problem c look at the constraints 0<=ai<=1000 and 0<=x<=1000 , that means you will have at most 1001 distinct numbers in the initial array . and after taking xor with number you can maximum number with with all the 9 bit set . Fact 1: A^X=B , B^X=>A Maintain the count of each number arr[K][number]=count , after K operations . so when you are taking xor with i , that means you are taking roughly count/2 numbers and changing it to x^i . That means roughly count/2 element count increase for x^i . as K will be very huge and you make state for odd and even operations . - See code Solution
 » 3 years ago, # |   +10 Seems that Problem E requires submitting a table, or your program needs to have a small constant. My program uses about 2.5s to calculate all the answer, which gives me confidence to submit. Then got TLE for big N only because N is very big :( Constant... Constant... Constant...
•  » » 3 years ago, # ^ |   +20 I didn't submit a table and got AC in ~1.0s.http://codeforces.com/contest/768/submission/24836830
•  » » 3 years ago, # ^ |   0 you can use the fact grundy(initial_stones)=n where {maximum value of n | n*(n+1)<=2*initial_stones}
 » 3 years ago, # |   +5 Why did so many F's failed systests? I can't see any kind of corner case
•  » » 3 years ago, # ^ | ← Rev. 2 →   +10 I think it is w=0 or f=0 (if w=0 answer is 1, if f=0 answer is w > h ? 1 : 0)
 » 3 years ago, # |   +14 Practice season please.
 » 3 years ago, # |   0 I guess that without assert my B would be AC :/ Listen me my dear friends, don't use asserts on cp, just don't. :D
•  » » 3 years ago, # ^ |   0 I was telling you many times — do test your code. You should have run it for n = 0 before submitting.
 » 3 years ago, # | ← Rev. 2 →   +7 Sorry for the error.
•  » » 3 years ago, # ^ |   +23 min = Math.**max**(min, a[i]);
•  » » 3 years ago, # ^ |   0 Can you explain how you tested it on the failed test case?
 » 3 years ago, # |   0 I messed up this contest...a silly mistake in problem A..(instead of i--,i was doing i++) . I messed up last contest also...was declaring array of size 10^5 instead of 2*10^5 for problem A. What is happening with me?
•  » » 3 years ago, # ^ |   0 The same happened with me. Just take a relax and do not think about anything. After some time you will surely be back on track :)
 » 3 years ago, # |   +14 When can we upsolve?
 » 3 years ago, # |   +104 [Problem D] Just curious, what did "the probability of (...) is at least , where ε  <  10 - 7 mean?Assuming that our task was to find the minimum number of days after which the probability of collecting all the orbs is larger than : did you check if for all the feasible inputs the answer will not change when the float precision errors are taken into account? For example, the answer could have changed when pi = 500 ± 10 - 200 and our solutions (DP based on some floating-point calculations) wouldn't even notice that.
•  » » 3 years ago, # ^ |   +10 I wrote the same solution in python using only integers, for all k I tried (including k = 1000) it gives the same answer as the c++ solution with long doubles and ε = 10 - 7.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +11 I wonder if using doubles and comparing the value against could be the reason for WA in test 19. 12 red coders including me got WA in that test.
•  » » » 3 years ago, # ^ |   +24 You did the comparisons against , though. :(
•  » » » » 3 years ago, # ^ |   0 Oh, I guess that's the reason. Thanks!
•  » » » 3 years ago, # ^ |   +8 I also got a WA on test 19 because a precision issues, but I was comparing against instead of .
•  » » » » 3 years ago, # ^ |   +8 Me too! :(
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 I'll be very sad if that's what causes WA :( I resubmitted to add epsilon..... WA Case: 935 1 2 I got 4607 with epsilon and 4608 (correct) without it ._.
 » 3 years ago, # |   -16 for B i used the same approach but he got ACC and i got TLE ? i use Java and he uses C++ . c++JAVATHAT'S NOT FAIR ?
•  » » 3 years ago, # ^ |   +21 c++ solution uses memoization in count function
•  » » » 3 years ago, # ^ |   0 thank you very Much i didn't notice that ? how can i do the same in Java ?
•  » » » » 3 years ago, # ^ |   0 use a map, if a number is already count, you can find it's count in map
•  » » » » » 3 years ago, # ^ |   +8 yes i got ACC now .. thank yoooou very much .thank you lovely guys <3
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 congratulations (≧∀≦)
 » 3 years ago, # | ← Rev. 2 →   0 problem D -> http://codeforces.com/contest/768/submission/24841958 Why do i get wrong answer on pretest 4 , i used dp solution ??? on my machine the code outputs the correct answer , also on cpp.sh.can some1 figure out what is wrong with my code ???ive compiled with gcc 5.4.1 and also with 6.2.0 same result (the correct result) thank you
 » 3 years ago, # |   0 Thank you codeforces..
 » 3 years ago, # |   +25 please add problems to practise.
 » 3 years ago, # |   +66 balanced
•  » » 3 years ago, # ^ |   +67 Step up your game
 » 3 years ago, # |   +1 I have an O(logN) solution for B. We can observe that the sum of number of ones in the expansion of n is n. f(n,l,r)=f(n,1,r)-f(n,1,l-1) and so now to calculate f(n,1,r) we can see where exactly r lies. Let M be the mid point of the expansion. If r lies to the left, we have a single call to f(n/2,1,r). Else we add n/2, n%2 and f(n/2,1,r-m), which is the remaining sum.
 » 3 years ago, # |   +5 Sad story hereAC: 24853687 Pretest Failed: 24851214All because i forgot writing "+" in: dp[i][j] += p*dp[i-1][j]; Probably could have grabbed that shirt for top 15 in India only if i would have realized this during contest...
 » 3 years ago, # | ← Rev. 5 →   +3 Can anyone explain the logic in the following code? I am not getting the point why k%1024 is taken? Please help me out. Problem C. Accepted solution link: http://codeforces.com/contest/768/submission/24852093Accepted code: `#include #include #include using namespace std; int main() { int n,k,x; vector v; cin>>n>>k>>x; for(int i=0;i>a; v.push_back(a); } if(k>1024) k=k%1024; for(int j=0;j
•  » » 3 years ago, # ^ |   -40 It's meaningless, because k <= 1000 by the constraint
•  » » » 3 years ago, # ^ |   +1 k<=10^5
•  » » » 3 years ago, # ^ |   +1 k <= 100000 by the constraint.
•  » » 3 years ago, # ^ |   +21 It's wrong.3 2048 8007 10 18answer: 810 18the code above prints: 18 7
 » 3 years ago, # |   0 After an hour of meditation I still cannot understand the following solution: 24828716.Could someone, please, explain it? =)