Link to the contest: SPC Round #001

#### A. Mango Juice

Problem Author: CharanSrikar

**Tutorial**

Given that $$$a$$$ and $$$b$$$ are even it is always possible to reach a multiple of $$$b$$$ after a certain number of operations.

Proof: let $$$a$$$ be $$$2p$$$ and b be $$$2q$$$, after $$$n$$$ number of operations, it becomes $$$2p+2n$$$ This should be a multiple of $$$b$$$ (which is $$$2q$$$)

$$$\therefore$$$ we can write:

$$$2p+2n = 2q(m)$$$ $$$\implies$$$ $$$p+n = q(m)$$$ $$$\implies$$$ $$$n = q(m) - p$$$

Now, from the equation we can see that for every $$$p$$$ and $$$q$$$ there exists atleast one solution to $$$(n,m)$$$

So, if $$$a$$$ and $$$b$$$ are even it is always possible. So you just have to output $$$YES$$$ for every testcase.

**Solution Code**

```
/* Hari Charan */
#include <bits/stdc++.h>
using namespace std;
#define int long long int
void solve()
{
int a,b; cin>>a>>b;
if(a%2==0 && b%2==0) cout<<"YES\n";
else if(a%2==0 && b%2==0) cout<<"YES\n";
else if(a%2==1 && b%2==0) cout<<"NO\n";
else cout<<"YES\n";
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t; cin>>t;
while(t--) solve();
}
```

#### B. Dance Contest

Problem Author: kuki22102002

**Tutorial**

For each $$$i$$$ ($$$1 \leq i \leq n$$$), we have to compare the values of $$$A_i$$$ and $$$B_i$$$. The greater value is multiplied by 10 and added to the lesser value to give the corresponding element of C.

$$$C_i$$$ = $$$10 \cdot max(A_i, B_i) + min(A_i,B_i)$$$

Time Complexity of the solution: $$$O(n)$$$

**Solution Code**

```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll n;
cin>>n;
ll a[n],b[n],c[n];
for(int j=0;j<n;j++)
cin>>a[j];
for(int j=0;j<n;j++)
cin>>b[j];
for(int j=0;j<n;j++)
{
c[j]=max(a[j],b[j])*10+min(a[j],b[j]);
cout<<c[j]<<" ";
}
return 0;
}
```

#### C. Even Product

Problem Author: CharanSrikar

**Tutorial**

For an array of size $$$2n$$$ to be $$$SPC$$$, we must be able to split it into $$$n$$$ pairs such that the product of each pair is even.

To do this, the worst case is exactly one element of each pair is even. So, it is clear that at least $$$n$$$ elements of the array must be even.

In one operation we can increment or decrement any $$$a_i$$$ by $$$1$$$. Basically, in one operation, we can make an odd element even or even element odd.

So, we convert an odd element to even in each operation until we have $$$n$$$ even elements. We want at least $$$n$$$ but as the minimum number of operations is asked we do till $$$n$$$ only.

So, we count the number of even elements in the array. Let this be count.

If count $$$\geq$$$ n, we don't need to do any number of operations. So, $$$0$$$

else we need $$$n-count$$$ operations.

**Solution Code**

```
/* Hari Charan */
#include <bits/stdc++.h>
using namespace std;
#define int long long int
void solve()
{
int n; cin>>n; int a[2*n];
int cnt=0;
for(int i=0; i<2*n; i++) {cin>>a[i]; if(a[i]%2==0) cnt++;}
if(cnt>=n) cout<<"0\n";
else cout<<n-cnt<<"\n";
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t; cin>>t;
while(t--) solve();
}
```

#### D. Aayush and Tiles

Problem Author: arsinha

**Tutorial**

Make an array of all possible scores by considering each tile as a starting point and then print the maximum element in this array.

If 0 is more than the above obtained value, then 0 is the answer. Else, the value obtained from the above method is the answer.

Time Complexity of the Solution: $$$O(\frac{n^2}{k})$$$ per test case.

PS: Can you think of a solution that has time complexity $$$O(n)$$$?

