Soluție HackerRank pentru Cyclic Quadruples, subdomeniul Combinatorics, în Python 3. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Cyclic Quadruples
  • Domeniu: Combinatorics
  • Limbaj: Python 3

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

Cerință

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 sursă

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