### Kerim.K's blog

By Kerim.K, history, 12 months ago,

Greetings Codeforces Community!

We invite you to participate in the CodeChef November Lunchtime — the 3-hour contest which offers 5 challenging problems to be solved. This will be a chance for you to code and show off your programming skills along with increasing your CodeChef rating.

The problem statements of the contest will be available in English, Hindi, Bengali, Russian, Mandarin, and Vietnamese. Also if you have some original and engaging problem ideas, and you’re interested in them being used in the CodeChef's contests, you can share them here: www.codechef.com/problemsetting/new-ideas

I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:

• Setters: Kerim.K (Kerim Kochekov), kingofnumbers (Hasan Jaddouh)

• Editorialist: Deadwing (Hussain Kara Fallah)

• Tester: KMAASZRAA (Kasra Mazaheri)

• Statement Verifier: Xellos (Jakub Safin)

• Mandarin Translator: gediiiiiii (Gedi Zheng)

• Vietnamese Translator: Team VNOI

• Russian Translator: Fedosik (Fedor Korobeinikov)

• Bengali Translator: solaimanope (Mohammad Solaiman)

• Hindi Translator: Akash Shrivastava

#### Contest Details:

• Start Date & Time: 30th November 2019 (1930 hrs) to 30th November 2019 (2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.
• 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 Indian and top 10 Global school students from ranklist will receive certificates and CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here.

Good Luck!
Hope to see you participating!!
Happy Programming!!

• +102

 » 12 months ago, # | ← Rev. 2 →   +18 one of the best cc contests in 2019 whats the solution of PLANT(full) and SRVR(both full and partial)
•  » » 12 months ago, # ^ |   +20 ServersIgnore the exclusive processing for now.If a task has d > p, obviously it won't fit this server.If we have tasks, all of with d <= p, it turns out we can fit it on this server as long as sum of d <= c*p. ProofFill the first row from left to right, then the second row, then the third, and so on.If we have exclusive processing, obviously we'll use it on the task with the largest d.Sort all tasks in non-decreasing d. Run knapsack for the tasks in this order.For a server, we iterate over the task which will have the largest d in the subset. Then, we use our precomputed knapsack to find the number of subsets given the largest d.Make sure to not use any modulo operations!https://www.codechef.com/viewsolution/28021269
•  » » 12 months ago, # ^ |   +59 Team TreesLet (i, j, l) be a triple such that the substrings with length l starting at i and j are equal and i+l <= j. Note that the answer for (i, j, l) is l*max(j, n-i-l).If (i, j, l+1) works then the answer will always be better than (i, j, l). ProofSince (i, j, l+1) works, i+l+1 <= j, j+l+1 <= n, i+2l+2 <= n, l+1 <= n-i-l-1.(a+1)*(b-1) > a*b when a+1 <= b-1, so (l+1)*(n-i-l-1) > l*(n-i-l).Also, (l+1)*j > l*j, so (l+1)*max(j, n-i-l-1) > l*max(j, n-i-l).Find suffix and lcp array first, then iterate over l from n to 1. For each i such that lcp[i] = l, merge the suffix with rank i and the suffix with rank i+1 in a dsu that maintains the minimum and maximum in a component. For all components that were merged, the suffixes in a component all share a prefix of length l, so we calculate the answer for (min, max, l), decreasing l to max-min if necessary. Note that it is optimal to choose i = min and j = max based on the formula.Finally, copy some O(n) suffix array implementation to get AC.https://www.codechef.com/viewsolution/28014811
 » 12 months ago, # |   +61 Why does "Servers" require constant optimizations? O(400^3) seems more reasonable than O(600^3).And why fail O(nlogn) suffix algorithms for "Team Trees"?
•  » » 12 months ago, # ^ |   +52 The constraints are indeed larger than usual, but there was no need for any constant optimizations. My solution runs around 2 seconds without any optimizations other than reducing the size of the knapsack array. Even uwi's java solution runs in 3.3 seconds out of the given 8 seconds.The intended solution for "Team Trees" is $O(N \times log(N))$ and from a few solutions I saw, most were indeed suffix array plus some sort of counting sort.
•  » » » 12 months ago, # ^ |   -57 Tbh should I ask one question? SpoilerHow much time problem setting panel of ltime devote to prepare a complete contest?Every now and then I find a reason to hate ltime and some of your mistakes just show how much underprepared you were in creating the contest.
 » 12 months ago, # |   +37 From https://www.codechef.com/problemsetting , "Intended towards the school students. The syllabus is strictly restricted to IOI." : which syllabus are you referring to? The official syllabus clearly excludes suffix automation and other string algorithms.
•  » » 12 months ago, # ^ |   0 Yeah, it turns out making hard problems (that challenge even the top people competing there) within the IOI syllabus is extremely tough and if you have such problems, it's better to just propose them for IOI. Combine that with not having enough problemsetters. That restriction isn't followed.