11052 - Economic phone calls

[ImLazy]

I find the offical I/O, and for this input:

Code: Select all

3
06:06:05:06 641037712 -
04:13:06:36 17 -
10:25:14:37 793127405919586 +

The output is:

Code: Select all

1

But I think the output should be "2". The first or the second log must be kept, otherwise the third log will come to the current year.

[mf]

The last log is always in the current year.

[Darko]

I think ImLazy is right - there are two years and by keeping only one log you can't determine that. Unless I misunderstood the problem.

[mf]

You should determine years, starting from the last log entry and going backwards (read the 'Recovery of Years' section carefully.)
And you'll always assign to the last log entry the current year.
Two previous log entries simply can't influence that.

[Darko]

Yes, sorry, I just reread it - I did misunderstand it. That's how I understood it during the contest so my mind was stuck. 2am contests right after work are fun

[ImLazy]

Oh, I misunderstood the problem. The last log in the input is the latest. I used to think the first one is.

[sarah]

Can you explain the greedy approach for this problem, #11052?
And what is the correct output for this input?

Code: Select all

1
07:21:14:00 1337 -
0

[arsalan_mousavian]

i think the answer for the above input is 0 , because we don't need to store anything , by the way i have used a greedy solution for this problem , but i 've got WA , can someone post some IO ?

tanx
Arsalan

[Martin Macko]

i think the answer for the above input is 0

Yes, the correct answer is 0.

[Martin Macko]

but i 've got WA , can someone post some IO ?

Some random test cases:

Code: Select all

19
01:23:21:41 47 -
09:11:14:05 47 -
10:31:11:11 47 +
09:04:22:52 47 -
05:10:17:55 47 -
02:15:19:30 47 -
09:21:01:26 47 +
01:24:06:53 47 +
04:29:18:25 47 -
02:18:05:01 47 +
09:25:15:37 47 -
12:17:21:05 47 +
09:14:02:54 47 -
04:13:08:13 47 +
06:03:22:23 47 +
03:18:15:21 47 -
07:13:00:54 47 -
02:17:06:22 47 -
11:27:08:54 47 +
11
04:16:03:43 47 +
06:18:03:31 47 -
10:29:00:30 47 +
01:11:00:58 47 -
04:05:14:19 47 -
10:10:18:58 47 -
09:24:04:08 47 +
04:17:02:08 47 +
02:24:19:47 47 -
04:11:06:18 47 -
04:18:15:31 47 +
8
01:03:10:18 47 +
03:06:10:53 47 -
01:09:03:21 47 -
11:03:09:27 47 +
12:11:05:20 47 -
05:19:19:24 47 -
08:23:13:42 47 -
04:07:12:38 47 +
12
01:04:07:12 47 -
03:21:15:37 47 -
01:18:09:44 47 +
01:26:23:36 47 -
12:28:17:08 47 +
12:12:11:31 47 -
11:28:14:05 47 -
04:02:21:49 47 -
10:04:05:50 47 +
03:03:02:39 47 -
06:18:13:52 47 -
10:04:04:24 47 +
20
03:23:08:57 47 +
01:01:01:18 47 -
08:26:13:26 47 +
05:15:11:29 47 -
11:29:03:25 47 -
11:09:15:44 47 -
08:08:08:40 47 +
11:27:20:58 47 -
11:22:04:25 47 +
04:04:20:52 47 -
01:04:13:36 47 -
05:08:04:00 47 -
03:30:07:08 47 -
07:26:09:25 47 -
05:10:21:17 47 -
07:31:02:07 47 +
12:04:15:12 47 -
06:17:06:12 47 -
12:22:00:32 47 -
10:19:10:48 47 -
0

My AC's output:

Code: Select all

15
7
6
6
19

[arsalan_mousavian]

thanks martin macko for you reply , but my program passes all your input ,
any suggestions ?

yours
Arsalan

[mf]

There's test data at http://www.informatik.uni-ulm.de/acm/Locals/2006/

[fh]

The sample output of this problem is 6 but my program produces 5 and my program is AC. Is that means that the sample output is WRONG?

[mf]

Tell us which 5 log entries should be kept, according to your program.

[fh]

I found my mistake, my code assume that if t'>t then phone call t' occurs in the previous year whether the correct assumption should be t' >= t.

So, for the sample input, i got 5 :

12:31:23:59 0123456789012345 +
07:21:19:00 1337 -
01:01:00:00 0987654321 -
07:21:14:00 1337 - (DELETED)
11:11:11:11 11111111111 +
01:01:00:00 0123456789 +
01:01:00:00 0987654321 - (DELETED)

Strangely, I got AC.

So i think the sample input is not in the judge test cases.