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
increase the size of array
in n element size u r filling n+1 elemenets
try quick sort rather than simple sort
@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;
}
@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
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;
}
}
}