LTM40AB - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Misha Chorniy
Tester: Sergey Kulik
Editorialist: Pawel Kacprzak

DIFFICULTY:

CAKEWALK

PREREQUISITES:

basic math

PROBLEM:

Given integers a, b, c, d find the number of integer solutions of inequality x < y, where a ≤ x ≤ b and c ≤ y ≤ d. In one test file there are several test cases to handle.

QUICK EXPLANATION:

Iterate through all possible values of x and for each one, count the number of valid values of y to pair with it.

EXPLANATION:

Subtask 1

In the first subtask, we know that a, b, c, d ≤ 103. For such low constraints, it can observed that in any valid pair of x < y, both x and y are less or equal than 103 as well. With this observation, it is possible to iterate over all possible x, y ≤ 103. Thus, for each fixed pair x, y, we can explicitly check if x < y and add 1 to the result if the inequality is fulfilled.

Subtask 2

In the second subtask we have a, b, c, d ≤ 106, so iterating over all possible values of x and y explicitly is not possible here. However, constraints are small enough to iterate over all possible values of one of the variables. Let’s say that we are going to iterate explicitly over all possible values of x. For one such fixed value of x, the problem reduces to how many values of y are there such that c ≤ y ≤ d and x < y. In other words, the task is to count the number of integers y, such that y ≥ max(c, x + 1) and y ≤ d. Let’s assume that c ≤ d, otherwise, there are no valid values of y of course. It follows, that for a fixed x, there are d - max(c, x+1) + 1 valid values of y, because the number of integers in a range [R1, R2] is given by R2 - R1 + 1.

The final result is the accumulated result for each possible value of x computed as described above. Total time complexity of this method is linear in terms of the number of possible values of x, which is at most 106.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution will be uploaded soon.
Tester’s solution can be found here.
Editorialist’s solution can be found here.

1 Like
2

Can someone tell me the problem in my solution, I calculated the result in O(1) time according the values of a,b,c,d.

3

An O(t) solution is also possible:-
https://www.codechef.com/viewsolution/11607413

1 Like
4

Mine O(t) solution : https://www.codechef.com/viewsolution/11610969

5

Here is my O(1) solution : https://www.codechef.com/viewsolution/11610143

1 Like
6

package com.codechef.easy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Codechef1 {
public static void main(String args[]) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
try {
int T = Integer.parseInt(br.readLine());
// int T = 1;
while (T-- > 0) {
String s1 = br.readLine();
String nums[] = s1.split(" ");
long a, b, c, d;
a = Long.parseLong(nums[0]);
b = Long.parseLong(nums[1]);
c = Long.parseLong(nums[2]);
d = Long.parseLong(nums[3]);
if (a > b || c > d || a > d)
System.out.println(0);
else {
// a2 b999999 c1 d100000
if (a > c)
c = a;
if (b > d)
b = d;
long p = 0;
if (b < c)
p = (b - a + 1) * (d - c + 1);
else {
p = (b - a + 1) * (d - c + 1);
p -= (b - c + 1) * (b - c + 2) / 2;
}
System.out.println§;
}
}
} catch (NumberFormatException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}
}

7

I tried to use n*(n+1)/2, can any one tell me the problem with my approach?

8

This line is all you need:

out.println(a > b || c > d ? 0 : 1L * (d - c + 1) * Math.max(0, (Math.min(b, c - 1) - a + 1)) + Math.max(0, Math.min(b, d - 1) - Math.max(a, c) + 1) * (2L * (d - Math.max(a, c)) + 1 - Math.max(0, Math.min(b, d - 1) - Math.max(a, c) + 1)) / 2);

9

what are test cases

10

//plzz tell me what is the problem with this code tisis not runnning any of test case but at ide it passes sample test cases…
#include <bits/stdc++.h>
using namespace std;

int main() {
//code
long long int a,b,c,d,x=0,y=0,count=0;
int t;
cin>>t;
for (int i = 0; i < t; i++) {
scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
if(a>1000&&b>1000&&c>1000&&d>1000){
for (x = a; x <= b; x++) {

        //count=count+d-max(c,x+1)+1;
    for (long long int i1 = c; i1 <= d; i1++) {
        /* code */if(x<i1) count++;
    }
    
   }

}
else{
for (x = a; x <= b; x++) {

        count=count+d-max(c,x+1)+1;
  }

}

printf("%lld\n",count);
count=0;
}
return 0;
}

11

plz tell me the solution…

12

Check my solution which is o(n) here but before that try taking long long int as it s clearly seen from testcase-2

13

can someone tell that why are we using max(c,x+1) and not max(c,x)?

14

@zoyron bcoz we have to find no. of y for y>x
and for finding max we r using >= sign
it may be possible that max can be x and y=x but we dont want it…

1 Like