PROBLEM LINK:
Author: Sobhagya Singh Dewal
Tester: Lavish Gupta, Takuki Kurokawa
DIFFICULTY:
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;
}