MAXSC - Editorial

PROBLEM LINK:

Practice
Contest

Author: Hruday Pabbisetty
Tester: Alexey Zayakin
Editorialist: Oleksandr Kulkov

DIFFICULTY:

CAKEWALK

PREREQUISITES:

None

PROBLEM:

You’re given N sequence A_1, \dots, A_N, each containing N elements. You should pick one element from each sequence (element picked from A_i is E_i). E_i should be strictly greater than E_{i-1}. Your task is to compute maximum possible E_1+E_2+\dots+E_N or output -1 if it’s impossible to pick such sequence.

QUICK EXPLANATION

Greedily take maximum possible E_i starting at E_n and ending at E_1.

EXPLANATION:

Let’s look at E_N. If there is element in A_N greater than E_N then we should pick it since it will not change that E_i is increasing but it will increase the sum. So E_N shoud be maximum possible element in A_N. Continuing by induction we can see that for E_i we should pick largest possible element, i.e. E_i is largest among all A_i < E_{i+1}. In this way one can solve problem in O(N^2) by picking E_i from N^{th} to 1^{st} and finding largest acceptable A_i each time. Example of solution:

int e[n];
e[n - 1] = *max_element(a[n - 1], a[n - 1] + n);
int64_t sum = e[n - 1];
for(int i = n - 2; i >= 0; i--) {
    e[i] = 0;
    for(int j = 0; j < n; j++) {
        if(a[i][j] < e[i + 1]) {
            e[i] = max(e[i], a[i][j]);
        }
    }
    if(e[i] == 0) {
        cout << -1 << endl;
        return;
    }
    sum += e[i];
}
cout << sum << endl;

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

RELATED PROBLEMS:

We don’t have a max function in c. So, what I did was sorted all the sequences in 2d array and proceeded. Yet somehow my solution showed runtime error. Here’s my solution. Can you suggest possible changes.

My solution received a score of 82. Though my approach might not be a efficient one, I would like to know the failing case.
https://www.codechef.com/viewsolution/17017153

@admin @hruday968 @alex_2oo8: Any test case which you can provide?

@admin provide testcases after the contest … it would be good for us.
if is very very very very hard to find just a small mistake
there should not be any problem in providing test cases after the contest…
bring some changes in your policy … now

@worldunique
I have tested my code against the 3 test cases and it gives -1 for all. I have pasted my code below:
using namespace std;

bool sortinrev(const pair<int,int> &a, 
               const pair<int,int> &b)
{
       return (a.first > b.first);
}

int main() {
     
     int i,j,n,t;
     cin>>t;
     while(t--){
     cin>>n;
     long long int x;
     vector< pair <long long int,int>  > vect;
     for(i=0;i<n;i++)
       for(j=0;j<n;j++){
       	cin>>x;
       	vect.push_back( make_pair(x,i) );

       }

        sort(vect.begin(), vect.end(), sortinrev);
        
       int n1=n-1;	    
       long long int res=0;
        for(i=0;i<n*n;i++){
        	if(vect[i].second==n1){
	        res+=vect[i].first;
	        n1--;	
	        if(n1<0)
	           break;
        	}
        }
        if(n1<0)
          cout<<res<<endl;
        else
         cout<<"-1\n";
           
     }
     return 0;
}

why this code is not working?it has no errors and it is giving correct answers…
#include<stdio.h>
int main()
{
long long int t,h,n,r,i,j,temp,sum,count;

scanf("%lld",&t);
while(t--)
{

    scanf("%lld",&n);
    r=-1;sum=0;count=0;

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

h=-1;
for(j=0;j<n;j++)
{

            scanf("%lld",&temp);

            if(temp>h)
             h=temp;

        }

          if(h>r)
          {   

              sum=sum+h;
              count=count+1;
              r=h;

          }
          else
          {

              printf("-1\n");
              break;

          }
    }

    if(count==n)
     printf("%lld %lld\n",count,sum);
}

}

