You are not logged in. Please login at www.codechef.com to post your questions!

×

MAXSC - Editorial

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:

This question is marked "community wiki".

asked 11 Jan '18, 01:43

melfice's gravatar image

4★melfice
811937
accept rate: 0%

edited 15 Jan '18, 21:24

admin's gravatar image

0★admin ♦♦
19.8k350498541


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.

link

answered 21 Jan '18, 18:08

pajamatester's gravatar image

1★pajamatester
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) worldunique3★

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?

link

answered 10 Feb '18, 23:58

ksanoop53's gravatar image

2★ksanoop53
11
accept rate: 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

link

answered 11 Feb '18, 00:35

worldunique's gravatar image

3★worldunique
1297
accept rate: 0%

edited 11 Feb '18, 00:54

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

answered 11 Feb '18, 11:06

ksanoop53's gravatar image

2★ksanoop53
11
accept rate: 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

https://ideone.com/KPwzY4

the above is your code , just check it

(11 Feb '18, 15:03) worldunique3★

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

}

link

answered 30 Sep '18, 11:21

nithishmreddy's gravatar image

2★nithishmreddy
1
accept rate: 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;
        }
    }
}
link

answered 02 Mar, 22:25

skywatcher's gravatar image

0★skywatcher
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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