PROBLEM LINK:
Author and Editorialist: Aman Gupta
Tester Hitansh Madan
DIFFICULTY:
Medium-Difficult
PREREQUISITES:
Basic Programming
Algebra
EXPLANATION:
The solution to this problem can be separated into 2 parts.
- Finding the value of a and b (by maximizing the min swaps)
- Finding the total amount of color formed by combining both the favorite colors.
Part 1
Finding max swaps is based on the hypothesis that a string in which all the same characters occur consecutively will be one of the many permutations that takes max swaps to form back the original string.
For example, if string is aba then aab is a possible permutation
for aabb , bbaa is a possible required permutation.
This fact can also be checked by using the brute-force method and calculating the swaps of every permutation for verification purposes.
As given in the problem statement, the string given has a maximum of 5 unique characters.
So total permutation strings such that every same character are consecutive will be at most 5!
We need to find all these strings and calculate swaps for each of them. The required string must be one of them.
This can easily be done in O(N log N) time.
Using the above logic the value of a and b can be found out.
Part 2
Assume n units of total favorite color is formed from k units of X and rest n-k units of color Y.
The total favorite color formed = n
Units of color X formed = k
Units of color Y formed = n-k
k units of color X = ka units of color x1 and kb units of color y1
n-k units of color Y = (n-k)a units of color y11 and (n-k)b units of color x1
The total units of x1 given in the question are P
Therefore
P>=ak + (n-k)b (some unit of x1 may not be used {see sample case})
on solving
P-nb >= k(a-b)
(P-nb)/(a-b) >= k (1)
Similarly another eq is
Q>=bk + (n-k)a
on solving
Q-na >=k(b-a)
(Q-na)/(b-a) <= k (2)
Also k>=0 && k<=n (3)
We get the max value of n which satisfies these above 3 conditions using binary search to get the final answer.
SOLUTION:
Setter's Solution
#include<bits/stdc++.h>
# define mp make_pair
# define pb push_back
# define pp pair<int,int>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define REP(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define M 1000000007
using namespace std;
ll getFav(ll x,ll y, ll a , ll b)
{
if (a == b)
return min(x, y) / a;
ll l = 0, r = 1e9 + 100;
if (a < b)
swap(a, b);//we assume a>b always
while (l<r)
{
ll m = (l+r+1) / 2;
ll x1 = floorl((x - m * b) * 1.0l / (a - b));//max possible k
ll x2 = ceill((y - m * a) * 1.0l/ (b - a));//min possible k
//min can't be less than 0 and max cant be greater than n
if (max(x2, 0ll) <= min(x1, m))// possible values are btw a nd b
l = m;
else
r = m-1;
}
return l;
}
ll check(string s , string A)
{
int i = 0;
ll ans = 0;
vector<char> v;
for (char c : s)//length 4
{
v.clear();
for (int j = i; j < A.size(); j++)
{
if (A[j] == c)
{
A[i] = c;
ans += j - i;
i++;
}
else v.push_back(A[j]);
}
for (int j = i; j < A.size(); j++)
A[j] = v[j - i];
}
return ans;
}
ll getCode(string x)
{
string c;
set <char>uniq;
REP(i,0,x.size())
{
if(uniq.find(x[i]) == uniq.end())
{
c.pb(x[i]);
uniq.insert(x[i]);
}
}
sort(c.begin(), c.end());
vector<string>permu;
do
{
permu.pb(c);
}
while (next_permutation(c.begin(), c.end()));
ll mx = 1;
for(int i=0;i<permu.size();i++)
{
ll temp = check(permu[i],x);
if(mx<temp)
{
mx = temp;
}
}
// cout<<ans;
return mx;
}
void solvefile(int i)
{
ll x,y;
cin>>x>>y;
int n1,n2;
cin>>n1>>n2;
string ac,bc;
cin>>ac>>bc;
ll a = getCode(ac);
ll b = getCode(bc);
ll ans = getFav(x,y,a,b);
cout<<ans<<'\n';
}
int main()
{
solvefile(0);
return 0;
}
Tester's Solution
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define MAX LLONG_MAX
#define MIN LLONG_MIN
#define M 1000000007
#define MM 998244353
#define rep(i, j, k) for (ll i = j; i < k; i++)
#define repr(i, j, k) for (ll i = j; i >= k; i--)
#define repi(i, j, k, l) for (ll i = j; i < k; i += l)
#define pb push_back
#define ppb pop_back
#define mem0(a) memset(a, 0, sizeof(a))
#define mem1(a) memset(a, -1, sizeof(a))
#define mp make_pair
#define pll pair<ll,ll>
#define out(a) for(auto x: a) cout<<x<<" "; cout<<endl
#define all(a) a.begin(),a.end()
#define vpll vector<pll>
#define ff first
#define ss second
#define sz(x) ((int)(x).size())
#define set_bits __builtin_popcountll
typedef long long ll;
typedef vector<long long> vll;
typedef vector<char> vc;
typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
ll getInvCount(ll arr[], ll n)
{
ll key;
ordered_set set1;
set1.insert(arr[0]);
ll invcount = 0;
for (ll i = 1; i < n; i++) {
set1.insert(arr[i]);
key = set1.order_of_key(arr[i] + 1);
invcount += set1.size() - key;
}
return invcount;
}
ll solve(string s,string t){
map<char, deque<ll>> v;
ll n = sz(t);
rep(i,0,n){
v[t[i]].pb(i);
}
ll arr[n];
rep(j,0,n){
arr[j] = v[s[j]].front();
v[s[j]].pop_front();
}
return getInvCount(arr,n);
}
ll find_inv(string s) {
vll cnt(200);
for(auto x:s)
cnt[x]++;
set<char> temp(all(s));
vc v(all(temp));
ll best = -1;
do{
string t;
for(auto x:v){
rep(i,0,cnt[x]){
t.pb(x);
}
}
ll tmp = solve(s,t);
if(tmp > best)
best = tmp;
} while(next_permutation(all(v)));
return best;
}
ll ans(ll p,ll q, ll a , ll b){
if (a < b)
swap(a, b);
if(a==b) return min(p,q)/a;
ll l = 0, r = M;
while (l<r) {
ll m = (l+r+1) / 2;
ll x1 = (p - m * b) / (a - b);
ll x2 = (q - m * a + b - a - 1)/ (b - a);
if (max(x2, 0ll) <= min(x1, m)) l = m;
else r = m-1;
}
return r;
}
void testcase(int tt){
ll p,q,n;
cin>>p>>q>>n>>n;
string s1,s2;
cin>>s1>>s2;
ll a = find_inv(s1);
ll b = find_inv(s2);
cout<<ans(p,q,a,b)<<endl;
}
int main() {
// ios_base::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ll t = 1;
// cin >> t;
for(int i = 1 ; i <= t ; i++){
// cout<<"Case #"<<i<<": ";
testcase(i);
}
return 0;
}