• ABV-Indian Institute of Information Technology And Management, Gwalior

# Editorial-Codehub1 (2018)

Yash Kodesia , Anshul Warade

* * *

# Problem -1 ) Game of glasses

All possible combinations will be 3!=6.

Thus the time period of swaps will be 6 .

For each time (0-5) store the position of 3 glasses in a matrix, label them as 0,1,2 and then take n mod 6.

And then display table[newposn][n%6].

See the code for reference.

```//Yash Kodesia, IIITM
//IPG-2015111
//yash.kodesia98@gmail.com
#include
using namespace std;
#define   UPR(x,y)  upper_bound(all(x),y)-x.begin()
#define   linp2(x,y) long long int x,y; cin>>x>>y;
#define   rep2(i,k,n) for(int i=k;i<=n;i++)
#define   all(x) x.begin(),x.end()
#define   vpll  vector
#define   vb  vector
#define   vll  vector
#define   MOD 1000000007
#define   sz(a) a.size()
#define   INF   1e18+7
#define   ff  first
#define   ss second
#define   pb push_back
#define   ld long double
#define   pll pair
#define   ll   long long int
#define   rep1(i,k,n) for(int i=k;i>n;
#define   present(c,x) ((c).find(x) != (c).end())
#define   LWR(x,y)  lower_bound(all(x),y)-x.begin()
const ll MAX = 10005;
// Start

void solve(){
ll mp={{0,1,1,2,2,0},{1,0,2,1,0,2},{2,2,0,0,1,1}};
linp1(n);
n%=6;
linp1(x);
cout<>t;
while(t--){
solve();
cout<<"
";
}
return 0;
}```

# Problem 2)- Naruto and some Japanese Person

First let us see for the middle cell , as that cell contributes to the sum of all the 2x2 matrices so it can take all the N values.

Now there will be 4 of 2x2 matrices let the partial sum be for matrix Matrix 1. a+b Matrix 2. b+d Matrix 3. d+c Matrix 4. c+a

The values that the cell can take will be shifted from MAX(all above values)-MIN(all above values) and thus the maximum value that a cell can take will be N-(MAX-MIN).

For example the above 4 values are 17,18,19,20 and N=10; Now to make partial sums equal to one another we need to add integers corresponding to them and these integers are the values (greater than equal to one and less than equal to N): To make total sum: 21=(17+4),(18+3),(19+2),(20+1) 22=(17+5),(18+4),(19+3),(20+2) 23.. 24.. 25.. 26.. 27=(17+10),(18+9),(19+8),(20+7)

As MAX-MIN=3; thus for values of N (1 to 10) we shift it by 3 so total possible values are from (4 to 10) ie 7 in this case.

IF(N-MAX-MIN<=0) then 0; Else ans=N-MAX-MIN;

See the code for reference

```//Yash Kodesia, IIITM
//IPG-2015111
//yash.kodesia98@gmail.com
#include
using namespace std;
#define   UPR(x,y)  upper_bound(all(x),y)-x.begin()
#define   linp2(x,y) long long int x,y; cin>>x>>y;
#define   rep2(i,k,n) for(int i=k;i<=n;i++)
#define   all(x) x.begin(),x.end()
#define   vpll  vector
#define   vb  vector
#define   vll  vector
#define   MOD 1000000007
#define   sz(a) a.size()
#define   INF   1e18+7
#define   ff  first
#define   ss second
#define   pb push_back
#define   ld long double
#define   pll pair
#define   ll   long long int
#define   rep1(i,k,n) for(int i=k;i>n;
#define   present(c,x) ((c).find(x) != (c).end())
#define   LWR(x,y)  lower_bound(all(x),y)-x.begin()
const ll MAX = 10005;
// Start

void solve(){
linp1(n);
linp2(a,b);
linp2(c,d);
ll mi=min(min(a+b,b+d),min(d+c,c+a));
ll mx=max(max(a+b,b+d),max(d+c,c+a));
ll diff=mx-mi;
diff=n-diff;
if(diff<=0){
cout<<0; return;
}
else
cout<>t;
while(t--){
solve();
cout<<"
";
}
return 0;
}```

# Problem 3) - Hammered distance

Basically we need to find Sum(i:1,N) Sum(j:1,i-1) (xj-xi)^2+(yj-yi)^2 We can process the X coordinate and Y coordinate part seperately.

For X part

Sum(i:1,N) Sum(j:1,i-1) (Xj-Xi)^2
Sum(i:1,N) Sum(j:1,i-1) (Xj^2+Xi^2-2XiXj)
Sum(i:1,N) ( (i-1)*Xj^2 + Sum(j:1,i-1)Xi^2 -2Xi(Sum(j:1,i-1)Xj))

