ENCODING - Editorial

editorial
, , , , ,
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
84

@vijju123 I was trying with the recurrence state as dp[index][tight][bitmask]
where index is the index in the number string,tight=0 or 1 to check whether we can place 0-9 or 0-arr[index] and bitmask is used to mark the numbers from 0-9 we have considered on left to check wether to add arr[k]*10^index to solution

Below is method

long long digitSum(int idx, long long sum,int tight,vector &digit,int bitmask,int n) {
if (idx == -1)
return sum;

if (dp[idx][tight][bitmask] != -1) {
	return dp[idx][tight][bitmask];
}
long long ret = 0; 
int k = (tight)? digit[idx] : 9; 
for (int i = 0; i <= k ; i++) { 
    bool alreadyIncluded = (bitmask >> i) & 1;
	int newTight = (digit[idx] == i)? tight : 0; 
	if(!alreadyIncluded){
	    int newbitmask = bitmask | (1<<i);
	    long long newsum = sum+((long long)(i*pow(10,idx)))%MOD;
	    ret += digitSum(idx-1, newsum, newTight, digit,newbitmask,n); 
	}
	else{
	    ret += digitSum(idx-1, sum, newTight, digit,bitmask,n); 
	}
} 
dp[idx][tight][bitmask] = ret; 

return ret;

}

Not able to figure out whats wrong with this logic :frowning_face:
Getting WA here CodeChef: Practical coding for everyone

Anyone can suggest any 1 case where bitmasking logic should break…

85

take your time @vijju123 but CSTREE too, you promised to explain it in the best possible way :stuck_out_tongue:

1 Like
86

Hey @vijju123 I read the blog on digit dp that you provided in the prerequisite and after that implement the solution. It works well without dp, can anyone please help me in how can i implement dp in this solution. solution

87

Please do it … I’m very much interested in learning different methods to solve the same problem

88

in your code can you explain use of line 103 and 104:
if(i)
ans=add(ans, mul( pre[i-1] , ip[2] ) );

89

Remind me after an hour or 2. Will get to it.

90

Weird. Your code gets some runtime error and/or goes into infinite loop. Need time.

91

But the code works fine in my pc. I know you are very busy but please whenever you have time take a look into it and help me in how can i apply dp in this.

92

if prefix exist then add number/10 to the answer.
Because let’s say number is 10000 then there will be 1000 numbers when ith ( except for leftmost position) digit is char c.
If we take another example the 10200 will have 1000 places when 4th digits is char c ( from right side). Same for 3rd digits.
And 1020 places for 2nd digits.

1 Like
93

find2 method is used to find numbers having ith and(i+1)th same digit so what is use of line 94 and 95:
if( (s[i]>j) || ((s[i]==j) && (s[i+1]>j)))
ans=p[n-2-i];

94

Sure @vijju123 , thanks for getting back to me , matters a lot!

95

Sure, thanks for getting back to me , matters a lot !

96

Why cant you look into it yourself, its not like he have a bunch of free time to be busy with stupid stuff like explaining to you what he have already written in the original post.

97

@vijju123 my bad did not read problem statement carefully ! It had to be divided into subsequences… I missed that part in approaching my solution. Thanks anyways!

1 Like
98

@vijju123 where is CSTREE editorial??

99

Did you read the updates I post at the contest invitation thread?

1 Like
100

Just store the value of states and return it. Rest all is correct. I think you are not clear with what your states are in first place - which is the most fundamental thing for dp.

1 Like
101

Hey @vijju123 , in setters solution what’s the significance of

We just write return 0 at the end of our main function so why are we using int32_t ??