## 11536 - Smallest Sub-Array

Moderator: Board moderators

Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am

### 11536 - Smallest Sub-Array

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?

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
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

### Re: 11536 - Smallest Sub-Array

My AC outputs the same values

Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am

### Re: 11536 - Smallest Sub-Array

Is there any tricky input I can check?

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm

### Re: 11536 - Smallest Sub-Array

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.
Mak
Help me PLZ!!

Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am

### Re: 11536 - Smallest Sub-Array

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)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm

### Re: 11536 - Smallest Sub-Array

Ohh yes,
I checked it. there have input where K==1.
Mak
Help me PLZ!!

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Re: 11536 - Smallest Sub-Array

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
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Contact:

### Re: 11536 - Smallest Sub-Array

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

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

### Re: 11536 - Smallest Sub-Array

I can't solve this. Give me some hint please.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

### Re: 11536 - Smallest Sub-Array

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.
Sleep enough after death, it is the time to work.