×

# FLYMODE - Editorial

Author: Pawel Kacprzak
Tester: Misha Chorniy
Editorialist: Pawel Kacprzak

SIMPLE

# PREREQUISITES:

Sorting, sweep line

# PROBLEM:

For a list of $N$ positive consecutive heights: $h_1, h_2, \ldots, h_N$ denoting some heights at which a plane was during its flight and knowing that between heights $h_i$ and $h_{i+1}$ it was flying the shortest path between these height, which means it was at every height between these two ones once, find the maximum integer $K$, such that the plane was $K$ times at some height during the flight.

# QUICK EXPLANATION:

For every pair of consecutive heights $h_i, h_{i+1}$ add each of these heights as either opening or closing time event to a list of all events, let’s call it $E$, happening in time. Sort $E$ and process it using sweep line keeping track of the number of current opened events that has not been closed. The result is the maximum number of opened events during this process.

# EXPLANATION:

In this subtask $N$ is at most $1000$ and we know that each $h_i \leq 1000$. This allows the following approach:

Let $K$ be the result to the problem and $H$ be the set of some candidate heights such that the plane was at some $h \in H$ exactly $K$ times. If $H$ is not too big, then we can for each $h \in H$ check how many times the plane was at height $h$ by iterating over all two consecutive input heights $h_i, h_{i+1}$ and counting the number of such pairs that contain $h$. The answer to the problem is the maximal such count. This approach has the time complexity of $O(|H| \cdot N)$, but how to chose $H$? Well, we can take advantage of the fact that $h_i \leq 1000$. Important thing to notice is that the height on which the plane was the most number of times can be a real number, not integer. However, the crucial observation is that we can put to $H$ all positive integers not greater than $1000$ and also floating points exactly between them, so $1.5, 2.5, \ldots$. Is turns out that these candidate heights are sufficient because all input heights are integers.

In the second subtask $N$ can be at most $10^5$ and each $h_i \leq 10^9$, so method described above will take too much time. The crucial observation to approach the problem is to notice that if $K$ is the answer to the problem, there exists height $h$ for which there exists $i$ such that $\min(h_i, h_{i+1}) \le h \le \max(h_i, h_{i+1})$ and the plane was at height $h$ exactly $K$ times. Thus the problem can be reduced to finding a point which is covered by most of these height pairs and returning the maximum size of such cover. Let’s think of pairs of consecutive heights as segments from the smaller to the larger height. Notice that changing height from $h_i$ to $h_{i+1}$ corresponds to one such segment. Moreover, the reduced problem can be easily solved using a sweep line algorithm by sorting all endpoints of the segments, then processing them from left to right counting the number of opened segments and returning the maximal such count during this process. The complexity of this solution is $O(N \cdot \log(N))$ dominated by the sorting phase.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Setter's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

74485097
accept rate: 12%

19.8k350498541

@pkacprzak

Can you please explain in a bit more detail. It just crossed my head.

