10690 - Expression Again

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

10690

Post by ImLazy » Sun Aug 27, 2006 10:21 am

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.
I stay home. Don't call me out.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: How to solve 10690?

Post by Martin Macko » Sun Aug 27, 2006 9:01 pm

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.

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Mon Aug 28, 2006 11:01 am

OK.
Sorry.
I stay home. Don't call me out.

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Sat Sep 09, 2006 5:29 pm

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?
I stay home. Don't call me out.

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Thu Sep 14, 2006 4:55 am

Who can answer me?
I stay home. Don't call me out.

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Mon Oct 23, 2006 3:49 am

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...
fahim
#include <smile.h>

bradd123
New poster
Posts: 17
Joined: Thu Jul 03, 2014 11:13 am

Re: 10690 - Expression Again

Post by bradd123 » Mon Feb 23, 2015 11:44 am

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10690 - Expression Again

Post by brianfry713 » Tue Feb 24, 2015 12:19 am

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.
Check input and AC output for thousands of problems on uDebug!

metaphysis
Experienced poster
Posts: 128
Joined: Wed May 18, 2011 3:04 pm

Re: 10690 - Expression Again

Post by metaphysis » Sun Feb 11, 2018 4:05 am

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

muazuicom22
New poster
Posts: 25
Joined: Tue Sep 11, 2018 10:32 pm

Post by muazuicom22 » Sat Sep 29, 2018 6:05 pm

CTY TDL CHUYÊN NHẬN LÀM GIẤY TỜ :

Kính gửi Quý khách hàng , Cty TDL chúng tôi

Nhận làm tất cả các loại giấy tờ liên quan đến BĐS , từ dễ đến khó , khu vực Thành Phố HCM Và Bình Dương.
* Vẽ thiết kế xây dựng, xin giấy phép xây dựng.
* Vẽ hiện trạng đo đạc nhà đất, nhà máy, nhà xưởng.
*Dịch vụ thiết kế Phòng cháy, chữa cháy và Thẩm duyệt.
* Dịch vụ xin chuyển mục đích sử dụng đất.
* Dịch vụ hoàn công nhà xưởng, công trình trên đất.
* Dịch vụ tách thửa sổ đỏ, nhà đất, nhà xưởng, nhà máy.
* Dịch vụ xin cấp mới sổ đỏ, sổ hồng hoặc xin cấp Giấy chứng nhận Quyền sử dụng đất, quyền sở hữu nhà ở và tài sản khác gắn liền với đất.
* Dịch vụ xác định lại ranh giới, thực trạng nhà đất, cấp sổ mới.
* Dịch vụ xem xét lại quy hoạch xây dựng.
* Dịch vụ hợp thức hóa nhà đất.
* Dịch vụ sang tên , đăng bạ sang tên chủ quyền, thừa kế di chúc.


Ai có nhu cầu liên hệ 0938.242.835 c.Hong.
Quý khách Lưu lại khi cần . Trân trọng cảm ơn. Uy Tin_ chinh chuan.
Chúc Anh chị một ngày tốt lành

Post Reply

Return to “Volume 106 (10600-10699)”