Given a set of integers A = { a1,a2,a3,...an } and an integer N. You need to find a way to reach N, starting from 1 and at each step multiplying current value by any element of A. Repetition of element is allowed. Since there may be many solutions having the minimum number of states to reach N you can print the lexicographically smallest series among the solutions which contains the least number of states.

For eg: N = 12 , A = [ 2,3,4 ]

a) 1 — > 2 — > 2 — > 3

b) 1 — > 4 -> 3

c) 1 — > 3 -> 4 ( This is the best solution )

Here is the problem link and the solution. I have wrote a recusive solution with memoization to not re compute the sub-problems which have been computed. But i am getting Runtime error due to too much memory allocation in unordered map. How can i optimize it to get A.C ?

My solution :

long long recur(long long n){
    if(n==0) return 0;
    else if(memo.find(n)!=memo.end()){
        return memo[n];
    }
    else{
        long long a = n%3 == 0 ? 1 + recur(n-(2*n)/3) : INT_MAX;
        long long b = n%2 == 0 ? 1 + recur(n-(n/2)) : INT_MAX;
        long long c = 1 + recur(n-1);
        vector<long long> v = {a,b,c};
        memo[n] = *min_element(v.begin(),v.end());
        return memo[n];
    }
}

How to solve today's atcoder contest problem. Also i have seen many people codes there is something they use like Mint? What is it

I got always confused on how to leviate in-built stl function to use upper and lower bound. For eg: in yesterday previous B question I wrote my own upperBound on vector pair.

I think mostly there are 3 variation:

lowerbound on pair with smallest index lowerbound on pair with largest index

upperbound pair with smallest index

Thanx codeforces

Problem Link . I tried to solve this problem but couldn't solve it. Try to read editorial using google translate help me nothing.

I just want to use priority queue with pair of integers such that it stores the maximum product of 2 numbers in descending order . How can i use it in C++ .

For Eg : —

2 5

5 10

3 6

will be save in priority queue as

5 10

3 6

2 5

and if a clash happen , then the first element should be prefer .

Also I was solving this problem using priority queue but getting WA at case 30 , strange RUNTIME error for comparison but it passes using vector of pairs . I just found on the net on how to write custom comparison function for priority queue . Is there any other method without using class or struct .