Hi everybody!
I invite you to participate in the CodeChef September Mega Cook-Off at https://www.codechef.com/COOK62. The problemset of the contest is prepared by me.
I hope you will like the problems: some of them require outstanding algorithmic thinking, some of them require brilliant coding skills — anyway, I'm pretty sure, that no one will get bored during the contest. ;)
Time: 20th September 2015 (21:30 hrs) to 21st September 2015 (00:00 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.
Details: https://www.codechef.com/COOK62
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.
The contest was prepared not only by me, but also by these amazing guys:
- Tester: Jingbo Shang(shangjingbo)
- Editorialist: Lalit Kundu(darkshadows)
- Contest Administrator: Praveen Dhinwa(PraveenDhinwa)
- Mandarin Translator: Gedi Zheng(gediiiiiii)
- Russian Translator: Vasia Antoniuk(Antoniuk)
- Vietnamese Translators: VNOI Team
- Language Verifier: Rahul Arora(rarora7777)
Prizes:
Top 10 performers in Global and Indian category will win a cool CodeChef T-shirt. (For those who have not yet got their previous winning, please send an email to [email protected])
Top 75 Indian performers will be provided with a reimbursement (for travel and registration) of upto INR 1500 for ACM ICPC 2015 regionals.
Good luck! See you on Sunday!
Note from contest admin:
Before we invite you to take part in this Cook-Off, let us take this opportunity on behalf of the engineering team at CodeChef, for the terrible experience that you had to go through at the last Cook-Off, which got unrated. And while we do this, we are completely aware of the fact that we have been making too many mistakes when it comes to Cook-Off and our apologies have also been on the rise. However, we have fixed a few things between then and now. And we are very hopeful that the same experience will not be repeated. Among many things that we have fixed, one major change will be the contest environment. We will be launching a much lighter version of the contest environment tonight. We hope you get a much better experience from now on. However, if there are any issues that you face in this environment, we request you to report them to us and we will fix them all.
UPD:
The contest starts in 30 minutes!
It was a really disappointing experience in the last round. I also don't think most people will participate as your time almost clashes with the next codeforces round which is 30mins after the start of the codechef round.
I don't know for others but it's definitely going to be a codeforces round for me come sunday
I think Indian college students will participate in codechef. Hope they don't get messed up this time!!
Yeah just read that it's an ACM-related cook off. So i guess it would help with those preparing for the upcoming regionals.
I think it clashes with the next codeforces round.Isn't it possible to change the schedule?
I still don't get it, why TOP 75 INDIAN PERFORMERS will be provided with a reimbursement for ACM ICPC 2015. ICPC is a contest for college students only(as the name suggests), so they should give the reimbursement to TOP 75 COLLEGE STUDENTS(Indians obviously) not indian performers.
Thats true. The reimbursement will be to top 75 Indian students who will reach the onsite regionals.
First weekend contest in nearly a month, and it gets moved back. Aw man..
Auto comment: topic has been updated by kostya_by (previous revision, new revision, compare).
Gentle reminder !! Contest starts under 5 minutes.
Объясните прекол нубу
There's no joke here, people do not like cactuses. http://codeforces.com/blog/entry/10161?#comment-156229
Could somebody give me an idea of how to approach "Super Numbers"?
φ(p1e1... pkek) = p1e1 - 1(p1 - 1)... pkek - 1(pk - 1).
Since we want phi divide n, we can cross out all piei - 1. That is, prime powers do not matter. So we need numbers n = p1e1... pkek such that (p1 - 1)... (pk - 1)|p1... pk.
First note that n should be even (except n = 1), since φ(n) is even for n > 2. Then (p1 - 1)... (pk - 1)|2p1... pk, since (2-1) does not bother us in the left side. This is only possible if some (pi - 1) = 2, that is pi = 3 and no other primes are present.
So we simply need to count numbers of the form 2e23e3, e2 ≥ 1, e3 ≥ 0. (count number 1 as special case). We can count by iterating over all e2 ≤ 59 and e3 ≤ 37.
Write a bruteforce for finding such numbers. Look at the first few. Do you see a pattern? :D
Something strange with penalty times in ranklist: if you add them, the result you get is less than total time shown by (16 minutes) times (number of wrong attempts). And one of Fdg's times is 02:47:54, so penalty time for each problem already counts wrong attempts; anyway, it doesn't add up.
Very good contest... I had big problems with fourth task, but I managed to solve it 3 minutes before end of contest.
About tasks, personally I don't like the first task ( he is simply implementation), other tasks was very interesting for me.
I didn't like third task,I didn't manage to solve it and from what somebody told me,is just observation...Every super number is made just out of prime factors 2 and 3.
Fourth task was nice and the first two implementation.
Also I like the fourth task at most. Very nice, easy idea with DP, but I had to spend a lot of time to solve it :)
The second and third task wasn't something spectacular, but they were new for me.
Thanks for the nice contest! I expected the problems to be a bit tougher and a simple DP solution for the fourth problem (Reigns2) was a little surprise for me.
PS: didn't have enough time to look at Counting Subgraphs, seems it was a hard one.
Thanks for your solution for the third problem :) I understood it very clearly.
Also it seems to me that last year mega cook-offs were more interesting,like september 2014. But maybe the next cook-off will be better.
I'm glad that the site works smoothly, I can put my whole attention on problems from now on.
Do you have a proof why DP gives desired answer? I fail To prove that dp is what we need.
Firsly I looked how to minimize the cost for k chosen cities.Of course,you sort them in decreasing order by B[i](cuz a[i] surely will be added and it doesn't matter).
So if you choose k cities randomly and this is the best answer for a fixed k, you'd better sort firstly the whole array decreasingly by b[i],because surely you will choose the same configuration and it's easier to calculate the cost.
Also for adding city i as j-th city(now being the last of them),the cost is fixed a[i]+(j-1)*b[i], so you want to minimize the cost of choosing j-1 cities from i-1 positions. This gives us the clue that we should maintain a min DP.
What is the intended complexity for SUBGRAPH? My solution is O(N * K2 * L) and it barely passes the TL.
How to solve this problem?
Until now there is no Tutorial in CodeChef.
https://discuss.codechef.com/questions/75320/subgraph-editorial
Added the editorial. :)
Neither tester nor author source codes are available for this problem. Could you kindly fix it?
I already have asked admins to fix it. I'll ping them again.
Anyway, testers: http://paste.ubuntu.com/12615547/
setters: http://paste.ubuntu.com/12615574/