Logging

Strip the problem down

The messages are pure noise. After parsing the input, all that remains is a sequence of times $t_1,t_2,\dots,t_n,$ where each $t_i$ is the minute of the day in $[0,1439]$.

A date in the original log cannot disappear and then come back later, because the full log was written in chronological order. So every date corresponds to one contiguous segment of the sequence. The whole problem is really:

Partition the sequence into the minimum number of contiguous blocks, where each block could be one day.

That is the whole game. No DP fireworks needed. Don't overengineer it.

Parsing the 12-hour clock correctly

Use $hour = (hh \bmod 12) + 12 \cdot [\text{p.m.}],$ $t = 60 \cdot hour + mm.$

This handles the annoying cases correctly:

• $12{:}xx$ a.m. $\to 0{:}xx$
• $12{:}xx$ p.m. $\to 12{:}xx$

The sentence about midnight belonging to the coming day is exactly why $12{:}00$ a.m. must be treated as the start of a day, not the end of the previous one.

When is one block a valid day?

A segment $[l,r]$ can belong to a single day iff:

1. times are nondecreasing: $t_l \le t_{l+1} \le \dots \le t_r,$
2. no exact minute appears more than $10$ times in that segment.

Why is that sufficient? Because those are exactly the constraints from the statement:

• within one date, chronological order means time cannot go backward;
• for one exact pair $(\text{date},\text{time})$, there are at most $10$ log lines.

Now here's the tiny but useful simplification: inside a nondecreasing sequence, equal values appear in one consecutive run. So condition 2 is equivalent to saying:

Every run of equal times has length at most $10$.

That means we do not need a full frequency table. Just track the current streak of equal minutes.

Why greedy works

Take the longest valid prefix as the first day, then repeat on the remaining suffix.

Let the current day start at position $l$, and let $r$ be the largest index such that $[l,r]$ is a valid one-day block.

Consider any optimal partition. Its first block cannot end after $r$ — by definition of $r$, anything longer is invalid.

Suppose its first block ends earlier, at some $p<r$. Then we can move records $p+1,p+2,\dots,r$ from the front of later blocks into the first block.

• The first block stays valid, because $[l,r]$ was chosen valid.
• The remaining blocks stay valid, because removing a prefix from a valid block leaves a suffix, and a suffix of a valid block is still valid.

So there exists an optimal solution whose first block is exactly the greedy longest valid prefix. Apply the same argument to the suffix. Done.

In plain English: if the next record still fits in the current day, cutting earlier is just self-inflicted pain. If the next record does not fit, then starting a new day is forced.

Greedy scan

Maintain for the current day:

• last = the last minute value,
• same = length of the current run of equal times.

For each next time $t_i$:

• if $t_i < last$, the time went backward, so this record must start a new day;
• if $t_i = last$ and same = 10, this would be the $11$-th record in the same minute of the same day, so again it must start a new day;
• otherwise, extend the current day.

That's it. Simple, brutal, correct.

Complexity

The scan is $O(n)$ time and $O(1)$ memory.

With $n \le 100$, this is hilariously safe.