Question Name:Kevin doesn’t like his array

#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/stack:16777216")
#include <string>
#include <vector>
#include <map>
#include <list>
#include <iterator>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <stack>
#include <deque>
#include <cmath>
#include <memory.h>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <utility>
#include <time.h>
using namespace std;
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define RFOR(i, b, a) for(int i=(b)-1;i>=(a);--i)
#define FILL(A,value) memset(A,value,sizeof(A))
#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define PB push_back
#define MP make_pair
#define Pi 3.14159265358979
typedef long long Int;
typedef unsigned long long UInt;
typedef vector<int> VI;
typedef pair<int, int> PII;
const int INF = 1000000000;
const int MAX = 100007;
const int MAX2 = 1000000;
const int MAXD = 20;
const int BASE = 1000000007;
const int MOD = 1000000007;
int b[MAX];
int a[MAX];
int c[MAX];
int main()
{
    //freopen("in.txt" , "r" , stdin);
    int n;
    cin >> n;
    vector<int> a(n);
    int B = 0;
    int C = 0;
    int S = 0;
    FOR(i,0,n)
    {
        scanf("%d" , &a[i]);
        b[a[i]]++;
        B = max(B , b[a[i]]);
        if (i && a[i] == a[i - 1])
        {
            ++S;
            c[a[i]]++;
            C = max(C , c[a[i]]);
        }
    }
    if (B > (n + 1) / 2)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << max((S + 1) / 2 , C) << endl;
    }
	return 0;
}
  • Problem Description
    Kevin has an array A of N integers, but he doesn’t like it – he only likes an array if all its neighboring elements are different (e.g. he likes the array [2,4,2,5,3,2,4], but not [1,2,3,3,4]).

    Kevin can reverse any contiguous subarray of his array any number of times. For example, if he has the array [2,4,2,5,3,2,4] and reverses the subarray from 2nd to 5th element, he will obtain the array [2,3,5,2,4,2,4].

    Now, Kevin wants to know the minimum number of reversals necessary to transform his array into an array he likes – if it’s possible.

    Input format:

    The first line of the input will contain an integer N. The second line will contain N space-separated integers – the elements of A.

    Output format:

    If it’s impossible to transform Kevin’s array into an array he likes, print “-1” (without the quotes). Otherwise, print one number – the minimum number of reversals necessary.

    Constraints:

    1 <= N <= 10^5
    1 <= Ai <= 10^5
    N <= 5 in test data worth 15% of all points
    N <= 10^3 in test data worth 40% of all points
  • Test Case 1
    Input (stdin)7
    1 3 2 2 4 4 4
    Expected Output2
  • Test Case 2
    Input (stdin)5
    42343 42343 99122 7722 7722
    Expected Output1

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.