GOTCHI - Editorial

editorial
, ,
1

Problem Link:

Setter: rjcode_1
Tester: rjcode_1
Editorialist: rjcode_1

DIFFICULTY:
Easy

PREREQUISITES:
Suffix Array, Greedy Approach, Sorting

Problem:

All submissions for this problem are available.Guruji says that gotchi is the answer to all of life’s problems. However, Sartaj knows how potent it really is . Given the array of measures of different potencies in a gotchi solution a1, a2…, an. Divide the array into p cups having non- empty consecutive subarrays such that every element of array is included in exactly one cup.
Let g(i) be the index of cup to which ith element belongs to (cups are numbered from 1 to p from left to right). The gotchi potency value of each cup is determined by following formula ∑(ai g(i)).
Given a= [-3, 4, 5, 4,−7, 8, -2 ] and we can divide it into 4 cups in the following way: [−3 , 4] , [5 , 4] , [−7 , 8] and [-2 ] then the overall potency value is equal to -3⋅1 + 4⋅1 + 5⋅2 + 4⋅2 - 7⋅3 + 8⋅3 – 2⋅4 = 14
Calculate the minimum potency value that Sartaj has to drink .

# EXPLANATION:
Let Suffix(k) be the suffix sum of array. Let the minimum sum (potency that Sartaj has to drink) be minsum.
We observe that at least once every array element is added in minsum. Now in order to find the exact value of minsum we need Suffix(1) and p-1 different suffix sums, for this we first sort the values of suffix sum and then take p-1 minimum values of suffix sum.
By this way we get minimum potency value.

Time Complexity:
O(n) to find suffix sum and O(nlogn) to sort values of suffix sum.

SOLUTIONS:

[details=“Setter’s Solution”]

import java.io.;
import java.util.;
public class Main
{
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int k=sc.nextInt();
int a[]=new int[n];

    int j=0;
    while (sc.hasNext())
    {
        a[j++]=sc.nextInt();
        if(j==n)
            break;
    }


    ArrayList<Long> suffix_sum=new ArrayList<Long>();
  long sum=0;
    for(int i=n-1;i>=0;i--)
    {
        sum+=a[i];
        if(i>0)
        suffix_sum.add(sum);

    }
    long res=sum;
    Collections.sort(suffix_sum);
  

    for(int i=0;i<k-1;i++)
        res+=suffix_sum.get(i);
    System.out.println(res);
}

}
[/details]

2 Likes
2

Why? How does one reach to the conclusion that one needs to take Suffix Sums and sort them? May be I am too dumb but that doesn’t seem intuitive to me.

1 Like
3

Sorry but doesn’t look like an official editorial to me. So, poorly written, neither does it explain the premise nor does it take care of writting it correctly. The editorialist didn’t even bother to format his code.

3 Likes
4

Ya, true. It looks like a bookish editorial. Make it a bit attractive too by boldening the important letters and topics, and provide a hyperlink to your solution so that a person who doesn’t want to look at the solution, but just get a hint to the problem from the editorial gets it.

5

I’ll have a stab at this - completely un-proof read. Please point out mistakes/ confusions :slight_smile:

The key point is that the sum of any break-down into cups of ranges is actually a sum of suffix-sums of a.

Assume 1-relative a with elements a_1, a_2, … a_N.

Assume we’ve picked an assignment of subranges into cups. We can represent this by a sequence c_1, c_2, … c_p where c_i is the index in a of the last element in cup i. (c_{i+1} > c_i for all valid i, and c_p=N).

In other words, our assignment is:

a_1, a_2, ... a_{c_1} (cup 1)
a_{c_1 + 1}, a_{{c_1} + 2}, ... a_{c_2} (cup 2)
…
a_{c_{p-2} + 1}, a_{c_{p-2} + 2}, ... , a_{c_{p-1}} (cup p - 1).
I’ll have a stab at this - completely un-proof read. Please point out mistakes/ confusions :slight_smile:

The key point is that the sum of any break-down into cups of ranges is actually a sum of suffix-sums of a.

Assume 1-relative a with elements a_1, a_2, … a_N.

Assume we’ve picked an assignment of subranges into cups. We can represent this by a sequence c_1, c_2, … c_p where c_i is the index in a of the last element in cup i. (c_{i+1} > c_i for all valid i, and c_p=N).

In other words, our assignment is:

a_1, a_2, ... a_{c_1} (cup 1)
a_{c_1 + 1}, a_{{c_1} + 2}, ... a_{c_2} (cup 2)
…
a_{c_{p-2} + 1}, a_{c_{p-2} + 2}, ... , a_{c_{p-1}} (cup p - 1).
a_{c_{p-1} + 1}, a_{c_{p-1} + 2}, ... , a_{c_p} (cup p).

