DCP-19: Multiplication Interval (need help)

Dev Skill archived problems can be discussed here.

DCP-19: Multiplication Interval (need help)

by rayhan50001 » Thu Jan 04, 2018 3:12 am

link: https://devskill.com/CodingProblems/ViewProblem/19

i need some help to solve this problem. i did everything but i am stuck when product is 1. :cry:
test case like this:

1
10 2
1 1 1 2 1 1 1 1 2
1 10
3 10
output:
5 9
5 9

how do i count maximum sub array length having 1 within given range.main thing is find start position and end position.

sorry for my bad English :cry:

TIA(thanks in advance) ;)
 
Posts: 11
Joined: Tue Oct 25, 2016 6:25 pm

Re: DCP-19: Multiplication Interval (need help)

by feodorv » Tue Jan 09, 2018 1:16 am

I setted two arrays b[100000] and e[100000] which designate the beginning and ending indexes of consecutive 1-area if the current index belongs to that 1-area (it can be done in O(N)).
With such help I used one sparse table for minimim value on the interval and two additional sparse tables for largest size of 1-area on the interval and for the index of the first 1 in that largest size 1-area. For sparse table if left 1-area is the continuation of right 1-area, then they shoud be correctly united.
Last edited by feodorv on Sat Jan 20, 2018 5:41 am, edited 1 time in total.
 
Posts: 11
Joined: Thu Jun 15, 2017 3:37 pm

Re: DCP-19: Multiplication Interval (need help)

by rayhan50001 » Fri Jan 12, 2018 8:57 pm

can you give me your code of this portion..
:?: :?: :?: :?:
TIA
 
Posts: 11
Joined: Tue Oct 25, 2016 6:25 pm

Re: DCP-19: Multiplication Interval (need help)

by feodorv » Sat Jan 20, 2018 5:39 am

Sended to you by privite message.
 
Posts: 11
Joined: Thu Jun 15, 2017 3:37 pm


Who is online
Users browsing this forum: No registered users and 1 guest
cron