Can anybody help me? Why this code doesn’t work? I tried all the possible cases I can think of

public static void main(String[] args) {
    FastReader in = new FastReader();

    int t = in.nextInt();

    for (int i = 0; i < t; i++) {
        int n = in.nextInt();
        int[][] s = new int[n][n];

        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                s[j][k] = in.nextInt();
            }
            Arrays.sort(s[j]);
        }

        int sum = s[n - 1][n - 1];
        int curr = s[n - 1][n - 1];

        try {
            for (int j = 1; j < n; j++) {
                int sub = 1;
                while (true) {
                    int x = s.length - 1 - j;
                    int y = s[s.length - 1 - j].length - sub;

                    if (curr > s[x][y]) {
                        curr = s[x][y];
                        sum += curr;
                        break;
                    } else {
                        sub++;
                    }
                }
            }
            
            System.out.println(sum);
        } catch (ArrayIndexOutOfBoundsException x) {
            System.out.println(-1);
            break;
        }
    }
}

increase the size of array
in n element size u r filling n+1 elemenets
try quick sort rather than simple sort

@ksanoop
try this test case

1

5

5 5 5 5 5

5 5 5 5 5

24 45 85 69 58

6 6 6 6 666

88888 6 6 6 6

output on ideone is 89649 but it should be -1

the above is your code , just check it

whats wrong with my code

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

class cd94
{

public static void main(String args[])throws IOException
{	
	try{
	int i,j;
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int T = Integer.parseInt(br.readLine());
	
	while(T>0)
	{
		int N = Integer.parseInt(br.readLine());
		int sum = 0;
		LinkedList<Integer> list[] = new LinkedList[N];
		
		for(i=0;i<N;i++)
		{
		list[i] = new LinkedList<Integer>();	
		String input1 = br.readLine();
		String[] strs1 = input1.trim().split("\\s+");
		int arr1[]  = new int[strs1.length];
		for (j = 0;j< strs1.length; j++)
		{			
		arr1[j] = Integer.parseInt(strs1[j]);	
		list[i].add(arr1[j]);
		}
		
		
		}
		
		for(i=0;i<N;i++)
		{
			Collections.sort(list[i]);
			
		}
		
		sum = sum + list[N-1].get(N-1);
		Stack<Integer> stack = new Stack<>();
		stack.push(list[N-1].get(N-1));
		int flag =1;
		for(i=N-2;i>=0;i--)
		{
			 Integer[] a = new Integer[N];  
			 Integer[] b =  list[i].toArray(a);  
				
			 Integer lb = lowerBound(b,N-1,stack.peek());		 
			
			 if(lb==0 && stack.peek()<list[i].get(lb))
			 {	 flag = 0;
				 break;
			 }else if(lb==0 && stack.peek()>list[i].get(lb))
			 {
				 sum = sum + list[i].get(lb);
				 stack.push(list[i].get(lb));
			 }else if(lb!=N-1)
			 {
		     stack.push(list[i].get(lb-1));
		     sum = sum + list[i].get(lb-1);			
			 }else
			 {
		     stack.push(list[i].get(lb));
		     sum = sum + list[i].get(lb);	
			 }
		}
		
		if(flag==0)
		{
			System.out.println(-1);
		}else
		{
			System.out.println(sum);
		}
		
		
		T--;
	}
	
	}catch(Exception e)
	{
		
	}
	
	
	
	
}


   public static Integer lowerBound(Integer[] array, Integer length, Integer value) {
    Integer low = 0;
    Integer high = length;
    while (low < high) {
        final Integer mid = (low + high) / 2;
        if (value <= array[mid]) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

}

Why we are checking element from the bottom to top? Why we not checking from top to bottom?

CAN WE FIND THE ELEMENT JUST SMALLER THAN MAX USING BINARY SEARCH …
I TRIED A LOT BUT ALL IN VAIN …
EVERYTIME I CAME OUT TO FIND SMALLEST ELEMENT INSTEAD…
SOMEONE PLZ HELP…