Hello CodeForces Community! Chef's next contest is just around the corner and I'd like to invite you for the same, the March Lunchtime 2018. Have a helping of Chef's challenges and solve all 6 contest problems to top the charts!
I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:
- Problem Setter:mgch (Misha Chorniy)
- Problem Tester: Lewin (Lewin Gan)
- Problem Editorialist: adkroxx (Adarsh kumar)
- Problem Admin: kingofnumbers (Hasan Jaddouh)
- Statement Verifier:Xellos (Jakub Safin)
- Russian Translator: CherryTree (Sergey Kulik)
- Mandarin Translator: huzecong (Hu Zecong)
- Vietnamese Translator: VNOI Team
I hope you will have a great time solving them. Your feedback on the problem set is most welcome in the comments below after the contest.
Contest Details:
Time: 31st March 2018 (1930 hrs — 2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your [timezone]https://www.timeanddate.com/worldclock/fixedtime.html?msg=March+Lunchtime+2018&iso=20180331T1930&p1=44&ah=3.
Contest link: https://www.codechef.com/LTIME58
Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.
Prizes: * Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu.
I think this is the first time when there will be 6 problems in LunchTime.
4 problems for each division, hardest 2 in div2 is easiest 2 in div1
UPD: 5 problems in each division
Ohh...It's My bad
Codechef site down??
Works fine for me, but I can't see any problems.
Same here. Sometimes 500 internal server error. Sometimes it loads but there is no problems that can be viewed.
Is it just me or nobody is able to see the problems ?
Nobody I guess, even if the page loads it says "Please click here to reload. If problem persists, please report to [email protected]"
can't access problems , server down :(
Servers down.
What a classic codechef mess-up.
I think we all should stop reloading the page to reduce load from their servers.
Atleast change the contest time by half hour so that problems don't appear suddenly.
15 minutes have passed no responses from them :(
They replied: "We are facing some issues with our servers and hence the problems are not visible on the contest page and practice section right now. Please bear with us."
Seems like April has arrived a day early this year xD
BeautyofCodechef
Is div2 having the same problem?
It's UP
Seriously, after 40 minutes they just put it up without warning. That's ridiculous. Should've just turned it off and postponed with an hour. Was everyone expected to eagerly refresh for 40 minutes straight?
yaa
Yes, I would do the same if I only knew how the contest begins. Sorry for that. I really have no idea what's going on :(
It was considered, but somehow they already got 4-5 submissions for easier problems before the bug was completely fixed. That way, damage was done- it couldnt be kept rated. The best that could be done was to hold an unrated round later.
Contest page is not showing correct number of accepted submissions(for div 1)!
Is it showing for anyone??
"You will have to login to check the contents on March Lunchtime 2018 Division 1 contest page.
Note: This is a restricted contest. It will only be accessible to users who are provided the permission. In case of any queries, please get in touch with the contest organizer."
Massive error in judgement there :(
Should have postponed it for an hour or so. First they display the problems all of a sudden without fixing the full issue. And now it seems the contest is "restricted". At least I am not able to see the contest page anymore.
I solved 3 problems and they made the contest restricted. It would have been a good one for me. :(
Same here.
what does it mean if the contest is restricted?
Wow! Final Exam tomorrow and ruined almost one and a half hour for nothing! -_-
same problem
UPD site is down
Site offline now I guess.
They cancelled the contest https://twitter.com/codechef/status/980098492197625858
mgch: questions are still accessible on direct link of the questions, please disable it.
The submit button for 1st problem ZOZ is not visible on problem page, Is anyone also facing same issue.
In partitions problem can we solve it using randomisation. ? is there any other simpler solution for it?
I think it focuses on the fact that there are only O(n1 / 3) divisors of a number!
Nope,my idea is to iterate over all k and check if all multiples of total/k till kth multiple are present among prefix sums or not.this will take O(NlogNlogN) with naive implementation but there can some optimisations done.Though I had not submitted ,this seems good to pass because in practice it should run much faster(Yeah I am sorry.May be to analyse any better may be your fact is required).
Yeah right! My one TLE's one case and yours passes in 0.2 second!
So you coded seive way and submitted?
In both solutions I am checking for k iff its a multiple of sum. So, complexity should be O(n1 / 3) * (Accumulated work for divisors)
First solution: Its O(n) implying O(n4 / 3)
Second solution: Uses prefix sums implying better than first xD
why the complexity of Accumulated work for divisors is O(n^1/3)? i think it should be like O(sum^1/3).
Yeah right! Though its not the accumulated work for divisors. Total complexity should be sum1 / 3 * (Accumulated work).
Infact in the first term sum1 / 3 gives upper bound on all the divisors of sum but we are only considering those ones which are less than n.
UPD: Author has explained it better about bounds on this below!
I was wondering if anybody was able to solve the last question of Div 1 — Queries on Tree on their own. The editorial cited a research paper. So, I'm guessing it was not a very well known algorithm. Was anybody able to solve the problem on their own in a different way ?
where are the links for the editorials, they are not in the usual place .
Here is it: https://discuss.codechef.com/tags/ltime58/
Few words about ARRP:
I can bound teja349's solution as O(N sqrt(N) * checking) using fact about Euler's function. But it's really hard to create test against it. If it's even possible.
My solution: O(N log N + N log A)
Let's create partial sums for every prefix, i.e. S[i] = A[1] + ... + A[i]
Now, when partition for K is possible?
If exists S[n] * 1 / K, S[n] * 2 / K, .. S[n] * K / K in the set of partial sums.
What does that mean for S[n] * i / K(i = 1..K) ? It's equivalent S[n] * i / K = S[j] (for some j=1..N) <-> i / K = S[j] / S[n]. A[i] >= 1, hence all the values of S[i] / S[n] are distinct.
Let's use reverse thinking, if we know the value of X / Y(irreducible fraction) = S[i] / S[n], how to find all values of K where it will be counted? Obviously, it will be counted for values Y, 2*Y, ..., [N/Y]*Y.
So, now we have the problem with denominators of irreducible fractions. And it sounds like the next one: we have the numbers Y1, ..., YN. We need to find for every K for how many Yi(K % Yi == 0), denote it as cnt[K]. It can be done with some application of Sieve of Eratosphenes. And a partition for K is possible iff cnt[K] == K.
The complexity is N log A(finding gcd for making the fractions S[i]/S[n] irreducible) and N log N(N + N / 2 + .. + N / N) for Sieve of Eratosphenes.
Below is my code for ARRP(it's absolutely clear): https://pastebin.com/SUHJvQUt
Thank you for the link and your explanation. I'll look at it.
This was my favourite LunchTime contest so far. I really liked that there are more problems now that it's unrated.
What is your opinion about the last problem of Div 1 ? Was it an impossible problem or is it possible for people who did not read that research paper to solve it ?
Glad to hear it!!
I guess you're asking about another approach. I'm not sure in this approach, probably you can solve it with sqrt-decomposition by queries and for every sqrt(Q) queries compress the tree in O(sqrt(Q)) (nodes+LCA of them)(nodes which will be used in the next O(sqrt(Q)) queries), then you can solve it in O((Q + N) * sqrt(Q) * log(N)) but with huge constant.
Can you tell me how to solve the question Queries on Trees, for arrays ? I don't know how to solve that simpler question.
I don't know if this is the right place but can you answer this question of mine regarding the problem GQR : Link
I liked how you transformed it to a question of counting irreducible denominators.
Heyy,Thanks
Actually I dont know what I was thinking while analysing complexity.I just thought that checking was similar to sieve and thought nlogn and(logn) for checking. But after your comment I realise my analysis was wrong.But anyways it seems breaking that solution is not possible.
There is no problem :)
Tester thought that this approach has complexity O(N log N). Even me at the very beginning. It's quite confusing. The most crucial optimization is check if SUM % i == 0.