[Solution] Bomb the base solution codechef – Given one bomb with attack strength XX, find the maximum number of houses that can get destroyed.

Bomb the base solution codechef

In Chefland, there are NN houses numbered from 11 to NNithith house has a defence system having strength AiAi.

Chef suspects a bomb drop on one of the houses very soon. A bomb with attack strength XX can destroy the ithith house, if the defence system of the ithith house AiAi, is strictly less than XX.

Also, when the ithith house is destroyed due to the bomb, all houses with indices jj such that 1j<i1≤j<i get destroyed as well irrespective of their defence system.

Given one bomb with attack strength XX, find the maximum number of houses that can get destroyed.

Input Bomb the base solution codechef

  • The first line will contain TT – the number of test cases. Then the test cases follow.
  • First line of each test case contains two integers N,DN,D.
  • Second line of each test case contains NN integers A1,A2,,ANA1,A2,…,AN.
  • Third line of each test case contains NN integers B1,B2,,BN

Bomb the base solution codechef

For each test case, output in a single line the maximum number of houses that can get destroyed if the bomb can hit any house.

Constraints

  • 1T101≤T≤10
  • 2N1062≤N≤106
  • 1D20001≤D≤2000
  • (i+1)AiN(i+1)≤Ai≤N  (1i<N)(1≤i<N)
  • AN=N+1AN=N+1
  • 1BiN1≤Bi≤N
  • Sum of NN over all test cases does not exceed 106106.

Bomb the base solution codechef

 

2
8 6
4 1 6 1 6 5 6 8
2 1
3 5

Sample Output 1 

6
0

Bomb the base Explanation

Test Case 11: Let us choose i=2i=2 and j=4j=4. Since A24A2≤4, a reaction can take place.
The heat released in this reaction is 242(32)=821=62⋅4−2⋅(3⊕2)=8−2⋅1=6. It can be proven that for no other reaction, the heat released is greater than 66.

Some other reactions can take place between (2,5)(2,5)(3,5)(3,5). Note that no reaction is possible between (3,4)(3,4) as A34A3≰4.

Test Case 22: The only possible reaction is between reagents 11 and 22. The heat released in this reaction is 123(12)=233=71⋅2−3⋅(1⊕2)=2−3⋅3=−7.

Leave a Comment