ENCODING - Editorial

Are the input file same for Python and CPP?? As my submission is in Python

Apart from it u took me and be as int input which in Python is taken as string and then explicitly type casted to int like:on=int(input())


Also this is the image shshowing error during the contest time span

I believe it is sufficient enough to support my claim @vijju123 rest thank you very much for addressing the issue.

Thats not the error given on test files - codechef does not reveal these messages. This seems to be some error you get on custom input due to not giving an input or not giving input correctly.

Even then we don’t have any plausible explanation for NZEC in the submission as shown in pic

I can give you one :smiley: . I ran your code on testing page and this is what I got-

Traceback (most recent call last):
  File "./prog.py", line 94, in <module>
  File "./prog.py", line 56, in ip
  File "./prog.py", line 59, in main
  File "./prog.py", line 9, in getSum
OverflowError: cannot convert float infinity to integer

Thanks a lot @vijju123 it will help a lot and will help for further development :innocent::innocent:

1 Like

@vijju123 I am beginner in cp. And in dp too. The editorial for ENCODING is very much scary for me. Can you tell me what all thing i need to cover before starting with digit dp? I am just not able to visualize what is stored in the 3d array. I read the editorial 5 6 times still not geting the logic and digit dp in general. Please help, thanks in advanced.

2 Likes

I get your Point of View dear. Thing is, its not easy at all to grasp this if pre requisites are not fulfilled.

Start with the GFG section of classical problems, and the DP (in general) link I gave in pre-requisites.

To fulfil pre requisites, your DP knowledge should be such that you are able to come up with dp of classical type problems yourself.

1 Like

Okay :slight_smile:I will start with GFG.

1 Like

I had a bug in my dp array that made the solution O(N ^ 2) :(. Spent a whole evening finding it.

But at least you found it! :slight_smile:

Hope I get 3 stars after next challenge :smiley:.

1 Like

can you please write a few comments in your code as i am not able to understand it properly

okay will write a neat code with comments for you.

https://www.codechef.com/viewsolution/25943813
Check this new code.

2 Likes

@vijju123
I am facing difficulty in understanding this.
Can you please add an example like 1234 and dry run and show.
That you help me a lot.
Thanks

The dp array in the code followed by the blog in codeforces is initialized as, “int dp[12][12][2]”. I get the first dimension is 12 so that the dp can hold values for upto 12 digit of numbers, and the last dimension’s value is 2 because the flag is gonna have 2 values, either 0 or 1, but how come the value in the middle is 12?

Read the states part here! Its a very trivial thing, but I want you to try and get it yourself. Just read the part where I talk about states :slight_smile:

I am sympathetic here. But the code is given. The recurrence is given. And with that, I’d want you to do the dry run yourself so that you do not need anyone else to explain it.

Run the code for various inputs and observe the values. Dry run on some small examples (start with 2-3 digits)$. Thats the way to understand it yourself.

Just give it a try once, and if you fail to come up with it I will explain :slight_smile: