INVITATION FOR ENCODING AUG'19

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! :blush: :smile: :hearts:

6 Likes

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??:sweat_smile:

2 Likes

No. This is purely Data structures and algorithm based @anon55659401 :hearts:

5 Likes

I love it!Thanks for the clarification :slight_smile:
Will this contest be held every month on Codechef? Seems a very nice initiative to me!

4 Likes

Yes. We try to host this every month. :hearts:
Hope you enjoy it. :blush:

4 Likes

Yes please host It every month

3 Likes

@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… :heart:

1 Like

@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

1 Like

Yes. Your are correct.
We will be uploading the editorials soon…

1 Like

@nuttela Thanks a lot :slight_smile:

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.

Code

2 Likes

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.

Link to the Code

!!! BEWARE it’s an iterative segment tree which I’ve used.

3 Likes

I love your solution @aman_robotics

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 :slight_smile: Thanks!

Thanks again :slight_smile: 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 :stuck_out_tongue:)
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.

2 Likes

Hey…it means if I ever see 2 seconds, and if I use square-root decomposition…Will I get AC? :stuck_out_tongue:
Amortized is the word that I have seen at many places but never checked its meaning. Thankyou! :slight_smile:

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.

1 Like