Beautiful Partitions Codechef Solution

Hello Programmers In this post, you will know how to solve the Beautiful Partitions Codechef Solution.

Beautiful Partitions Codechef Solution
Beautiful Partitions Codechef Solution

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Codechef by yourself. If you find any difficulty after trying several times, then you can look for solutions.

Problem

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 BrokenProgrammers. This tutorial is only for Educational and Learning purposes.

Note:- I compile all programs, if there is any case program is not working and showing an error please let me know in the comment section. If you are using adblocker, please disable adblocker because some functions of the site may not work correctly.

Next: Bodybuilder Codechef Solution

Leave a Reply

Your email address will not be published. Required fields are marked *