WEIRDBLD - Editorial



Author: Hrishikesh Patel
Tester: Roshan Gupta, Shivam Sarang, Yash Shah
Editorialist: Yash Shah




Imagine a weird hotel which has n floors and n rooms on each floor. The weird thing is, to go to the $n$th room, one has to start from the first room and sequentially visit all the rooms prior to it.

But some k rooms have lift going from that room to some other fixed room after it. One can choose to take a lift or not take.

No room has more than one lift starting from it. There can be two or more lifts ending in the same room.

Your task is to find out which lifts should be taken to reach the last room in the hotel while visiting the least possible number of rooms.

Input Format:

  • First line contains an integer indicating number of testcases, t.
  • First line in each testcase contains two integers n, k.
  • n is the number of floors and rooms on each floor.
  • Followed by k lines, each contains 2 integers.
  • 1st integer gives the start room number of the lift, s and 2nd integer gives the room number where to which that lift takes, e.

Output Format:

  • For each testcase, a single line containing a bit string of length k, where 0 indicates that the lift is not taken and 1 indicates the lift is taken.
Note :-
  • Bit string output should be maintaining the order in which the lifts were given in input.
  • In case of multiple possible answers, you have to output the solution whose bit string represents the smallest value.
  • For example, if 011 and 100 both are skipping same number of rooms, then your output should be 011.


Sample Test Case:

5 2
5 23
1 15
10 5
1 30
2 15
50 95
32 51
25 99
7 3
2 47
5 30
0 35


  • For first testcase, there are 2 lifts the first skips (23 – 5) 18 rooms and the second skips (15 – 1) 14 rooms.
  • So, 2nd lift is not taken because if it is taken, we cannot take the 1st lift (which skips more rooms).
  • Thus 10 is the output according to the input sequence of lifts, 1st is taken (1) and second is not taken (0).


Setter's Solution
import itertools as it
bs = ["0" for _ in range(14)]
T = int(input())
for _ in range(T):
    N, K = tuple(map(int, input().split()))
    L = []
    for k in range(K):
	    L.append(list(map(int, input().split())))
	    L[k].append(L[k][1] - L[k][0])
    L_orig = [x[0] for x in L]
    C_c = []
    for r in range(1, K + 1):
	    c = it.combinations(L, r)
	    C_c.extend([list(e) for e in c])
    C, ps = [], -1
    for c in C_c:
	    i = 1
	    flag = True
	    while i < len(c):
		    if c[i][0] < c[i - 1][1]:
                            flag = False
		    i += 1
	    if flag:
		    s = 0
		    for v in c:
			    s += v[2]
		    if s > ps:
    out = max(C, key=lambda x: x[-1])[:-1]
    temp = [o[0] for o in out]
    for k in range(K):
	    bs[k] = str(int(L_orig[k] in temp))