RECNDNOS - Editorial

[rishup_nitdgp]

PROBLEM LINK:

Practice
Contest

Author: Ritesh Gupta
Tester: Sachin Yadav
Editorialist: Ritesh Gupta

DIFFICULTY:

CAKEWALK

PREREQUISITES:

NONE

PROBLEM:

You are given a sequence A_1, A_2, \ldots, A_N (1 \le N \le 10^3 and 1 \le A_i \le 10^3). You have to find out the minimum element of the given sequence which makes the length of the valid subsequence is maximum possible. A valid subsequence defines as:

• It should not be empty.
• All the values of the subsequence should be the same.
• No two values are selected which are adjacent in the given sequence.

QUICK EXPLANATION:

• As A_i is almost 1000. So, for each i from 1 to 1000, we can find the largest valid subsequence is possible with i as it’s an element. If there are many valid i for which length of the valid subsequence is the same then the answer is minimum possible i.

EXPLANATION:

OBSERVATION:

• As the valid subsequences are uni-valued. So, we can solve the question for each distinct value independently.
• It is optimum to select the alternate numbers to start from the first element in a layer of equivalent numbers i.e. consider \{2, 2, 2, 2, 2, 2, 2\}, we can choose 4(1^{st}, \space 3^{rd}, \space 5^{th}, and 7^{th}) out of 7 values.

Let suppose there are D distinct values d_1, d_2, \ldots, d_D and frequency of each is f_1, f_2, \ldots, f_D respectively.

For each valid d_i, we can hash the index values for which the value present at these indexes is d_i in the given sequence. If the index values are p_{i,1}, p_{i,2}, \ldots, p_{i,f_i} for some d_i then we just need to pick some of them according to the third conditions mentioned in the definition of the valid subsequence.
Let suppose index values are \{1,3,4,7,8,9,11\} then we greedily select the \{1,3,7,9,11\}. Here, from 3 and 4, we can select any one of them but from 7, 8 and 9, the only way to select two indices are 7 and 9.

It is easy to prove that we should pick the elements greedily from start(left the proof as an exercise) and it gives the optimum answer.

Now, the answer is the minimum of all d_i for which the length of the valid subsequence is maximum possible.

Bonus Problem

You are given a sequence A_1, A_2, \ldots, A_N (1 \le N \le 10^5 and 1 \le A_i \le 10^9). You have to find the count of the valid subsequence. A valid subsequence defines as:

• It should not be empty.
• All the values of the subsequence should be the same.
• No two values are selected which are adjacent in the given sequence.

COMPLEXITY:

TIME: O(N)
SPACE: O(N)

SOLUTIONS:

Setter's Solution

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int t;
    cin >> t;
 
    while(t--)
    {
        int n;
        cin >> n;
 
        vector <int> v[1001];
 
        for(int i=0;i<n;i++)
        {
            int x;
            cin >> x;
 
            v[x].push_back(i);
        }
 
        int curr = 0;
        int ans = -1;
 
        for(int i=1;i<=1000;i++)
        {
            if(v[i].empty())
                continue;
 
            int cnt = 0;
            int prev = -1;
 
            for(int j:v[i])
            {
                if(j > prev)
                {
                    cnt++;
                    prev = j + 1;
                }
            }
 
            if(curr < cnt)
            {
            	curr = cnt;
            	ans = i;
            }
        }
 
        cout << ans << endl;
    }
} 

Tester's Solution

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        int n, freq[1001]={0};
        cin>>n;
        int last=-1, x;
        bool take=1;
        for(int i=0; i<n; ++i)
        {
            cin>>x;
            if(last==x)
                take=!take;
            else
                take=1;
            if(take) ++freq[x];
            last=x;
        }
        int ans=0, mfreq=0;
        for(int i=1; i<=1000; ++i)
        if(freq[i]>mfreq)
        {
            ans=i; mfreq=freq[i]; 
        }
        cout<<ans<<"\n";
    }
    return 0;
} 

[anshumanprasad]

