×

# 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[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:

This question is marked "community wiki".

4★melfice
811937
accept rate: 0%

19.8k350498541

 0 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. answered 21 Jan '18, 18:08 9 accept rate: 0% increase the size of array in n element size u r filling n+1 elemenets try quick sort rather than simple sort (11 Feb '18, 00:45)
 0 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? answered 10 Feb '18, 23:58 11 accept rate: 0%
 0 @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 answered 11 Feb '18, 00:35 129●7 accept rate: 0%
 0 @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 &a, const pair &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 > vect; for(i=0;i>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

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


}

1
accept rate: 0%

 0 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; } } }  answered 02 Mar, 22:25 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,688
×191
×2
×1

question asked: 11 Jan '18, 01:43

question was seen: 1,704 times

last updated: 02 Mar, 22:25