CONFCAT - Editorial

PROBLEM LINK:

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

Author: S. Manuj Nanthan
Tester: Takuki Kurokawa
Editorialist: Nishank Suresh

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You are given an array C of N distinct integers, that is the result of a merge (as in mergesort) operation between two arrays A and B. Find any two appropriate arrays A and B, or claim that they don’t exist.

EXPLANATION:

One simple construction is as follows:

  • Let M = \max(C), and let i be the position of M in C, i.e, C_i = M.
  • Set A = [C_1, C_2, \ldots, C_{i-1}] and B = [C_i, C_{i+1}, \ldots, C_N].
  • If i = 1, then A is empty and we report -1 instead.

Why does this work?

  • Suppose i \gt 1, so M is not the first element.
    • M is the first element of B, and every element of A is less then M.
    • So, all of A will be pushed into C first, and then since A is now empty, all of B will be pushed in, which is what we want.
  • Suppose i = 1, so M is the first element.
    • Suppose a solution existed. Then, M must be the first element of either A or B.
    • Either way, all elements of the other array are less than M, and so will be pushed into C first.
    • However, since C_1 = M, this can only happen when one of the arrays is empty, which is not allowed.
    • So, no solution exists for this case.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Setter's code (Python)
t=int(input())

for _ in range(t):
    n = int(input())
    a = list(map(int,input().split()))
    if(max(a) == a[0]):
        print(-1)
    else:
        z = a.index(max(a))
        first = a[:z]
        second = a[z:]
        print(len(first))
        print(*first)
        print(len(second))
        print(*second)
Editorialist's code (Python)
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    m = max(a)
    if m == a[0]:
        print(-1)
        continue
    flag, b, c = 0, [], []
    for x in a:
        if x == m:
            flag = 1
        if flag == 0:
            b.append(x)
        else:
            c.append(x)
    print(len(b))
    print(*b)
    print(len(c))
    print(*c)

//why this code gives TLE

import java.util.*;

import java.lang.*;

import java.io.*;

class Codechef {

public static void main(String[] args) throws IOException {

    Scanner sc = new Scanner(System.in);

    int t = sc.nextInt();

    while (t-- > 0) {

        int n = sc.nextInt();

        int c[] = new int[n];

        int pos = -1;

        int max = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {

            c[i] = sc.nextInt();

            if (c[i] > max) {

                max = c[i];

                pos = i;

            }

        }

       

        if (pos == 0) {

            System.out.println(-1);

        } else {

            System.out.println(pos);

            for (int i = 0; i < pos; i++) {

                System.out.print(c[i] + " ");

            }

            System.out.println();

            System.out.println(n - pos);

            for (int i = pos; i < n; i++) {

                System.out.println(c[i] + " ");

            }

        }

    }

}

}

Because Sopln() is slow and you’re trying to access it N times. Try storing the answer in a StringBuffer and output that instead. It would be faster and hence not give TLE!

You can view my solution for reference, I had the same issue.

2 Likes

Mine Logic is also same but its in C++ and When i submit it just gives “Judge Error”. I dont know what is it. Can u plz look at my code.
#include<bits/stdc++.h>
using namespace std;
int main(){
long long t;
cin>>t;
while(t–){
long long n;
cin>>n;
long long a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
long long max=0,x;
for(int i=0;i<n;i++){
if(a[i]>max){
x=i;
max=a[i];
}
}
if(x==0){
cout<<-1<<endl;
continue;
}
cout<<x<<endl;
for(int i=0;i<x;i++){
cout<<a[i]<<" “;
}
cout<<endl;
cout<<n-x<<endl;
for(int i=x;i<n;i++){
cout<<a[i]<<” ";
}
cout<<endl;
}
return 0;
}

2 Likes

/* package codechef; // don’t place package name! */

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
{
BufferedReader sc= new BufferedReader(new InputStreamReader(System.in));
int T=Integer.parseInt(sc.readLine());
while(T-- >0){
int n=Integer.parseInt(sc.readLine());
StringTokenizer tk=new StringTokenizer(sc.readLine());
int arr[]=new int[n];
for(int i=0;i<n;i++)
arr[i]=Integer.parseInt(tk.nextToken());
ArrayList a=new ArrayList();
ArrayList b=new ArrayList();
boolean sw=false;
int max=arr[0];
a.add(max);
for(int i=1;i<arr.length;i++){
if(max<arr[i]){
max=arr[i];
sw=!sw;
if(sw)
b.add(max);
else
a.add(max);
continue;
}
if(sw)
b.add(arr[i]);
else
a.add(arr[i]);
}
if(a.size() == 0 || b.size() == 0)
System.out.println("-1");
else{
System.out.println(a.size());
System.out.println(a.toString().replace(",","").replace("[","").replace("]",""));
System.out.println(b.size());
System.out.println(b.toString().replace(",","").replace("[","").replace("]",""));
}
}
}
}

This is the exact solution that i was trying to submit earlier and this code passes all the given test cases but during the contest, only one of the test case was not getting passed and this was the test case:

Now here in the first test case:
6
7 6 3 8 2 9

The given test case can have two possible solution:
First==> The one given in the screenshot.
Second==>
4
7 6 3 9
2
8 2

The above answer also gives back the input correctly.
I request codechef peeps to have a look into this as my code passes all test cases and my solution should be considered.
Thanks :slight_smile:

The input can have negative integers, so initializing max = 0 is wrong. Initialize it with an appropriate negative number (like -1e9) and it should get AC.

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T;
    cin>>T;
    while(T--){
        long long int n;
        cin>>n;
        std::vector<int>c ;
        long long int max = INT_MIN;
        long long int pos;

        for(int i = 0; i < n; i++){
            cin>>c[i];
            if(c[i] > max){
                max = c[i];
                pos = i;
            }
        }
        
        cout<<endl<<pos<<endl;
        for(int i = 0; i < pos; i++)
            cout<<c[i]<<" ";
        cout<<endl<<n-pos<<endl;
        for(int i = pos; i < n; i++)
            cout<<c[i]<<" ";
        
        
        
        }
    return 0;
}

why is this giving tle?

I don’t see you printing -1 anywhere in the impossible cases, so that’s probably the reason for any weird behavior.

@d_pan
There are two bugs in your code

  1. Abv code gives SIGSEV error - segmentation fault - it happens when you try to access a memory that is not defined. Here, initially, you have simply declared a vector but have no elements stored in your vector and you are directly accessing an element in it that isn’t defined/doesn’t exist.
    Ways to Fix
    a) replace vector<int> c ; with vector<int>c(n), this will initialize the vector with n elements
    OR
    b) instead of taking input like : cin>>c[i]
    Replace it with :
    int x ;
    cin>>x;
    c.push_back(x)
  2. Logical Error : You haven’t consider the edge test case, as pointed out by @iceknight1093, when the pos of max is 0.
    Working code
1 Like

Scanner for input and Sopln() for output takes too much time.
Another way of taking fast input’s and output’s is by using BufferedReader for input and BufferedWriter for output, using them will remove TLE taking buffer space.
Check my solution here, its fast: CodeChef

ohh sorry I am dumb… thanks a lot for the reply…

ahh got it thanks a lot!