Please let me know where i m wrong.
#include
using namespace std;
int main(){
int t;
cin>>t;
while(t–)
{int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{cin>>a[i];}
int mark=0,max=0,ans=0;
for(int i=1;i<=n;i++)
{int count=0;
for(int j=0;j<n;j++)
{if(a[j]==i&&a[j]!=a[j-1]){count++;mark=j;}
else if(a[j]==i&&a[j]==a[j-1]){if((j-mark)%2==0)count++;}}
if(count>max){max=count;ans=i;}
else if(count==0)break;}
cout<<ans<<endl;
}
return 0;
}

[anon68898584]

please can anyone tell why my code is giving TLE???
//no
#include
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
string s;
cin>>s;
string s1="",s2="";
int l=s.length();
for(int i=0;i<s.length()-1;i++)
{
s1=s1+s[i];
}
for(int i=1;i<s.length();i++)
{
s2=s2+s[i];
}int ctr=0;
s1=s[l-1]+s1;
s2=s2+s[0];
for(int i=0;i<l;i++)
if(s1[i]==s2[i])
ctr++;
if(ctr==l)
printf(“YES\n”);
else printf(“NO\n”);
}
return 0;
}

[anon83463980]

My solution is to club all duplicate type occurring from some index k to j together and find the count of it and if its count is odd then increment hash[type] = count/2 +1 otherwise count/2 and mark all those visited & then traverse the array and increment the hash[a[i]] of non-visited types.( Ai to An)

#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t–){
int n;
cin>>n;
int a[n+1];
a[n]=1100;
bool vis[n+1];
for(int i=0;i<n;i++)
{ cin>>a[i];
vis[i]=false;
}
long int hash[1001];
for(int i=0;i<=1000;i++)
hash[i]=0;
int count=1,flag=0;
for(int i=1;i<=n;i++)
{
if(a[i]==a[i-1]){
count++;
flag=1;
vis[i]=true;
vis[i-1]=true;
}
else
{
if(flag==1){
flag=0;
if(count%2==0)
hash[a[i-1]]+=count/2;
else
hash[a[i-1]]+=count/2+1;
count=1;
}
}
}
for(int i=0;i<n;i++)
{
if(!vis[i])
{ // cout<<i<<" ";
hash[a[i]]++;
}
}
long int mx=0;
int ans=0;
for(int i=1;i<=1000;i++)
{
if(mx<hash[i])
{
mx=hash[i];
ans=i;
}
}
cout<<ans<<endl;
}

return 0;

}

[anon48051421]

i don’t understand why you are unnecessarily iterating from 1 to 1000
Is my solution wrong (i got AC asking about any testcases it may fail)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
void solve(){
int n, i, _ip; cin >> n;
vector a;
map <int, int > hash;
for(i=0; i<n; ++i) cin >> _ip, a.pb(_ip);
int prev = a[0];
hash[prev]++;
for(i=1; i<n; ++i) {
if(a[i]==prev) {
prev = -100;
continue;
}
hash[a[i]]++;
prev = a[i];
}
int max =-1, entry = -1;
for(auto x : hash) {
if(max < x.second) {
max = x.second;
entry = x.first;
}
}
cout << entry << endl;
}

int main(){
int _t;
cin >> _t;
while(_t–)
solve();
}

[rt24]

can someone please explain why this is incorrect

https://www.codechef.com/viewsolution/32350962

[rt24]

have just used multiple if statements

[better_sleep]

@rishup_nitdgp Can you tell how to approach bonus problem?
Contest had good problems. Thank you

[rishup_nitdgp]

Let suppose, f(n) denotes the valid subsequences ends at n^{th} index and you know the answer for all indexes less than n, then f(n) would be the \sum_{i=0}^{n-1}(f(i)\space * \space(A[i] == A[n])) \space + \space 1. Now, the answer to the problem is \sum_{i=0}^{n-1}f(i),

[dewanshnigam]

Here is my logic.

