PROBLEM LINK:

Practice

Code Drive Contest Division 1

Code Drive Contest Division 2

Code Drive Contest Division 3

Author: Sobhagya Singh Dewal

Tester: Lavish Gupta, Takuki Kurokawa

Easy

PREREQUISITES:

Maths, Implementation

PROBLEM:

For all array of length n made up of 0, 1 or 2 , calculate the number of peaks. A peak exists at i^{th} position if (A[i−1]<A[i]>A[i+1]) or (A[i−1]>A[i]<A[i+1]).

QUICK EXPLANATION:

It is done by generating all possible arrays of length n and calculating total peaks in each of these, The answer total\_peaks will be sum of these peaks.

EXPLANATION:

You can use recursive methods, along with backtracking to generate the array, The answer can be simply calculated by iterating over each element of an array and checking if it makes a peak.

Another mathametical rigorous solution can be given as :

We are sure that only 10 tuples will contribute to the answer these are:
[0,1,0],[1,2,1],[1,0,1],[2,1,2],[0,2,0],[2,0,2],[0,2,1],[1,2,0],[1,0,2],[2,0,1].

So each of these tuples contribute 1 in the answer now for N places we need to choose 3 consecutive for any tuple to occur, so choosing 3 consecutive from N is N-2 ways and now remaining N-3 elements can be anything so that is 3^{(N-3)}.
So for 1 tuple contribution will be (N-2)*3^{(N-3)} to the ans. As are 10 tuples hence the final answer is 10*(N-2)*3^{(N-3)}.

SOLUTIONS:

Setter’s Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long int
const int mod=1e9+7;
int power(int x, int y, int p)
{
int res = 1;
x = x % p;
while (y > 0)
{
if (y & 1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return res;
}

void myfun()
{
int n; cin>>n;
int ans=10*(n-2)*power(3,n-3,mod);
if(n<3) ans=0;
cout<<ans<<"\n";
}

int32_t main()
{
//freopen("input1.txt", "r", stdin);
//freopen("output1.txt", "w", stdout);
int t=1;
cin>>t;
while(t--)
myfun();
return 0;
}

Tester's (Lavish Gupta) Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long

/*
------------------------Input Checker----------------------------------
*/

long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}

if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}

return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}

/*
------------------------Main code starts here----------------------------------
*/

const int MAX_T = 10;
const int MAX_N = 10;
const int MAX_SUM_N = 100000;

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int sum_n = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll z = 1000000007;

ll power(ll a ,ll b , ll p){if(b == 0) return 1 ; ll c = power(a , b/2 , p) ; if(b%2 == 0) return ((c*c)%p) ; else return ((((c*c)%p)*a)%p) ;}
ll inverse(ll a ,ll n){return power(a , n-2 , n) ;}

void solve()
{
int n = readIntLn(1 , MAX_N) ;

if(n <= 2)
{
cout << 0 << '\n' ;
return ;
}

ll ans = (n-2)*10 ;
ans *= power(3 , n-3 , z) ;
cout << ans << '\n' ;
return ;
}

signed main()
{
//fast;
#ifndef ONLINE_JUDGE
freopen("inputf.txt" , "r" , stdin) ;
freopen("outputf.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif

int t = 1;

t = readIntLn(1,MAX_T);

for(int i=1;i<=t;i++)
{
solve() ;
}

assert(getchar() == -1);
// assert(sum_n <= MAX_SUM_N);

cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
// cerr<<"Sum of lengths : " << sum_n << '\n';
// cerr<<"Maximum length : " << max_n << '\n';
// cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
}

Tester's (Takuki Kurokawa) Solution
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
if (n <= 2) {
cout << 0 << '\n';
continue;
}
long long ans = 0;
for (int x = 0; x < 3; x++) {
for (int y = 0; y < 3; y++) {
for (int z = 0; z < 3; z++) {
if (x > y && y < z) {
ans++;
} else if (x < y && y > z) {
ans++;
}
}
}
}
for (int i = 0; i < n - 3; i++) {
ans *= 3;
}
ans *= n - 2;
cout << ans << '\n';
}
return 0;
}

5 Likes

doesn’t this 10∗(N−2)∗3^(N−3) formula give “the number of arrays with atleast one peak”.

3 Likes

No, it will give total number of peaks in N length arrays. There may be more than 1 peak in an array. We are just counting the contribution of each tuple in the final answer and contribution of 1 tuple is (N-2)*3^(N-3).

2 Likes

Better way of explaining this is that taking the 10 tuples as the base case we can only produce the extremum. So 10 tuples are options for each of the 3 consecutive elements:

Let’s for 4:

[0,1,0,2] has 2 peaks

Where we see “[0,1,0] and [1,0,2]” as two 3 sized tuples given
Let’s for 5:

[0,1,0,2,1] has 3 peaks
Where we see “[0,1,0], [1,0,2] and [0,2,1]” as three 3 sized tuples

Also for 4:

[0,1,0,0] has 1 peak
We see “[0,1,0] from list and 0 as added bonus as don’t care”

[1,2,1,1]
[1,2,1,0]
Above two sheds light more on don’t care part
“[1,2,1] form list and (0,1) as added bonus of don’t care”

Notice a pattern where we can select 3 sized tuples and construct any n"
Such that with 0,1,2…(n-2) peaks as max peak of

N number is N - 2

So number of peaks are (N - 2) in fact as zero peaks are no use to solution

(N-2) peaks can be selected (has more than 1 peaks)
10 base tuples to form a peak
3^(N-3) for selecting rest of the elements as it is don’t cares
So we want all them at once

As meaning We need one at least one peak

10 Likes

Here is a funny solution. Generate a random sequence from \{0, 1, 2\}^n and compute the expected number of peaks in it. Our answer will be 3^n times this. Now if we set up Bernoulli variables X_i for each 2 \leqslant i \leqslant n-1 depicting whether it’s a peak or not, then we need only determine \mathbb{E}[X_i] by linearity of expectation. For each indice, this value is instantly computed to be 10/27. Overall, for n > 2 we have an answer of 10 \cdot(n-2)\cdot3^{n-3}.

3 Likes

ohk, nice. got it. Thanks!

Hi, could you please show the computation of this E[Xi]? I wanted to generalise it for permutations of n numbers with repetition

Um I didn’t understand. What do you mean by “generalising to permutations”? Also the EV computation is just through the linearity of expectation.