Hey everyone, I appeared for the contest and solved [1972C](https://codeforces.net/contest/1972/problem/C). I made a stupid error that got me lagging behind int the contest but I found a solution in time. I'm pretty sure, other people might have also come up with this idea but my version makes it easier for beginners to understand.↵
↵
You can refer to my solution [here](https://codeforces.net/contest/1972/submission/258910359) .↵
↵
First things first, we start with making maximum number of permutations that we can. We maintain the count of used coins and deduct them whenever used, we break the loop when we reach a point where we have insufficient coins.↵
↵
sort the array↵
↵
~~~~~↵
// ct1 is the number of type of coins passed until now↵
int ct=a[0],ct1=1;;↵
for (int i=1;i<n;i++){↵
if(a[i]>a[i-1]){↵
int add = ct1*(a[i]-a[i-1]);↵
if(m<add){↵
ct+=m/ct1;↵
m-=(m/ct1)*ct1;↵
break;↵
}↵
else{↵
ct+=a[i]-a[i-1];↵
m-=add;↵
}↵
}↵
ct1++;↵
}↵
~~~~~↵
↵
The array a has to be sorted for this to be possible. At the end we will be left with ↵
↵
- m : number of coins left (after making all the purchases)↵
↵
- ct : number of permutations we made (full permutations with n elements)↵
↵
As we are sure that the every permutation we made will require one occurance of every type of card, i.e., 1..n. This implies [ct] permutations will require [ct] occurances of every type of card. ↵
↵
Now we just subtract ct from the available coins, and get the extra coins that we are left with, we will only get 3 cases for each type of coin viz, [no coins left], [one coin left] and [more than or equal to two coins left].↵
↵
Lets store number of type of coins that appear once and more than once in _n1_ and _n2_ variables respectively.↵
↵
~~~~~↵
int n2=0,n1=0;↵
for(int i=0;i<n;i++){↵
k=max((int)0,k-ct);↵
if(k>=2){↵
n2++;↵
}↵
else if(k>=1){↵
n1++;↵
}↵
}↵
~~~~~↵
↵
We only have to consider the number of permutations possible. We already made _ct_ permutations. ↵
↵
That would fetch us the answer _ct*n-(n-1)_ . As when arranged, we can start from any index except the last _n-1_ indices to count our permutations (look the image below). lets call this number to be _ans_.↵
↵
_ans_ = _ct*n-(n-1)_↵
↵
Example:↵
↵
↵
Now simply for a fact we can say that m + n2 + n1 will not exceed n (as that would mean we have not considered a possible permutation).↵
↵
Now we only have to address the _n2_ and _n1_ count. Since we already know that [n2 + n1 + m] will not exceed n, we can add it directly to the answer.↵
↵
**This is an alternative way to think, not a part of solution **↵
↵
We can address the n2 count particularly this way:↵
↵
add _n2_ elements in the front and back of already made permutations, on top of that, if we have more coins left, we can add _m_/2 elements to front and back as well. that would lead our solution to be max of ans and [ (_m_/2 + _n2_)*2+ans ].↵
↵
We can visualize it as follows : We already have at least one instances of [n1+n2] different types of cards, we can buy _m_ more, since we are left with m coins. Hence the answer.↵
↵
I made this blog because I thought I found a O (n) solution but later realized i sorted the array in the beginning, poor me.
↵
You can refer to my solution [here](https://codeforces.net/contest/1972/submission/258910359) .↵
↵
First things first, we start with making maximum number of permutations that we can. We maintain the count of used coins and deduct them whenever used, we break the loop when we reach a point where we have insufficient coins.↵
↵
sort the array↵
↵
~~~~~↵
// ct1 is the number of type of coins passed until now↵
int ct=a[0],ct1=1;;↵
for (int i=1;i<n;i++){↵
if(a[i]>a[i-1]){↵
int add = ct1*(a[i]-a[i-1]);↵
if(m<add){↵
ct+=m/ct1;↵
m-=(m/ct1)*ct1;↵
break;↵
}↵
else{↵
ct+=a[i]-a[i-1];↵
m-=add;↵
}↵
}↵
ct1++;↵
}↵
~~~~~↵
↵
The array a has to be sorted for this to be possible. At the end we will be left with ↵
↵
- m : number of coins left (after making all the purchases)↵
↵
- ct : number of permutations we made (full permutations with n elements)↵
↵
As we are sure that the every permutation we made will require one occurance of every type of card, i.e., 1..n. This implies [ct] permutations will require [ct] occurances of every type of card. ↵
↵
Now we just subtract ct from the available coins, and get the extra coins that we are left with, we will only get 3 cases for each type of coin viz, [no coins left], [one coin left] and [more than or equal to two coins left].↵
↵
Lets store number of type of coins that appear once and more than once in _n1_ and _n2_ variables respectively.↵
↵
~~~~~↵
int n2=0,n1=0;↵
for(int i=0;i<n;i++){↵
k=max((int)0,k-ct);↵
if(k>=2){↵
n2++;↵
}↵
else if(k>=1){↵
n1++;↵
}↵
}↵
~~~~~↵
↵
We only have to consider the number of permutations possible. We already made _ct_ permutations. ↵
↵
That would fetch us the answer _ct*n-(n-1)_ . As when arranged, we can start from any index except the last _n-1_ indices to count our permutations (look the image below). lets call this number to be _ans_.↵
↵
_ans_ = _ct*n-(n-1)_↵
↵
Example:↵
↵
↵
Now simply for a fact we can say that m + n2 + n1 will not exceed n (as that would mean we have not considered a possible permutation).↵
↵
Now we only have to address the _n2_ and _n1_ count. Since we already know that [n2 + n1 + m] will not exceed n, we can add it directly to the answer.↵
↵
**This is an alternative way to think, not a part of solution **↵
↵
We can address the n2 count particularly this way:↵
↵
add _n2_ elements in the front and back of already made permutations, on top of that, if we have more coins left, we can add _m_/2 elements to front and back as well. that would lead our solution to be max of ans and [ (_m_/2 + _n2_)*2+ans ].↵
↵
We can visualize it as follows : We already have at least one instances of [n1+n2] different types of cards, we can buy _m_ more, since we are left with m coins. Hence the answer.↵
↵
I made this blog because I thought I found a O (n) solution but later realized i sorted the array in the beginning, poor me.
