Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### Cache's blog

By Cache, history, 4 weeks ago, ,

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 Cache Vardhan Reddy

• Tester: Felipe fmota Mota

• Editorialist & Post-Contest Streaming: Rajarshi RestingRajarshi Basu

• Statement Verifier: Jakub Xellos Safin

• Mandarin Translator: Hanlin I_love_PHP Ren

• Vietnamese Translator: Team VNOI

• Russian Translator: Fedor Fedosik 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 !!

• +119

 » 4 weeks ago, # |   +9 Contest starts in 10 minutes!
 » 4 weeks ago, # | ← Rev. 2 →   -8 I hope that the problems are tasty!
 » 3 weeks ago, # |   +75 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.
•  » » 3 weeks ago, # ^ |   +36 I am a witness too. Um_nik answered the question saying that he learned it 4 days ago.
•  » » » 3 weeks ago, # ^ |   -38 https://codeforces.com/blog/entry/61306?#comment-452948This appeared in previous contest and a well known combinatorics problem.https://www.codechef.com/PCO12020/problems/HELCARP
•  » » » » 3 weeks ago, # ^ |   +10 Nice fake account lmao. Doesn't matter if it appeared before, cheatin's cheatin'
•  » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   -23 cheatin's cheatin' Agreed
•  » » » » » 3 weeks ago, # ^ |   -24 Nice fake account lmao. Thanks.
•  » » » » 3 weeks ago, # ^ |   +5 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.
•  » » 3 weeks ago, # ^ |   +38 Thanks, will escalate it.
•  » » 3 weeks ago, # ^ |   -44 Still participating in long-plagiarized-contests?
•  » » 3 weeks ago, # ^ |   +21 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.
•  » » » 3 weeks ago, # ^ | ← Rev. 3 →   -57 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.
•  » » » » 3 weeks ago, # ^ |   -30 CodeChef_admin Remove these ridiculous longs Noone asked a cheater for advice.
•  » » » » » 3 weeks ago, # ^ |   -28 So you think I am hehaodele xD, There exists many who hate Codechef Longs & its braggers in discuss
•  » » » » » » 3 weeks ago, # ^ |   -16 You admitted you are cheating.I never said you are hehaodele you only bought this here. its braggers in discuss You can do a lot of productive things other than opening discuss. There exists many who hate Codechef Longs 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.
•  » » » » » » » 3 weeks ago, # ^ |   +23 You can simply stop participating in long.I did that mistake once. Never participated thereafter. BTW Thanks for the advice.
•  » » 3 weeks ago, # ^ |   +86 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.
•  » » » 2 weeks ago, # ^ |   +6 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.
•  » » » » 2 weeks ago, # ^ |   +29 https://judge.yosupo.jp/problem/sharp_p_subset_sumYou 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)$.
•  » » » » » 2 weeks ago, # ^ |   +3 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.
•  » » » » » 2 weeks ago, # ^ | ← Rev. 2 →   +2 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?
 » 2 weeks ago, # |   +19 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. :(
•  » » 2 weeks ago, # ^ |   +5 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
 » 2 weeks ago, # |   +49 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.
•  » » 2 weeks ago, # ^ |   -21 reduce the duration of long challenge maybe to 2 or 3 days or stop conducting long challenge.We all know that these absolutely logical words will have no effect whatsoever. It's so sad to see Codechef this way. :facepalm:
 » 2 weeks ago, # |   +4 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!
•  » » 2 weeks ago, # ^ |   0 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)
•  » » » 2 weeks ago, # ^ |   0 Yes I also thought of this possibility, I'm unaware of how codechef chooses top 20 indians.