11052 - Economic phone calls

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

Moderator: Board moderators

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Tue Aug 01, 2006 11:46 am

Yes, you are right, the sample input is not in the judge test cases, I forgot to include it.

User avatar
joeluchoa
New poster
Posts: 28
Joined: Sat Jul 31, 2004 12:11 am
Location: Brasil

Post by joeluchoa » Mon Aug 14, 2006 5:24 pm

I've got WA!
Somebory can give me a hint?

This is my code:

Code: Select all

Removed, I had not understood the problem correctly!
Last edited by joeluchoa on Tue Aug 15, 2006 1:51 pm, edited 2 times in total.

User avatar
fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

Post by fh » Mon Aug 14, 2006 5:41 pm

I used backtracking to consider all possibilities... I'm also curious whether it can be solved using greedy?
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

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

Post by Martin Macko » Mon Aug 14, 2006 7:52 pm

joeluchoa wrote:I've got WA!
Somebory can give me a hint?
Not working for:

Code: Select all

4
04:09:06:59 47 -
02:07:05:49 47 +
09:01:03:11 47 -
01:30:02:34 47 -
0
The correct output is:

Code: Select all

2

User avatar
joeluchoa
New poster
Posts: 28
Joined: Sat Jul 31, 2004 12:11 am
Location: Brasil

Post by joeluchoa » Tue Aug 15, 2006 12:03 am

I'm not understand the above input!!
Why is 2 the output?
You can explain to me?

I think that the answer would be:
3

4
04:09:06:59 47 - [year 2]
02:07:05:49 47 + [year 1]
09:01:03:11 47 - <delete>
01:30:02:34 47 - [year 0 (current)]

What is wrong in my idea?
http://acm.uva.es/problemset/usersnew.php?user=47903

All men are like grass,and all their
glory is like the flowers of the field;
the grass withers and the flowers fall,
but the word of the Lord stands forever.
[1 Peter 1:24-25]

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

Post by Martin Macko » Tue Aug 15, 2006 10:48 am

joeluchoa wrote:I'm not understand the above input!!
Why is 2 the output?
You can explain to me?
What is wrong in my idea?
The years of all the phone calls are as follows:

Code: Select all

04:09:06:59 47 -     [year 1] (as 04>02)
02:07:05:49 47 +     [year 1] (as 02<09)
09:01:03:11 47 -     [year 0] (as 09>01)
01:30:02:34 47 -     [year 0] (as it is the first one)
After removing the first and the last one you get:

Code: Select all

04:09:06:59 47 -     [delete]
02:07:05:49 47 +     [year 1] (as 02<09)
09:01:03:11 47 -     [year 0] (as it is the first one)
01:30:02:34 47 -     [delete]

User avatar
joeluchoa
New poster
Posts: 28
Joined: Sat Jul 31, 2004 12:11 am
Location: Brasil

Post by joeluchoa » Tue Aug 15, 2006 3:47 pm

Thanks Martin Macko. I hadn't undestood the problem correctly!
http://acm.uva.es/problemset/usersnew.php?user=47903

All men are like grass,and all their
glory is like the flowers of the field;
the grass withers and the flowers fall,
but the word of the Lord stands forever.
[1 Peter 1:24-25]

Towhid
New poster
Posts: 38
Joined: Wed May 28, 2003 5:30 pm
Location: Bangladesh
Contact:

Post by Towhid » Fri Aug 18, 2006 3:37 pm

fh wrote:I used backtracking to consider all possibilities... I'm also curious whether it can be solved using greedy?
I have used Greedy approach. The code is a bit big with some if else condition. I started from the first entry....
From 0 to 0

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

Post by lonelyone » Thu Aug 24, 2006 9:18 am

Martin Macko wrote:
joeluchoa wrote:I'm not understand the above input!!
Why is 2 the output?
You can explain to me?
What is wrong in my idea?
The years of all the phone calls are as follows:

Code: Select all

04:09:06:59 47 -     [year 1] (as 04>02)
02:07:05:49 47 +     [year 1] (as 02<09)
09:01:03:11 47 -     [year 0] (as 09>01)
01:30:02:34 47 -     [year 0] (as it is the first one)
After removing the first and the last one you get:

Code: Select all

04:09:06:59 47 -     [delete]
02:07:05:49 47 +     [year 1] (as 02<09)
09:01:03:11 47 -     [year 0] (as it is the first one)
01:30:02:34 47 -     [delete]
Sorry, I still couldn't understand it.
Could someone explain it more detailed?

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan » Tue Sep 12, 2006 10:31 am

Can any one pls clearly explain when should I delete a log ???? & why ?
I didnt clearly understand the problem

Thanks in Advance

annhy
New poster
Posts: 40
Joined: Sun May 27, 2007 1:42 am
Location: Taiwan

Post by annhy » Sun Jun 10, 2007 5:20 am

Martin Macko wrote: The years of all the phone calls are as follows:

Code: Select all

04:09:06:59 47 -     [year 1] (as 04>02)
02:07:05:49 47 +     [year 1] (as 02<09)
09:01:03:11 47 -     [year 0] (as 09>01)
01:30:02:34 47 -     [year 0] (as it is the first one)
After removing the first and the last one you get:

Code: Select all

04:09:06:59 47 -     [delete]
02:07:05:49 47 +     [year 1] (as 02<09)
09:01:03:11 47 -     [year 0] (as it is the first one)
01:30:02:34 47 -     [delete]
Strangely, my understanding is different to yours, but I get AC..

In my understanding, the years of all the phone calls are as follows:

Code: Select all

04:09:06:59 47 -     [year -2]
02:07:05:49 47 +     [year -1]
09:01:03:11 47 -     [year -1] (the last year)
01:30:02:34 47 -     [year 0] (current year) 
The result:

Code: Select all

04:09:06:59 47 -     [delete]  (before the first important call)
02:07:05:49 47 +     [year -1]
09:01:03:11 47 -     [delete]  (02 > 01, this one can be deleted)
01:30:02:34 47 -     [year 0]

dibery
Learning poster
Posts: 76
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

Re: 11052 - Economic phone calls

Post by dibery » Mon Feb 02, 2015 4:56 am

One more case.

Input:

Code: Select all

9              
09:16:10:18 0 -
01:12:03:22 0 +
02:22:14:48 0 -
04:05:11:29 0 +
03:04:01:42 0 +
05:10:08:08 0 -
12:18:02:27 0 -
05:01:08:27 0 -
09:08:04:31 0 +
0
Output:

Code: Select all

5
Life shouldn't be null.

Post Reply

Return to “Volume 110 (11000-11099)”