How to Solve this Problem from Geeks for Geeks Hiring Contest? - Codeforces

→ Pay attention

Before contest
Educational Codeforces Round 173 (Rated for Div. 2)
29:26:54
Register now »

→ Streams

CF Edu Round 173 Solution Discussion

By aryanc403

Before stream 31:36:54

View all →

→ Top rated

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Countries | Cities | Organizations

→ Top contributors

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	160
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	Dominater069	154
8	awoo	154
10	luogu_official	151

View all →

→ Find user

→ Recent actions

Detailed →

mayank0802's blog

How to Solve this Problem from Geeks for Geeks Hiring Contest?

By mayank0802, history, 5 years ago, In English

In English

https://practice.geeksforgeeks.org/contest-problem/maximum-absolute-difference/0/

+15

mayank0802
5 years ago
5

Comments

Comments (4)

Show archived | Write comment?

»

5 years ago, # |

Vote: I like it

+10

Vote: I do not like it

I'm under the impression that whenever you decrement some value it's optimal to take it all the way down to 1. Therefore, you can go for a dynamic programming approach to solve the problem, where dp[i][flag] = largest possible answer for the i-th prefix and flag indicates if the last element stayed at his value or if he was reduced to 1.

→ Reply

»

5 years ago, # |

← Rev. 2 →

Vote: I like it

0

Vote: I do not like it

code

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int,int>
#define pb push_back
#define F first
#define S second
#define mod 1000000007
#define maxn 1000005
#define inf 1e18
#define boost ios::sync_with_stdio(false);cin.tie(0)
#define fr freopen("source.txt","r",stdin),freopen("output.txt","w",stdout)
#define SET(a,b) memset(a,b,sizeof(a))
ll a[maxn],dp[maxn][2];
ll n;
ll go(ll i,ll j){
    if(i==(n-1)) return 0;
    ll &ans=dp[i][j];
    ans=0;
    if(i==0){
        ans=max(ans,abs(a[i]-1)+go(i+1,1));
        ans=max(ans,abs(a[i]-a[i+1])+go(i+1,0));
        ans=max(ans,abs(1-a[i+1])+go(i+1,0));
    }
    else if(j==0){
        ans=max(ans,abs(a[i]-1)+go(i+1,1));
        ans=max(ans,abs(a[i]-a[i+1])+go(i+1,0));
    }
    else{
        ans=max(ans,go(i+1,1));
        ans=max(ans,abs(1-a[i+1])+go(i+1,0));
    }
    return ans;
}
int main()
{
    boost;
    ll i,j,x,t;
    cin>>t;
    while(t--){
        cin>>n;
        for(i=0;i<n;i++)cin>>a[i];
        SET(dp,-1);
        cout<<go(0,0)<<"\n";
    }
}

→ Reply

»

»

5 years ago, # ^ |

Vote: I like it

+1

Vote: I do not like it

Nobody got an AC on this problem, was there some problem with it's test cases?

solution

#include "bits/stdc++.h"
using namespace std;

#define int long long
#define rep(i,a,n) for (int i = a; i <= n; ++i)
const int N = 1e6 + 3;

int dp[3][N];
int a[N];
 
inline void solve() {
   int n;
   cin >> n;
   rep(i,1,n) {
    dp[0][i] = dp[1][i] = dp[2][i] = 0;
    cin >> a[i];
   }   
   rep(i,2,n) {
    dp[0][i] = abs(a[i]-a[i-1]) + dp[2][i-1];
    dp[1][i] = abs(a[i-1]-1) + max(dp[0][i-1], dp[2][i-1]);
    dp[2][i] = abs(a[i]-1) + dp[1][i-1];
   }
   cout << max({dp[0][n], dp[1][n], dp[2][n]}) << '\n';
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  int t = 1;
  cin >> t; while(t--)
  solve();
  return 0;
}

→ Reply

»

5 years ago, # |

Vote: I like it

+8

Vote: I do not like it

Congratulation for creating the 69420th blog of codeforces

→ Reply