**Solution Code**

```
#include<bits/stdc++.h>
using namespace std;
#define int long long
int32_t main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,k;
cin>>n>>k;
int tiles[n];
for(int i=0; i<n; i++){
cin>>tiles[i];
}
int sum;
int tilesum[n];
for(int i=0; i<n; i++){
int j = i+k;
sum = tiles[i];
while(j<=n-1){
sum = sum + tiles[j];
j=j+k;
}
tilesum[i]=sum;
}
int xx=0;
int ans = max(xx,*max_element(tilesum, tilesum +n));
cout<<ans<<endl;
return 0;
}
```

#### E. Divisible Arrays

Problem Author: kuki22102002

**Tutorial**

The core idea of this problem is:

Given 3 integers $$$n, d$$$ and $$$k$$$, can we find another positive integer $$$t$$$ such that $$$(n+td)$$$ $$$mod$$$ $$$k = 0$$$ i.e. $$$(n+td) = quotient \cdot k$$$ ?

Let us say the $$$GCD(d,k) = g$$$ i.e. $$$d = gx$$$ and $$$k = gy$$$ where $$$x$$$ and $$$y$$$ are coprime. This means the condition we have becomes:

$$$n + t(gx) = quotient \cdot (gy)$$$

$$$n = g \cdot (tx - qy)$$$

Hence, $$$n$$$ must be divisible by $$$g$$$.

Also, if 2 numbers $$$x$$$ and $$$y$$$ are coprime, then there exist integers $$$t,q$$$ such that $$$tx - qy = 1$$$.

As $$$tx - qy$$$ can be equal to 1, it can be equal to any other value as well (If $$$tx - qy = 1$$$, then $$$atx - aqy = a$$$ i.e. $$$t'x - q'y = a$$$).

Hence, $$$n$$$ can be any multiple of $$$g$$$.

**Conclusion:** $$$\exists$$$ $$$t$$$ such that $$$(n+td)$$$ $$$mod$$$ $$$k = 0$$$ if and only if $$$n$$$ is divisible by $$$GCD(d,k)$$$.

Hence if all elements of the array are divislbe by $$$g$$$, then we can print "YES". Else print "NO".

Time Complexity: $$$O(n$$$ $$$log(max(d,k)))$$$ per test case.

**Solution Code**

```
/* AdC_AB2, CodeForces
SPC G2 - Swift Coders */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b)
{
if(b==0)
return a;
return gcd(b, a%b);
}
ll func(ll n, ll d, ll k)
{
if(n % gcd(d,k) == 0)
return 1;
else
return 0;
}
void solv()
{
ll n,d,k;
cin>>n>>d>>k;
ll a[n];
for(int i=0; i<n; i++)
{
cin>>a[i];
}
for(int i=0; i<n; i++)
{
if(func(a[i],d,k)==0)
{
cout<<"NO\n";
return;
}
}
cout<<"YES\n";
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll test_cases=1;
cin>>test_cases;
for(ll loop_var=1;loop_var<=test_cases;loop_var++)
{
solv();
}
return 0;
}
```

#### F. Clean Arrays

Problem Authors: Kruthic & AdC_AB2

**Tutorial**

For $$$n>1$$$, we can prove that the array can be made *clean* if it contains atleast 1 odd number.

The parity of a number does not change if we subtract an even number from it.

Let us consider 2 cases $$$(n > 1)$$$:

1) All elements are even. In this case we cannot change the parity of numbers in odd indices (eg. $$$a_1$$$, $$$a_3$$$,...). Hence the array cannot be made *clean*.

2) The array has atleast one odd element.

(i) There is an odd number at an odd index: We can use this element to change the parity of even elements in odd indices and odd numbers in even indices.

(ii) All the odd numbers are in even indices: In this case, $$$a_1$$$ (More generally $$$a_i$$$ where $$$i$$$ is odd) will be even. Let us say the index $$$j$$$ contains an odd element. Now we do a move: $$$a_1$$$ = $$$a_1$$$ — $$$a_j$$$ (More generally, $$$a_i = a_i - a_j$$$). As a result, $$$a_1$$$ (More generally, $$$a_i$$$) becomes an odd element. We now have an odd element in an odd index and we can use the previous logic to make the array *clean*.

