MAXSC - Editorial

cakewalk
editorial
hruday968
jan18
maxsc

#1

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* = 0;
    for(int j = 0; j < n; j++) {
        if(a*[j] < e[i + 1]) {
            e* = max(e*, a*[j]);
        }
    }
    if(e* == 0) {
        cout << -1 << endl;
        return;
    }
    sum += e*;
}
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:


#2

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.


#3

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?


#4

@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


#5

@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*.second==n1){
	        res+=vect*.first;
	        n1--;	
	        if(n1<0)
	           break;
        	}
        }
        if(n1<0)
          cout<<res<<endl;
        else
         cout<<"-1

";

     }
     return 0;
}

#6

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

");
break;

          }
    }

    if(count==n)
     printf("%lld %lld

",count,sum);
}
}


#7

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;
        }
    }
}

#8

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


#9

@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