PROBLEM LINK:
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.
PREREQUISITES:
- Basic STL
DIFFICULTY:
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([])
s.add(0)
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
s.add(curr)
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])