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:
- AakashHanda, apoorv_kulsh, arnabsamanta, killer_bee, vntshh and myself (sidprasad) for setting the problems.
- usaxena95, shubhamgoyal__, aditya1495, harshil, rohitranjan017, k_sudharsan, and vedaanta for their contribution to the problemset.
- KAN and netman for all their invaluable help with the round.
- MikeMirzayanov for the amazing Codeforces and Polygon platforms.
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:
- y0105w49
- W4yneb0t
- V--o_o--V
- Merkurev
- anta
- I_love_Tanya_Romanova
- Endagorion
- BigBag
- HYPERHYPERHYPERCUBELOVER
- jqdai0815
- natsugiri
- mnbvmar
- halyavin
- Shik
- Aeon
Indian Top 15:
- Sumeet.Varma
- rajat1603
- xorfire
- memset123
- animeshf
- akulsareen
- shubham1694
- alecsyde
- AnonymousBunny
- ajinkya1p3
- mohitbindal
- wittyskull
- chintu
- ajs97
- polingy
UPD3: Editorial
Good luck !
Great.Looking forward to it.
Cool! Must participate in. Thanks for contest
Hehe Now would be a fight because of the T-shirts)
Всё кароч, ща будет мясо из-за маечек)
why servers so unfair to us...
13 people
worked to make this round !!so it has many cartoons and long statements :D
You will be surprised.
Everyone wrote one line in each problem statement :D
Someone posted a photo on the last round's blog..About Pigeon Hole theory.. 13 writers made me remind of that :'|
It had better the T-shirts was for random people from 1..500(for example).Then there will be a chance to win it!!!
You never know, you might win it.
...
:)
wallpapers fetish !!
It's not customary to ask if it's a rated, so I have to come up with different question...
Is it racist?
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.
I don't know if it's racist, but it's definitely stupid.
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?
It is none of your business ! :O
"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
"I just press the F button"
Learnt something new today :D
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
Well done! because you say thanks to MikeMirzayanov
So now codeforces is not just Russia, Spreading legs.
good work mike and team
'Spreading wings' is the English phrase for expanding to and exploring new realms.
'Spreading legs' means sexual enticement and promiscuity.
I don't know why, but I feel some math problems
Finally a contest with its time given in IST :D
No need to convert to IST from UTC :P
...you can see the contest in your local time if you go to the contests tab.
I hasn't had a T-Shirt before :'(
Can I register now? I forgot yesterday and now I am seeing it's Registration is completed!
Of course you can. You should click that "Register now »" and join it.
India is becoming popular day by day in terms of organizing programming contest in Codeforces.
YES !!! INDIA ROCKS !!! ALL OTHER COUNTRIES SUCK !!! :) :) :)
इंडिया !!!!!!!!!!!!!!!!!!
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 :
Some 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 .
ALL OTHER COUNTRIES SUCK !!! :) :) :)
Thats why u have been downvoted(i think)
Hope there won't be cheaters :) Good luck everyone.
no cheaters means no work for you :D
Codeforces judging system seems down! God knows what will happen! :(
Good luck to everyone
I hope to redeem myself from the previous contest. :)
Will it be a rated one? I did not see u guys mentioning it anywhere.
Yes, it's rated.
"largest college festival of central India" — every central India college fest claims this :P
I hope it's good contest
The points distribution shows that the problems don't have gap in their complexity! Good!
feel sleepy at midnight zzz~
Rating prediction for this contest could be found here (after contest begins)
Extensions:
About CF-Predictor
Good luck & high rating to everyone!
Wow, thanks :D
wow,i get the same result thank you <3
this time it was close to the real rating. good job ;)
Was it wrong for you? According to my tests, prediction is 100% correct for this contest:)
no for me it was correct. thank you
You are welcome!
WOW,I just get the same result.
Same result ! Thanks ;)
damn . cant understand problem c again :|
too easy I forgot to submit !!
Why the solution of number B is in queue for a long time????
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
Judge system down :(
It seems like queue of hack is very big! Submitted about 8 minutes ago , Still in queue!
Queue :(
10 minutes in queue.
Seems like unrated round :(
Whatever Happens!! I want to see ratings changed!! :P
Just after the announcement on 'C' judge system went down! Submission of 'C' everywhere!!
Is the system divided by zero?
Cf get runtime error xD
yeah i have no idea why i am getting runtime error
did you ever figure this out? also got runtime error on B pretest 5 with python
yeah same here; thats because of overflow with range/xrange switching to while loop may help.
Thanks, would never have guessed that. It works fine on locally on the same example with pypy and python2.7.12.
solutions are in queue for a very long time . Contest might become unrated.
The contest should be unrated.
I think the same
Cause of your rating ?! you wanna escape from newbie ?! Right ?
I don't waste my time talking to people like you on net ...
please extend the time of contest
yes please extend time if its rated.
either time should be extended or the contest should be made unrated!
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.. :(
Make it unrated!! 25 min wait times are unreasonable.
It has to be unrated
There you go.. :P
The time was extended, queue stabilized, I dont see any reasons to make it unrated ...
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 :(
Maybe the main reason it's good round for you?
Some people for some reason do not have access to debug tools other than codeforce which went down for an hour. Rated, seriously?
In Problem C I used the trivial solution :D I do the operations until I find that my array is repeated :D
Will this exceed the Time limit in some cases ? :p
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.
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)
Same here :(
Should not it be k*1023 ? 959 xor 64 is 1023
How does this solution look like?
Use counting sort kindof. So you now how much elements you need to xor and how much will remain the same. 24848957
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
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?
Subtracting what 2 numbers? I still don't know how to easily say if points loss was adjusted.
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.
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
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.
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.
You should wait for systests to finish before mentioning the leaderboard.
Why? I got TLE in G and my hacks weren't canceled. Which of my comments makes less sense now?
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.
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.
ranting part 2
I think that tricky tests with f = 0 or w = 0 in 768F - Barrels and boxes 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 - The Winds of Winter.
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.
Could someone please explain how to solve B? Thanks.
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 :(
Thanks! Any solution is better than no solution to me :)
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 17
the array built will be 1 2 4 8 17
suppose l is 12 and r is 16
12 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 0
13 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 1
14 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 0
15 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))
Thanks! Would you mind explaining the proof behind your method?
problem B why i get TLE ..complexity is O((r-l) LOGN * LOG N ) ?
r-l <=10e5
here
N is 2^50
any explaination please ?
Sure! O((r-l) log²(something)) = O(10⁵ log²(something)) which, sometimes, gets TLE.
read G
persistent dynamic online balanced link-cut tree decomposition
hack greens instead
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.
I think you can get O(nlogn) if you use fractional cascading.
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: 25420160
For 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.
Some constant factor optimizations. If I remember correctly, the main thing is that I replaced small multisets with vectors.
And you sort these small vectors for every update, if necessary?
Edit: Or maybe you just run linear passes, since the vectors are small?
Linear passes are better for small sizes.
Thanks!
My reaction : https://ibb.co/i703Yv
Was B really hard or was it just me :(
edit — just a stupid mistake :/
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.
Not quite, consider n = 8
Thus 2^3 has 7 0s, so 2^50 Should have 2^50 — 1 zeros.
Oh sorry, my bad.
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
Maybe looking solutions of top participants will help..
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)-1
this observations suggest a recursive function
so you do a q(long long number,long long l,long long r) my code is here:https://ideone.com/kFdyY1
What's the matter with last contests? Bug, bug everywhere :(
Problem E get WA on pretest 17, can't find the bug..
How do you solve it?
Just some game theory about NIM.
What do you do with NIM? I tried to think of something but failed.
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<ll, int> dp[80];
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.
That pattern is simply: grundy[i]=maximum number j that 1+2+3+...+j = j*(j+1)/2 <= i
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.
get accepted on pretests in E ))))))))))))00000000)))))))))0
http://codeforces.me/contest/768/submission/24852367
This doesn't even call srand
if it gets accepted,i will laugh so hard
ha ha ha you get wrong on test 21
such unexpectable...
It passed 20 tests !!!
How to solve E? I could not find out the Grundy numbers of the states?
Brute forces could do the trick.
I wrote a bruteforce and found its like 1,1,2,2,2,3,3,3,3... ith value repeated i+1 times...
The Grundy number of each i is the maximum number j such j * (j + 1) / 2 <= i
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"
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
the slow of system was to show as what's happening when you divide by zero :D
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.
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." :-(
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" )
I'm much more stupid. I asked a question:
I got answer: It's equivalent to 1<=f+w
... and I misread that answer and understood 1 <= f, w
;_;
I was aware of that case and I hoped to hack someone. Unfortunately noone else submitted this problem in my room.
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!
...
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.
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!
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.
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.
It was for Div0 — for participants who like corner cases and hacking :)
I also think so,A-F implementation only,G didn't read.And i'm only violet.
Well, feedback-less problem is a good reason to make a contest unrated, but its difficulty is not.
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?
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.
In problem F, is there any way to handle the case when q is divisible by 1e9+7?
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.
What should be q^-1 mod 1e9+7 if q is divisible ? Does it exist ?
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.
Oh i see! but if p is not divisible then the answer simply doesn't exist. So i guess the problem is wrong ? :P
In reduced formP/Q, Q will never be divisible by 1e9+7.
Nice!
According to the statement, formally, that is not the answer we should output in this case.
The contest is named "Divide by zero", an evidence of the availability of that deadly corner case???
Did you ask the judges during the contest?
Cannot because q = C(f, f+w)
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
I actually asked them and they said such case will never happen.
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?
bruteforce?
i wrote a dp(number , mask) and ran it locally to get all values from 0 to 60 (took about 5 seconds to run)
I just screwed up this round but this might be the last pretest-passed submission. Cool
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?
Does somebody know what pretest 4 on problem D was?
I've looked through other participants code,but the main ideea was the same.
Should I cry now or later ?
Maybe now :)
Done :D
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?
You don't need inverse of p, do you?
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 :)
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.
Easy for you. I only managed to solve C correctly.
Is problem E's solution the same as nim problem? I saw some codes pass the pretest doing the same thing as the nim
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.
please Explain why i got TLE ?
problem B ..complexity is O((r-l) LOGN * LOG N ) ? r-l <=10e5 Here
Which is too slow. You need or better to pass.
Not really, I'm quite sure my solution is (r-l)*log(n)*loglog(n) :)
i modified it ..i used tree map to as MEMO for count Function and it ACC now
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!
any ideas, guys!!!
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
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?
I think 10000 is enough
I had the same idea, but I didn't have time to code it...
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.
@fauzdar65, thanks for your clarification.
is supposed to TLE in B?
nevermind , it fails for N = 0 case.
it has O(n) : Link
In problem C, if k is even nothing (besides sorting) in array won't be changed yes? If I'm wrong please correct me.
that's right
And if k is odd it is equal to 1 operation yes?
no
because the order of elements changes after each operation
Oh, I just forgot that, my bad :( Thanks.
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.
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.
Obviously they updated the ratings without rejudging. Contest authors these days tend to ignore comments from the community.
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.
This case is obviously different from hashing. We are talking about tests that should have been included when the problem is prepared.
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
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.
All my arguments work for contests without full feedback too.
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 HYPERHYPERHYPERCUBELOVER), there are three main reasons that we should add tests in my opinion:
I'm sorry if i wrote too long, but some of the recent contests were facing similar issues which lead me to think seriously.
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.
ok, they can do it for upsolving
But they got AC and in the long run caring about corner cases gives better places obviously.
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.
G with 978 points :(
675 pts for F here (though I got WA 9 times)
MerdanHe~~~~
Editorial Please !!
Can some one explain the logic of 3rd question?
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
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...
I didn't submit a table and got AC in ~1.0s.
http://codeforces.me/contest/768/submission/24836830
you can use the fact grundy(initial_stones)=n where {maximum value of n | n*(n+1)<=2*initial_stones}
Why did so many F's failed systests? I can't see any kind of corner case
I think it is w=0 or f=0 (if w=0 answer is 1, if f=0 answer is w > h ? 1 : 0)
Practice season please.
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
I was telling you many times — do test your code. You should have run it for n = 0 before submitting.
Sorry for the error.
min = Math.**max**(min, a[i]);
Can you explain how you tested it on the failed test case?
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?
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 :)
When can we upsolve?
[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.
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.
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.
You did the comparisons against , though. :(
Oh, I guess that's the reason. Thanks!
I also got a WA on test 19 because a precision issues, but I was comparing against instead of .
Me too! :(
I'll be very sad if that's what causes WA :( I resubmitted to add epsilon.....
[Edit] WA Case:
I got 4607 with epsilon and 4608 (correct) without it ._.
for B i used the same approach but he got ACC and i got TLE ? i use Java and he uses C++ .
c++
JAVA
THAT'S NOT FAIR ?
c++ solution uses memoization in count function
thank you very Much i didn't notice that ? how can i do the same in Java ?
use a map, if a number is already count, you can find it's count in map
yes i got ACC now .. thank yoooou very much .thank you lovely guys <3
congratulations (≧∀≦)
problem D ->
http://codeforces.me/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
please add problems to practise.
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.
AC: 24853687 Pretest Failed: 24851214
All because i forgot writing "+" in:
Probably could have grabbed that shirt for top 15 in India only if i would have realized this during contest...
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.me/contest/768/submission/24852093
Accepted code:
}
It's meaningless, because k <= 1000 by the constraint
k<=10^5
k <= 100000 by the constraint.
It's wrong.
3 2048 800
7 10 18
answer: 810 18
the code above prints: 18 7
After an hour of meditation I still cannot understand the following solution: 24828716.
Could someone, please, explain it? =)
First he's reversing the bit-pattern of 'n'.
In the final generated sequence, the i'th number corresponds to the k'th most significant bit (MSB) of input 'n' (where 'k' is the position of least significant 1 in binary representation of i).
Ex: n = 5 (101 in binary)
generated sequence 's'
s : 1 0 1 1 1 0 1
i : 1 2 3 4 5 6 7
k : 1 2 1 3 1 2 1
i to k, for i = 6: 6 = 110 in binary, the least significant 1's position (k) in 'i' is 2
similarly for i = 7, k = 1;
I have also observed all of that, but this isn't really an understanding of the algorithm :)
I'd like to know the conceptual thing. Generalization rather than the details.
My collection is complete!
What about codingame?
In C problem , i supposed that the cycle is small. But how should I prove that the length of this cycle is smaller than 100 ? :) my accepted code :
http://codeforces.me/contest/768/submission/24855247
editedWrong answer on test 41! :v
sorry , i linked other submission.. the accepted solution that i told is this new !
Someone knows why this n*log(n) solution for problem C gets AC? http://codeforces.me/contest/768/submission/24855627 Weak test cases?
Yes
Unsual time and variable limits on problem c! :|
Hey, can someone tell me: There has been several instances where using a memo table and solving a dp problem recursively has gotten me TLE while an iterative solution done extremely similar would get AC. Is there something inherently wrong or restricting with recursive dp or is it something I'm doing wrong?
Here's an example from this contest:
In contest recursive: 24838211
Out of contest iterative: 24854866
There is a noticeable difference in the in contest one as I was using binary search on the day, but I don't think that was what was getting TLE, if it was please tell me. Thank you!
In general recursive dp (with memoization) has same complexity although with a higher constant than iterative dp. That is because of function call overhead .
It's a pity I don't see my id in homepage. Hope to add top 5 in div2 to announcement. :)
I don't know why my code outputs too many answers in test case 7. Please tell me the reason! http://codeforces.me/contest/768/submission/24859236
Replace
with
because you are accessing dp[DAYMAX] in your looping
Thanks! I can get AC! http://codeforces.me/contest/768/submission/24861018
HELPPP PLEASE — Im getting CRAZY/NUTS/COCONUTS
REGARDING PROBLEM C, I submited three identical solutions but with different results wrong , right1 and right2. The only diference is the vector size (1025, 1024 and 1500 respectively). all should work since the probolem uses only the first 1024 slots.
I suppose it is somekind of undefined behaviour, can someone please help me? this is driving me crazy...
Only the 1024 version should be AC. You have a for loop:
for(int i = 0; i<v[ATUAL].size(); i++){
. If you have 1025 in your code, the last value ofi
will be 1024. Two lines later, you accessv[OUTRO][i^x]
, which will be out of bounds ifx > 1
.Did anyone get their T-Shirts? I haven't received mine yet...
Actually, the International T-Shirts are done. The Indian ones are taking time. We are trying to finish that as soon as possible. We are deeply sorry as it is taking lot more time than expected.
Thanks for informing us about it :)