Flappy Bird Codechef Solution

Flappy Bird Solution Problem Code: FLAPPYBD

Chef is playing a noob version of the game Flappy Bird with the following rules:

  • The bird starts at a height HH at x=0x=0.
  • There are NN obstacles (numbered 11 through NN). For each valid ii, the ii-th obstacle is at a position xixi and it has a height hihi.
  • For each integer ii (0≤i<xN0≤i<xN), Chef has the option to click once when the bird is at x=ix=i. Let’s denote the bird’s height (yy-coordinate) at that point by jj. If he clicks, the bird moves to x=i+1x=i+1 and y=j+1y=j+1. Otherwise, the bird moves to x=i+1x=i+1 and y=j−1y=j−1.
  • There is no ceiling and all the obstacles extend upwards from the bottom and not the other way around.
  • For each valid ii, the bird crosses the ii-th obstacle successfully if the bird’s height at x=xix=xi is strictly greater than hihi.
  • At any point before x=xNx=xN, the bird’s height should remain non-negative, otherwise it will drown.
  • If the bird crosses the NN-th obstacle successfully, Chef wins the game.

Can you tell Chef if he can win the game (get the bird to cross all the obstacles) and the minimum number of clicks required to win in such a case?

Input

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains two space-separated integers NN and HH.
  • The second line contains NN space-separated integers x1,x2,…,xNx1,x2,…,xN.
  • The third line contains NN space-separated integers h1,h2,…,hNh1,h2,…,hN.

Output

For each test case, print a single line containing one integer — the minimum number of clicks required to cross all the obstacles successfully, or −1−1 if it is impossible to cross all the obstacles.

Constraints

  • 1≤T≤3⋅1041≤T≤3⋅104
  • 1≤N≤1051≤N≤105
  • 0≤H≤1090≤H≤109
  • 1≤x1<x2<…<xN≤1091≤x1<x2<…<xN≤109
  • 1≤hi≤1091≤hi≤109 for each valid ii
  • the sum of NN over all test cases does not exceed 5⋅1055⋅105

Example Input

3
1 0
2
1
2 1
1 3
1 1
5 10
1 2 3 4 5
10 11 12 13 15

Example Output

2
2
-1

Explanation

Example case 2: The figure below shows one possible way to successfully cross all the obstacles using the minimum number of clicks.

Flappy Bird Codechef Solution

Example case 3: It is clear that even by clicking all the time, it is impossible to cross the last obstacle.

Flappy Bird Codechef Solution

Weekly Contest 247

Biweekly Contest 55

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Related :

Related :

Leave a Comment

Please Click on 1 or 2 Ads to help us run this site.
+