CO_OS_THOC's blog

By CO_OS_THOC, history, 15 months ago, In English

An Infectious disease is spreading in a city. The Mayor of the city wants to take strict actions to provide proper prevention from the disease

There are N persons in the city who stey side by side in increasing order of their index that is, the person ith person has the (i-1)th and (i+1)th staying next to him or her.

Initially, it is found that among N persons, exactly M are infected with the disease. Further, it was found the disease is contagious and it spreads from en infected person to his or her neighbors. It means that if the ith person is infected, then the (i-1)th person and (i + 1)th person staying just next to the person can get infected from him or her.

Also is observed that people who are not infected (people apart from initial M infected people) get infected in a particular sequence. This sequence provides the ordere in which people(who are not infected initially) gets infected with the increasing span of time. It may be possible that xth person gets infected only after the yth person and this defines a particular order among them, that is y must always be placed before x in the sequence.

For example, N = 6 and person 3 and 5 are infected. Here, person 2 gets affected before person 1. Simarly person 2 and 4 can be placed with any relative order as they can get infected from 3 directly.

The Mayor wants you to determine the number of unique sequences in which the other persons can get infected. Since the answer can be large print modulo 1000000007

Input: First line contains 2 space separated integers N & M. Next line contains M space separated integers denoting infected people.

Output: No of possible sequences

TestCase:

Input:

5 2

1 5

Output: 4

Explaination: Person 2 & 4 can get infected from person 1 & 5. Person 3 can only get infected after either Person 2 or Person 4 gets infected.

The possible sequences: [2,3,4] [2,4,3] [4,3,2] [4,2,3]

Constraints: 1 <= N <= 2e5 1 <= M <= N -1

 
 
 
 
  • Vote: I like it
  • -8
  • Vote: I do not like it

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by CO_OS_THOC (previous revision, new revision, compare).

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by CO_OS_THOC (previous revision, new revision, compare).

»
15 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Did you write this statement yourself or did you copy it from some online judge? If it is the first, please provide a problem link instead, it is impossible to understand the statement.

  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not able to provide the link, because the code was asked in an online test for the placements. At that time I was unable to code the question. The code statement is around 99% the same.

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by CO_OS_THOC (previous revision, new revision, compare).

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

plz provide a code... thank you and have a good day

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Find two closest number that are infected let's say x and y, than either the elements between x and y are even or odd, if even than there are 2 list [x+1,(x+(y-x-1)/2],[...,y-1] merging and combination between them is going to be 2mCm where m is size of array, find all such consecutive pair and find combination of all value from pairs(don't forget the value before first infected element).