11386 - Triples

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

Moderator: Board moderators

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

11386 - Triples

Post by DP » Sat Jan 12, 2008 5:19 pm

Code: Select all

cut
Last edited by DP on Sat Jan 12, 2008 7:19 pm, edited 1 time in total.

mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm
Location: Madrid

Something hidden in the statement?

Post by mpi » Sat Jan 12, 2008 5:45 pm

My algorithm is very simple and yet i'm getting WA all the time. Here it goes:

Code: Select all

1 - Sort the input in non-decreasing order into num
2 - nt = 0
3 - Iterate from i=3..n
        j = 0
        k = i - 1
        While (j < k)
            sum = num[j] + num[k]
            if (sum < num[i])
               ++j  // discard the element from the left end
            else if (sum > num[i])
               --k  // discard the element from the right end
            else // new triple
               if (num[j] == num[k])      // e.g.: 1 1 1 1 1 2
                 nt += c(k-j+1, 2)  // binomial coefficient (e.g.: c(5, 2) = 10)
                 j = k // stop here
               else
                 j2 = first element != num[j] && > j
                 k2 = first element != num[k] && < k
                 assert(j2 <= k2)
                 nt += (j2-j) * (k-k2)
                 j = j2
                 k = k2

4 - Print nt as result
Any hints? :(
Last edited by mpi on Sat Jan 12, 2008 7:14 pm, edited 1 time in total.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sat Jan 12, 2008 6:06 pm

So does the obvious O(n^2) solution work? And how big can the input integers be? Just less than 2^31?

[EDIT] Accepted. Let me answer my questions: O(n^2) works. Have to use 64-bit ints in the code.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm
Location: Madrid

Post by mpi » Sat Jan 12, 2008 7:17 pm

Observer,

Are you saying that my approach is right? When I have to use 64-bit integers: output (of course) AND input?? unsigned, signed?

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sat Jan 12, 2008 8:02 pm

Sorry. I was only talking about my own algorithm. :D I use for loop only for smallest and largest number in the tuple. It is also good to "group" the repeated numbers.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm
Location: Madrid

Post by mpi » Sat Jan 12, 2008 8:25 pm

OK. Then, what's the output for the following input:

Code: Select all

7
3 3 3 5 5 8 8
My output

Code: Select all

12

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sat Jan 12, 2008 8:28 pm

Your output is correct.

-----
Rio

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

Post by sonyckson » Sat Jan 12, 2008 9:02 pm

I did an O((n^2)log(n)) solution, and i didnt have problems with the Time Limit. gl! Eric.

mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm
Location: Madrid

Post by mpi » Sat Jan 12, 2008 10:31 pm

Somebody got any tricky input?? This problem is definitely driving me crazy, it's not so hard even with a naive O(n^2) algorithm like mine!

[Edited] Finally, I got ACC. Besides grouping the numbers after sorting, I changed 'int' to 'unsigned int' and all worked OK! :lol:

joshi13
New poster
Posts: 9
Joined: Sun Jan 06, 2008 3:18 am

Thanks.

Post by joshi13 » Sun Jan 13, 2008 3:41 am

Thanks Rio.
Last edited by joshi13 on Mon Jan 14, 2008 2:31 am, edited 1 time in total.

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

Post by Ron » Sun Jan 13, 2008 1:45 pm

why im getting TLE ..............

Code: Select all

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int i,j,k;
	unsigned int arr[5000],n,m,count;
	while(cin>>n){
		for(i=0;i<n;i++)	cin>>arr[i];
		sort(arr,arr+n);
		count=0;
		for(i=0;i<n-2;i++){
			for(j=i+1;j<n-1;j++){
				m=arr[i]+arr[j];
				for(k=j+1;k<n;k++){
					if(arr[k]>=m){
						if(arr[k]>m)	break;
						count++;
					}
				}
			}
		}
		cout<<count<<endl;
	}
	return 0;
}

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sun Jan 13, 2008 1:57 pm

>>joshi13
Use long long int. The grouping idea is:

Code: Select all

1 1 1 2 3 3  -->  (1,3) (2,1) (3,2)
Anyway, your code and algorithm is beautiful :)

>>Ron
O(n^3) is too slow. Try O(n^2logn) or O(n^2).
-----
Rio

pawelz
New poster
Posts: 1
Joined: Sat Dec 29, 2007 2:28 pm

Post by pawelz » Sun Jan 13, 2008 6:22 pm

Hi!
Firstly, I did simple O(n^2*logn) program, but it didn't pass. Then I used my own hash table and after some troubles with RE I got AC! (3.470s). Can anyone tell me how to solve it with O(n^2) but without hashing?

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sun Jan 13, 2008 6:35 pm

If you have grouped the numbers, then the O(n^2) is very obvious. :)

Hint: suppose we are to find tuples (X, y, z), where X is fixed. Think of how to do so in O(n).

There are many other ways to get O(n^2) solutions for this task.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm
Location: Madrid

O(n^2) algorithm

Post by mpi » Sun Jan 13, 2008 10:52 pm

The O(n^2) algorithm doesn't need any hashing mecanishm. All you have to do is, at each step i, iterate over the elements in the range j=1,..,k=i-1. Depending on the sum of the elements of both ends you will have to update j and k properly (incrementing j and/or decreasing k). The loop ends with j >= k (with no grouping) and with j > k (with grouping).

Post Reply

Return to “Volume 113 (11300-11399)”