meiniak's blog

By meiniak, history, 11 months ago,

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 )

• 0

By meiniak, history, 12 months ago,

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];
}
}

• 0

By meiniak, history, 18 months ago,

Given an array of strings, each of the same length and a target string construct the target string using characters from the strings in the given array such that the indices of the characters in the order in which they are used form a strictly increasing sequence. Here the index of a character is the position at which it appears in the string. Note that it is acceptable to use multiple characters from the same string. Determine the number of ways to construct the target string. One construction is different from another if either the sequences of indices they use are different, or the sequences are the same but there exists a character at some index such that it is chosen from a different string in these constructions. Since the answer can be very large, return the value modulo (109 + 7). Consider an example with n = 3 strings, each of length 3. Let the array of strings be words = ["adc", "aec", "erg"], and the target string target = "ac". There are 4 ways to reach the target.

1. Select the 1st character of "adc" and the 3rd character of "adc".
2. Select the 1st character of "adc" and the 3rd character of "aec".
3. Select the 1st character of "aec" and the 3rd character of "adc".
4. Select the 1st character of "aec" and the 3rd character of "aec".

• -1

By meiniak, history, 19 months ago,

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

• 0

By meiniak, history, 19 months ago,

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

• +2

By meiniak, history, 22 months ago,

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

• 0

By meiniak, history, 2 years ago,

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 .