# Lucky Integers- Editorial

Author: mugdha273

Editorialist: mugdha273

Tester: dragno99

# PROBLEM:

Given an array A of size n filled with elements from Recamán’s sequence ; a_0 to a_{n-1}.

Lets define a variable res.

• Pick any 2 elements from the array, a_i (0 \leq i \leq n-1) and a_j (i-k \leq j \leq i+k , provided it exists) such that a_i ≠ a_j and store the product of a_i and a_j into res.

• Add any element a_p (0 \leq p \leq n-1) to res.

After performing both operations , res = a_i*a_j + a_p.

You are provided with a positive integer Y, and an integer k such that 1 \leq k \leq 3 and n, the length of the array. You have to find out the valid values of a_i, a_j, a_p such that it satisfies the equation Y = res , if it is not possible to find the suitable triplet print -1.

NOTE:

• If multiple answers are possible, then consider answer having least value of a_i*a_j.

• If a_i*a_j is same for 2 triplets, then consider answer having least value of a_i.

• If a_i is also identical for 2 triplets, then consider answer having least value of a_j.

• Basic STL

EASY

# Approach:

Let’s Break the question into parts for better understanding:

• Precompute the Recamán sequence till n=1001 and store it in a vector, let’s say vec.

• Observe that: k is small, so we can precompute a vector v which will store values in such a fashion that v holds pairs ((a_i * a_j, j), (a_i, a_j)).

→ Logic: v.first.first will store the value of res according to each a_i * a_j, v.first.second will hold the value of k ranging from 1 to 3 in both left and right directions so that we can utilize it later according to our input.

→ v.second.first will store value of a_i, a_j in order to find a and b as per our need.

Diving into the main function,

We’ve precomputed all possible res values for all possible k, however, our final solution is dependent on the k given in the input, therefore taking into account values as per the k given in each test case.

• Use set s to store unique values of all possible values of (Y-res).

But why do I care about Y-res?

Well, This will provide you with values from which you may select a suitable c to add res to generate Y.

As a result, choose an appropriate c while keeping the NOTE criteria in mind.

This appears to be fairly straightforward till this point, however ignoring a few cases could land you in WAs.

(1) As per the NOTE, sort values of all a_i * a_j such that you pick correct a and b.

Example: Y= 113, we can have possible res as 90 and 110 where we can add c = 23 and 3 respectively to generate Y but 90 was generated from 9 * 10 and 110 from 11 * 10 hence we’ll go for 9,10,23 rather than 10,11,3.

This can be done by simply storing the values into a vector in a sorted manner and picking the first value.

(2) In Recamán’s sequence, with the same value of res we can get a bunch of different a_i, a_j For example, res = 2604 we can have 42 * 62 as well as 31 * 84 but we are allowed to pick only one!

(3) When “res” and “a” have the same value, it STILL yields different possibilities of b, such as a=0, b=1, and a=0, b=3, which are frequently overlooked; both have the same value of res and least possible a but we have to pick a=0, b= 1 as it is clearly mentioned in the third point of NOTE to grab least possible b if the first and second conditions are same for some set of values.

# SOLUTION:

Setter's Solution in C++

/*author : Mugdha Sharma

(mugdha273)*/

#include <bits/stdc++.h>

#define rep(i, a, b) for (int i = a; i < b; i++)

#define repr(i, a, b) for (int i = a; i >= b; i--)

#define M 1000000007

#define all(a) (a).begin(), (a).end()

#define pb push_back

#define ll long long int

using namespace std;

vector<ll> vec;

void recaman(int n)

{

if (n <= 0)

return;

vec.push_back(0);

unordered_set<int> s;

s.insert(0);

int prev = 0;

for (int i = 1; i < n; i++)

{

int curr = prev - i;

if (curr < 0 || s.find(curr) != s.end())

curr = prev + i;

s.insert(curr);

vec.push_back(curr);

prev = curr;

}

}

vector<pair<pair<ll, ll>, pair<ll, ll>>> gen()

{

vector<pair<pair<ll, ll>, pair<ll, ll>>> v;

int s = vec.size();

rep(i, 0, s)

{

unordered_set<ll> temp;

rep(j, 1, 4)

{

if ((i - j) >= 0)

{

v.push_back(make_pair(make_pair(vec[i] * vec[i - j], j), (make_pair(vec[i], vec[i - j]))));

}

else

{

continue;

}

}

rep(j, 1, 4)

{

if ((i + j) <= s - 1)

{

v.push_back(make_pair(make_pair(vec[i] * vec[i + j], j), (make_pair(vec[i], vec[i + j]))));

}

else

{

continue;

}

}

}

return v;

}

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(NULL);

// freopen("@i6.txt", "r", stdin);

// freopen("@o6.txt", "w", stdout);

recaman(1001);

vector<pair<pair<ll, ll>, pair<ll, ll>>> v = gen();

int T;

cin >> T;

while (T--)

{

ll n;

ll k, y;

cin >> n >> k >> y;

ll a, b, c;

ll sz = (n - 6) * 6 + 24;

set<ll> s;

set<ll> s2;

rep(i, 0, sz)

{

if (v[i].first.second <= k)

{

ll e = v[i].first.first;

s.insert(y - e);

}

}

for (int i = 0; i < n; i++)

{

s2.insert(vec[i]);

}

int ele;

bool w = 0;

for (auto x : s2)

{

int sb = s.size();

s.insert(x);

int sa = s.size();

if (sa == sb)

{

ele = x;

w = 1;

}

}

vector<pair<ll, ll>> vec2;

if (w == 1)

{

c = ele;

for (int i = 0; i < sz; i++)

{

if ((v[i].first.first == y - c) && v[i].first.second <= k)

{

a = v[i].second.first;

b = v[i].second.second;

vec2.push_back({a, b});

}

}

sort(vec2.begin(), vec2.end());

a = vec2[0].first;

b = vec2[0].second;

cout << a << " " << b << " " << c << " " << endl;

}

else

{

cout << -1 << endl;

}

}

return 0;

}


Tester's Solution in Python

def recaman(n):

s = set([])

ls = list([])

ls.append(0)

curr = 0

for i in range(1 , n):

curr = ls[-1] - i

if curr<0 or (curr in s):

curr = ls[-1] + i

ls.append(curr)

return ls

for _ in range(int(input())):

[n, k, y] = (int(x) for x in input().split())

rec_seq_list = recaman(n)

rec_seq_set = set(rec_seq_list)

ans = list([10000000 , -1 , -1 , -1])

for i in range(n):

for j in range(i - k ,i + k + 1 , 1):

if j >= 0 and j < n and i != j :

num = rec_seq_list[i] * rec_seq_list[j]

need = y - num

if need in rec_seq_set:

curr = list([num , rec_seq_list[i] , rec_seq_list[j] , need ])

ans = min(ans , curr)

if ans[0] == 10000000:

print(-1)

else:

print(ans[1],ans[2],ans[3])


1 Like