import java.util.;
import java.io.;
class Solution
{
static InputReader in=new InputReader(System.in);
static OutputWriter out=new OutputWriter(System.out);
static StringBuilder sb=new StringBuilder();
static long MOD = (long)(998244353);
// Main Class Starts Here
public static void main(String args[])throws IOException
{
// Write your code.
int t = in();
while(t–>0) {
int n=in();
int a[] = an(n);
int count[]=new int[1001];
int lastIndex[]=new int[1001];
Arrays.fill(lastIndex, -2);
for(int i=0;i<n;i++) {
int li = lastIndex[a[i]];
if(li == (i-1)) {
continue;
}
lastIndex[a[i]] = i;
count[a[i]]++;
}
int type = 0;
int max = -1;
for(int i=0;i<count.length;i++) {
if(max < count[i]) {
max = count[i];
type = i;
}
}
app(type+“\n”);
}
out.printLine(sb);
out.close();
}

static class Pair{
	int val;
	int index;
	public Pair(int val,int index) {
	this.val=val;
	this.index = index;
	}
}
           
public static long rev(long n) {
	if(n<10L)
		return n;
	long rev = 0L;
	while(n != 0L) {
		long a = n % 10L;
		rev = a + rev*10L;
		n /= 10L;
	}
	return rev;
}

public static long pow(long a,long b) {
	if(b==0)
		return 1L;
	if(b==1)
		return a % MOD;
	long f = a * a;
	if(f > MOD)
		f %= MOD;
	long val = pow(f, b/2) % MOD;
	if(b % 2 == 0)
		return val;
	else {
		long temp = val * (a % MOD);
		if(temp > MOD)
			temp = temp % MOD;
		return temp;
	}
}

public static int gcd(int a,int b) {
	if(b==0)
		return a;
	return gcd(b, a%b);
}

public static int[] an(int n) {
	int ar[]=new int[n];
	for(int i=0;i<n;i++)
		ar[i]=in();
	return ar;
}

public static int in() {
	return in.readInt();
}

public static long lin() {
	return in.readLong();
}    

public static String sn() {
	return in.readString();
}

public static void prln(Object o) {    	
	out.printLine(o);
}

public static void prn(Object o) {    	
	out.print(o);
}

public static int getMax(int a[]) {
	int n = a.length;
	int max = a[0];
	for(int i=1; i < n; i++) {
		max = Math.max(max, a[i]);
	}
	return max;
}

public static int getMin(int a[]) {
	int n = a.length;
	int min = a[0];
	for(int i=1; i < n; i++) {
		min = Math.min(min, a[i]);
	}
	return min;
}

public static void display(int a[]) {
	out.printLine(Arrays.toString(a));
}    

public static HashMap<Integer,Integer> hm(int a[]){
	HashMap<Integer,Integer> map=new HashMap<>();
	for(int i=0; i < a.length;i++) {
		int keep = (int)map.getOrDefault(a[i],0);
		map.put(a[i],++keep);
	}
	return map;
}

public static void app(Object o) {
	sb.append(o);
}

public static long calcManhattanDist(int x1,int y1,int x2,int y2) {
	long xa = Math.abs(x1-x2);
	long ya = Math.abs(y1-y2);
	return (xa+ya);
}

static class Point
{
	int x;
	int y;
	String dir;
	public Point(int x,int y,String dir) {
		this.x=x;
		this.y=y;
		this.dir=dir;
	}
}    


static class InputReader {
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int readInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public long readLong() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public String readString() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }

    public boolean isSpaceChar(int c) {
        if (filter != null)
            return filter.isSpaceChar(c);
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public String next() {
        return readString();
    }

    public interface SpaceCharFilter {
        public boolean isSpaceChar(int ch);
    }
}

static class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }

    public void print(Object...objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0)
                writer.print(' ');
            writer.print(objects[i]);
        }
    }

    public void printLine(Object...objects) {
        print(objects);
        writer.println();
    }

    public void close() {
        writer.close();
    }
} 

}

[anon39640204]

Please let me know where I am wrong

https://www.codechef.com/viewsolution/32344523

[pulkit_mittal]

Store the frequency of each element in a map( Can’t use array as max. value is 1e9).
Modify the way of increasing frequency, i.e. , Skip a[i+1] if a[i] == a[i+1].
Output max. frequency element.
My solution
I used array to store freq. during contest. Should be replaced by map for bonus problem.

