11536 - Smallest Sub-Array

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
Location: Bangladesh

11536 - Smallest Sub-Array

Post 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
Image

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 11536 - Smallest Sub-Array

Post by Leonid »

My AC outputs the same values

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

Re: 11536 - Smallest Sub-Array

Post by Donotalo »

Is there any tricky input I can check?
Image

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

Re: 11536 - Smallest Sub-Array

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

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

Re: 11536 - Smallest Sub-Array

Post 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?
Image

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

Re: 11536 - Smallest Sub-Array

Post by mak(cse_DU) »

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

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

Re: 11536 - Smallest Sub-Array

Post by L I M O N »

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

Post by andmej »

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

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

Post Reply

Return to “Volume 115 (11500-11599)”