We’re halfway through the year and its time for our sixth Long Challenge of the year 2020. We invite you to participate in CodeChef’s June Long Challenge, this Friday, 5th June, 15:00 IST onwards The contest will be open for 10 days i.e. until 15th June.
Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.
Joining me on the problem setting panel are: - Setters: Sahil sahi1422 Chimnani , Naman smartnj Jain , Vikas _wildfire_ Pandey , Vinit Vitz Solanki , Taranpreet taran_1407 Singh, Raja raja1999 Vardhan Reddy , Sofiia Sonechko Melnyk , Ildar 300iq Gainullin , Arthur arthur.nascimento Nascimento
Admin : Teja teja349 Vardhan Reddy
Tester: Felipe fmota Mota
Editorialist & Post-Contest Streaming: Rajarshi RestingRajarshi Basu
Statement Verifier: Jakub Xellos Safin
Mandarin Translator: Hanlin Ioser Ren
Vietnamese Translator: Team VNOI
Russian Translator: Fedor Mediocrity Korobeinikov
Bengali Translator: Mohammad solaimanope Solaiman
Hindi Translator: Akash Shrivastava
Prizes
Top 20 performers in the Indian category and top 10 performers in the Global category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. First to solve each problem except challenge — 100 laddus. Know more here
Good Luck!
Hope to see you participating!!
Happy Programming !!
Contest starts in 10 minutes!
I hope that the problems are tasty!
User hehaodele, currently in rank 8, solved the problem PPARTS by asking in the CF forum in the last 5 hours, pretending it is the problem he came up with. Now the article is deleted, but there is already some witness (Um_nik). Please investigate and disqualify him.
I am a witness too. Um_nik answered the question saying that he learned it 4 days ago.
https://codeforces.com/blog/entry/61306?#comment-452948
This appeared in previous contest and a well known combinatorics problem.
https://www.codechef.com/PCO12020/problems/HELCARP
Nice fake account lmao. Doesn't matter if it appeared before, cheatin's cheatin'
Wow not supporting anyone,but might be genuine mistake of this guy, as I solved this question and I too was curious how to optimise the solution, I didn't knew until it is long challenge question. Because, if someone wanted to cheat then he/she would have used fake account instead of original.Just a possibility wanna share.
Thanks, will escalate it.
Thanks for reporting! We have removed the user from the ranklist, and blocked their account on CodeChef. We'll update here if they provide any reasonable explanation for what's happened.
Are you going to block all those users who witnessed this/got AC after that blog?
Don't let things change your good character. Stop participating in these plagiarized challenges.
PS: CodeChef_admin Remove these ridiculous longs and start some Dinner/Break-Fast, post editorials at the right time.
Noone asked a cheater for advice.
So you think I am hehaodele xD,
There exists many who hate Codechef Longs & its braggers in discuss
You admitted you are cheating.
I never said you are hehaodele you only bought this here.
You can do a lot of productive things other than opening discuss.
Looking at you comments your reason for hating it is cheating which you are encouraging. You can simply stop participating in long. Codechef_admin is not coming to your house and forcing you to participate.
You can simply stop participating in long.
I did that mistake once. Never participated thereafter. BTW Thanks for the advice.
I can confirm that roughly 10 hours ago I answered a question by hehaodele and my answer can be used as a solution to PPARTS.
Now that the contest is over can you tell your solution?
I solved it by applying the xDln operator on the question which converted it into a simpler form.
https://judge.yosupo.jp/problem/sharp_p_subset_sum
You can watch submissions there.
In short:
We want first $$$n$$$ coefficients of $$$Q(x) = \prod_{k=1}^{n} (1 + x^{k})^{c_k}$$$
Let's define $$$P(x) = \ln Q(x) = \sum_{k=1}^{n} c_k \ln (1 + x^k)$$$
$$$\ln (1 + x) = \sum_{i=1}^{\infty} \frac{(-1)^{i + 1} x^{i}}{i}$$$
$$$P(x) = \sum_{k=1}^{n} \sum_{i=1}^{n/k} \frac{(-1)^{i+1} x^{ik}}{i}$$$
We can calculate $$$P(x)$$$ in $$$O(n \log n)$$$ since there $$$O(n \log n)$$$ summands. Then $$$Q(x) = \exp P(x)$$$ which can be calculated in $$$O(n \log n)$$$.
Yeah thanks, I did almost exactly that but I took the derivative of $$$ln(1+x^k)$$$. And integrated it to get the same result you got.
math.stackexchange link Here, there is a method of nth derivative of generating function, can we somehow apply the same method here,if we just want to Calculate for sum a_i * b_i =n, is it possible?
Did anyone manage to fit $$$O(nlog^2n)$$$ in TL for DIFVAL? i.e without the dsu on tree approach.
I tried segtree on dfs time array where each node is a persistent segtree, and ended up having to create 7e7 nodes per case. Was unable fit it in TL. :(
I used Sack (DSU on Tree) along with a persistent segtree to do it in Nlog²N.
It ran in first attempt but I had done a few optimizations. Like adding the light subtrees by BFS instead of DFS (this is helpful because it guarantees minimum number of operations), also instead of removing elements from the segtree, I just applied the updates on the blank segtree (I can do this because it's persistent).
Apart from this, my segtree was persistent as well as Dynamic.
Here's the link to the solution: https://www.codechef.com/viewsolution/34062043
CodeChef_admin Hey I think its the time to either reduce the duration of long challenge maybe to 2 or 3 days or stop conducting long challenge. Instead come with something like Dinner, Breakfast, Snacks or something else. I find two reason for this
Plagiarism (that usually remain undetected as person change the name of variable ,use different templates etc)
Long challenge sounds odd one out from Lunchtime and Cook-off, so contest like Snacks , Dinner, Break-Fast will sound far more logical.
We all know that these absolutely logical words will have no effect whatsoever. It's so sad to see Codechef this way. :facepalm:
Top 20 performers in Indian category would mean top 20 in div1, or is top 10 from each division.
My name is on 19th in the following list : https://www.codechef.com/rankings/JUNE20A?filterBy=Country%3DIndia&order=asc&sortBy=rank (filter :India, sort : ASC).
Am I eligible for any laddus(assuming ranklist is unaffected after MOSS)? If yes then how many.
Thanks!
But how codechef determine someone is Indian or not because one can change his/her location to India just to get free laddus (in case he is not in top 20 in global but is in top 20 Indians)
Yes I also thought of this possibility, I'm unaware of how codechef chooses top 20 indians.