Challenge: Cyclic Quadruples

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 60.0 / 60

Submission status: Accepted

Submission score: 1.0

Submission ID: 464744588

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/cyclicquadruples/problem

Cerinta

You need to count the number of quadruples of integers _(X<sub>1</sub>, X<sub>2</sub>, X<sub>3</sub>, X<sub>4</sub>)_,
such that _L<sub>i</sub> ≤ X<sub>i</sub> ≤ R<sub>i</sub>_ for `i = 1, 2, 3, 4`
and _X<sub>1</sub> ≠ X<sub>2</sub>_, _X<sub>2</sub> ≠ X<sub>3</sub>_,
_X<sub>3</sub> ≠ X<sub>4</sub>_, _X<sub>4</sub> ≠ X<sub>1</sub>_.


The answer could be quite large.  
Hence you should output it modulo _(10<sup>9</sup> + 7)_.  
That is, you need to find the remainder of the answer by _(10<sup>9</sup> + 7)_.


**Input Format**  
The first line of the input contains an integer _T_ denoting the number of test cases.
The description of _T_ test cases follows.
The only line of each test case contains 8 space-separated integers
_L<sub>1</sub>, R<sub>1</sub>, L<sub>2</sub>, R<sub>2</sub>, L<sub>3</sub>, R<sub>3</sub>, L<sub>4</sub>, R<sub>4</sub>_, in order.

**Output Format**  
For each test case, output a single line containing the number of required quadruples modulo _(10<sup>9</sup> + 7)_.

**Constraints**  
1 ≤ _T_ ≤ 1000  
1 ≤ _L<sub>i</sub>_ ≤ _R<sub>i</sub>_ ≤ 10<sup>9</sup>

**Sample Input**

    5
    1 4 1 3 1 2 4 4
    1 3 1 2 1 3 3 4
    1 3 3 4 2 4 1 4
    1 1 2 4 2 3 3 4
    3 3 1 2 2 3 1 2

**Sample Output**  

    8
    10
    23
    6
    5
    
**Explanation**  
**Example case 1.** All quadruples in this case are

    1 2 1 4
    1 3 1 4
    1 3 2 4
    2 1 2 4
    2 3 1 4
    2 3 2 4
    3 1 2 4
    3 2 1 4

**Example case 2.** All quadruples in this case are

    1 2 1 3
    1 2 1 4
    1 2 3 4
    2 1 2 3
    2 1 2 4
    2 1 3 4
    3 1 2 4
    3 1 3 4
    3 2 1 4
    3 2 3 4

**Example case 3.** All quadruples in this case are

    1 3 2 3
    1 3 2 4
    1 3 4 2
    1 3 4 3
    1 4 2 3
    1 4 2 4
    1 4 3 2
    1 4 3 4
    2 3 2 1
    2 3 2 3
    2 3 2 4
    2 3 4 1
    2 3 4 3
    2 4 2 1
    2 4 2 3
    2 4 2 4
    2 4 3 1
    2 4 3 4
    3 4 2 1
    3 4 2 4
    3 4 3 1
    3 4 3 2
    3 4 3 4

**Example case 4.** All quadruples in this case are

    1 2 3 4
    1 3 2 3
    1 3 2 4
    1 4 2 3
    1 4 2 4
    1 4 3 4

**Example case 5.** All quadruples in this case are

    3 1 2 1
    3 1 3 1
    3 1 3 2
    3 2 3 1
    3 2 3 2

Cod sursa

p = int(1e9+7)
def intsc(l1,l2):
    if l1==[] or l2==[]:
        return([])
    else:
        a = max(l1[0],l2[0])
        b = min(l1[1],l2[1])
        if b<a:
            return([])
        else:
            return([a,b])
def cd(l):
    if l==[]:
        return(0)
    else:
        return(l[1]-l[0]+1)

t = int(input())
for tst in range(t):
    
    s = input().strip().split()
    w = []
    for i in s:
        w.append(int(i))
    z= {}
    z[0]=[w[0],w[1]]
    z[1]=[w[2],w[3]]
    z[2]=[w[4],w[5]]
    z[3]=[w[6],w[7]]

    comp = 0
    for i in range(4):
        tmp = 1
        L = intsc(z[i],z[(i+1)%4])
        j = (i+2)%4
        k = (i+3)%4
        tmp = (tmp*cd(L))%p
        tmp = (tmp*cd(z[j]))%p
        tmp = (tmp*cd(z[k]))%p
        comp = (comp+tmp)%p
    for i in range(4):
        tmp = 1
        L = intsc(z[i],z[(i+1)%4])
        L = intsc(L,z[(i+2)%4])
        tmp = cd(L)%p
        tmp = (tmp*cd(z[(i+3)%4]))%p
        comp = (comp-tmp)%p
    a1 = intsc(z[0],z[1])
    a2 = intsc(z[2],z[3])
    a3 = intsc(z[1],z[2])
    a4 = intsc(z[3],z[0])
    comp = (comp - (cd(a1)*cd(a2))%p)%p
    comp = (comp - (cd(a3)*cd(a4))%p)%p
    b = intsc(a1,a2)
    comp = (comp+3*cd(b))%p
    tot = 1
    for i in range(4):
        tot*=cd(z[i])
        tot%=p
    tot-=comp
    tot%=p
    print(tot)
HackerRank Combinatorics – Cyclic Quadruples