$a_{c_{p-1} + 1}, a_{c_{p-1} + 2}, ... , a_{c_p}$ (cup $p$)

or in other words:

\overbrace{a_1, a_2, ... ,a_{c_1}}^{\text{cup }1},\overbrace{a_{c_1 + 1}, a_{{c_1} + 2}, ... ,a_{c_2}}^{\text{cup }2},a_{{c_2}+1},\dots, \overbrace{a_{c_{p-2} +1},\dots, a_{c_{p-1}-1},a_{c_{p-1}}}^{\text{cup }(p-1)},\overbrace{a_{c_{p-1} + 1}, a_{c_{p-1} + 2}, ... , a_{c_p}}^{\text{cup }p}

Our potency then is:

1 \times \sum_{i = 1}^{c_1} a_i + 2 \times \sum_{i = c_1+1}^{c_2} a_i + ... + (p-1) \times \sum_{i = c_{p-2} + 1}^{c_{p-1}} a_i + p \times \sum_{i = c_{p-1} + 1}^{c_p} a_i

Let’s examine the last two terms in more detail. Note that, since c_p=N, the last term is actually a suffix sum of a, multiplied by p.

(p-1) \times \sum_{i = c_{p-2} + 1}^{c_{p-1}} a_i + p \times \sum_{i = c_{p-1} + 1}^{c_p} a_i=
(p-1) \times \sum_{i = c_{p-2} + 1}^{c_{p-1}} a_i + (p - 1) \times \sum_{i = c_{p-1} + 1}^{c_p} a_i +\sum_{i = c_{p-1} + 1}^{c_p} a_i=
(p-1) \times \sum_{i = c_{p-2} + 1}^{c_{p}}a_i+\sum_{i = c_{p-1} + 1}^{c_p} a_i

What’s happened here? We started off with some random term multiplied by p-1 and a suffix sum multiplied by p. Now, we’ve got one suffix sum, and another suffix sum multiplied by p-1.

Let’s look at the last three terms that we have now:

(p-2) \times \sum_{i = c_{p-3} + 1}^{c_{p-2}} a_i + (p-1) \times \sum_{i = c_{p-2} + 1}^{c_{p}} a_i +\sum_{i = c_{p-1} + 1}^{c_p} a_i

We can now repeat the procedure for the terms beginning with (p-2) and (p-1), ending up, I think, with:

(p-2) \times \sum_{i = c_{p-3} + 1}^{c_{p}} a_i + \sum_{i = c_{p-2} + 1}^{c_{p}} a_i +\sum_{i = c_{p-1} + 1}^{c_p} a_i

So the term beginning with (p-2) has now also become a suffix sum (multiplied by (p-2)).

In this way, we gradually, from the right hand side, break down our original sum into a sum of p (distinct) suffix sums - a formal proof via induction would probably be quite easy, but I can’t be bothered :). Finding the p suffix sums with minimum sum should then give us our minimum potency.

8 Likes
6

@ssjgz as @vijju123 said, you should definitely be applying for an Editorialist at Codechef.

3 Likes
7

I actually thought of solving it using DP(like Matrix Chain Multiplication) , which I think, is although correct would have timed out. When would I be able to think like this. :pensive:

8

lol - I did the same thing (after the contest, of course :)). Since N<=10^4 and P<=10^4, an O(N \times P) solution would probably just about work :slight_smile:

May as well include it, in all its crappy glory:

Possible DP-based solution 
// Simon St James (ssjgz) - 2019-XX-XX
//#define SUBMISSION
#define BRUTE_FORCE
#ifdef SUBMISSION
#undef BRUTE_FORCE
#define NDEBUG
#endif
#include <iostream>
#include <vector>
#include <limits>

#include <cassert>

#include <sys/time.h> // TODO - this is only for random testcase generation.  Remove it when you don't need new random testcases!

using namespace std;

template <typename T>
T read()
{
    T toRead;
    cin >> toRead;
    assert(cin);
    return toRead;
}

void solutionBruteForceAux(const int N, const int P, const vector<int64_t>& a, int index, int cupNum, int64_t minCostSoFar, int64_t& best)
{
    if (index == N)
    {
        if (cupNum == P)
        {
            best = min(best, minCostSoFar);
        }
        return;
    }

    solutionBruteForceAux(N, P, a, index + 1, cupNum, minCostSoFar + cupNum * a[index], best);
    if (cupNum <= index)
        solutionBruteForceAux(N, P, a, index + 1, cupNum + 1, minCostSoFar + (cupNum + 1) * a[index], best);
}

int64_t solveBruteForce(int N, int P, const vector<int64_t>& a)
{
    int64_t result = numeric_limits<int64_t>::max();

    solutionBruteForceAux(N, P, a, 0, 1, 0, result);
    
    return result;
}

