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

#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!

Statement:

There is a collection of photos to place into an empty photo album, one at a time by order of importance. Each time a photo is inserted, all subsequent photos are shifted toward right by one position.

Given the id's of the photos and the positions where each should be placed, find out the sequence of the photos in the album after all photos have been inserted.

Example:

 n = 5
 index = [0, 1, 2, 1, 2]
 identity = [0, 1, 2, 3, 4]

 Explanation:
 insert 0 at index 0
 insert 1 at index 1
 insert 2 at index 2
 insert 3 at index 1 and shift 1, 2
 insert 4 at index 2 and shift 1, 2

 output = [0, 3, 4, 1, 2]

Constraints:

1 <= n <= 2 * 10^5

0 <= index[i], identity[i] <= n

Required Tc: < O(n^2)

Update: Can someone pls help...tell me if something is missing in the problem details.

Hello codeforces, I was solving EXPEDI Spoj problem and my solution is here. Can someone tell me why it's giving me wrong answer. It's working on sample test cases and I think there's some edge case I'm missing. Thanks much :)

My Idea: Firstly I'm sorting all the stops based on their distance from starting point (max from town). Then I'm using a max heap to storing all the possible fuels I can use in the way. While I can't reach the next stop with current fuel I'm using the maximum fuel stored from the max heap (top element). Please take a look at submission link for more understanding.

Can someone please help me with this problem. Here is my solution. It's giving me wrong answer on test 2. I am applying simple lazy prapogation logic. Can someone help me, It will hardly take 5 minutes of your time.

My logic: Firstly I fill the whole segment tree with -1's. Now, query function is simply finding an element present on a particular index and when we have some update pending in the path from root to this node I will simply assign this value to it's children and current node will have value -1 after this. My english is poor, sorry.

Thanks very much.

Upd: Accepted code