Tuesday, 15 March 2016

***City and Campers 2

City and Campers 2

Alex has split into N parts, and each of these N parts is wandering around the city aimlessly. You have to handle Qqueries; which consist of two groups of Alex's finding each other and becoming one larger group. After each query, output the minimum difference between two groups. If there is only one group, output 0. At first, everyone is in their own group. What this means is that there are N groups, each of which contain 1 part of Alex.

Also note, if the two Alex's in the query are already in the same group, print the current answer, and skip merging the groups together.

Input:

The first line consists of two space separated integers, N and Q

The next Q line consists of two integers, A and B, meaning that the groups involving Alex A and Alex B find each other.

Output:

Output Q lines, the answer after each query.

Constraints:

1 <= N <= 10⁵

1 <= Q <= 10⁵

Sample Input

(Plaintext Link)

2 1
1 2

Sample Output

(Plaintext Link)

Explanation

The two groups merge to become one larger group, so the difference will be 0.

--------------------------------------------------------------------editorial---------------------------------------------------------------------

This problem can be solved using DSU. I shall be using this concept to explain my approach. If you are not familiar with the concept, please give the editorial of City and Floods a read to understand the basics of DSU.

This is pretty similar to City and Campers, but what makes the problem challenging, in my opinion, is that we are looking for the smallest, and not the largest difference between 2 sets. Like any DSU problem, we are given some disjoint sets initially where each set has a single element.

Here is a naive approach to the problem. Simply keep track of sizes of each disjoint set. Then in O(n^2), find the minimum difference between sizes of two sets, but we have a very large number of queries, q. So, this solution would time out.

An improvement would be store the sizes in some data structure that C++ STL provides, like set or multiset and iterate over the whole set in O(n) to get the minimum difference in the sizes of two disjoint sets. This is still O(n*q) and would time out.

An even better improvement would be to also store tuples which holds 3 values, (representative 1, representative2, abs(representative1.size - representative2.size)). If this can be ordered by the 3rd value, i.e., abs(representative1.size - representative2.size), then each query can be answered in O(1) for obtaining the value + O(log n) if you use sets/multisets for keeping track of the current tuples. So, this reduces to O(q*(log n)).

--------------------------------------------------------------code-----------------------------------------------------------------------

/*
*/

//#pragma comment(linker, "/STACK:16777216")
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <memory.h>
#include <ctime>

#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash

#define eps 1e-9
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 512

using namespace std;

int n,m,w[1<<20],sz[1<<20];
set<int> S;
multiset<int> I;
map<int, int> cnt;
int ans;

int get(int x)
{
if (x==w[x])
return x;
return w[x]=get(w[x]);
}

set<int>::iterator it;

void remove_number(int x)
{
S.erase(x);
it=S.lower_bound(x);
int val=(*it);
--it;
int val2=(*it);
//cout<<val<<" "<<val2<<endl;
//cout<<val-x<<" "<<x-val2<<" "<<I.size()<<endl;
I.erase(I.find(val-x));
I.erase(I.find(x-val2));
I.insert(val-val2);
}

void add_number(int x)
{
it=S.lower_bound(x);
int val=(*it);
--it;
int val2=(*it);
// cout<<val<<"@"<<val2<<endl;
I.erase(I.find(val-val2));
I.insert(val-x);
I.insert(x-val2);
S.insert(x);
}
multiset<int> D;

void merge(int a,int b)
{
w[a]=b;
// cout<<"@"<<endl;

D.erase(D.find(cnt[sz[a]]));
--cnt[sz[a]];
if (cnt[sz[a]])
D.insert(cnt[sz[a]]);

// D.insert(sz[a]+sz[b]);
//cout<<"@"<<endl;
if (cnt[sz[a]]==0)
{
remove_number(sz[a]);
}
//cout<<"@"<<endl;
D.erase(D.find(cnt[sz[b]]));
--cnt[sz[b]];
if (cnt[sz[b]])
D.insert(cnt[sz[b]]);
if (cnt[sz[b]]==0)
remove_number(sz[b]);
sz[b]+=sz[a];
// cout<<"@"<<endl;
if (cnt[sz[b]]==0)
add_number(sz[b]);

// cout<<"@"<<endl;
if (cnt[sz[b]]>0)
D.erase(D.find(cnt[sz[b]]));
cnt[sz[b]]++;
D.insert(cnt[sz[b]]);
ans=(*I.begin());
if (*D.rbegin()>1)
ans=0;
}

