Beautiful Partitions Codechef Solution

Hello coders, today we are going to solve Beautiful Partitions Codechef Solution.

Codechef solutions

Problem

Beautiful Partitions Codechef Solution: Sidaga calls a sequence beautiful if the sum of elements of this sequence is strictly positive.

Kaspers gave Sidaga a sequence A1,A2,…,ANA1,A2,…,AN and asked him to partition it into exactly KK non-empty contiguous subsequences such that each element of AA belongs to exactly one subsequence and all KK subsequences are beautiful.

Sidaga is getting ready for his wedding – he is busy learning how to dance, so he cannot solve this problem. Can you help him?

Input

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains two space-separated integers NN and KK.
  • The second line contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.

Output

For each test case, print a single line containing the string "YES" if it is possible to partition AA into KK contiguous subsequences or "NO" otherwise.

If it is possible to partition AA, print a second line containing KK space-separated integers B1,B2,…,BKB1,B2,…,BK denoting the sizes of the subsequences, where 1≤Bi1≤Bi for each valid ii and B1+B2+…+BK=NB1+B2+…+BK=N. The first B1B1 elements of AA belong to the first subsequence, the next B2B2 elements belong to the second subsequence and so on.

If there is more than one solution, you may print any one.

Constraints

  • 1≤T≤1,0001≤T≤1,000
  • 1≤K≤N≤5⋅1051≤K≤N≤5⋅105
  • 0≤|Ai|≤1090≤|Ai|≤109 for each valid ii
  • the sum of NN over all test cases does not exceed 5⋅1055⋅105

Example Input

2
4 2
2 -1 1 3
2 2
1 -1

Example Output

YES
1 3
NO

Explanation

Example case 1:

In first case, there are more than one options. Another such valid option is {2,2}.

In second case, it is not possible.

Beautiful Partitions – CodeChef Solution in JAVA

import java.io.PrintWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Arrays;
import java.util.ArrayDeque;
import java.util.Stack;
import java.util.HashMap;
import java.util.TreeSet;
import java.util.TreeMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.ArrayDeque;
import java.util.Comparator;
import static java.lang.Math.min;
import static java.lang.Math.max;
import static java.lang.Math.sqrt;
import static java.lang.Math.pow;
import static java.lang.Math.abs;
import static java.lang.Integer.MIN_VALUE;
import static java.lang.Integer.MAX_VALUE;
public class Main {
    static boolean ONLINE_JUDGE = false;
    static Fast f = new Fast();
    static PrintWriter out = new PrintWriter(System.out);
    static boolean TEST_CASES = true;
    static int mod1 = (int)1e9+7;
    static int mod2 = 998244353;
    static long[] endElement;
    static int[] len;
    static void solve() {
          int n = ri(), k = ri();
          int[] a = ra(n);
          long sum = 0;
          ArrayList<long[]> psum = new ArrayList<>();
          sum += a[0];
          if(sum>0) {psum.add(new long[]{sum,0l});}
          for(int i = 1; i < n; i++) {
             sum += a[i];
             if(sum>0) psum.add(new long[]{sum,i*1l});
          }
          if(sum>0){
              int ans = LIS(psum);
              if(ans>=k) {
                    out.println("YES");
                    ArrayList<Integer> candidateAns = new ArrayList<>();
                    candidateAns.add(psum.size()-1);
                    for(int i = psum.size()-2; i > -1 && candidateAns.size()<k; i--) {
                       int prev = candidateAns.get(candidateAns.size()-1);
                         if(psum.get(i)[0]<psum.get(prev)[0] && len[i]==len[prev]-1){
                          candidateAns.add(i);
                         }
                    }
                    int prev = -1;
                    for(int i = 0; i < k; i++) {
                      if(i>0) out.print(" ");
                      int ind = candidateAns.get(k-1-i);
                      int cur = (int)(psum.get(ind)[1]);
                      out.print(cur-prev);
                      prev = cur;
                    }
                    out.println();
                    return;
              }
          }
          out.println("NO");
    }
    /*LIS in nlog(n) */
    static int LIS(ArrayList<long[]> arr){
      if(arr.size()==0) return 0;
      int size = arr.size();
      /*
         Here, endElement array contains the end element of increasing sequence.
         i.e.  endElement[i] contains the end element of increasing sequence of length i+1
      */
      endElement = new long[size];
      len = new int[size];
      int lisLen = 0;
      endElement[0] = arr.get(0)[0];
      lisLen = 1;
      len[0] = 1;
      int ans = lisLen;
      for(int i = 1; i < size; i++) {
          if(arr.get(i)[0]<endElement[0]) {
             endElement[0] = arr.get(i)[0];
             ans = 1;
          }
          else if(arr.get(i)[0]>endElement[lisLen-1]) {
             endElement[lisLen++] = arr.get(i)[0];
             ans = lisLen;
          }
          else {
            int index = binarySearch(endElement,-1,lisLen-1,arr.get(i)[0]);
            endElement[index] = arr.get(i)[0];
            ans = index+1;
          }
          len[i] = ans;
      }
      return ans;
    }
    static int binarySearch(long[] arr, int l, int r, long key) {
        int mid = l+(r-l)/2;
        while(l+1<r) {
           if(arr[mid]>key) r = mid;
           else l = mid;
           mid = l+(r-l)/2;
        }
        return r;
    }
    public static void main(String[] args)throws Exception{
      if(TEST_CASES){
          int t = ri();
          while(t-->0){
            solve();
          }
      }
      else {
        solve();
      }
      out.close();
    }
    static int nod(long l) {
       if(l>=1000000000000000000l) return 19;
       if(l>=100000000000000000l) return 18;
       if(l>=10000000000000000l) return 17;
       if(l>=1000000000000000l) return 16;
       if(l>=100000000000000l) return 15;
       if(l>=10000000000000l) return 14;
       if(l>=1000000000000l) return 13;
       if(l>=100000000000l) return 12;
       if(l>=10000000000l) return 11;
       if(l>=1000000000) return 10;
       if(l>=100000000) return 9;
       if(l>=10000000) return 8;
       if(l>=1000000) return 7;
       if(l>=100000) return 6;
       if(l>=10000) return 5;
       if(l>=1000) return 4;
       if(l>=100) return 3;
       if(l>=10) return 2;
       return 1;
    }
    static int ri() {
      return f.nextInt();
    }
    static long rl() {
      return f.nextLong();
    }
    static String rs(){
      return f.next();
    }
    static String rS(){
       return f.nextLine();
    }
    static char rc(){
         return f.next().charAt(0);
    }
    static int[] ra(int n) {
      int[] a = new int[n];
      for(int i = 0;i<n;i++) a[i] = ri();
      return a;
    }
    static long[] ral(int n) {
      long[] a = new long[n];
      for(int i = 0;i<n;i++) a[i] = rl();
      return a;
    }
    static char[] rac(){
        char[] c = rs().toCharArray();
        return c;
    }
    static int[][] rm(int n, int m){
       int[][] mat = new int[n][m];
       for(int i = 0; i < n; i++) mat[i] = ra(m);
       return mat;
    }
    static char[][] rmc(int n){
      char[][] cmat = new char[n][];
      for(int i = 0; i < n;i++) cmat[i] = rac();
      return cmat;
    }
    static void sort(int[] a) {
      ArrayList<Integer> list=new ArrayList<Integer>();
      for (int i:a) list.add(i);
      Collections.sort(list);
      for (int i=0; i<a.length; i++) a[i]=list.get(i);
    }
    static void sort(double[] a) {
      ArrayList<Double> list=new ArrayList<Double>();
      for (double i:a) list.add(i);
      Collections.sort(list);
      for (int i=0; i<a.length; i++) a[i]=list.get(i);
    }
    static class Fast{
       public BufferedReader br;
       public StringTokenizer st;
       public Fast(){
            try{
                br = ONLINE_JUDGE? (new BufferedReader(new FileReader("input.txt"))):(new BufferedReader(new InputStreamReader(System.in)));
            }
            catch(Exception e){
              throw new RuntimeException(e);
            }
       }
       String next(){
            while(st==null || !st.hasMoreTokens()){
                 try{
                      st=new StringTokenizer(br.readLine());
                 }
                 catch(IOException e){
                      throw new RuntimeException(e);
                 }
            }
                 return st.nextToken();
            }
       int nextInt(){
            return Integer.parseInt(next());
       }
       long nextLong(){
            return Long.parseLong(next());
       }
       double nextDouble(){
            return Double.parseDouble(next());
       }
       String nextLine()
          {
              String str = "";
              try
              {
                  str = br.readLine();
              }
              catch (IOException e)
              {
                  e.printStackTrace();
              }
              return str;
          }
     }
}

