When will you upload the editorial for CHGORAM and the challenge question? Just asking
I am trying to wrap up SYNBAC today itself!
If things go right, you can request for unapproved version of it tonight after 8pm
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
@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
Getting WA here CodeChef: Practical coding for everyone
Anyone can suggest any 1 case where bitmasking logic should break…
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
Please do it … I’m very much interested in learning different methods to solve the same problem
in your code can you explain use of line 103 and 104:
if(i)
ans=add(ans, mul( pre[i-1] , ip[2] ) );
Remind me after an hour or 2. Will get to it.
Weird. Your code gets some runtime error and/or goes into infinite loop. Need time.
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.
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.
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];
Sure, thanks for getting back to me , matters a lot !
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.
@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!
Did you read the updates I post at the contest invitation thread?
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.
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 ??