For $$$n=1$$$, if $$$a_0$$$ is even then the array is *clean*, else it can't be made *clean*.

Time Complexity: $$$O(n)$$$ per test case.

**Solution Code**

```
/* AdC_AB2, CodeForces
SPC G2 - Swift Coders */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solv()
{
ll n;
cin>>n;
ll a[n];
for(int i=0; i<n; i++)
{
cin>>a[i];
}
if(n==1)
{
if(a[0]%2==0)
cout<<"YES\n";
else
cout<<"NO\n";
return;
}
for(int i=0; i<n; i++)
{
if(a[i]%2==1) //If there is atleast 1 odd number, we print YES and end this testcase
{
cout<<"YES\n";
return;
}
}
cout<<"NO\n"; //If there are no odd numers in the array, we print NO
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll test_cases=1;
cin>>test_cases;
for(ll loop_var=1;loop_var<=test_cases;loop_var++)
{
solv();
}
return 0;
}
```

#### G. Polycarp and Rocks

Problem Author: Abdullah_Md010

**Tutorial**

The total number of rocks would be $$$1 + \frac{n - k}{m}$$$, where the 1 represents the rock at the $$$k^{th}$$$ position, and $$$\frac{n - k}{m}$$$ represents all the rocks after it.

Now, there are three cases for the region controlled by Petya:

1) $$$q < k$$$ : There are no rocks under Petya's control.

2) $$$p \leq k \leq q$$$ : The first $$$\frac{n - k}{m}$$$ are rocks under Petya's control.

3) $$$p < k$$$ : The first $$$\frac{q - k}{m}$$$ — $$$\frac{p - 1 - k}{m}$$$ are rocks under Petya's control.

NOTE : Remember that Petya controls regions from $$$p$$$ to $$$q$$$ (inclusive).

Time Complexity of the solution: $$$O(1)$$$ per test case.

**Solution Code**

```
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int n, k, m, p, q;
cin >> n >> k >> m >> p >> q;
int total = 1 + (n - k) / m;
if (q < k)
{
cout << total << endl;
return;
}
else if (p <= k)
{
int removed = 1 + (q - k) / m;
cout << total - removed << endl;
}
else
{
int removed = (q - k) / m - (p - 1 - k) / m;
cout << total - removed << endl;
}
}
int32_t main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int tc = 1;
cin >> tc;
while (tc--)
solve();
}
```

#### H. Vasya's Beads

Problem Author: Abdullah_Md010

**Tutorial**

We can maintain a position array with the first bead inserted being assigned position 0 and further beads being assigned increasing values if they are added on the right hand side, and decreasing values if they are added to the left hand side.

We can perform this assignment by maintaining variables $$$l$$$ and $$$r$$$, which essentially serve as counters for beads added on the left and right hand sides respectively excluding the first bead. These counters can then be used to measure the distances of a bead from the end for commands of the third type.

Time Complexity of the solution: $$$O(t)$$$

**Solution Code**

```
#include<bits/stdc++.h>
using namespace std;
#define int long long
int pos[200005];
void solve()
{
int T;
cin >> T;
int l = -1, r = 1;
for (int i = 0; i < T; ++i)
{
int type, x;
cin >> type >> x;
if (!i)
pos[x] = 0;
else if (type == 1)
{
pos[x] = l;
--l;
}
else if (type == 2)
{
pos[x] = r;
++r;
}
else
cout << min(pos[x] - l - 1, r - pos[x] - 1) << endl;
}
}
int32_t main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int tc = 1;
//cin >> tc;
while (tc--)
solve();
}
```

#### I. Doubles Teams

Problem Author: AdC_AB2

**Tutorial**

We first sort the players in ascending order based on their strength.

Let us say the sorted strengths are $$$b_0, b_1,...,b_{n-1}$$$.

We set a variable $$$r$$$ to $$$n-1$$$.

