Hi all!
Programming Club, IIT Mandi and ACM Student Chapter, IIT Mandi are organizing Dementia 2020, our annual programming contest on 13th August, 8:30 pm — 11 pm IST.
The contest features 5 problems of varying difficulty and contest duration is 2 hours and 30 minutes. The contest is rated for Division 2 on CodeChef (<1800 rating). However, Division 1 can participate out of competition (4* and 5* users especially, should find some problems interesting).
The problem setters for the contest are lane, dhr_1, rtanmay, _-Noob-_ and swapnilr.
We would like to thank jtnydv25 for being the round coordinator on behalf of CodeChef and suggesting a major improvement to one of the problems and l_returns for testing the problems and catching issues that slipped our internal testing, taran_1407 for an initial review of the problem ideas, as well as the rest of the CodeChef team for managing other logistics of the contest.
Good luck and have fun!
UPD: The author's solution for HELPHAND was pointed out to be incorrect and since this affects a lot of users, the contest will be unrated. We hope you find the other problems good for learning purposes. We apologize for the mistake. Editorials are being added on CodeChef Discuss.
Correction- In Codechef Contest page, its written "Rated for all". Link
Resolved.
If 4-stars will find the problemset interesting then why not make it rated for them. Like codeforces has div 2/educational rounds rated upto 2100 even though people above 1900 are officially in div 1.
CodeChef and Codeforces both do not support custom rating bounds (for good reasons). Codeforces just places Candidate Masters in both divisions — but you are not given a choice there either, you can't set a Div 2 only round where only upto Experts are rated.
What if someone gets to division 1 after giving your round. Will he be continuing giving long in division 2?
Yes, the person would belong in division 1 from next challenges.
For the current Long he will keep continuing participating in DIV2 all rating updates will be simultaneous as LONG Ends as per the rules and policies of Codechef.
I forgot the name of the round .
swapnilr Anything special for our college participants?
Reminder: contest starts in 5 hours. Hope to see you in the standings!
Will there be a separate Ranklist for div1?
Unfortunately, during the contest, only Div. 2 contestants will be visible in the standings. However, once the contest is over, the combined Div1+2 ranklist will definitely be provided (this is managed by CodeChef, and I think we would need to wait for MOSS to be applied before releasing the ranklist).
DCOD2019 had separate ranklists. Why not this time?
That was a separate contest for each division, like how Cook-Offs, Lunchtimes, Long challenges are organized. Think of this one more like a Div2 only round like the ones on Codeforces, but it's hosted on CodeChef, so there is no "show unofficial" option to view yourself in the ranklist.
There should be some more contests in CodeChef that should be rated for all.
That where unexpected difficult problems.
Pretty tough contest....can someone explain the solution of "Helping Hands" problem
Every prime counts as 2, every other number as 1.
Precalculate the number of distinct primes till a number for each number from 1 to 1e6. This can be done by applying sieve and doing prefix sum.
For a number n let this number be p, then to create the final lcm for 1 to n we will require p-1 moves where we take the highest power of each prime at each step at the end we will have 2 numbers(the numbers involved in the last operation) which will attain the required value. For the remaining n-2 numbers we can take their lcm with any of the above 2 numbers therefore we will only need 1 move for each of the remaining n-2 numbers.
Final formula: p-1+n-2 (for n>2)
I missed the cases with n=2 and n=1, now I feel so stupid...
Same is the case with me.I missed n=2 :(
First, you need to get a pair of numbers equal to LCM(1,2,...,n) then it will take 1 operation for each of the n-2 remaining numbers. To do this, we will perform the operation on biggest powers of primes <= n. There is one such power for each prime, so we can count this using sieve. Ok, now say there x such powers. Answer = solve(x) + n-2, treat very small cases separately because they are weird. You can compute solve(x) with DP. Base cases are solve(0)=solve(1)=0 and the recurrence is solve(x) = solve((x+1)/2) + solve(x/2) + 1 we split set of powers in half and use 1 extra operation to combine them at the end.
We hope you found at least some of the problems interesting.
Problem authors-
MINMXSTR — swapnilr (with suggestion by Jatin Yadav (contest coordinator from CodeChef) to increase constraints and make the problem interesting instead of O(N*Q))
TOWIN — rtanmay
SPPSTR — lane
BEACIRC — _-Noob-_
HELPHAND — dhr_1
Will there be any editorial?
Yes, these are the solution outlines — full editorial will be released soon.
https://docs.google.com/document/d/1nO516f8O-g--9fVvCMDAKarH5ClrQoPCLbhKe_4IjDQ/edit?usp=drivesdk
I don't know why I was getting WA in beautiful circles.I did the same thing as in editorial. Can anyone help me in it.Here is the link of the solution https://www.codechef.com/viewsolution/36691768
UPD:Got the mistake.
Great contest! What is the expected time complexity for the question of intersecting circles My n^2*log(n) solution is getting TLE! Can anyone point out as to why that is happening? Link to my submission- https://www.codechef.com/viewsolution/36692585
I think in worst case your program will reach O(n^3).
Yes, but in the worst case, wouldn't the answer be n(n-1)(n-2)/6? So, you would have to iterate over all possible triplets..? (Haven't seen the tutorial)
No.
We don't have to iterate all the triplets. Here is my approach. Iterate over all pairs of circles. Circle passing through intersection of C1 and C2 will have equation C1+kC2=0.Also there is one more condition,the circle passes through the centres of C1 and C2.So when you put the points in the above equation and do some maths and then compare the k values obtained you will get dist(c1,c2)=r1^2 + r2^2 where c1,c2 are centre coordinates. So the problem reduces to finding all pairs of circles satisfying the above condition. Now you can find the centre of circle as (c1+c2)/2 and radius as dist(c1,c2)/2.So you just have to find how many such circles are there which can be done using map.
[Update]
I got the answer. please ignore it.
[DELETED]
Looks like your issue was the increasing size of map and that was leading to TLE.
Thank you for the contest, problems are nice and I think MINMXSTR is very interesting.
Are tests weak for A ? Like this solution will fail at this case :
Your general idea for n!=2 is correct — if it was incorrect, you wouldn't have got AC.
Apart from obvious n=1 and n=10^4, we can't make testcases for arbitrary n. I wouldn't call the testcases weak, especially on a cakewalk problem.
My solution to beautiful circles, its quite need and easy to understand just in case somebody needs a reference
Hi. My ratings on codechef have not been updated,is it because it was my first codechef contest?
It will be updated after august long challenge over.
so, rating will be updated according to current rating?
This was a disaster for me , i read that string problem which was solved by only four (thought it was easy) . And thought i can do it. But after wasting more than half time ,i got tle. Solved the easiest in last half hour .
Is the contest still rated? As Helping Hand problem had a wrong test case.
No, it's unrated, read the update in this announcement.
Problem editorials have been uploaded. Here are the links-
https://discuss.codechef.com/t/towin-editorial-dementia/74776
https://discuss.codechef.com/t/minmxstr-editorial/74612/
https://discuss.codechef.com/t/beacirc-dementia/74610
https://discuss.codechef.com/t/sppstr-editorial/74638
Problem HELPHAND was found to be incorrect, so no editorial for that.