A problem

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

A problem

Post by mohiul alam prince » Fri Apr 22, 2005 1:56 pm

Hi
Last weak i have thinked about this problem but my idea is going to
TLE
Any body tell me how to solve this type of problem's
time limit is only one second and Memory Limit:65536K

Code: Select all

Description 

The input contains N natural (i.e. positive integer) numbers ( N <= 10000 ). Each of that numbers is not greater than 15000. This numbers are not necessarily different (so it may happen that two or more of them will be equal). Your task is to choose a few of given numbers ( 1 <= few <= N ) so that the sum of chosen numbers is multiple for N (i.e. N * k = (sum of chosen numbers) for some natural number k). 

Input 

The first line of the input contains the single number N. Each of next N lines contains one number from the given set. 

Output 

In case your program decides that the target set of numbers can not be found it should print to the output the single number 0. Otherwise it should print the number of the chosen numbers in the first line followed by the chosen numbers themselves (on a separate line each) in arbitrary order. 

If there are more than one set of numbers with required properties you should print to the output only one (preferably your favorite) of them.

Sample Input 


5
1
2
3
4
1


Sample Output 


2
2
3

 

domino
New poster
Posts: 19
Joined: Thu Dec 25, 2003 6:01 pm

Post by domino » Fri Apr 22, 2005 3:28 pm

Isn't this just a pigeon-hole principle application?
Is your array is A[1]... A[n] just compute S = A[1] + A[2] + .. + A
if any S % N == 0 then you have a solution (A[1] A[2] .. A), otherwise there will be an S equal to S[j] (i < j) and the solution is A[i+1] A[i+2]...A[j].

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny » Fri Apr 22, 2005 5:46 pm

This problem can also be solved using O(N^2) within the time limit.

Regards
Sanny

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Sat Apr 23, 2005 10:40 am

Thanks domino for ur reply
Hi
sunny can u explain ur O(n*n) algorithm

Thanks
MAP

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny » Sun Apr 24, 2005 2:03 am

(n^2) algo:

1. You have a boolean flag array 0...n-1. This indicates which numbers so far can u generate.

2. Input numbers are in the array inp[1..n].

3. In a loop from 1 to n, you add inp to previously generated numbers to see what new can you generate. All these numbers % n are flagged 1.

4. Whenever you get n or 0 (n%n), you terminate the loops.

5. To trace back to print all numbers, you need an additional array.


Regards
Sanny

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Sun Apr 24, 2005 7:43 am

Hi Sunny
Thanks for ur reply. but one thing is that my algorithm is same of you. :)
I have optimized my code with another idea and i think it is take's
(n(logn)*(logn)). and i also made a data set in my home and it take's 1.109 second i thought that my data was very critical but when i submit this problem it also gave me TLE.

I want to konw is there any O(n*logn) Solution in this problem. :o

Thanks
MAP

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny » Sun Apr 24, 2005 9:34 am

Hi Prince,
My O(n^2) passes the time limit and runs .14 sec in judges input. :D So may be there's some problem with your implementation. You can send me your code to let me see what's the problem or I can send you my code if you like.

Regards
Sanny

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Mon Apr 25, 2005 6:23 am

HI
I have got AC. 8)
I don't know that the Mod operation is so expensive.
I have changed in my code with this expresion.
My previous code was

Code: Select all

z = (x + y) % N;
After changing my code

Code: Select all

if ( x + y) > N
      z = (x + y) % N;
This operation happen's more than 10000000 time's.

Now my time is only 000.342
it is a peking university problem. problem no - 2356.

Thanks Sanny
MAP

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny » Mon Apr 25, 2005 7:01 am

This problem is actually more of a timus problem than pku. Peking University Judge just collects problems from different sources and arrange contests every 3/4 days (As far as I have seen in last few months). And also timus usually doesn't allow 64MB of memory :cry: .

Regards
Sanny

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Tue Apr 26, 2005 12:27 pm

Hi Sunny
Do you know any good website where i can learn more about DP ? :)

Thanks
MAP

Post Reply

Return to “Algorithms”