We invite you to participate in CodeChef’s Starters 78, this Wednesday, 22nd February. The contest will be rated for users upto $$$6$$$-star, i.e, with rating $$$\lt 2500$$$.
Time: 8 PM — 11:00 PM IST
Joining us on the problem setting panel are:
- Setters: Kanhaiya notsoloud1 Mohan, GudeGude, Amir Hossein E404_Not_Found Farhadi, Satish Kumar NinjaSenpai Prajapati, Danny dannyboy20031204 Boy, Nishank IceKnight1093 Suresh
- Testers: Takuki tabr Kurokawa, Yash yash_daga Daga
- Statement Verifier: Nishank IceKnight1093 Suresh
- Video Editorialists: Sundar K Letscode_sundar, Madhav jhamadhav Jha, Suraj jhasuraj01 Jha, Jwala jwalapc, Rohit ezo_tihor Oze, Adhish ak2006 Kancharla
- Text Editorialist: Nishank IceKnight1093 Suresh
- Contest Admins: Satyam satyam343, Nishank IceKnight1093 Suresh
Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest.
The video editorials of the problems will be available for all users for 1 day as soon as the contest ends, after which they will be available only to Pro users.
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.
Hope to see you participating. Good luck!
As an author, I recommend everyone to participate, the problems are really interesting!
MinAdd is exactly the same as https://codeforces.net/contest/1560/problem/F2, with a difference in the output answer.
(I'm not saying that it is copied)
How to solve Divisible Array Counting ?
Hint: Any good subarray will contain atmost 30 distinct elements.
Good array contains no more than $$$O(\log n)$$$ distinct elements. Also if subarray $$$[l; r]$$$ is good so is $$$[l; r - 1]$$$. So let's calculate array $$$r$$$ where $$$r_i = max \, j$$$ such that $$$[i; j]$$$ is good. We can do it naively in $$$O(n\log^2 n)$$$. Now we can answer queries off-line with a couple of Fenwick trees and scanline.
Observation: There are no more than $$$O(logN)$$$ different values in a good array.
Let $$$dp[i]$$$ be the largest index such that $$$[i ... dp[i]]$$$ is good. As $$$dp[i] \leq dp[i + 1]$$$, you can easily calculate it with two pointers using the observation above.
We will answer queries offline. Iterate over $$$L = N ... 1$$$ and add $$$1$$$ to the segment $$$L ... dp[L]$$$. Answer is sum of $$$[L...R]$$$.
Complexity: $$$O(Nlog^2N + QlogN)$$$.
screencast with commentary
What is the intended solution for Balanced Suffix?
My solution has a complexity of $$$O(n \cdot |C|^3)$$$ and it passed in 0.56 s.
I did it squared and passed w/ 0.03s
For each position you could iterate through the alphabet quadratically
Mine is $$$O(n|C|^2)$$$ but it can be improved to at least $$$O(n|C|\log|C|)$$$. UPD: Now that I think about it, it can be solved in $$$O(n\log|C|)$$$ Don't think it can be done faster than that.