ENCODING - Editorial

editorial
, , , , ,
64

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

65

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.

66

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

67

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
68

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

1 Like
69

@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
70

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
71

Okay :slight_smile:I will start with GFG.

1 Like
72

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

73

But at least you found it! :slight_smile:

74

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

1 Like
75

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

76

okay will write a neat code with comments for you.

77

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

2 Likes
78

@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

79

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?

80

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:

81

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:

82

When will you upload the editorial for CHGORAM and the challenge question? Just asking :slight_smile:

1 Like
83

I am trying to wrap up SYNBAC today itself!

If things go right, you can request for unapproved version of it tonight after 8pm :slight_smile:

CHGORAM is the next in the list. I’m sorry for the slow speed, its just that some things are tricky and I want to take some time to explore how I can explain it the best :slight_smile:

2 Likes