INCRDEC - Editorial

editorial
, , ,
44

//Can anyone help me to know where am I going wrong
// I adapted the same ideology as given in this editorial but still got WA

`import java.util.*;
public class q2n{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int t=sc.nextInt();
for(int z=0;z<t;z++){
int n=sc.nextInt();
Integer a[]=new Integer[n];
for(int i=0;i<n;i++)
a[i]=sc.nextInt();
Arrays.sort(a);
boolean flag=true;
for(int i=0;i<n-1;i++){
if(a[i]==a[i+1])
flag=false;
}
if(flag==true){
System.out.println(“YES”);
for(int i=0;i<n;i++)
System.out.print(a[i]+" “);
}
else{
boolean f=true;
for(int i=0;i<n-2;i++){
if(a[i]==a[i+1] && a[i]==a[i+2]){
f=false;
break;
}
}
if(a[n-2]==a[n-1])
f=false;
if(f==false)
System.out.print(“NO”);
else{
ArrayList al=new ArrayList<>();
for(int i=0;i<n-1;i++){
al.add(a[i]);
if(a[i]==a[i+1])
i++;
}
Arrays.sort(a,Collections.reverseOrder());
for(int i=0;al.size()<n;i++){
al.add(a[i]);
if(a[i]==a[i+1])
i++;
}
System.out.println(“YES”);
for(int i=0;i<n;i++)
System.out.print(al.get(i)+” ");
}
}
System.out.println();
}
}
}

45

I am getting runtime error on running my code but it is getting successfully submitted.why this is happening so?
plz help

my code:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t --)
{
int flag=0;
int n;
cin>>n;
int a[n];
int maxx=0;
map<int,int>m;

   for(int i=0;i<n;i++)
    {
        cin>>a[i];
        m[a[i]]++;
        if(m[a[i]]>=3)
        {
            
            flag=1;
        }
        if (a[i]>maxx)
        {
            maxx=a[i];
        }
        
    }
      if (flag==1)
      {
          cout<<"NO"<<endl;
          continue;
      }
      if (m[maxx]>1)
      {
          cout<<"NO"<<endl;
          continue;
      }
      
          cout<<"YES"<<endl;
          
          for (auto i=m.begin();i!=m.end();i++)
          {
              cout<<i->first<<" ";
              i->second-=1;
          }
          
          for (auto i=m.rbegin();i!=m.rend();i++)
          {
              if(i->second!=0)
                  cout<<i->first<<" ";
              
          }
          cout<<endl;
      
      
  
}

}

46

Nice and simple :smile:
I did it a similar way here . The difference is I used the same loop for the following:

  • Adding to the 1st list

  • Adding to the second list

  • Checking for violations

47
I think it will take less than o( n logn ) time 
#--------------------fast io----------------------------------
import sys
def finp(): return sys.stdin.readline() 
def fop(s): return sys.stdout.write(str(s)+"\n")
def fintinp(): return int(sys.stdin.readline())
def flistintinp(): return list(map(int,finp().split()))

#----------------------simple io------------------------------
def op(s): return s
def inp(): return input()
def intop(s): return int(s)
def intinp(): return int(input())
def listintinp(): return list(map(int,inp().split()))
def listinp(): return list(map(str,inp().split()))

#-----------------sieve for prime computing------------------
import math
primelists=[]
maxprecomprimeval=100001
from math import ceil,sqrt
mysievelists=[i for i in range(maxprecomprimeval)]
def primeprecomputer():
  for i in range(2,math.ceil(math.sqrt(maxprecomprimeval))):
    if(mysievelists[i]==i):
      for j in range(i*i,maxprecomprimeval,i):
        if(mysievelists[j]==j):
          mysievelists[j]=i
  for i in range(2,maxprecomprimeval):
    if(mysievelists[i]==i):
        primelists.append(mysievelists[i])
  return primelists

#------------call--primeprecomputer()--(end)------------------
#---------------------bisection function---------------------
from bisect import bisect_right,bisect_left
def bisectright(lists,nbr):return bisect_right(lists,nbr)
def bisectleft(lists,nbr):return bisect_left(lists,nbr)

#-------------------------mod--------------------------------- 
MOD=100000007

#-------------------MINIMUM PRIME FACTOR---------------------
mpflists=[]
def mpf(n):
  k=0
  primeprecomputer()
  while(n!=1):
    print(mysievelists[n])
    mpflists.append(mysievelists[n])
    n//=mysievelists[n]
    k+=1 
  return mpflists

#-------------------CODE STARTS HERE------------------------------

    
"""# cook your dish here
@abhishek kumar
abhishek__2007
                            e  
                          *    *
                        d        c  
                      *            *
                    o                h 
                  *   @abhishek__2007  *
                c                        e 
                ************f*************                        

"""
for __ in range(fintinp()):
  f=[]
  s=[]
  n=intinp()
  lists=flistintinp()
  lists.sort()
  if(n==1):
    print("YES")
    print(lists[0])
    continue
  if(lists[-1]==lists[-2]):
    print("NO")
    continue 
  i=0 
  br=0 
  while(i<n):
    ct=0 
    if(i+1<n and lists[i]==lists[i+1]):
      ct=2 
      if(i+2<n):
        if(lists[i]==lists[i+2]):
          print("NO")
          br=1
          break 
        else:
          f.append(lists[i])
          s.append(lists[i])
    else:
      ct=1 
      f.append(lists[i])
    i+=ct 
  if(br==0):
    print("YES")
    print(*f,end=" ")
    s.reverse()
    print(*s)
48

so what to do then…

49

Thanks @sachinpant1326

1 Like
50

It worked @pankaj_chopra . Didn’t know it will make such a huge difference. Thank you so much.

51

Hi,
I don’t know why my code is giving me a TLE. I have only used single for loop which does work in O(n) and done rest of the work via map which does work in O(1).
Plz help why is O(n) not working here.
https://www.codechef.com/viewsolution/34932382

52

Do not print elements of array one by one. Store it in a String builder object and then print.
CodeChef: Practical coding for everyone .
Also try to use fast I/O methods instead of Scanner.