Hi all,
Programming club, Indian Institute of Technology, Mandi is hosting Dementia '18 as part of our cultural-cum-technical fest Exodia. The contest will take place on 12th April,2018 at 20:00 IST(14:30 UTC). The contest features 6 delectable problems of varying difficulty and you'll get 2.5 hours for solving them. The problem setters and testers for the contest are me(avi224) and hitesh_r. The contest is rated for division II on codechef(below 1800 rating). However, division I can participate out of competition.
There are prizes worth Rs 5K for the top participants(from both divisions) from India.
What if someone gets into division 1 after this contest? Will he participate in long as division 1? He might already have solved problems in division 2.
Fine problems :)
Can someone elaborate solution for the hardest task ? I tried binary search + several wrong greedy strategies for picking optimal plants. I believe I can solve it on a little harder way (always is optimal to water smallest plant — it can be simulated somehow). But I believe there is some easier solution.
P.S. Can you share standings for unofficial participants ?
Thanks :)
So the greedy approach would be to choose the smallest ai plants on i'th day and water them. Then you can apply binary search over days and find the ans.
There is one other approach using segment tree. The idea is to first sort the heights of tree and then keep it sorted after every day. For eg 1 1 1 2 3 3 3 3 3 5 5 5 5 are the heights on some day and you have to water 6 plants, then you go to 6th index and find value ‘h’ and find first and last occurrence of ‘h’. Then increment all the numbers before the first occurrence and some of the numbers with height same as ‘h’, as needed. So the heights will become 2 2 2 3 3 3 3 4 4 5 5 5 5. So the array is still sorted.
Editorial will be out soon which would give more clear idea about the binary search solution.
Combined ranklist will be out soon as well.
I tried to find the lower bound and upper bound of value of h using binary search and then tried to update their heights by increasing them by 1 so that I need not sort the array d times. The complexity will be O(max(nlogn,nd)).I am getting TLE. What is the intended complexity?
Still waiting for combined ranklist
This is the reply we got from CodeChef:
"The combined ranklist cannot be shown publicly now. That will take some time.
For you privately, yes, sorry for the delay. I'll remind the concerned person again to get the combined ranklist. It takes some work because this is the first time we're doing it and some DB scipt needs to be written."
I've put the link to the combined ranklist in the blog. Congrats!
This problem seems somewhat similar to the "Halum and Candies " link: (http://codeforces.net/gym/101353/attachments) the editorial page describes the solution http://codeforces.net/blog/entry/51642
when the problem is add in practice.
Problems are automatically sent to practice now after the contest. You can submit from the problem page itself :)
today it is not working. now it fixed.
When will the ratings be updated,before ending long or after it??
after long is finished.
What is the intended solution to the problem where each query is of the form [Left, Right, x]
And the answer to the query is sum( ceil(A[i]/x) ).
I'm seeing many solutions which solved the problem by just going from Left to Right and summing over ceil(A[i]/x). O(NQ)
Is this the intended solution ?
No, it was using binary search and/or merge sort tree. O(NQ) passed as we didn't expect 5*10^8 operations to pass in 1 s. The observation is that we have to count the frequency of O(sqrt(x)) numbers only for each query. I'll put a detailed editorial soon.
Can also be done using MO's algorithm + Binary Indexed Tree
Kindly elaborate Lakh and avi224. Please post the editorial link on here when it is released !
So I came in second in this contest and was going to get 1.5k . The organiser sent me 3 of such coupons -_- .
UPD : The prize money has now been transferred.
Hi Vaibhav, I am Sahil, ex-Coordinator of Programming Club at IIT Mandi. I would like to thank you for bringing into notice this issue and thank you for updating your comment. Kudos to the coordinators for resolving the issue within a day.
Also, I would like to tell you that the moment I got to know this happened, we started looking where the fault lied, and while the coordinators were busy solving your issue, I realized that the way you had done all this was EXTREMELY UNPROFESSIONAL. When you got the prizes and you were not happy with them, you should have mailed or called the respective authority rather than posting on public forums that you did not like the prize you got.
I would also like to tell you that prizes are not in our hands, but in the hands of the sponsors. They told coordinators here that they'll be giving prizes worth this much and we got these coupons from the sponsors. I fail to understand the fault of the coordinators here if you did not like the prizes.
I was in no way involved in the administration of the event, and was just a spectator as others are on codechef and codeforces, but since I know the whole story which you did not post, I can confidently say that the coordinators did a great job, and that because of your unprofessionalism the community here has received some undeserved flak. I would request you to kindly get to the issue first and behave more professionally from next time.
You are talking about unprofessionalism, nobody contacted me informing about the prize even when I had filled the google form. I personally had to contact the organiser on facebook regarding the prizes. He told me the prizes will be transferred by Sunday but there was still no mail/sign by Sunday.
When I messaged him again he told me that a guy named Naveen will contact me. So the guy calls me asks for my mail at 10 PM, I tell him the mail, he says he sending the mail immediately. I am anticipating a mail but the guy sends me the mail at 4 AM in the morning which contained these coupons.
And you say the prizes were directly transferred from the sponsors as coupons. Then, please-o-please tell me how the hell did the prize change from these worthless coupons to cash prize money immediately after I posted these on codeforces and codechef. I don't think the sponsors for the event changed overnight.
Checkout the "PROFESSIONAL" problem-setting done by the team in the later comment.
Hi again Vaibhav, Thanks for letting me know your point of story. Indeed someone here is at fault and I would have been extremely upset as you are on these prizes.
I would, however, like to point out that the prizes were truely not in the hands of the coordinators. You are correct that timely delivery of prizes is an important factor of an event, I also apologize for this.
However, a post on these public platforms stating that a particular college duped you of the prizes is extremely demeaning to each and every student of that college. This was the first rated contest from IIT Mandi, and a lot of students had put up a great deal of effort in this. Also, even the teams handling the organization and prizes was different. There was indeed lack of communication between the teams, however, only because the prizes were not upto one's expectations is not a great reason to write such a post criticizing an entire community, when a simple email could have probably worked.
I would also like to bring to your notice that the cash prize you received later were given from the pockets of the coordinator handling the event prizes, not from any sponsor.
This was not a great incident indeed, and the biggest lesson people here have got is to ensure better sponsors from next year. I would also like to make it clear that nobody here has any intentions to dupe anyone of the prizes, and I hope you understand that it was these complex situations which lead to this unfortunate series of events. At last again, apologies for what happened with you. Hope this makes sense.
I know it portrayed your college in a bad light. That is why I deleted the post and edited the comment after receiving the prize.
But you are calling me unprofessional, whereas I have explained how the team at your college handled the event unprofessionally.
I was not going to bring this up but now that you are making UNPROFESSIONALISM an issue, the hardest problem for the contest is same as this one.
Problem from csacademy
I just changed one line of my accepted code for the problem and submitted and got accepted. So it seems like a notorious coincidence to me.
That's professional enough for you?
PS : It's okay not to have prize money in your contests. If they are interesting, people will participate.