DOM - Domino's effect

no tags 

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 x-1, x-2, ..., x-h.

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?


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 hi - heights of subsequent tiles.

It ends with n-1 integers di - distances between neighboring tiles.

(1 <= hi, di <= 106).


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 xi (1 <= xi <= n) and one letter (either L or P). It means that during the i-th move, we topple a tile number xi (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.



1 5 1 1 1 1
2 1 2 1 1


2 P
1 L


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: 2016-08-15 12:31:18

The question is a bit 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: 2016-08-14 11:01:18

@author : you can increase n to 100000. that would be more fun.

Last edit: 2016-08-14 11:01:36
Piotr Jagie³³o: 2016-07-27 12:21:04

Any correct answer will be accepted.

entcat: 2016-07-26 08:24:59

Does multiple possible answers exist?

Added by:Piotr Jagiełło
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
Resource:PIZZA 2016 qualifying round