 MAXSC - Editorial

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

CAKEWALK

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:

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

";

}
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

");
break;

}
}

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

",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) {

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;
int T = Integer.parseInt(br.readLine());

while(T>0)
{
int N = Integer.parseInt(br.readLine());
int sum = 0;

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

}

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?