 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Problem Statement for FoxAndGCDLCM | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior
The key point behind this question is prodect(AB)=gcd*lcm. Now since the number crosses
10^12 which means gcd*lcm may excedd the bound. So first inference if (lcm%gcd!=0) then there is no pair A and B.
Now first we divide lcm/gcd let the value be temp. Now the numbers should be such that when
multiplied gives temp and is coprime to each other. We choose such A,B such that A+B is minimised. The answer is (A+B)*gcd.
******** Code goes here ***************
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define ss second
#define ff first
#define ll long long int
#define inf 5000000000000000000
ll get(ll g, ll l)
{
if(l%g!=0)
return -1;
ll val=l/g;
ll temp=sqrt(val);
ll mi=inf;
for(int i=1;i<=temp;i++)
{
if(val%i==0)
{
ll f1=i;
ll f2=val/i;
if(__gcd(f1,f2)==1)
{
mi=min(inf,f1+f2);
}
}
}
return mi*g;
}
int main()
{
ll g,l;
cin>>g>>l;
cout<<get(g,l)<<endl;
return 0;
}
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Saturday, 5 March 2016
Friday, 4 March 2016
C. The Smallest String Concatenation
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You're given a list of n strings a1, a2, ..., an. You'd like to concatenate them together in some order such that the resulting string would be lexicographically smallest.
Given the list of strings, output the lexicographically smallest concatenation.
Input
The first line contains integer n — the number of strings (1 ≤ n ≤ 5·104).
Each of the next n lines contains one string ai (1 ≤ |ai| ≤ 50) consisting of only lowercase English letters. The sum of string lengths will not exceed 5·104.
Output
Print the only string a — the lexicographically smallest string concatenation.
Examples
input
4 abba abacaba bcd er
output
abacabaabbabcder
input
5 x xx xxa xxaa xxaaa
output
xxaaaxxaaxxaxxx
input
3 c cb cba
output
cbacbc
EDITORIAL
The problem was suggested by Lewin Gan lewin. The proof of the transitivity also belongs to him.
Let's sort all the strings by comparator a + b < b + a and concatenate them. Let's prove that it's the optimal answer. Let that operator be transitive (so if 
). Consider an optimal answer with two strings in reverse order by that operator. Because of the transitivity of operator we can assume that pair of strings are neighbouring. But then we can swap them and get the better answer.
). Consider an optimal answer with two strings in reverse order by that operator. Because of the transitivity of operator we can assume that pair of strings are neighbouring. But then we can swap them and get the better answer.
Let's prove the transitivity of operator. Consider the strings as the 26-base numbers. Then the relation a + b < b + a equivalent to 
. The last is simply the relation between real numbers. So we proved the transitivity of the relation a + b < b + a.
. The last is simply the relation between real numbers. So we proved the transitivity of the relation a + b < b + a.
C++ solution by me.
Python solution by lewin.
Complexity: O(nLlogn), where L is the maximal string length.
*********************** CODE GOES HERE********************
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int a[500010];
#define mxn 500010
ll fa[mxn];
ll fb[mxn];
ll bb[mxn];
ll ba[mxn];
int bob[mxn];
#define pb push_back
bool cmp(string a ,string b)
{
return a+b<b+a;
}
int main()
{
int n;
cin>>n;
vector<string> v;
for(int i=0;i<n;i++)
{
string s;
cin>>s;
v.pb(s);
}
sort(v.begin(),v.end(),cmp);
for(int i=0;i<n;i++)
cout<<v[i];
cout<<endl;
return 0;
}
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Here we have to apply a bitmask of 2^n state so as to generate all possible bitmasked state. Now it is understood the for any subset {1,2,3}. we can generate all numbers between low[1]+low[2]+low[3] to high[1]+high[2]+high[3] Now we can form a simple array and update freq[low]++ and freq[high+1]-- . And after forming the prefix all indices that have value greater than 1 can be generated. But this solution gives a memory timed out exception . So we need to realise the points in form of segments and apply a line sweep through them.The code is there for understanding | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
#include<bits/stdc++.h>
using namespace std;
int cost[20];
int unit[20];
int dp[210];
int idx=0;
#define inf 10000000
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
int countPossibilities(vector<int> low, vector<int> high )
{
int n=low.size();
int val=(1<<n)-1;
int mx=0;
vector<pair<int,int> > inv;
for(int i=1;i<=val;i++)
{
int sumi=0;
int sumx=0;
for(int j=0;j<n;j++)
{
if(i>>j &1 )
{
sumi+=low[j];
sumx+=high[j];
}
}
// cout<<"sumi "<<sumi<<" "<<sumx<<endl;
mx=max(sumx,mx);
inv.pb(mp(sumi,sumx));
}
int ans=0;
sort(inv.begin(),inv.end());
n=inv.size();
// for(int i=0;i<n;i++)
// {
// cout<<inv[i].ff<<" "<<inv[i].ss<<endl;
//}
int s=inv[0].ff;
int end=inv[0].ss;
for(int i=1;i<n;i++)
{
if(end>=inv[i].ff)
{
end=max(end,inv[i].ss);
}
else
{
if(end<=9000)
{
ans+=0;
}
else
{
ans+=(end-max(9001,s))+1;
}
s=inv[i].ff;
end=inv[i].ss;
}
}
if(end>9000)
{
ans+=(end-max(s,9001))+1;
}
return ans;
}
int main()
{
int n,m;
cin>>n;
int xx;
vector<int> a,b;
for(int i=0;i<n;i++)
{
cin>>xx;
a.push_back(xx);
}
for(int i=0;i<n;i++)
{
cin>>xx;
b.push_back(xx);
}
cout<< countPossibilities(a,b)<<endl;
return 0;
}
Subscribe to:
Posts (Atom)