11536 - Smallest Sub-Array

[Donotalo]

Hi, I'm getting WA in this problem. I can't figure my mistake out. Can anyone check my output to the following input with an AC code's output?

Thanks in advance.

INPUT:

Code: Select all

15
20 12 4
20 12 8
3 5 3
1000000 10 12
3 1 2
1000000 1000 100
50 50 50
29 17 11
29 17 33
14 6 3
14365 66 3
353540 233 99
222222 222 22
333333 333 33
100000 555 55

OUTPUT:

Code: Select all

Case 1: 13
Case 2: sequence nai
Case 3: 3
Case 4: sequence nai
Case 5: 2
Case 6: sequence nai
Case 7: sequence nai
Case 8: sequence nai
Case 9: sequence nai
Case 10: 3
Case 11: 3
Case 12: 660
Case 13: 433
Case 14: 552
Case 15: 1331

[Leonid]

My AC outputs the same values

[Donotalo]

Is there any tricky input I can check?

[mak(cse_DU)]

Try these Input:

Code: Select all

2
20 12 2
20 1 2

output:

Code: Select all

Case 1: 2
Case 2: 2

Hope you find mistake.

[Donotalo]

This is weird!

The input of the problem statement states that N(2 < N < 1000001), M(0 < M < 1001) and K(1< K < 101). I found that my program outputs "sequence nai" for K == 1. I fixed that so the output become 1 for K == 1. And got accepted.

Is in the judge data there was an input where K == 1?

[mak(cse_DU)]

Ohh yes,
I checked it. there have input where K==1.

[sohel]

Yes, sorry about this. In the judge data, there are cases where K = 1 and for that the result is also 1.

[L I M O N]

here some test data: http://www.youngprogrammer.com

[andmej]

I can't solve this. Give me some hint please.

[898989]

Hi,

When you have an Array, and required to find Sub-Array with certain criteria, usually this is done by "sliding window".

sliding window means with a window with a size on input. E.g. imagine array 1 2 3 4 5 6, and we move with FIXED size window 3.
in 1st iteration, window cover 1 2 3
in 2nd iteration, window cover 2 3 4
in 3rd iteration, window cover 3 4 5
in 4th iteration, window cover 4 5 6

in 2D, best sub-rectangle, can be found by reducing problem to 1D version.

In this problem, we apply "sliding window" in O(N), but its size will be variable.
think how we can move to catch all windows containing numbers from 1-K & minimize length.

Hope it is enough, if not, just ask.