DOM  Domino's effect
Original problem statement (in Polish) can be found here.
Dominik "Domino" Domański is a scientist. He's conducting research on quantum physics. Lately, he started taking a closer look at certain very interesting effect, which can be observed when some quantum objects interact.
In his next experiment, he placed n infinitely thin lines on the table, perpendicularly to the surface, in a row. Lines have different heights, distances between the lines can also differ. (Dominik calls these lines "domino tiles"). Looking from the front, they look like n segments, standing vertically on the X axis of the Cartesian coordinate system.
Domino tiles can be toppled. If a tile has a height of h, it will topple other tiles at most h units away. More precisely, if tile is placed at the position x, and is knocked over to the right, it will topple the tiles placed at positions x+1, x+2, ..., x+h. If this tile is knocked over to the left, it will topple the tiles at positions x1, x2, ..., xh.
Dominik observed a very interesting phenomenon, which he called "Domino's effect"  toppling one domino tile can cause other tiles to topple, which can in turn topple other tiles. He started to wonder how to take advantage of this effect in a best possible way. What is the minimum number of tiles that need to be toppled, in order for all the dominoes to fall?
Input
The first line contains a single integer t, denoting the number of testcases. Then, testcases follow.
The description of a single testcase begins with a single integer n (1 <= n <= 1000)  the number of domino tiles in an arrangement.
It is followed by n integers h_{i}  heights of subsequent tiles.
It ends with n1 integers d_{i}  distances between neighboring tiles.
(1 <= h_{i}, d_{i} <= 10^{6}).
Output
For every testcase you should find a sequence of domino tiles, that will knock down the whole arrangement. It should begin with an integer k (1 <= k <= n), denoting the number of tiles to be pushed. Then, descriptions of moves should follow. One move is described by one integer x_{i} (1 <= x_{i} <= n) and one letter (either L or P). It means that during the ith move, we topple a tile number x_{i} (counting from 1, according to original arrangement). L means that we knock it over to the left, P means knocking over to the right.
The sequence should knock over all the tiles, while using as few moves as possible.
Example
Input:
1 6 1 5 1 1 1 1 2 1 2 1 1
Output:
2 2 P 1 L
Explanation
First we topple the domino tile number 2 (of length 5) to the right, which knocks over everything to the right of that tile. Then, we topple tile number 1  the only one that remains.
hide comments
smtcoder:
20160815 12:31:18
The question is a bit unclear...do this when its spoj toolkit comes out....u have to look out for some special cases...such as the case when the tiles overlap eachother but still cant take down eachother...I got to know about it by the comparing my outputs to that of Rishav Goyal's Code..after so so long struggle on this question..finally accepted.. ;) 

Rishav Goyal:
20160814 11:01:18
@author : you can increase n to 100000. that would be more fun. Last edit: 20160814 11:01:36 

Piotr Jagie³³o:
20160727 12:21:04
Any correct answer will be accepted. 

entcat:
20160726 08:24:59
Does multiple possible answers exist? 
Added by:  Piotr Jagiełło 
Date:  20160725 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: GOSU 
Resource:  PIZZA 2016 qualifying round 