int main(){
//freopen("blind.in","r",stdin);
//freopen("blind.out","w",stdout);
//freopen("F:/in.txt","r",stdin);
//freopen("F:/output.txt","w",stdout);
ios_base::sync_with_stdio(0);
//cin.tie(0);

cin>>n>>m;

for (int i=1;i<=n;i++)
w[i]=i,
sz[i]=1;

S.insert(-1e9);
S.insert(1e9);
cnt[1]=n;
I.insert(2e9);
add_number(1);
ans=0;

D.insert(n);
int g=n;

//cout<<I.size()<<endl;

/*for (multiset<int>::iterator it=I.begin();it!=I.end();it++)
{
cout<<"*"<<(*it)<<endl;
}
*/
for (int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
a=get(a);
b=get(b);
if (a==b)
{
cout<<ans<<endl;
continue;
}
--g;
merge(a,b);
if (g==1)
ans=0;

cout<<ans<<endl;
}

return 0;}

City and Soldiers

Today, King Trophies is on another rampage to destroy the small village controlled by Alex. Please help his soldiers.

At first, there are N individual soldiers, who haven't yet joined together; each of these soldiers is the leader of his/her own group. You have to handle 3 types of operations:

1) Two groups find each other, and the leader of the first group steps down.

2) A becomes leader of his group

3) Output the leader of a certain group

Input:

The first line contains the number N, the number of soldiers, and Q, the number of operations.

The next Q lines contains operations in the following format:

1 a b: Groups containing person a and person b find each other, and the leader of the group containing person asteps down, i.e., leader of group containing b becomes the leader of the merged group. If a is in b's group or vice versa ignore the operation.

2 a: a becomes the leader of his group.

3 a: Output the leader of the group containing person a.

Output:

Output the answer for each query of type 3.

Constraints:

1 <= N <= 10⁵

1 <= Q <= 10⁵

SAMPLE INPUT

2 2
1 1 2
3 1

SAMPLE OUTPUT

Explanation

Here, 2 will take over after 1 steps down.

--------------------------------------------------------------EDITORIAL-------------------------------------------------------

JUST CHANGE THE REPRESENTATIVE OF THE GROUP ....

---------------------------------------------------------CODE--------------------------------------------------------------------

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli parent[1000000];
lli rankk[1000000];
lli find(lli a)
{
if(parent[a]!=parent[parent[a]])
{
parent[a]=find(parent[a]);
}
return parent[a];
}

int merge(int a,int b)
{
int pa=find(a);
int pb=(find(b));
parent[pb]=pa;
rankk[pb]=0;
//parent[a]=a;
}
int main()
{
int n;
cin>>n;
int q;
cin>>q;
for(int i=0;i<=n;i++)
{
rankk[i]=1;
parent[i]=i;
}
for(int i=0;i<q;i++)
{
int type ;
cin>>type;
if(type==1)
{
int a,b;
cin>>a>>b;
if(find(a)!=find(b))
{
merge(b,a);

}
}
else if(type==2)
{
int a;
cin>>a;
int pa=find(a);
parent[pa]=a;
rankk[pa]=0;
parent[a]=a;
}
else
{
int a;
cin>>a;
// cout<<"call "<<endl;
cout<<find(a)<<endl;
// cout<<"call "<<endl;
}

}
return 0;
}

Friday, 4 March 2016

***Circular Subarrays

Circular Subarrays

You are given a circular array of size N and an integer K. On this array you can perform operations of incrementing or decrementing an element. The cost of such an operation is 1. You can perform more than one operation on a single element.

You want each subarray of length K to have the same sum of elements. Compute the minimum cost needed to achieve this.

Standard input

The first line contains two integer values N and K.

