Блог пользователя KulikAlex

Автор KulikAlex, история, 9 месяцев назад, По-английски

Can anyone suggest a test that breaks my solution?

1284D - New Year and Conference

358658250

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
9 месяцев назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +5 Проголосовать: не нравится

Your code misses a venue-sensitive pair as it only checks up to 11 lectures ahead for b overlaps outside fo the a overlap window.

Input:

13
2 2 1 10
4 4 20 20
6 6 21 21
8 8 22 22
10 10 23 23
12 12 24 24
14 14 25 25
16 16 26 26
18 18 27 27
20 20 28 28
22 22 29 29
24 24 30 30
26 26 5 6

Outputs YES when NO is expected for this test case, as in venue a, all lectures are single time points (2, 4, 6 -> 26). As a result of this, there are zero overlaps, meaning {1,13} is attendable in venue a. But in venue b, lecture one is [1,10] while lecture 13 is [5,6], meaning they overlap, which means {1,13} is not attendable in venue b, making it venue-sensitive.

Your code seemed to break here

for (int j = l + 1; j < n; j++) {
   ...
   if (j > l + 10) break;
}

because after processing j, it checks j = 1 -> 11 and breaks, never reaching j=12 which is lecture 13, making it incorrectly output YES.