Can anyone provide ?
Thanks in advance.
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
for (int i = 1; i <= t; ++i)
{
int k;
cin >> k;
vector <int> a(k);
for (int i = 0; i < k; ++i) cin >> a[i];
int g = 0, l = 0, ans = 0;
for (int i = 1; i < k; ++i)
{
if (a[i] == a[i-1]) continue;
else if (a[i] > a[i-1])
{
++g;
ans += ((((l+1) / 4) + (((l+1) % 4) != 0))-1);
l = 0;
} else {
++l;
ans += ((((g+1) / 4) + (((g+1) % 4) != 0))-1);
g = 0;
}
}
ans += ((((l+1) / 4) + (((l+1) % 4) != 0))-1);
ans += ((((g+1) / 4) + (((g+1) % 4) != 0))-1);
cout << "Case #" << i << ": " << ans << '\n';
}
}
We need to keep count of the length of strictly increasing and decreasing sequences.
Consider this:
You’re given 1 2 3 4 5 6 7 8. You can group 1 2 3 4 as A B C D. But 6 is greater than 5 and we’ve already used up all notes till D. We can be greedy and pick A. Now you have A B C D A B C D. We broke the rule only once while switching from D to A. Do the same for all decreasing sequences. Now, you simply need to add ceil of \dfrac{\text{length of sequence}}{4}. But this will include the first group as well. We need to exclude it. So just subtract 1 from this expression. Also, if consecutive values are equal, we don’t care about them because they don’t contribute to the answer.
5 Likes
here is my solution, this might be a little more easy to understand …
basic trick in this problem was you can skip notes while decreasing or increasing, but you cannot make more that 4 strictly increasing tones…
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int T, i_ = 1; cin >> T;
for (;T;T--) {
int K; cin >> K;
vector<int> A(K);
for (int i = 0 ; i < K ; i++) cin >> A[i];
int res = 0, s_i = 0, s_d = 0;
for (int i = 1 ; i < K ; i++) {
if (A[i] < A[i - 1]) {
s_i = 0;
s_d ++;
}
if (A[i] > A[i - 1]) {
s_d = 0;
s_i ++;
}
if (s_i > 3 || s_d > 3) {
s_i = s_d = 0;
res ++;
}
}
cout << "Case #" << i_++ << ": " << res << '\n';
}
return 0;
}
Hi, I have used a simple observation and that is to check if a group of 4 elements in ascending or descending in nature. If it is then we check for the next element to see if it still continues the trend and if it does happen, then we increment the count.
Also, when I was taking the input I made sure that I do not have consecutive similar elements ( eg: 2 3 3 4 4).
#include<bits/stdc++.h>
using namespace std;
const int mxN = 1e4+10;
vector<int> arr(mxN);
bool isAscending(int index){
int var1 = arr[index], var2 = arr[index+1], var3 = arr[index+2], var4 = arr[index+3];
if(var1 < var2 && var2 < var3 && var3 < var4){
return true;
}
return false;
}
bool isDescending(int index){
int var1 = arr[index], var2 = arr[index+1], var3 = arr[index+2], var4 = arr[index+3];
if(var1 > var2 && var2 > var3 && var3 > var4){
return true;
}
return false;
}
void solve(int cnt){
int n;
cin >> n;
int x;
int size = 0;
for(int i = 0; i < n; i++){
cin >> x;
if(!i){
size++;
arr[i] = x;
}
else{
if(x != arr[size-1]){
arr[size] = x;
size++;
}
}
}
int answer = 0;
cout << "Case #" << cnt << ": ";
if(size <= 4){
cout << "0\n";
return;
}
for(int i = 0; i <= size-5; i++){
if(isAscending(i)){
int index = i+4;
bool yes = false;
while(index < n){
if(arr[index] > arr[i+3]){
answer++;
yes = true;
break;
}
else if(arr[index] == arr[i+3]){
index++;
continue;
}
else{
break;
}
}
if(yes){
i += 3;
}
}
if(isDescending(i)){
int index = i+4;
bool yes = false;
while(index < n){
if(arr[index] < arr[i+3]){
answer++;
yes = true;
break;
}
else if(arr[index] == arr[i+3]){
index++;
continue;
}
else{
break;
}
}
if(yes){
i += 3;
}
}
}
cout << answer << "\n";
return;
}
int main(){
int t;
cin >> t;
int cnt = 1;
while(t--){
solve(cnt);
cnt++;
}
}
#include <bits/stdc++.h>
int a[N];
void solve(){
int n,ma=4,mi=1,cnt=0;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=2;i<=n;i++){
if(a[i]>a[i-1])mi++,ma=4;
if(a[i]<a[i-1])ma--,mi=1;
if(mi>ma)cnt++,mi=1,ma=4;
}
cout<<cnt;
}
int main()
{
int xx=0;
int t;cin>>t;while(t--){xx++;cout<<"Case #"<<xx<<": ";solve();cout<<"\n";}
return 0;
}
This was my in-contest AC submission
let every index have a max possible value of max
and a min value of min.
initialize them by 4 , 1 respectively.
Now on every iteration keep updating the two variables.
Whenever mi>ma we update answer by 1 and reset the variables.
This takes O(n) operations.
can anybody send the DP solution ? with brief explanation ?
fro dp just check for every possible position and take min value
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define inf (ll)1e12 + 10
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define um map <ll,ll>
#define rep(i,z,n) for(ll i=z;i<n;i++)
#define repi(i,z,n) for(ll i=z;i<=n;i++)
#define repn(i,z,n) for(ll i=n-1;i>=z;i--)
#define vec vector<ll>
#define vecp vector<pair<ll,ll>>
#define pi (double)3.14159265358979323846
#define ld long double
#define all(z) z.begin(),z.end()
ll power(ll a,ll b,ll m) { ll ans=1; a=a%m; if(a==0) return 0; while(b) { if(b&1) ans=(ans*a)%m; b/=2; a=(a*a)%m; } return ans; }
ll modInverse(ll a, ll m) {return power(a, m-2, m);}
const ll mod = 1e9+7;
// const ll N = 1e9;
int main()
{
speed;
ll t1=1;
ll test;
cin>>test;
while(test--){
ll n;
cin>>n;
vec a(n);
rep(i,0,n)
cin>>a[i];
ll dp[n][4]={};
rep(i,1,n){
rep(j,0,4){
if(a[i]>a[i-1]){
dp[i][j]=dp[i-1][j]+1;
rep(k,0,j){
dp[i][j]=min(dp[i][j],dp[i-1][k]);
}
rep(k,j+1,4){
dp[i][j]=min(dp[i][j],dp[i-1][k]+1);
}
}
else if(a[i]<a[i-1]){
dp[i][j]=dp[i-1][j]+1;
rep(k,0,j){
dp[i][j]=min(dp[i][j],dp[i-1][k]+1);
}
rep(k,j+1,4){
dp[i][j]=min(dp[i][j],dp[i-1][k]);
}
}
else{
rep(k,0,4)
dp[i][k]=dp[i-1][k];
}
}
}
// rep(i,0,n){
// rep(j,0,4)
// cout<<dp[i][j]<<" ";
// cout<<endl;
// }
ll ans=INTMAX_MAX;
rep(i,0,4){
ans=min(ans,dp[n-1][i]);
}
cout<<"Case #"<<t1<<": "<<ans<<endl;
t1++;
}
return 0;
}t=int(input())
z=1
while z<=t:
n=int(input())
a=list(map(int,input().split()))
m=-1
ans=0
for i in range(5,n):
if a[i-3]>a[i-4] and a[i-2]>a[i-3] and a[i-1]>a[i-2] and a[i]>a[i-1]:
ans+=1
elif a[i-3]<a[i-4] and a[i-2]<a[i-3] and a[i-1]<a[i-2] and a[i]<a[i-1]:
ans+=1
print(“Case #{}:”.format(z),ans)
z+=1
very easy implementation
/*author - Ashutosh Chitranshi*/
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define watch2(x,y) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<"\n"
#define watch3(x,y,z) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<" and "<<(#z)<<" is "<<(z)<<"\n"
#define pow2(x) ((x)*(x))
#define ll long long
#define ld long double
#define eb emplace_back
#define pb push_back
#define pf push_front
#define mod 1000000007
//#define ordered_set tree<pair<ll,ll>,null_type,less<pair<ll,ll>>,rb_tree_tag,tree_order_statistics_node_update>
#define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
#define mp make_pair
#define ff first
#define ss second
#define null NULL
#define all(c) (c).begin(),(c).end()
#define nl "\n"
#define inf INT_MAX
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector< vi > vvi;
typedef vector< vl > vvl;
typedef pair< int,int > ii;
typedef pair< ll,ll> pll;
typedef map< ll,ll> mll;
typedef map< int,int> mii;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0); //cout << "Case #" << _ << ": ";
ll t;
cin >> t;
for(int _ = 1;_<=t;_++)
{
ll k;
cin >> k;
ll ar[k];
for(int i=0;i<k;i++)
{
cin >> ar[i];
}
ll dp[k][4];
dp[0][0] = dp[0][1] = dp[0][2] = dp[0][3] = 0ll;
for(int i=1;i<k;i++)
{
if(ar[i] > ar[i-1])
{
dp[i][0] = min({dp[i-1][0],dp[i-1][1],dp[i-1][2],dp[i-1][3]})+1;
dp[i][1] = min({dp[i-1][0],dp[i-1][1]+1,dp[i-1][2]+1,dp[i-1][3]+1});
dp[i][2] = min({dp[i-1][0],dp[i-1][1],dp[i-1][2]+1,dp[i-1][3]+1});
dp[i][3] = min({dp[i-1][0],dp[i-1][1],dp[i-1][2],dp[i-1][3]+1});
}
else if(ar[i] == ar[i-1])
{
dp[i][0] = min({dp[i-1][0],dp[i-1][1]+1,dp[i-1][2]+1,dp[i-1][3]+1});
dp[i][1] = min({dp[i-1][0]+1,dp[i-1][1],dp[i-1][2]+1,dp[i-1][3]+1});
dp[i][2] = min({dp[i-1][0]+1,dp[i-1][1]+1,dp[i-1][2],dp[i-1][3]+1});
dp[i][3] = min({dp[i-1][0]+1,dp[i-1][1]+1,dp[i-1][2]+1,dp[i-1][3]});
}
else
{
dp[i][0] = min({dp[i-1][0]+1,dp[i-1][1],dp[i-1][2],dp[i-1][3]});
dp[i][1] = min({dp[i-1][0]+1,dp[i-1][1]+1,dp[i-1][2],dp[i-1][3]});
dp[i][2] = min({dp[i-1][0]+1,dp[i-1][1]+1,dp[i-1][2]+1,dp[i-1][3]});
dp[i][3] = min({dp[i-1][0]+1,dp[i-1][1]+1,dp[i-1][2]+1,dp[i-1][3]+1});
}
}
cout << "Case #" << _ << ": " << min({dp[k-1][0],dp[k-1][1],dp[k-1][2],dp[k-1][3]}) << nl;
}
return 0;
}
For dp solution you can refer this. On the basis of comparison of value between ar[i] and ar[i-1] we have three cases and in each case simply try all possible 4 values.
1 Like
If they are equal the do we need to check the min case?
dp[i][1]=dp[i-1][1];
dp[i][2]=dp[i-1][2];
dp[i][3]=dp[i-1][3];
dp[i][4]=dp[i-1][4];
This was also accepted. Is this because of weak TC?
1 Like
Actually, No test cases aren’t weak, it is a greedy approach and this problem is solvable by greedy algorithm also. What I did is actually a general dynamic programming approach.
Got it.
Thank you all for the replies. I understood the solution.
1 Like
#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
int main()
{
long long int t;
cin>>t;
for(int tc=1;tc<=t;tc++)
{
ll n;
cin>>n;
vector<ll> arr(n);
for(ll i=0;i<n;i++)
cin>>arr[i];
if(n==1)
{
cout << "Case #" << tc << ": " << 0 << endl;
continue;
}
ll cnt=0;
vector<ll> dp(n+2,-1);
ll i=0,type=-1,p=1;
while(p<n)
{
if(arr[p]!=arr[p-1])
{
if(arr[p]>arr[p-1])
type=0;
else
type=1;
break;
}
else
p++;
}
if(type==-1)
{
cout << "Case #" << tc << ": " << 0 << endl;
continue;
}
while(i<n)
{
ll j=i+1;
if(type==0)
{
while(j<n)
{
if(arr[j]>=arr[j-1])
j++;
else
break;
}
ll val=1;
if(i==0)
{
dp[i]=0;
val=0;
}
else
{
dp[i]=1;
dp[i-1]=0;
val=1;
}
for(ll k=i+1;k<j;k++)
{
if(arr[k]>arr[k-1])
{
val=(val+1)%4;
dp[k]=val;
}
else
dp[k]=val;
}
i=j;
type^=1;
}
else
{
while(j<n)
{
if(arr[j]<=arr[j-1])
j++;
else
break;
}
ll val=2;
if(i==0)
{
dp[i]=3;
val=3;
}
else
{
dp[i]=2;
dp[i-1]=3;
val=2;
}
for(ll k=i+1;k<j;k++)
{
if(arr[k]<arr[k-1])
{
val=(val-1+4)%4;
dp[k]=val;
}
else
dp[k]=val;
}
i=j;
type^=1;
}
}
for(ll i=1;i<n;i++)
{
if(arr[i]>arr[i-1] and dp[i]<=dp[i-1])
cnt++;
else if(arr[i]<arr[i-1] and dp[i]>=dp[i-1])
cnt++;
else if(arr[i]==arr[i-1] and dp[i]!=dp[i-1])
cnt++;
}
cout << "Case #" << tc << ": " << cnt << endl;
}
return 0;
}