Description:
Encoding is a monthly contest hosted by CodeChef-NSEC. This is a coding contest based on algorithms and data structures, and aims to encourage participants to apply their knowledge towards problem solving.
Contest Link:
click here
How to participate?
You just need to have a CodeChef username to participate. No seperate registration is required. If you do not have a CodeChef ID create one at https://codechef.com
Date: 24th August
Time: 7:30PM - 10:30PM
See you in the ranklist! 
Looking forward to it. There was a Decipher contest 2-3 days back. And all questions were of very low quality and of this type:- Cipher text is given . Encode it. Decode it. All 6 qns were same of that type only. I never want to waste my time in such questions which dont relate with cp.
So can I expect a nice cp contest from āencodingā or will there be encoding questions only??
I love it!Thanks for the clarification 
Will this contest be held every month on Codechef? Seems a very nice initiative to me!
Yes. We try to host this every month. 
Hope you enjoy it. 
Yes please host It every month
@nuttela Very nice educational contest. Can you share the solution sketch for the last problem ?
For the dp problem, I submitted a solution , got WA. Submitted the same thing after 3 minutesā¦got AC ? Why did this happen ? It gives some anxiety during contest. Overall a great contest!
Can you share the links of your solution?
Are you talking about āNuttela needs a little more helpā?
Thanks a lotā¦ 
@nuttela Can you please share some ideas/editorial for solving some of the harder questions from the contest, particularly those with "Nuttela ā¦ " in the title? I think they were to be solved with segment trees but I donāt have much experience implementing them.
Thanks in advance
Yes. Your are correct.
We will be uploading the editorials soonā¦
My solution:
Idea : Square Root Decomposition
Create blocks of size sqrt(n) keeping a frequency array of size 26 , which stores count of i_th character in that block.
Update the partially intersecting blocks manually and for fully intersecting blocks as keeping a offset array of size sqrt(n) which would keep track of by how much the whole block was updated.
Query : For partially intersecting blocks just query manually and for the fully intersecting blocks check how many each type of vowel can be made if the original character was shifted cyclically offset amount.
My solution:
Just used a lazy propagated segment tree, storing the count of each character in the range.
In the case there is an update, doing the rotation of count of characters is what is required which can be easily done.
As a lazy propagation, each node in the segment tree has an update variable, which keeps the count by which the characters need to be rotated.
By rotation of characters I mean a->b,b->c,ā¦,y->z,z->a.
Count of rotation means, for example it is = 2. a->c,b->d and so on.
!!! BEWARE itās an iterative segment tree which Iāve used.
Nice Idea. But for each query, it will take ān time, where ānā is the length of string.
n=10^6 and q=10^5. So total time=O(number of test-casesqān) = 10^9 operations. Maybe weak test cases. @nuttela do look into it.
Wowā¦thats what I was thinkingā¦that how to do lazy prog. Now, its clear that we should store āxā which indicates by how much the character needs to be rotated Thanks!
Thanks again Wish I could like it 10 times!!
Well the ān factor is amortized. Generally they depend on the test cases(you cannot give a test case where the query range [l, r] can be TLEād because then you can vary the block size 
)
About weak test cases most of them can write a heuristics to pass them. I donāt see any sign of weak test cases because my soln(including many others) with map did got TLE. Generally the TL for sqrt decomposition solutions is set 2secs and thatās correct in the regard of this problem.
Heyā¦it means if I ever see 2 seconds, and if I use square-root decompositionā¦Will I get AC?
Amortized is the word that I have seen at many places but never checked its meaning. Thankyou!
It depends.
Often sqrt decompositions solutions have a large constant factor so yeah but there is no harm checking if it passes or not because generally they are easier to think of.