Hello CodeForces Community! We are thrilled to invite you to participate in the August Long Challenge 2018 sponsored by ShareChat. In addition, there are some exciting internship and full-time job opportunities by ShareChat for Indian programmers in the August Long Challenge 2018. For more details, you may visit the contest page.
I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:
Problem Tester: AllCatsAreBeautiful (Mark Mikhno)
Problem Authors: likecs (Bhuvnesh Jain), vidyut_7 (Ashesh Vidyut), step_by_step (Stepan Filippov), pieguy (David Stolp), allllekssssa (Aleksa Plavsic), bciobanu (Bogdan Ciobanu), mraron (Aron Noszaly), Sheoran_Jitu (Jitender Sheoran), PraveenDhinwa (Praveen Dhinwa)
Problem Editorialist: likecs (Bhuvnesh Jain)
Statement Verifier: Xellos (Jakub Safin)
Russian Translator: Mediocrity (Fedor Korobeinikov)
Mandarin Translator: huzecong (Hu Zecong)
Vietnamese Translator: VNOI Team
I hope you will enjoy solving them. Please give your feedback on the problem set in the comments below, after the contest.
Contest Details:
Time: 3rd August 2018 (1500 hrs) to 13th August 2018 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.
Contest link: https://www.codechef.com/AUG18
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 global and top 20 Indian winners get 300 Laddus each, with which the winners can claim cool CodeChef goodies. Know more here: https://discuss.codechef.com/questions/51999/how-do-i-win-a-codechef-goodie (For those who have not yet got their previous winning, please send an email to winners@codechef.com). First to solve each problem individually: 100 laddus (For problems common to both Divisions, only one user will get laddus for that problem).
Good Luck!
Hope to see you participating!!
Happy Programming!!
The contest has started. Hope to see you at the leaderboard. Good luck and enjoy the contest.
How to solve Safe Partition ?
Subtask 1 was a variation to classical DP. I couldn't think of further tasks!
What's the idea behind KCOMPRES?
I like how CodeChef calls it a "tie-breaker" problem when all but 10 people are tied at 0 points.
Initial set of editorials:
1.SPELLBOB
2.SHKNUM
3.PROBLEMS
4.GCDMOD
5.KCOMPRES
6.LONCYC
When will you upload rest of the editorials?
nilesh8757, Really sorry for the delays. I had been busy shifting to a new city for my work for the last week. Just got free today. Rest of the editorials will be available within 2 days. All queries in the previous ones will also be answered.
INMAT
RIVER
PRINDRAG
The problem pages for those three don't have links to the editorials. When you put so much effort to writing these editorials, it's a pity if people can't find them!
I can't find an editorial for SAFPAR, is it still work in progress?
The extent to which editorials on CodeChef are delayed is ridiculous.
dp[i] = number of safe partitions given the first i elements.
Consider the restriction min(S)<=|S|. Let b1(l) = the minimum r such that the inequality holds. It's obvious that all r>=b1(l) also work. b1(l) is monotonic and can be computed with two pointers. b2(r) can be found in a similar way and all subarrays such that l<=b2(r) work. For the rest of the explanation, I will ignore this restriction, but it can be included easily.
Precompute next > elements and previous >= elements to find each element's "dominating range". Let [a, b] be the "dominating range" of element i. All subarrays [l, r] such that a<=l<=i and i<=r<=b will have a maximum of element i.
There are 2 ways to process the dp normally. You could iterate through a<=l<=i and add all of dp[l-1] to dp[i], dp[i+1], ..., dp[b]. Using prefix sums, this will take O(i-a) per element. You could also iterate through i<=r<=b and add dp[a-1]+dp[a]+...+dp[i] to dp[r]. Similarly, this will take O(b-i) per element. Choosing any of them seems to result in an O(n^2) algorithm.
If you choose the one with O(min(i-a, b-i)) independently for each element, then the total time complexity will be O(nlogn). See http://mirror.codeforces.com/blog/entry/56345.
https://www.codechef.com/viewsolution/19445478 (I know, the indexing is cancerous)
Thank you!
Can you explain your RIVER code? Is it a top-tree?
Yes, it is just a top-tree with a dp for finding the maximum matching.
"just a top-tree with a dp"
I spent several hours trying to make this approach work and failed. After the contest ended I saw your code and thought it seems familiar but it's way too short!
Kudos, and thanks for the answers.