We start iterating from the first variable and we decrement $$$r$$$ as long as $$$b_0 + b_r > k$$$. Once we reach a point where this condition is violated, we count the number of times $$$r$$$ was changed i.e. the number of indices $$$r$$$ such that $$$b_0 + b_r > k$$$.

Now when we go to the next element $$$b_1$$$, we can take for granted that when $$$b_1$$$ is paired with $$$b_{r+1}$$$ or $$$b_{r+2}$$$ or ..., he will win the game because $$$b_0$$$ $$$\leq$$$ $$$b_1$$$ and $$$b_0$$$ was able to defeat Marley's team with these partners.

So we continue to decrement $$$r$$$ as long as $$$b_1$$$ + $$$b_r$$$ > $$$k$$$ and once we reach a violation of the condition, we add the number of decrements to r (from the start of the loop) to the answer.

The underlying logic is that if $$$b_i$$$ can defeat the opponent team with partner $$$b_j$$$, then $$$b_{i+1}$$$ can also defeat the opponent team with partner $$$b_j$$$.

Now from the above sum, we will have to decrease the number of $$$i$$$'s for which $$$2 \cdot b[i] > k$$$ (these will be counted in the above method).

Also, each pair of players is counted twice (first with $$$b_i$$$ as the player in focus and then $$$b_j$$$ as the player in focus). We make the required modification and output the answer.

Time Complexity = O($$$n$$$ $$$logn$$$) per test case.

**Solution Code**

```
/* AdC_AB2, CodeForces
SPC G2 - Swift Coders */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solv()
{
ll n,k;
cin>>n>>k;
ll a[n];
for(int i=0; i<n; i++)
{
cin>>a[i];
}
sort(a,a+n);
ll r=n-1, s=0, ans=0;
for(int i=0; i<n; i++)
{
while(a[i]+a[r]>k && r>=0)
{
s++;
r--;
}
ans += s;
}
for(int i=0; i<n; i++)
{
if(2*a[i]>k)
ans--;
}
ans /= 2;
cout<<ans<<endl;
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll test_cases=1;
cin>>test_cases;
for(ll loop_var=1;loop_var<=test_cases;loop_var++)
{
solv();
}
return 0;
}
```

#### J. Dom and Family

Problem Author: AdC_AB2

**Tutorial**

Note that the value if $$$a_i$$$ is small (Range 2-100). Hence all prime factors of $$$a_i$$$ are less than 100. Hence, the GCD of any *family* that can be formed from an array has a factor less than 100.

Thus, we can run a loop from j = 2 to max($$$a_i$$$). In each iteration we will count the number of array elements which are not divisible by $$$j$$$ and store it in an array, say $$$cnt_j$$$.

We can make a family with it's GCD as a factor of $$$j$$$ by merging all the elements not divisible by $$$j$$$ with a number that is divisible by $$$j$$$ (like in test case 1).

The number of operations in each case will be the number of elements not divisible by $$$j$$$. So we find the minimum value of this number i.e. min($$$cnt_j$$$) for all valid $$$j$$$.

Time Complexity: $$$O$$$($$$n$$$ $$$\cdot$$$ max($$$a_i$$$)) per test case.

**Solution Code**

```
/* AdC_AB2, CodeForces
SPC G2 - Swift Coders */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solv()
{
ll n;
cin>>n;
ll a[n];
ll maxi = 0;
for(int i=0; i<n; i++)
{
cin>>a[i];
maxi = max(maxi,a[i]);
}
ll cnt[maxi+1], ans=n-1;
for(int j=2; j<=maxi; j++)
{
cnt[j]=0;
for(int i=0; i<n; i++)
{
if(a[i]%j!=0)
cnt[j]++;
}
ans = min(ans,cnt[j]);
}
cout<<ans<<endl;
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll test_cases=1;
cin>>test_cases;
for(ll loop_var=1;loop_var<=test_cases;loop_var++)
{
solv();
}
return 0;
}
```

#### K. Bored Ryuk

Problem Author: AdC_AB2

**Tutorial**

