P3169 - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You’re given an array A. In one move, you can delete either a prefix or a suffix of A, as long as A doesn’t become empty.
Find the minimum number of moves needed to make K the most frequent element of A.
It’s guaranteed that A contains K.

EXPLANATION:

Since K appears in A, the answer is definitely at most 2: let i be an index such that A_i = K, then on the first move we can delete everything before i, and on the second move everything after i, leaving K as the only element in A.

This means we need to check if the answer can possibly be 0 or 1.

Checking if the answer is 0 is easy: no moves can be made, so K must already be the most frequent element in A.
Compute the frequencies of every element and check if \text{freq}[K] is the maximum among them.

This leaves checking for the answer being 1.
In one move, we can delete either a prefix or a suffix - equivalently, we’ll leave either a prefix or a suffix.
So, all that needs to be checked is whether K is the most frequent element in some prefix or some suffix.

This can be done as follows, for the prefix (suffix is similar, just reverse the array and run the same algorithm):

  • Define \text{freq}[i][x] to be the frequency of x among the first i elements of A.
  • This can be computed as follows:
    • \text{freq}[i][A_i] = 1 + \text{freq}[i-1][A_i]
    • \text{freq}[i][x] = \text{freq}[i-1][x] for each x \neq A_i

Since A_i \leq 20, all these values can be computed in \mathcal{O}(20\cdot N) time.
Then, check if there exists an i such that \text{freq}[i][K] \geq \text{freq}[i][x] for every x - if yes then the answer can be 1.

As noted above, this algorithm should be run on both the prefix and suffix to check if the answer can be 1.
If the checks for both 0 and 1 fail, the answer will be 2 instead.

TIME COMPLEXITY:

\mathcal{O}(20\cdot N) per testcase.

CODE:

Author's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    ll kitne_cases_hain;
    kitne_cases_hain=1;
    cin>>kitne_cases_hain;
    while(kitne_cases_hain--){          
        ll n,k;
          cin>>n>>k;
          ll a[n+1];
          ll cnt[n+1][21];
          for(int i=1;i<=20;i++){
            cnt[0][i]=0;
          }
          for(int i=1;i<=n;i++){
            cin>>a[i];
            for(int j=1;j<=20;j++){
              cnt[i][j]=cnt[i-1][j];
            }
            cnt[i][a[i]]++;
          }
          ll flag=0;
          for(int i=1;i<=20;i++){
            if(cnt[n][i]>cnt[n][k]){
              flag=1;
              break;
            }
          }
          if(!flag){
            cout<<"0\n";
            continue;
          }
          flag=0;
          for(int i=1;i<=n;i++){
            flag=1;
            for(int j=1;j<=20;j++){
              if(cnt[i][j]>cnt[i][k]){
                flag=0;
                break;
              }
            }
            if(flag){
              cout<<"1\n";
              break;
            }
            flag=1;
            for(int j=1;j<=20;j++){
              if((cnt[n][j]-cnt[i-1][j])>(cnt[n][k]-cnt[i-1][k])){
                flag=0;
                break;
              }
            }
            if(flag){
              cout<<"1\n";
              break;
            }
          }
          if(!flag){
            cout<<"2\n";
          }
    }
	return 0;
}
Editorialist's code (PyPy3) 
def check(a, k):
    freq = [0]*21
    ret = 2
    for x in a:
        freq[x] += 1
        if freq[k] == max(freq): ret = 1
    if freq[k] == max(freq): ret = 0
    return ret

for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    print(min(check(a, k), check(a[::-1], k)))
2

My logic was also the same and I stored the frequency of k (cnt). Then checked if cnt>=rem (rem = n-cnt) then answer is 0 otherwise iterate from start to end-1 and decrement the frequency based on value (if current element is k then decrement cnt else rem) and check if at any moment cnt becomes greater than equal to rem then answer is 1. Also i did the same for the suffix as well by iterating from end to start+1.
Otherwise the answer would be 2.

Here’s my code :
include <bits/stdc++.h>
using namespace std;

define int long long
define endl “\n”
define vi vector
define vvi vector<vector>
define vb vector
define vvb vector<vector>
define vc vector
define vvc vector<vector>
define pii pair<int,int>
define vpii vector<pair<int,int>>
define pb push_back
define yes cout << “YES” << endl;
define no cout << “NO” << endl;
define alias cout << “Alias” << endl;
define bob cout << “Bob” << endl;
const int MOD = 1e9+7;
const int INF = 1e18;

void solve() {
int n,k; cin>>n>>k;
vi arr(n);
for(int i=0;i<n;i++) cin>>arr[i];
int cnt=0;
for(auto ele: arr){
if(ele == k){
cnt++;
}
}
int rem=n-cnt;
if(cnt>=rem){
cout << 0 << endl;
return;
}
int temp=cnt;
int temp1=rem;
for(int i=0;i<n-1;i++){
if(arr[i] == k){
cnt–;
}else{
rem–;
}
if(cnt>=rem){
cout << 1 << endl;
return;
}
}
cnt=temp;
rem=temp1;
for(int i=n-1;i>0;i–){
if(arr[i] == k){
cnt–;
}else{
rem–;
}
if(cnt>=rem){
cout << 1 << endl;
return;
}
}

cout << 2 << endl;

}

int32_t main() {
int t = 1;
cin >> t;
while (t–) {
solve();
}
return 0;
}

Can you please tell me why it’s giving me wrong answer on test case 3.

1 Like
3

You never gave that there is only 1 k in the array!!!

#include <stdio.h>

void findFirstAndLast(int arr[], int size, int num, int *first, int *last) {
    *first = -1;
    *last = -1;
    for (int i = 0; i < size; i++) {
        if (arr[i] == num) {
            if (*first == -1) {
                *first = i;
            }
            *last = i;
        }
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, k;
        scanf("%d %d", &n, &k);
        int A[n], ck = 0, f = -1, l = -1;

        // Read the array and count occurrences of k
        for (int i = 0; i < n; i++) {
            scanf("%d", &A[i]);
            if (A[i] == k) {
                ck++;
            }
        }

        // Find first and last occurrence of k
        findFirstAndLast(A, n, k, &f, &l);

        // If k is already the most frequent element
        int a= n/2;
        if (n%2!=0){
            a+=1;
        }
        if (ck >= a) {
            printf("0\n");
            continue;
        }

        // Minimum operations to make k the most frequent
        int min_operations = 0;
        if (f!=0){
            int m= (n-f)/2;
            if ((n-f)%2!=0){
                m+=1;
            }
            int d= (n-f-(n-f-1))/2;
    
            // Case 1: If there are enough Ks in the suffix (after the first occurrence)
            if (ck >= m) {
                min_operations = 1;
            }
            // Case 2: If there are enough Ks in the prefix (before the last occurrence)
            else if (ck >= (d) / 2) {
                min_operations = 2;
            }
        printf("%d\n", min_operations);
        }
        else if (f==0){
            printf("%d",1);
        }
    }

    return 0;
}

this is my code tell what is wrong !!

4

look for this case:

6 3
4 4 4 3 2 1

The answer should be 1.