### swapnilr's blog

By swapnilr, 6 weeks ago,

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 smit_mandavia 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.

• +74

 » 6 weeks ago, # |   +10 Correction- In Codechef Contest page, its written "Rated for all". Link
•  » » 6 weeks ago, # ^ |   +6 Resolved.
 » 6 weeks ago, # |   0 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.
•  » » 6 weeks ago, # ^ |   +9 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.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   -13 6 star king is back take care all
 » 6 weeks ago, # |   +3 What if someone gets to division 1 after giving your round. Will he be continuing giving long in division 2?
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Yes, the person would belong in division 1 from next challenges.
•  » » 6 weeks ago, # ^ |   +3 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.
•  » » » 6 weeks ago, # ^ |   0 Ok that clears everything
 » 6 weeks ago, # |   -18 my favorite codechef
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 deleted..!
 » 6 weeks ago, # |   +22 I forgot the name of the round .
 » 6 weeks ago, # |   +1 swapnilr Anything special for our college participants?
 » 5 weeks ago, # |   +3 Reminder: contest starts in 5 hours. Hope to see you in the standings!
 » 5 weeks ago, # |   0 Will there be a separate Ranklist for div1?
•  » » 5 weeks ago, # ^ |   +5 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).
•  » » » 5 weeks ago, # ^ |   +5 DCOD2019 had separate ranklists. Why not this time?
•  » » » » 5 weeks ago, # ^ |   0 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.
•  » » » » » 5 weeks ago, # ^ |   0 when the rating updated?
 » 5 weeks ago, # |   +8 There should be some more contests in CodeChef that should be rated for all.
 » 5 weeks ago, # |   0 expecting some graph theory problems....
 » 5 weeks ago, # |   +12 That where unexpected difficult problems.
 » 5 weeks ago, # |   0 Pretty tough contest....can someone explain the solution of "Helping Hands" problem
•  » » 5 weeks ago, # ^ |   +2 Every prime counts as 2, every other number as 1.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +10 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)
•  » » » 5 weeks ago, # ^ |   +3 I missed the cases with n=2 and n=1, now I feel so stupid...
•  » » » » 5 weeks ago, # ^ |   +1 Same is the case with me.I missed n=2 :(
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Awesome....thanks yash_daga
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Hey yash_daga was you able to do C(Beautiful Circles)?
•  » » » 5 weeks ago, # ^ |   0 can you please explain how we get the highest power of each prime in p-1 moves?
•  » » 5 weeks ago, # ^ |   +3 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.
 » 5 weeks ago, # | ← Rev. 4 →   +6 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 — rtanmaySPPSTR — laneBEACIRC — _-Noob-_HELPHAND — dhr_1
 » 5 weeks ago, # |   0 Will there be any editorial?
•  » » 5 weeks ago, # ^ |   +3 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
 » 5 weeks ago, # | ← Rev. 3 →   0 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/36691768UPD:Got the mistake.
 » 5 weeks ago, # |   0 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
•  » » 5 weeks ago, # ^ |   0 I think in worst case your program will reach O(n^3).
•  » » » 5 weeks ago, # ^ |   0 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)
•  » » » » 5 weeks ago, # ^ |   0 No.
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +12 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.
• »
»
»
»
»
5 weeks ago, # ^ |
Rev. 3   0

#### [Update]

###### [DELETED]
•  » » » » » » 5 weeks ago, # ^ |   0 Looks like your issue was the increasing size of map and that was leading to TLE.
 » 5 weeks ago, # |   +8 Thank you for the contest, problems are nice and I think MINMXSTR is very interesting.
 » 5 weeks ago, # |   0 Are tests weak for A ? Like this solution will fail at this case : 1 2 5 10 
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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.
 » 5 weeks ago, # | ← Rev. 2 →   0 i was doing the same in Beautoful Circles as mentioned in solutions outlines but i don't know what went wrong and i started thinking that this method is wrong............shit i would've tried ............so its ok......overall contest was good problem A and B were amazing and rest is history...........However why is difficulty not balanced as you can see problem C was way harder than problem B. there is a huge hike in difficluty after B.
 » 5 weeks ago, # |   0 My solution to beautiful circles, its quite need and easy to understand just in case somebody needs a reference AC_CODE#include using namespace std; #define int long long #define ar array #define pb push_back #define vi vector #define FOR(i,j,n) for(int i=j;i a,arb){ return (a[0]-b[0])*(a[0]-b[0])+(a[1]-b[1])*(a[1]-b[1]); } bool ok(ara,arb){ return d(a,b)==a[2]*a[2]+b[2]*b[2] ; } void solve(){ int n ;cin >> n ; vi>a(n) ; FOR(i,0,n) FOR(j,0,3) cin >> a[i][j],a[i][j]*=2; map,int >mp ; for(ar x:a) mp[x]++ ; set>s(all(a));a.clear() ; for(ar x:s) a.pb(x); n= a.size();int ans =0; FOR(i,0,n){ FOR(j,i+1,n){ int di=d(a[i],a[j]),cd=sqrt(d(a[i],a[j])); if(!ok(a[i],a[j])||di^(cd*cd)) continue ; arck ={(a[i][0]+a[j][0])/2,(a[i][1]+a[j][1])/2,cd/2}; ans+=mp[a[i]]*mp[a[j]]*mp[ck] ; } } cout << ans << "\n" ; } signed main() { int t ;cin >> t ; while(t--) solve() ; } 
 » 5 weeks ago, # |   0 Hi. My ratings on codechef have not been updated,is it because it was my first codechef contest?
•  » » 5 weeks ago, # ^ |   0 It will be updated after august long challenge over.
•  » » » 5 weeks ago, # ^ |   0 so, rating will be updated according to current rating?
 » 5 weeks ago, # |   +1 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 .
•  » » 5 weeks ago, # ^ |   0 It was my first short contest on codechef i did the same mistake i read minmax string problem for 20-25 min as it was on top when contest started i wasn't able to do it then i saw dashboard and i was like fu*k then i fastly solve problem to win and help hands which lead me under 70
 » 5 weeks ago, # |   0 Is the contest still rated? As Helping Hand problem had a wrong test case.
•  » » 5 weeks ago, # ^ |   0 No, it's unrated, read the update in this announcement.
 » 5 weeks ago, # | ← Rev. 4 →   0 Problem editorials have been uploaded. Here are the links-Problem HELPHAND was found to be incorrect, so no editorial for that.