(03 Jan '17, 18:42) 1★

 6 Kindly make problem available for practise. answered 01 Jan '17, 01:18 31●1 accept rate: 0% 2 ^ make it available for practice. (01 Jan '17, 15:22) It's available in practice now (02 Jan '17, 01:29)
 4 This question can also be solved by dp.This problem can be generalised as: We are having an array having infinite elements.We are adding 1 to each value between h1 and h2. Now we can maintain a dp map and update the element h1 plus some small value(maybe 0.0005) to +1 and h2+ 0.0005 to -1.Now after this process is done take the cumulative sum of the map elements.The answer is the maximum of all the elements. Here is my AC solution. https://www.codechef.com/viewsolution/12389466 answered 03 Jan '17, 18:28 4★abx_2109 275●1●11 accept rate: 0%
 3 The problem is simple since we need to find only maximum number of overlapping intervals. Complexity: NLogN Useful link: Link Code : Code answered 04 Jan '17, 03:05 4★ishpreet 97●1●8 accept rate: 0%
 0 https://www.codechef.com/viewsolution/12382371 Why does this give WA? This was my approach. 1) Every pair of consecutive elements is added to vector vec, such that the first element of the pair is minimum among them. 2) Vector vec is sorted by 1st element, if 1st element same, then 2nd element 3) Now coming to the conditions (probably missed something here): Let's fix the 1st pair of the vector let's call this fixed index i. Now fix the 2nd pair of the vector and call the index j. We have a counter initialized to 1. If i and j are disjoint intervals i=j Counter = 1 This pair is your new starting point. If interval j is embedded in i i=j Increment counter by 1 Else Increment counter by 1 And ans=max(ans,counter) each time Anything I am missing? answered 31 Dec '16, 23:07 2★sandy999 391●1●16●38 accept rate: 10% Yeah i did the same thing as well. Link to my solution is https://www.codechef.com/viewsolution/12381924 . It would be very helpful if someone tells me the mistake in this. Thanks in advance :) (31 Dec '16, 23:45) 7 20 40 70 30 50 100 60 Your code gives wrong output on this test case. The answer should be 4 (01 Jan '17, 00:48) Thanks, I'll modify the code. (03 Jan '17, 22:52) sandy9992★
 0 Just to elaborate on the sweep line part: -If there is peak or crest then the answer would decrease and increase by two respectively.If the point under consideration is starting or ending point then the answer would change by +1 or -1.One can maintain a global variable to keep track of maximum value attained while sweeping. answered 01 Jan '17, 22:15 31●1 accept rate: 0%
 0 I could not get the answer right. I was getting WA in 7 tests. My logic is as follows: Make the array continuous. That is, if the input is: 1 7 2 4 9 Make it 1 2 3 4 5 6 7 6 5 4 3 2 3 4 5 6 7 8 9 Let A[i] denote peak at height i in the flight journey. Peaks can be known by the input vector easily. in this case, 7 and 2 are the peaks.(Note that 4 is not a peak). Calculate D, such that D is the frequency of i in the above continuous array. Push back D to a vector. Calculate B & C such that B is the height at the start of flight and C is the height at the end of flight. Calculate the number of times the flight is at height B and C individually and push the frequency of B and C in the same vector. At last, output the maximum of the vector. Can anybody please tell me where am i going wrong? My code is here: FLYMODE answered 02 Jan '17, 00:42 2★prajneya 2 accept rate: 0%
 0 @prajneya The runtime error is due to bad_alloc,meaning you are allocating to much memory.The vector is of size 10^9 at max which is a way large than permissible limit.You don't need to make the array continuos. answered 02 Jan '17, 04:29 31●1 accept rate: 0%
 0 @prayas_sahni And what about the WA? In Subtask 1 I could only get 3 ACs and the other WAs. Does that mean there is some problem in the logic? answered 02 Jan '17, 09:20 2★prajneya 2 accept rate: 0%

why is my code giving 0 (empty) output on every online ide while running on my local compiler (dev c++)

# include<stdlib.h>

struct node

{

long int s;

node* next;

long int data;

long int q;
};


node* getnode() {

node* temp=(node*)malloc(sizeof(node));

temp->s=0;

temp->q=0;

temp->data=0;

temp->next=NULL;


}

node* find(long int s,long int q)

{

node* temp=head;

while(temp!=NULL)

{

if(temp->s==s&&temp->q==q)

return temp;

temp=temp->next;

}

return NULL;


}

void add(long int s,long int q)

{

node* temp=find(s,q);

if(temp==NULL)

{

node* k=getnode();

k->s=s;

k->q=q;

k->data=1;

}

else

temp->data=temp->data+1;


}

/*void print()

{

node* temp=head;

while(temp!=NULL)

{

printf("%ld<>%ld=>%ld",temp->s,temp->q,temp->data);

temp=temp->next;

}


}*/

void findmax()

{

node* temp=head;

long int m=0;

while(temp!=NULL)

{

if(temp->data>m)

m=temp->data;

temp=temp->next;

}

printf("%ld",m);


}

int main()

{

long int a[100000],n,i;

scanf("%ld",&n);

for(i=0;i<n;i++)

{

scanf("%ld",&a[i]);

}

for(i=0;i<n-1;i++)

{

if(a[i]<a[i+1])

else if(a[i]>a[i+1])

{

}

}

findmax();


}

1
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,639
×1,173
×785
×78
×29
×9

question asked: 31 Dec '16, 18:41

question was seen: 2,832 times

last updated: 25 Feb '17, 17:49