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:
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.
@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
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;
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;
}
}
}
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…