We invite you to participate in CodeChef’s Starters118, this Wednesday, 24th January, rated for till 5-Stars (ie. for users with rating < 2200).
Time: 8:00 PM — 10:00 PM IST
Joining us on the problem setting panel are:
Setters: Kanhaiya notsoloud1 Mohan, S.Manuj DarkSparkle Nanthan, Mamalesh SunQuest Rajkumar Hake, Maksym mshcherba Shcherba
Tester: Shreyan Dominater069 Ray
- Statement Verifier: Kanhaiya notsoloud1 Mohan
- Text Editorialists: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 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!
Can you make sure the editorials for the previous Starters 117 are complete? The code for Expected Diameter problem is missing.
Finally, here is a contest.
How to solve WATERBUCKETS
Divide the array into blocks of size $$$O(\sqrt n)$$$. The size of the water bucket is fixed. For each $$$i$$$, compute the minimum number of buckets you need to escape the block and the amount of water left in the last bucket if you start at $$$i$$$. This you can do by Segtree walk in $$$O(log_2(\sqrt n))$$$. Now to process an update, just update the block. To process queries, you can jump from block to block using this structure fast. Total complexity $$$O(n \sqrt n * log_2(\sqrt n))$$$.
I got the same approach during the contest but was thinking about whether it could give TLE or not. poor me :(
Damn, that's awesome, thanks
I think you can use 2-pointers for calculating the amount you can jump to the right within one bucket inside a block. When recalculating a whole block it is only $$$O(\text{size of block})$$$ work total, no log factors and no need for segment trees.
This improves the time complexity also, because now you can change the block size and get $$$O(q \sqrt{ n \log(n) })$$$ complexity.
anyone has the idea how to solve "Is it uniquely decodable?"
I tried a dp solution , in this I got the idea that , all subsequences that ends with a will consist of all the subsequences of previous a only , similarly for all b it can consisit of previous b
https://www.codechef.com/viewsolution/1041477881
Here is what i tried its wrong but what was the idea
okay thanks bro , can you tell me what is the correct approach ?
I have solved using dp. Here $$$dp_{i, j, k}$$$ denotes the no of ways such that we have traversed till $$$i$$$ indices and $$$j$$$ ($$$0$$$ if we need not to put anything strictly here otherwise $$$1$$$ if we need to put a $$$b$$$ here) and $$$k$$$ ($$$0$$$ if the string doesn't end with a $$$ab$$$ and $$$1$$$ if it does). Transitions are pretty much intutive. submission
Editorial
Can anyone please tell me why this solution is giving WA for this problem (Subcount).
I have used matrix exponentiation to solve it.
how to solve SUBCOUNT task?
You can use any strig matching algorithm, i will recommend this — Z-algorithm.