Page 1 of 1
11536 - Smallest Sub-Array
Posted: Tue Oct 21, 2008 5:28 pm
by 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
Re: 11536 - Smallest Sub-Array
Posted: Tue Oct 21, 2008 5:54 pm
by Leonid
My AC outputs the same values
Re: 11536 - Smallest Sub-Array
Posted: Tue Oct 21, 2008 6:01 pm
by Donotalo
Is there any tricky input I can check?
Re: 11536 - Smallest Sub-Array
Posted: Tue Oct 21, 2008 8:41 pm
by mak(cse_DU)
Try these Input:
output:
Hope you find mistake.
Re: 11536 - Smallest Sub-Array
Posted: Wed Oct 22, 2008 3:33 pm
by 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?
Re: 11536 - Smallest Sub-Array
Posted: Thu Oct 23, 2008 7:46 pm
by mak(cse_DU)
Ohh yes,
I checked it. there have input where K==1.
Re: 11536 - Smallest Sub-Array
Posted: Fri Oct 24, 2008 7:35 am
by sohel
Yes, sorry about this. In the judge data, there are cases where K = 1 and for that the result is also 1.
Re: 11536 - Smallest Sub-Array
Posted: Sun Oct 26, 2008 3:44 pm
by L I M O N
Re: 11536 - Smallest Sub-Array
Posted: Mon Oct 27, 2008 4:06 pm
by andmej
I can't solve this. Give me some hint please.
Re: 11536 - Smallest Sub-Array
Posted: Sat Nov 15, 2008 11:01 pm
by 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.