[akshy_8]

Why this solution is accepted?? I just want to know , how this solution is able to find minimum of all maximums.

#include<bits/stdc++.h>
#define pb(x) push_back(x)
#define vi vector
#define ll long long
#define mp make_pair
#define vvi vector<vector>
#define st stack
#define ln “\n”
#define all(x) x.begin(),x.end()
#define sz(x) x.size()
#define bg(x) x.begin()
#define ed(x) x.end()
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i–)
#define atob(i,a,b) for(int i=a;i<=b;i++)
#define btoa (i,a,b) for(int i=b;i>=a;i–)

using namespace std;

int main()
{
ios_base::sync_with_stdio(!cin.tie(0));

        int t ;
        cin>>t;
         while(t--)
      {
          int x, max=-1;
          int n; cin>>n;
          int a[n],b[1001]={};
          rep(i,n){cin>>a[i];}
          rep(i,n){b[a[i]]++; if(a[i]==a[i+1])i++;}
          rep(i,1001){if(max<b[i]){max=b[i];x=i;}}
         cout<<x<<ln;
      }       
  
 return 0;

}

[rishup_nitdgp]

Just try to dry run this code with sample input given in the problem and you will understand that this code is same as mine but with less memory. The solution is slitly wrong as you are accessing (a[n]) which should result in error but for cakewalk problem, it is too harsh to prevent this type of error.

[akshy_8]

no bro I never accessed the a[n] element … You wrong observed . It was in my macro description rep(i,n) i<n.

Well I must be actually sorry for that , for not providing proper comments …

Finally , I got the point after dry running . The max is only changing values when it found other element strictly greater than itself otherwise It stores the first occurence …

Thanks bro

[rishup_nitdgp]

@akshy_8 But you are accessing a[i+1].

[coodieaniket]

https://www.codechef.com/viewsolution/32642861

Its a DP solution.

[pkrz]

Can someone tell me what’s wrong with this solution?

import java.util.;
import java.lang.;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class CodeChef{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int k,var;
ArrayList resulttab=new ArrayList() ;
for(int i=0;i<n;++i) {
k=sc.nextInt();
ArrayList table=new ArrayList() ;
for(int z = 0;z<1001;z++) {
table.add(0);
}
int last=-1;
int lb=0;
for(int m=0;m<k;++m) {
var=sc.nextInt();
if(m==0) {table.set(var, table.get(var)+1);last=var;lb=1;}
else if(last==var &&lb==1) lb=0;else
{table.set(var, table.get(var)+1);last=var;lb=1;}
}
int result=Collections.max(table);
resulttab.add(table.indexOf(result));
}
for(int y=0;y<resulttab.size();++y) {
System.out.println(resulttab.get(y));
}

}

}

[pkrz]

yes, i forgotten to close Scanner - thnx

[deathspeed]

can anyone tell me why i have getting wrong ans on submitting this code?

#include<iostream.h>
using namespace std;

int finds(int arr[],int a){
int c=(sizeof(arr)),n=0;
for(int i=0;i<=c;i++){
if(a==arr[i])
n++;
}
if(n==0)
return 1;
else
return 0;

}

int number(int arr[]){
int c=(sizeof(arr)),arr1[c],x=0,y=0,z=0,d;
arr1[x]=arr[0];
for(int j=0;j<=c;j++){
if(finds(arr1,arr[j])==1||j==0){
x++;
arr1[x]=arr[j];
for(int i=0;i<=c;i++){
if(arr[i]==arr[j]){
y++;
i++;
}

    }
    if(y==z){
        if(arr[j]<arr[d])
            d=j;
    }
    if(j==0){
    z=y;
    d=j;
    }
    if(y>z){
        z=y;
        d=j;
    }
    y=0;

  }

}
return d;
}

int main(){
int n,c=0,y=0,z=0;
cin>>n;
while(c<n){
cin>>z;
int arr[z];
for(int i=0;i<z;i++)
cin>>arr[i];
y=number(arr);
cout<<arr[y]<<"\n";
c++;
}
return 0;
}