dynamic programming
PROBLEM:
You are provided with a set A. A good range is the largest range of elements that contain only one element from the set A.
you are also a range of numbers from 1 to N and M queries. In each query , an integer X is added to the set A. For each query , your task is to print the sum of left and right border indices of all the avaiable good ranges.
INPUT:
TWO INTEGERS N AND M
NEXT M LINES: ONE INTEGER X
OUTPUT:
FOR EACH QUERY,PRINT ONE INTEGER THAT REPRESENTS THE SUM OF ALL THE BORDER INDICES OF THE GOOD RANGES.
SAMPLE INPUT:
10 10
2
7
5
9
6
1
8
10
3
4
SAMPLE OUTPUT:
11
20
30
46
58
61
77
96
102
110
EXPLANATION:
first 2 is added to the set and the largest range containing only 2
is [1,10]
then 7 is added and the range containing only 2 becomes [1,6]and
containing only 7 becomes [3,10]
then 5 is added and the ranges are
For 2: [1,4]
For 5: [3,6]
For 7: [6,10]
similiarly for all other queries.
You are provided with a set A. A good range is the largest range of elements that contain only one element from the set A.
you are also a range of numbers from 1 to N and M queries. In each query , an integer X is added to the set A. For each query , your task is to print the sum of left and right border indices of all the avaiable good ranges.
INPUT:
TWO INTEGERS N AND M
NEXT M LINES: ONE INTEGER X
OUTPUT:
FOR EACH QUERY,PRINT ONE INTEGER THAT REPRESENTS THE SUM OF ALL THE BORDER INDICES OF THE GOOD RANGES.
SAMPLE INPUT:
10 10
2
7
5
9
6
1
8
10
3
4
SAMPLE OUTPUT:
11
20
30
46
58
61
77
96
102
110
EXPLANATION:
first 2 is added to the set and the largest range containing only 2
is [1,10]
then 7 is added and the range containing only 2 becomes [1,6]and
containing only 7 becomes [3,10]
then 5 is added and the ranges are
For 2: [1,4]
For 5: [3,6]
For 7: [6,10]
similiarly for all other queries.
Last edited on
This isn't a "dump your homework and get a free pass" site.
You want help?
Post some effort.
The ability to merely copy/paste questions from your tutor to here, and to copy/paste answers from here to your tutor doesn't count as a skill or effort.
You want help?
Post some effort.
The ability to merely copy/paste questions from your tutor to here, and to copy/paste answers from here to your tutor doesn't count as a skill or effort.
@salem
I want some hint or approach not a full solution or code.
and this is not my homework...
this is amazon coding round question.
I want some hint or approach not a full solution or code.
and this is not my homework...
this is amazon coding round question.
> I want some hint or approach not a full solution or code.
Pencil and paper.
It's the same start for all problems which are not immediately obvious.
It's all hard graft and head scratching until you figure out what the problem is all about.
> this is amazon coding round question.
So if we do well for you, you get a job offer?
Pencil and paper.
It's the same start for all problems which are not immediately obvious.
It's all hard graft and head scratching until you figure out what the problem is all about.
> this is amazon coding round question.
So if we do well for you, you get a job offer?
I made some pattern but it's not working for all test cases,it works for few test cases.
if u know how to solve this problem
then give me some hint, i don't want full solution
just a small hint ......
> so if we do well....
i am 2nd year student.....so at a time job doesn't matter for me
if u know how to solve this problem
then give me some hint, i don't want full solution
just a small hint ......
> so if we do well....
i am 2nd year student.....so at a time job doesn't matter for me
The problem is that you need to see the pattern. What can you do to show us what you understand of the problem?
We will help you understand the problem. Most of the regulars here can solve it easily enough. Hint: there are three possible cases you need to consider.
We will help you understand the problem. Most of the regulars here can solve it easily enough. Hint: there are three possible cases you need to consider.
@duthomhas
i also considered 3 cases
1st case- when the next query is greater than the last query
2nd case- when the next query is less than the last query
3rd case -when the next query is equal to the last query
am i right?
>The problem is that you need to see the pattern
I am trying to find pattern from last 2 days, i made a pattern but it works for few test cases
i also considered 3 cases
1st case- when the next query is greater than the last query
2nd case- when the next query is less than the last query
3rd case -when the next query is equal to the last query
am i right?
>The problem is that you need to see the pattern
I am trying to find pattern from last 2 days, i made a pattern but it works for few test cases
Last edited on
Erg, yes they are.
Sorry. I was thinking about another math problem, and I forgot the constraints on this one.
Last edited on
Topic archived. No new replies allowed.