Editorial:-
**Problem :- Squares inside another squares**
Squares inside another squares editorial.
Problem.
Given a square of side n and infinite squares of side a<n and b<n.
The task is to find that if you can fill the big squares with only small squares.
One line answer we can fill the bigger square if at least one of the following condition hold.
- n%a==0
- n%b==0.
But why ?
If you try dividing one side of square with other small square side into a sum of given two squares.then same way if you full fill all the 4 sides . It is clearly visible that the unfilled space is no more a perfect square. It have some spaces holes in between which by anyway can not be filled by these two given squares.
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define endl "\n"
ll a[200001];
ll b[200001];
ll v[200001];
void solve(){
ll n,i,j,k,l,o,p,q,r;
cin>>p>>q>>r;
if(p%q==0||p%r==0){
cout<<"Yes\n";
}
else {
cout<<"No\n";
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
ll t;
t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
**Problem:- Rearrangement**
You are given an array A of N numbers you have to perform the rearrangement of the given array
such that no two adjacent elements are equal in the rearranged array. If such a rearrangement is Possible
Output Yes and in the next line output the rearranged array . If it is not possible to rearrange the array
as per the required conditions than output no.
We can approach this problem in a greedy fashion. If we observe carefully, it is reasonable to first take care
of the elements with a higher number of occurrence in the array otherwise in the end we will be left with same
numbers which had a high frequency. The algorithm goes as such - first we take the element with the highest frequency
and push is to the resultant array. Now we need to check if we have another number with second highest frequency. If
not we stop the process here else we also push the number with the second highest frequency into the resultant
array. Now we decrease the frequencies of both these numbers and they will be considered again only if there
frequency is still greater than 0. This process needs to repeated until all elements are processed or we reach a
state where we donât have a number with second highest frequency. The best data structure to stimulate this
process is a priority queue which is essentially a heap. We need to use a priority queue which has can store
both the frequency and the elements itself and gives the element with highest frequency the first priority.
code
# include <bits/stdc++.h>
using namespace std;
# define lli long long int
# define MOD 1000000007
# define INF 10000000000009
# define MAX 1000000
# define pb push_back
class compare{
public:
bool operator()(pair<int, int> p1, pair<int, int> p2){
return p1.first <= p2.first;
}
};
void solve(){
int n;
cin >> n;
int arr[n];
map<int, int> mp;
for(int i = 0; i < n; i++){
cin >> arr[i];
mp[arr[i]]++;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;
for(auto x : mp){
pq.push({x.second, x.first});
}
vector<int> ans;
while(!pq.empty()){
pair<int, int> t1 = pq.top();
ans.pb(t1.second);
pq.pop();
if(pq.empty()){
break;
}
pair<int, int> t2 = pq.top();
ans.pb(t2.second);
pq.pop();
if(t1.first - 1 > 0){
pq.push({t1.first - 1, t1.second});
}
if(t2.first - 1 > 0){
pq.push({t2.first - 1, t2.second});
}
}
if(ans.size() == n){
cout << "Yes\n";
for(auto x : ans){
cout << x << " ";
}
}else{
cout << "No";
}
}
int main() {
int t;
t = 1;
while(t--){
solve();
}
return 0;
}
**Problem Dice Throw**
Problem.
Throw a normal dice exactly n times to get at most A ones at most B twos , at most C threes , at most D 4s. , atmost E 5s and at most F six.
Solution seems like of a recurring task of chosing between varioi options at the ith step starting from 0th Step and recursion upto nth step as a base condition. And finally at the nth step validate the atmost given conditions and return 1 if possible or not.
Time complexity. N^6.
N=50 thus N^6.=1.56e10. requires at least 50 seconds.
Think of optimization of it. See the constraints are low to apply dynamic programming and get easy results.
This recursion can be easily optimised using Dp. I define the Dp states as follows.
Dp[a][b][c][d][e][f][n]
as number of ways to reach the n th step holding the conditions with till now consuming a 1s b 2s c 3s d 4s e 5s f 6s.
and also did n moves earlier.
If the current state allow to do any of the move make transition to another state by incrementing the suitable of a,b,c,d,e,f and n by 1.
And make transition.
Donât forget to apply the modulo. Of 1e9+7 at each step.
code
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define N 100001
ll dp[51][6][6][6][6][6][6];
ll P=1e9+7;
ll solve(ll n,ll a,ll b,ll c,ll d,ll e,ll f){
if(a+b+c+d+e+f==0&&n>0){
return 0;
}
if(n==0){
return 1;
}
if(dp[n][a][b][c][d][e][f]!=-1){
return dp[n][a][b][c][d][e][f];
}
ll ans=0;
if(a>0){
ans+=solve(n-1,a-1,b,c,d,e,f);
ans%=P;
}
if(b>0){
ans+=solve(n-1,a,b-1,c,d,e,f);
ans%=P;
}
if(c>0){
ans+=solve(n-1,a,b,c-1,d,e,f);
ans%=P;
}
if(d>0){
ans+=solve(n-1,a,b,c,d-1,e,f);
ans%=P;
}
if(e>0){
ans+=solve(n-1,a,b,c,d,e-1,f);
ans%=P;
}
if(f>0){
ans+=solve(n-1,a,b,c,d,e,f-1);
ans%=P;
}
return dp[n][a][b][c][d][e][f]=ans;
}
void solve(){
ll i,j,k,l,m,n,o,p,q,r,a,b,c,d,e,f;
cin>>a>>b>>c>>d>>e>>f>>n;
memset(dp,-1,sizeof(dp));
cout<<solve(n,a,b,c,d,e,f)<<endl;
}
int main(){
ll t=1;
while(t--){
solve();
}
return 0;
}
**Problem-String equivalency:-**
Given a string s1 , s2. Mutation can be done in string s2. We need to make the strings equivalent to each other. That is all characters in s2 must be k (a positive integer ) times as compared to s1.
Brute force O(n*26) time algorithm.
For each k from 1 to n keep checking the minimum number of insertion depletion operations required in s2 to be made to make it k equivalent to s1. And finally update the minimum answer.
Note that a distinct character in s1 is restricted to only another distinct character in s2. No intra relationship exist in between characters
Thus for each k we can find the minimum required answer as find two hash arrays which store frequency of lower case letters in s1 lets name this frequency array as f1. Similarly name another frequency array as f2 storing characters frequency of string s2.
Now the minimum answer for each k is summation of this over all characters from a to Z.
S=0.
S+=abs(k*f1[c]-f2[c]).
c >=âaâ and c<=âzâ
S is the minimum value for selected k. Iterate over all possible k values from 1 to n and update the answer as ans=min(ans,S);
Return ans as minimum required number of operations
code
# include <bits/stdc++.h>
using namespace std;
# define lli long long int
# define MOD 1000000007
# define INF 10000000000009
# define MAX 1000000
# define pb push_back
void solve(){
string s1, s2;
cin >> s1 >> s2;
int p1[26], p2[26];
memset(p1, 0, sizeof(p1));
memset(p2, 0, sizeof(p2));
for(auto c : s1)
p1[c - 'a']++;
for(auto c : s2)
p2[c - 'a']++;
int ans = INT_MAX;
for(int k = 1; k <= 1000; k++){
int cnt = 0;
for(int i = 0; i < 26; i++){
cnt += abs(k*p1[i] - p2[i]);
}
ans = min(ans, cnt);
}
cout << ans << "\n";
}
int main() {
int t;
t = 1;
while(t--){
solve();
}
return 0;
}
**Problem-largest-subarray**
Task is generally calculate largest size subarray the product of all elements of that subarray is a perfect square.
Solution.
You cannot store the product of any big subarray in any integer. Thus you need to think of something smart.
What if we decompose this numbers in the form of prime factors. Have you noticed why the limit was kept to 250 for primes. There was a big reason for that.
Notice a subarray product will be perfect square only if the resulting prime numbers in the product have even powers. By power of exponents. We transform that for all primes pi present in the subarray lets the sum of their powers in all elements present in the array be S if S%2==0 then only the subarray product is a perfect square.
Lets make use of prefix sum of powers over a range of 1 to I store in the prefix vector where at each step you need to push. Current sum of prime P=S%2.since we need to check only the parity thus the %2 values of sum is sufficient.
Thus after this at every index we need to look for the same pattern. For all those 250 primes located at the leftmost position of prefix vector to get the Maximum Subarray. Same thing can be done using map , multisets and tries.
Most efficient is trie to search and insert a pattern into trie. See the implementation for more details on tries.
Solutions
Simple code
/**
* Coded by : lucky_21
* --------Lokesh Singh
**/
#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#define F first
#define S second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define fix fixed<<setprecision(10)
#define rep(i,a,b) for(int i=int(a);i<=int(b);i++)
#define repb(i,b,a) for(int i=int(b);i>=int(a);i--)
#define FastIO ios_base::sync_with_stdio(0),cin.tie(0)
typedef double db;
typedef long long ll;
const int N=2e5+5;
const int mod=1e9+7;
int n,ans,f[55];
map<string,int>m;
signed main(){
FastIO;
string tp(55,'0');
m[tp]=0;
vector<int>p;
rep(i,2,250){
bool ok=1;
rep(j,2,i-1) if(i%j==0) ok=0;
if(ok) p.pb(i);
}
cin>>n;
rep(i,1,n){
int a;
cin>>a;
rep(j,0,p.size()-1){
int cnt=0;
while(a%p[j]==0){
cnt++;
a/=p[j];
}
f[j]=(f[j]+cnt)%2;
}
string s;
rep(i,0,54) s+=to_string(f[i]);
if(!m.count(s)) m[s]=i;
else ans=max(ans,i-m[s]);
}
cout<<ans;
return 0;
}
Efficient code using tries
//Jai Sai Ram
// Always keep helping me while debugging and solving my life.
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
string arr[100001];
ll smallest_prime[2000001];
void seive()
{
ll i,j,k,l,m,n,o,p;
for(i=1;i<=2000000;i++)
{
smallest_prime[i]=1;
}
smallest_prime[0]=smallest_prime[1]=1;
for(i=2;i<=2000000;i++)
{
if(smallest_prime[i]==1)
{
for(j=2*i;j<=2000000;j+=i)
{
if(smallest_prime[j]==1)
smallest_prime[j]=i;
}
smallest_prime[i]=i;
}
}
}
vector<pair<ll,ll>> prime_divisors(ll n)
{
ll i,j,k,l,m,o,p,q,r,s,t;
vector<pair<ll,ll>> vp;
if(n<=1)
return vp;
while(n!=1)
{
p=0;
k=smallest_prime[n];
while(n%k==0)
{
n/=k;
p++;
}
if(p>0)
vp.push_back(make_pair(k,p));
}
if(n>1)
{
vp.push_back({n,1});
}
return vp;
}
struct Trie{
Trie *chars[2];
bool is_end;
ll count=0;
ll position=-1;
};
Trie *create()
{
Trie *ro=new Trie;
ro->is_end=false;
for(ll i=0;i<2;i++)
{
ro->chars[i]=NULL;
}
ro->count=0;
ro->position=-1;
return ro;
}
void insert(Trie *root,string key,ll pos)
{
Trie *temp=root;
for(ll i=0;i<key.length();i++)
{
ll index=(key[i]-'0');
if(!temp->chars[index])
{
temp->chars[index]=create();
}
temp->chars[index]->count++;
temp=temp->chars[index];
}
temp->is_end=true;
temp->position=pos;
}
ll search(Trie *root,string key)
{
Trie *temp=root;
for(ll i=0;i<key.length();i++)
{
ll index=(key[i]-'0');
if(!temp->chars[index])
{
return -1;
}
temp=temp->chars[index];
}
if(temp!=NULL&&temp->is_end==true)
{
return temp->position;
}
return -1;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
Trie *root=new Trie;
root=create();
ll t,i,j,k,l,m,n,o,p,q,r,a[300001];
cin>>n;
memset(arr,0,sizeof(arr));
seive();
ll ans=0;
a[0]=0;
string s="";
for(i=0;i<=250;i++)
{
s+='0';
}
insert(root,s,0);
arr[0]=s;
for(i=1;i<=n;i++)
{
cin>>a[i];
vector<pair<ll,ll>> vp=prime_divisors(a[i]);
s=arr[i-1];
for(auto it:vp)
{
k=it.first;
l=it.second;
m=s[k];
m-=48;
l=l%2;
l+=m;
l%=2;
s[k]=(char)(l+48);
}
arr[i]=s;
// cout<<s<<endl;
if((p=search(root,s))!=-1)
{
//cout<<p<<endl;
ans=max(ans,i-p);
}
else
{
insert(root,s,i);
}
}
cout<<ans<<endl;
return 0;
}