The second line contains N integers, the values of the array.

Standard output

The output should contain a single integer value representing the minimum cost needed.

Constraints and notes

1 ≤ N ≤ 100 000
1 ≤ K ≤ N
The values of the array are between -10 000 and 10 000
The array is circular, so there are always exactly N subarrays of lengthK.

Task Limits

Time limit: 400 ms
Memory limit: 128 MB

Input	Output
10 1 1 2 3 4 5 6 7 8 9 10	25
10 2 1 6 2 7 3 8 4 9 5 10	12
9 3 1 4 7 2 5 8 3 6 9	6
10 10 1 2 3 4 5 6 7 8 9 10	0

------------------------------------------------editorial----------------------------------------------------

after some observation i find that for making each k segment array with equal sum, we need to do operation like

if input is like 9 3

than

we have to make valuse at index

till m-1 do this

0=0+(3-1)=0+(3-1)+(3-1)

1=1+(3-1)=1+(3-1)+(3-1)

2=2+(3-1)=2+(3-1)+(3-1)

and making equal we need to set all element at its median value (this is the least costly to make all element equal )

above approach will work if n%m==0 or array will be not circular else this approach will give wa

like for 10,4 this approach will fail ,

soo for general case we have to use dsu to group all elements which need to make equal in a single group ,
---------------------------------------------------or-----------------------------------------------------------

A first observation we can make is that it is sufficient to ensure that every two consecutive subarrays of size K have equal sum. Lets suppose we look at the two subarrays that start on positions i and i+1. If they are equal it follows that elements v[i] and v[i+K] need to be equal too. We get N equality constraints between the elements of the array. We can group the elements such that all the values in a group need to be equal. It can be proven that there will always be gcd(N, K) groups of size N / gcd(N, K), but this information is not relevant for solving the problem.

Each group can be solved independently. Basically, the subproblem we need to solve now is to make all the elements of a set equal, minimising the total cost. This is a classical problem and the answer is to make all the elements equal to the median of the set. A proof can be found

---------------------------------for clearity see code-----------------------------------------------------------

#include<iostream>

#include<stdio.h>

#include<vector>

#include<algorithm>

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

int rankwa[1000000];

int parent[1000000];

lli arr[1000000];

vector<lli> v[1000000];

lli solve(vector<lli> vv,int mid)

{

vector<lli> v;

int size=vv.size();

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

{

// storing values from index

v.push_back(arr[vv[i]]);

}

// cout<<endl;

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

lli ret=0;

// cost to make all elements equal to median

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

{

ret+=abs(v[mid]-v[i]);

}

return ret;

}

lli find(lli a)

{

if(parent[a]!=parent[parent[a]])

{

parent[a]=find(parent[a]);

}

return parent[a];

}

int merge(int a, int b)

{

int x=find(a);

int y=find(b);

if(rankwa[x]>rankwa[y])

{

parent[y]=x;

//parent[y]=-1;

}

else

{

parent[x]=y;

if(rankwa[x]==rankwa[y])

rankwa[y]++;

}

int main()

{

int n,m;

cin>>n>>m;

int mn=n;

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

cin>>arr[i];

for(int i=0;i<=m-1;i++)// making array circular by copying firmst m elements

{

arr[n+i]=arr[i];

}

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

{

parent[i]=i;

rankwa[i]=1;

}

n=n+m;

for(int j=0;j<m;j++)

{

for(int i=j;i<n;i+=m)

{

int id=i;

id=id%mn;// sinse extra elements are from index 0to m

if(find(id)!=find(j))

{

merge(id,j);

}

lli ans=0;

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

{

v[find(i)].push_back(i);

//storing indexs accorting to its particular group

}

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

{

if(v[i].size()!=0)

{

// for each group finding ans to make elements of thst group equal

if(v[i].size()%2==1 )// if size of group odd than only 1 median element

{

ans+=solve(v[i],v[i].size()/2);

}

// 2 medians

else

ans+=min(solve(v[i],v[i].size()/2),solve(v[i],v[i].size()/2-1));

}

cout<<ans<<endl;

return 0;

}