DoD($$$n!$$$ , $$$p$$$) = $$$\left \lfloor{\frac{n}{p}}\right \rfloor$$$ + $$$\left \lfloor{\frac{n}{p^2}}\right \rfloor$$$ + $$$\left \lfloor{\frac{n}{p^3}}\right \rfloor$$$ + ...

(Why so? Note that $$$\left \lfloor{\frac{n}{p}}\right \rfloor$$$ is the number of values in $$$[1,n]$$$ divisible by $$$p$$$.)

DoD($$$nCr$$$ , $$$p$$$) = DoD($$$n!$$$ , $$$p$$$) — DoD($$$(n-r)!$$$ , $$$p$$$) — DoD($$$r!$$$ , $$$p$$$) as $$$nCr$$$ = $$$\frac{n!}{(n-r)! r!}$$$

Using the above 2 relations, we can compute DoD($$$nCr$$$ , $$$p$$$) $$$\forall$$$ $$$0 \leq r \leq n$$$.

We can now iterate through all possible values of $$$r$$$, find DoD($$$nCr$$$ , $$$p$$$) and find the maximum value among them (similar to finding maximum element in an array).

Time Complexity: $$$O$$$($$$n$$$ $$$\log_p n$$$) per test case.

**Solution Code**

```
/* AdC_AB2, CodeForces
SPC G2 - Swift Coders */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll DoD_fac(ll n, ll p)
{
ll ans=0;
while(n)
{
ans += n/p;
n /= p;
}
return ans;
}
void solv()
{
ll n,p;
cin>>n>>p;
ll r=0,dod_max=0,tmp;
for(ll i=0; i<=n; i++)
{
tmp = DoD_fac(n,p)-DoD_fac(n-i,p)-DoD_fac(i,p);
if(tmp>=dod_max)
{
dod_max = tmp;
r = i;
}
}
cout<<r<<' '<<dod_max<<endl;
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll test_cases=1;
cin>>test_cases;
for(ll loop_var=1;loop_var<=test_cases;loop_var++)
{
solv();
}
return 0;
}
```

#### L. Who's Group is the best?

Problem Author: KDVinit

**Tutorial**

This is a typical Game Theory Problem. You might try to find some pattern but after a few attempts you can see it doesn't follow any law. The trick is to instead do some pre computations and Brute Force the Solution.

This is a 2 player game in which there will be a definite result every time, and it can be proved that every game of this kind will always have a winning strategy with exactly one of them (given the initial condition of the game). Also it can be seen how the answer for the number of stones being ($$$n+1$$$) can be induced from all the answers in ($$$1$$$ ---> $$$n$$$). Thus we bruteforce for any $$$i$$$, all the numbers that we can reach from here ($$$i$$$ — all possible perfect squares till $$$i$$$), and if either of them is losing, this position is winning, else if all the positions we can reach from here are winning this position is trivially losing.

For time complexity each test case will take $$$O(n \sqrt n)$$$, and thus if we do this for all test cases it will be well above the time constraints. Thus instead we precompute the answer to all the values till $$$2 \cdot 10^5$$$ and then print the answer to each test case in $$$O(1)$$$.

**Solution Code**

```
/*
K.D. Vinit |,,|
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+1;
int win[N]={0};
void solve()
{
int n;
cin>>n;
if(win[n]==1) cout<<"Amarnath"<<endl;
else cout<<"Tej"<<endl;
}
int32_t main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
for(int i=1; i<N; i++)
{
for(int j=1; (j*j)<=i; j++)
{
int k = (j*j);
if(win[i-k]==0) win[i]=1;
}
}
int t; cin>>t;
while(t--) solve();
return 0;
}
```

Auto comment: topic has been updated by AdC_AB2 (previous revision, new revision, compare).Where can we see the problems?AdC_AB2

I've added a link to the contest in the blog. :)

Thanks :)

This editorial is for a private contest, held for the attendees of Summer Programming Club conducted by the Programming Club, IIT Madras.

Auto comment: topic has been updated by AdC_AB2 (previous revision, new revision, compare).