Page 2 of 2

10690

Posted: Sun Aug 27, 2006 10:21 am
by ImLazy
To maximize the expression, I think I should divide the numbers into two parts and make their difference minimum. But how to do it? Some one says DP. But I still have no idea how to DP. Who can give more hints.

Re: How to solve 10690?

Posted: Sun Aug 27, 2006 9:01 pm
by Martin Macko
There is already a thread on this problem. If there is a thread on a particular problem, please, use it to post your question and do not create a new one. (see http://online-judge.uva.es/board/viewtopic.php?t=6213 and http://online-judge.uva.es/board/viewtopic.php?t=6233)
forum 'Volume CVI' description wrote:All about problems in Volume CVI. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Posted: Mon Aug 28, 2006 11:01 am
by ImLazy
OK.
Sorry.

Posted: Sat Sep 09, 2006 5:29 pm
by ImLazy
How to DP? Could you tell it more detailedly? I've solved 10664, but keep getting TLE on 10690. Let me describe my algorithm:

Code: Select all

Use an array of set, named "reach". reach[i] stores the sums that can be reached by i numbers.

for every number n {
    for every count of number c (from greater to lower) {
        With the set reach[c] and the number n, I can add more sums to the set reach[c + 1].
    }
}
And I used an optimizing: in the second loop, the count number c is never greater than the count of x in the problem description (Or the count of y, use the lower one).
Can you give me more idea to optimize my algorithm? Or my algorithm is totally wrong?

Posted: Thu Sep 14, 2006 4:55 am
by ImLazy
Who can answer me?

Posted: Mon Oct 23, 2006 3:49 am
by smilitude
I am not that sure :(, but did you notice that they asked that the numbers can be negetive ? I think that can produce wrong answers for your algo..

Like if you have -39 to add from greater value, like 1045, you'll have 1006, then again you'll have 967...

Re: 10690 - Expression Again

Posted: Mon Feb 23, 2015 11:44 am
by bradd123
Hi, I got time limit exceeded for this problem. Please tell me how to improve solution. I used dp subset sum.

Code: Select all

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int _min,_max;
int dp[110][110][5500];
int N,M,a[110];
int mi,totalsum;
void ExpAgain(int idx,int num,int sum){
    if(num==mi){
        _min=min(_min,sum*(totalsum-sum));
        _max=max(_max,sum*(totalsum-sum));
        return;
    }
    if(idx>=(N+M)) return;
    if(dp[idx][num][sum+2600]!=-1) return;
    dp[idx][num][sum+2600]=1;
    ExpAgain(idx+1,num+1,sum+a[idx]);
    ExpAgain(idx+1,num,sum);
}
int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d %d",&N,&M)!=EOF){
        totalsum=0;
        for(int i=0;i<(N+M);i++){
            scanf("%d",&a[i]);
            totalsum+=a[i];
        }
        mi=min(N,M);
        _max=0;
        _min=2000000000;
        memset(dp,-1,sizeof dp);
        ExpAgain(0,0,0);
        printf("%d %d\n",_max,_min);
    }
}

Re: 10690 - Expression Again

Posted: Tue Feb 24, 2015 12:19 am
by brianfry713
My approach, AC in 1.156 seconds.

You need to divide the numbers into two groups, so find all the possible sums of min(N, M) of the integers. The sum of the remaining integers is easy to find.
I use a hash: unordered_set<int> to store all possible sums of each number of integers.
Iterate through each of the N + M integers, and then iterate through each of the numbers of integers, and add the current integer to each of the possible sums.

Re: 10690 - Expression Again

Posted: Sun Feb 11, 2018 4:05 am
by metaphysis
Test data generator.

Code: Select all

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, char *argv[])
{
    srand(time(NULL));
    int number[101];

    for (int i = 1; i <= 110; i++)
    {
        int N = rand() % 50; N++;
        int M = rand() % 50; M++;
        int T = (N + M);
        
        cout << N << ' ' << M << '\n';
        
        for (int j = 1; j <= T; j++)
        {
            int K = rand() % 101; K -= 50;
            number[j] = K;
        }
        
        cout << number[1];
        for (int j = 2; j <= T; j++)
            cout << ' ' << number[j];
        cout << '\n';
    }
    
    return 0;
}