The above process can be done in single pass hence O(n). Refer to code for implementation details.

```//Yash Kodesia, IIITM
//IPG-2015111
//yash.kodesia98@gmail.com
#include
using namespace std;
#define   UPR(x,y)  upper_bound(all(x),y)-x.begin()
#define   linp2(x,y) long long int x,y; cin>>x>>y;
#define   rep2(i,k,n) for(int i=k;i<=n;i++)
#define   all(x) x.begin(),x.end()
#define   vpll  vector
#define   vb  vector
#define   vll  vector
#define   MOD 1000000007
#define   sz(a) a.size()
#define   INF   1e18+7
#define   ff  first
#define   ss second
#define   pb push_back
#define   ld long double
#define   pll pair
#define   ll   long long int
#define   rep1(i,k,n) for(int i=k;i>n;
#define   present(c,x) ((c).find(x) != (c).end())
#define   LWR(x,y)  lower_bound(all(x),y)-x.begin()
const ll MAX = 1000005;
const ll pts=10007;
// Start

ll n;
vpll points,presum,presq,cnt;
void solve(){
cin>>n;
points.resize(n+1);
presum.resize(n+1);
presq.resize(n+1);
cnt.resize(n+1);
rep1(i,1,n+1){
cin>>points[i].ff>>points[i].ss;
presum[i].ff=presum[i-1].ff+points[i].ff;
presum[i].ss=presum[i-1].ss+points[i].ss;
presq[i].ff=presq[i-1].ff+pow(points[i].ff,2);
presq[i].ss=presq[i-1].ss+pow(points[i].ss,2);
}
rep1(i,1,n+1){
cnt[i].ff=(i-1)*pow(points[i].ff,2)+presq[i-1].ff-2*points[i].ff*presum[i-1].ff;
cnt[i].ss=(i-1)*pow(points[i].ss,2)+presq[i-1].ss-2*points[i].ss*presum[i-1].ss;
cnt[i].ff+=cnt[i-1].ff;
cnt[i].ss+=cnt[i-1].ss;
}
cout<>t;
while(t--){
solve();
cout<<"
";
}
return 0;
}
```

# Problem 4)- The GATE-Gatsby

Consider for a professor i:

He takes classes with time slots

i,N+i,2*N+i,3*N+i,......,N^2-N+i So in this series must exist at least a single multiple of every number from (1 to K) so that student should be able to attend that class.

Given that at least K students should pass out of N and each student attends classes in the multiple of its numbering. (Assume = is congruent operator here ) Suppose for K=4: 1) X=0MOD1 and X=0MODN must have atleast 1 solution 2) Y=0MOD2 and Y=0MODN must have atleast 1 solution 3) Z=0MOD3 and Z=0MODN must have atleast 1 solution 4) W=0MOD4 and W=0MODN must have atleast 1 solution

From chinese remainder theorem we know that any 2 congruent equations have solution when their MOD value is co-prime. Thus we need to find that N which is coprime for each of (1-K) so the solution must exist. This can be seen as an inverse Euler totient function: K is the euler totient value of N and we need to find minimal N. As the limit on K is 10^6 so we can precalculate the totient values and for each totient value we can store the minimum N for which it is the output. And then queries can be answered in constant time.

```//Yash Kodesia, IIITM
//IPG-2015111
//yash.kodesia98@gmail.com
#include
using namespace std;
#define   UPR(x,y)  upper_bound(all(x),y)-x.begin()
#define   linp2(x,y) long long int x,y; cin>>x>>y;
#define   rep2(i,k,n) for(int i=k;i<=n;i++)
#define   all(x) x.begin(),x.end()
#define   vpll  vector
#define   vb  vector
#define   vll  vector
#define   MOD 1000000007
#define   sz(a) a.size()
#define   INF   1e18+7
#define   ff  first
#define   ss second
#define   pb push_back
#define   ld long double
#define   pll pair
#define   ll   long long int
#define   rep1(i,k,n) for(int i=k;i>n;
#define   present(c,x) ((c).find(x) != (c).end())
#define   LWR(x,y)  lower_bound(all(x),y)-x.begin()
const ll MAX = 10007;
// Start

map phi;
ll tot(ll n) {
ll result=n;
for(ll i=2; i*i<=n; ++i)
if(n%i==0) {
while(n%i==0)
n/=i;
result-=result/i;
}
if(n>1)
result-=result/n;
return result;
}
void solve(){
linp1(m);
rep1(i,1,MAX){
ll val=tot(i);
if(!phi[val])
phi[val]=i;
}
while(m--){
linp1(k);
if(!phi[k])
cout<<"-1
";
else
cout<
```