FLYMODE - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

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:

Subtask 1

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.

Subtask 2

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.

2 Likes
2

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?

3

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 :slight_smile:

4

7
20 40 70 30 50 100 60
Your code gives wrong output on this test case. The answer should be 4

5

Kindly make problem available for practise.

3 Likes
6

^ make it available for practice.

1 Like
7

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.

8

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

9

It’s available in practice now

10

@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.

11

@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?

12

why is my code giving 0 (empty) output on every online ide while running on my local compiler (dev c++)
#include<stdio.h>
#include<stdlib.h>

struct node

{

long int s;

node* next;

long int data;

long int q;
};

node* head=NULL;

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;

	k->next=head;

	head=k;

}

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])

	add(a[i],a[i+1]);

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

	{

		add(a[i+1],a[i]);

	}

}

findmax();

}

13

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

2 Likes
14

@pkacprzak

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

15

Thanks, I’ll modify the code.

16

The problem is simple since we need to find only maximum number of overlapping intervals.

Complexity: NLogN

Useful link: [Link][1]

Code :


[2]


  [1]: http://stackoverflow.com/questions/18365107/maximum-no-of-overlaps-of-all-time-intervals
  [2]: https://www.codechef.com/viewsolution/12380441
2 Likes