Beautiful Partitions – CodeChef Solution in CPP

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
    fast;
}
struct BIT
{
    vvi b;
    int n;
    BIT(int N)
    {
        n = N;
        b.resize(n + 1);
        for (int i = 0;i<=n;i++)b[i] = {-inf,-inf};
    }
    void update(int i,vi v)
    {
        for (++i;i<=n;i += i & (-i))b[i] = max(b[i],v);
    }
    vi query(int i)
    {
        vi ret = {-inf,-inf};
        for (++i;i>0;i -= i & (-i))ret = max(ret,b[i]);
        return ret;
    }
};
int32_t main()
{
    setIO();
    int t;
    cin>>t;
    while (t--){
        int n,k;
        cin>>n>>k;
        vl p(n + 1);
        for (int i = 1;i<=n;i++){
            cin>>p[i];
            p[i] += p[i - 1];
        }
        vl actP = p;
        sort(p.begin(),p.end());
        BIT bit(n);
        vvi dp(n + 1,vi(2));
        bit.update((int)(lower_bound(p.begin(), p.end(), 0) - p.begin()),{0,0});
        for (int i = 1;i<=n;i++){
            int j = lower_bound(p.begin(),p.end(),actP[i]) - p.begin();
            dp[i] = bit.query(j - 1);
            dp[i][0]++;
            bit.update(j,{dp[i][0],i});
        }
        if (dp[n][0] < k){cout<<"NO\n";continue;}
        vi all;
        for (int i = n;i>0;i = dp[i][1])
            all.pb(i - dp[i][1]);
        reverse(all.begin(),all.end());
        assert((int)all.size() >= k);
        while ((int)all.size() > k){
            int x = all.back();
            all.pop_back();
            all.back() += x;
        }
        cout<<"YES\n";
        for (int v:all)cout<<v<<" ";
        cout<<'\n';
    }
    return 0;
}

Disclaimer: The above Problem (Beautiful Partitions) is generated by CodeChef but the solution is provided by  Chase2learn.This tutorial is only for Educational and Learning purpose.

Leave a Comment