How can I memoize this digit dp problem's rec solution?

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Hello codeforces community!

Problem:

Given a lowerlimit and upperlimit (Values on coupon).

A coupon containing the sumofdigits= S will win the lottery. Find S in such a way that max no of people win the lottery.

In short return the count of sum (S) that is repeating max no of times. And the ways to choose that count.

Ex: LL:1 UP:5

array:[1,2,3,4,5]

Sumof digits: [1,2,3,4,5]

Count:1

No of ways to choose that count :5 (max count =1 for 5 )

Ex: LL:1 UP: 10

Array [1,2,3,4,5,6,7,8,9,10]

Sumofdigits: [1,2,3,4,5,6,7,8,9,1]

Count: 2 (sum=1 is repeating 2 times)

No of ways to choose :1

Constraints: 1<=lowerlimit<upperlimit<=10^18

My solution[C++]

#include <bits/stdc++.h>
using namespace std;

int n;
string s;
unordered_map<int, int> mp;

void helper(int idx, int sum, int tight)
{
	if(idx==n)
	{
		mp[sum]++;
		return;
	}
	if(tight)
	{
		for(int i=0;i<=s[idx]-'0';i++)
		{
			helper(idx+1, sum+i, (i==s[idx]-'0'));
		}
	}
	else
	{
		for(int i=0;i<10;i++)
		{
			helper(idx+1, sum+i, 0);
		}
	}
}

void solve()
{
	cin>>s;

	n=s.size();

	helper(0, 0, 1);

	int mx=0, cnt=0;

	for(auto x: mp)
	{
		if(x.second>mx)
		{
			mx=x.second;
			cnt=1;
		}
		else if(x.second==mx)
		{
			cnt++;
		}
	}

	cout<<mx<<" "<<cnt<<endl;
}
 
signed main() {

	solve();
 
return 0;
}

Now I want to memoize this rec solution but can't find a way to do it(as currently the func's return type is void). Can someone pls help :) Thanks!

Комментарии (3)

Написать комментарий?

hijibijee

3 года назад, # |

Didn't get what's going on in your code. Here is my solution for the problem: https://pastebin.com/Uh5CXjc5 May be it will help. :D

→ Ответить

dv.jakhar_

3 года назад, # ^ |

Wow, we can go sumwise too...Got this...Thanks a ton, bro! Actually in my solution I was only taking the upper limit for simplicity.

vedant-z

2 месяца назад, # |

My Code

#include <bits/stdc++.h>
using namespace std;
 
const int M=1e9+7;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define fr(a,b) for(int i = a; i < b; i++)
#define all(x) (x).begin(),(x).end()
#define ll long long int

long long int dp[20][165][2][2];

long long int solve(int i, int sum, int tight1, int tight2, string& l, string& r) {
    if(i>=l.length()) return sum==0;
    if(dp[i][sum][tight1][tight2]!=-1) return dp[i][sum][tight1][tight2];
    long long int ans=0;
    for(char dig='0';dig<='9';dig++){
        if(sum<dig-'0') break;
        if((tight1 && dig<l[i]) || (tight2 && dig>r[i])) continue;
        ans+=solve(i+1,sum-(dig-'0'),tight1 && dig==l[i],tight2 && dig==r[i],l,r);
    }
    return dp[i][sum][tight1][tight2]=ans;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  long long int lowLimit,highLimit;cin>>lowLimit>>highLimit;
  string temp=to_string(lowLimit),l,r=to_string(highLimit);
  int dif=r.length()-temp.length();
  while(dif--) l+='0';
  l+=temp;
  unordered_map<int,long long int> mp;
  memset(dp,-1,sizeof(dp));
  for(int sum=1;sum<163;sum++){
    long long int res=solve(0,sum,1,1,l,r);
    if(res) mp[sum]+=res;
  }
  long long int mx=0,ct=0;
  for(auto i:mp) mx=max(mx,i.second);
  for(auto i:mp){
    if(i.second==mx) ++ct;
  }
  cout<<ct<<" "<<mx;

  return 0;
}

Блог пользователя dv.jakhar_