0

I solved the problem below Binary String Problem in Hackerearth the problem which says "Given four integers x,y,a and b. Determine if there exists a binary string having x 0's and y 1's such that the total number of sub-sequences equal to the sequence "01" in it is a and the total number of sub-sequences equal to the sequence "10" in it is b." " with the following code reverse engineering the sample test cases:

import sys
s = sys.stdin.read()

for i in s.split('\n'):
    string = i.split(' ')
    if len(string) != 4:
        print('')
    else:
        x,y,a,b = string
        x = int(x)
        y = int(y)
        a = int(a)
        b = int(b)

        if (x*y == a+b):
            print('Yes')
        else:
            print('No')

The explanation provided in the editorial which if x*y==a+b, then it's such a binary string exists, which I had also figured out reverse engineering the test cases but I really could not how the condition satisfies.

One of the sample cases given is x, y, a and b are 3, 2, 4 and 2 respectively, for which string 00110 is a valid string because 3*2=4+2.

But ** 00110 has 01 & 10 how is it having so the number of 01 is not equal to "a" and number of 10 is not equal to "b". Is there any logic or any other side to the problem which I'm missing out?**

You can refer to actual Problem link for further details

served_raw
  • 92
  • 5
  • Not sure if this would result in a copyright violation but I really was keen on understanding the actual issue here. I can delete the question if that helps. – served_raw May 07 '20 at 21:55
  • Edited based on your suggestion. Thanks. :) – served_raw May 07 '20 at 22:14
  • 1
    They are talking about subsequences, not slices. The `01` _subsequence_ appears in `00110` 4 times: `0x1xx, 0xx1x, x01xx, x0x1x`. – user58697 May 08 '20 at 01:36
  • Thanks mate.. Now I get it. This means when input is 3 2 4 2, so x=3, y=2 a=4, b=2. Number of **10**(b) sub-sequences in `00110` is **2**, `xxx10` `xx1x0` & Number **01**(a) sub-sequences in `00110` is **4**, `x01x` `0x1xx` `x0x1x` `x01xx` And x*y=a+b as, 3*2=4+2 – served_raw May 08 '20 at 19:35

0 Answers0