int64_t solveOptimised(int N, int P, const vector<int64_t>& a)
{
    vector<vector<int64_t>> minWithFirstNInPCups(N + 1, vector<int64_t>(P + 1, numeric_limits<int64_t>::max()));

    for (int i = 0; i <= N; i++)
    {
        minWithFirstNInPCups[i][0] = 0;
    }
    for (int i = 0; i <= P; i++)
    {
        minWithFirstNInPCups[0][i] = 0;
    }

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= P; j++)
        {
            const auto addNewAToNewCup = (i >= j && (j > 1 || i == 1) ? minWithFirstNInPCups[i - 1][j - 1] + (j * a[i - 1]) : numeric_limits<int64_t>::max());
            const auto addNewAToOldCup = (i - 1 >= j ? minWithFirstNInPCups[i - 1][j] + (j * a[i - 1]) : numeric_limits<int64_t>::max());


            minWithFirstNInPCups[i][j] = min(addNewAToNewCup, addNewAToOldCup);

        }
    }

    return minWithFirstNInPCups[N][P];
}

int main(int argc, char* argv[])
{
    ios::sync_with_stdio(false);
    if (argc == 2 && string(argv[1]) == "--test")
    {
        struct timeval time;
        gettimeofday(&time,NULL);
        srand((time.tv_sec * 1000) + (time.tv_usec / 1000));

        int N = rand() % 5 + 1;
        int P = rand() % 5 + 1;
        const int maxAbsA = rand() % 100 + 1;

        if (N < P)
            swap(P, N);

        cout << N << " " << P << endl;

        for (int i = 0; i < N; i++)
        {
            int a = rand() % maxAbsA;
            if (rand() % 2 == 0)
                a = -a;
            cout << a << " ";
        }
        cout << endl;

        return 0;
    }
    
    const int N = read<int>();
    const int P = read<int>();

    vector<int64_t> a(N);
    for (int i = 0; i < N; i++)
    {
        a[i] = read<int>();
    }


    
#ifdef BRUTE_FORCE
#if 1
    const auto solutionBruteForce = solveBruteForce(N, P, a);
    cout << "solutionBruteForce: " << solutionBruteForce << endl;
#endif
#if 1
    const auto solutionOptimised = solveOptimised(N, P, a);
    cout << "solutionOptimised:  " << solutionOptimised << endl;
    
    assert(solutionOptimised == solutionBruteForce);
#endif
#else
    const auto solutionOptimised = solveOptimised();
    cout << solutionOptimised << endl;
#endif

    assert(cin);
}

Edit:

Huh - just looked through the AC solutions, and a surprisingly large amount used the DP approach, rather than the one in the Editorial. Don’t feel so bad, now :slight_smile:

1 Like
9

Well, let’s make sure what I’ve written isn’t total garbage, first :slight_smile: If I ever get some of my own Problems accepted, I’ll do the Editorials for them as practice :slight_smile:

3 Likes
10

This problem is 100% copy of a contest from 6 months ago on codeforces. There is a very nice editorial for it as well. I knew the solution before looking at the qn lol.

3 Likes
11

Provide me link to solution of codeforces …rokda denga…:last_quarter_moon_with_face::full_moon_with_face:

12

That is the benefit of practice. Same qns appear here and there​:joy::grin:

13

It simply means solve as more as possible, u never know which problem comes which u already did.

1 Like
14

The place from where the question was taken:-

(Even Sample Test Cases Match) .
Nice Job Setter :stuck_out_tongue:

2 Likes
15

Yeah, setter should take on the responsibility of not asking existing questions or atleast not copying them 100% (I know I am speaking way out of my potential (aukat as they in Hindi.) being an extreme noob). In my very humble opinion it defeats the purpose of contest and gives an unfair advantage to those who have already solved the problem.

3 Likes
16

But this question is easy-medium. I mean searching for it, or deriving its solution would take same time. You can never trust external contests.

1 Like
17

Even the last question is standard and matches some places, but we cant complain as every qn cant be fully new naa…

2 Likes
18

The reason why external contests are unrated.

2 Likes
19

I don’t think good setters will ever ask repeated problems. I don’t think one would ever find repeated questions in Long, Lunchtime or Cook-Off. But I agree solving more problems help, I remember reading one answer of Bohdan Pryschenko(I_love_tanya_romanova) that he is able to solve hard problems because he has solved a lot many of them and he is often able to find patterns that he saw in problems he had solved earlier. He says he has solved over 8000 problems!:frowning:

1 Like
20

Yup…But I like both rated as well as unrated .
The next contest I am allowed to participate in is Oct-Long. Exams in Sep.:disappointed_relieved: