You are not logged in. Please login at www.codechef.com to post your questions!

×

FLYMODE - Editorial

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

This question is marked "community wiki".

asked 31 Dec '16, 18:41

pkacprzak's gravatar image

5★pkacprzak ♦♦
74485097
accept rate: 12%

edited 31 Dec '16, 22:31

admin's gravatar image

0★admin ♦♦
19.8k350498541

@pkacprzak

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

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

Kindly make problem available for practise.

link

answered 01 Jan '17, 01:18

prayas_sahni's gravatar image

1★prayas_sahni
311
accept rate: 0%

2

^ make it available for practice.

(01 Jan '17, 15:22) anshkhanna74★

It's available in practice now

(02 Jan '17, 01:29) pkacprzak ♦♦5★

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

link

answered 03 Jan '17, 18:28

abx_2109's gravatar image

4★abx_2109
275111
accept rate: 0%

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

Complexity: NLogN

Useful link: Link

Code : Code

link

answered 04 Jan '17, 03:05

ishpreet's gravatar image

4★ishpreet
9718
accept rate: 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?

link

answered 31 Dec '16, 23:07

sandy999's gravatar image

2★sandy999
39111638
accept rate: 10%

edited 31 Dec '16, 23:24

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) satyroxx13975★

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) satyroxx13975★

Thanks, I'll modify the code.

(03 Jan '17, 22:52) sandy9992★

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.

link

answered 01 Jan '17, 22:15

prayas_sahni's gravatar image

1★prayas_sahni
311
accept rate: 0%

edited 02 Jan '17, 01:40

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

link

answered 02 Jan '17, 00:42

prajneya's gravatar image

2★prajneya
2
accept rate: 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.

link

answered 02 Jan '17, 04:29

prayas_sahni's gravatar image

1★prayas_sahni
311
accept rate: 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?

link

answered 02 Jan '17, 09:20

prajneya's gravatar image

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<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();

}

link

answered 03 Jan '17, 18:03

sid120498's gravatar image

2★sid120498
1
accept rate: 0%

edited 03 Jan '17, 18:12

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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