Đếm Cặp Version 2
Đề bài
Cho ba số nguyên $L, R, T$. Hãy đếm xem có bao nhiêu cặp số nguyên $x, y$ thoả mãn:
- $L \le x < y \le R$;
- $x + y = T$.
Dữ liệu: Vào từ thiết bị vào chuẩn gồm ba dòng chứa ba số nguyên $L, R, T$, mỗi số trên một dòng. $(-10^{18} \le L < R \le 10^{18};\ |T| \le 10^{18})$
Kết quả: Ghi ra thiết bị ra chuẩn gồm một số nguyên duy nhất là kết quả của bài toán.
Ràng buộc:
- 60% số test tương ứng với 60% số điểm có $-10^6 \le L < R \le 10^6$;
- 40% số test còn lại tương ứng với 40% số điểm không có ràng buộc gì thêm.
5
10
132Giải thích: Có 2 bộ số thoả mãn: $(5, 8), (6, 7)$.
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesBên dưới là toàn bộ cuộc trò chuyện giữa mình và em ấy, từ lúc em ấy mới được 60 điểm cho tới khi AC, mình biên tập lại theo từng phần cho dễ theo dõi.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Code của em: hai con trỏ, chỉ được 60%
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long l,r,k;
cin>>l>>r>>k;
long long d=0;
while (l<r)
{
if (l+r==k)d++,l++;
else if (l+r<k)l++;
else r--;
}
cout<<d;
}l = int(input())
r = int(input())
k = int(input())
d = 0
while l < r:
if l + r == k:
d += 1
l += 1
elif l + r < k:
l += 1
else:
r -= 1
print(d)Em làm được 60/100 tức là đúng 60% test, nghĩa là với các test thuộc subtask 1: $-10^6 \le L < R \le 10^6$.
Ý tưởng của em là hai con trỏ: l đứng ở đầu trái, r đứng ở đầu phải. Nếu l + r == k thì đếm 1 cặp rồi dịch l; nếu tổng còn nhỏ hơn $k$ thì phải tăng l; nếu tổng lớn hơn $k$ thì phải giảm r. Ý tưởng này đúng, chỉ có điều mỗi bước chỉ dịch được 1 đơn vị.
Anh xem code em rồi, em làm vòng lặp như thế tính ra nó sẽ lặp hết $R - L$ lần, như thế không ổn rồi vì đề bài cho giới hạn $-10^{18} \le L < R \le 10^{18}$. Lỡ như $L = -10^{18}$, $R = 10^{18}$ như thế em lặp hết $2 \cdot 10^{18}$ lần. Nếu theo ngôn ngữ C++ cho 1 giây máy chạy $10^8$ phép tính thì em sẽ cần $2 \cdot 10^{10}$ giây, tức là 20 tỷ giây.
$20$ tỷ $/ 31{,}536{,}000 \approx 634$ năm thôi chứ mấy :)) nên time limit 1 giây thì chắc chắn TLE rồi.
Bài này cách tối ưu giải quyết trong $O(1)$ em nha, không cần lặp gì cả, làm vài phép tính là ra thôi, ra kết quả NGAY LẬP TỨC. Để làm được điều đó em cần phải nháp nhiều chút để nhìn ra quy luật.
Kết quả lệch 1 đơn vị thì debug thế nào?
Em có biết là trên trang web này nó cho xem trường hợp sai không? Chỉ cần em bấm vào đó nó sẽ cho xem đó. Còn nếu đã xem được test sai nhưng test sai lớn quá em khó debug thì em random test nhỏ, sau đó viết code vét cạn để check đi (mình có để công cụ kiểm tra ở cuối bài).
Ý tưởngĐặt mốc X = L, Y = T − X rồi đếm bằng công thức
Muốn hiểu nó thì em cứ thử nhiều ví dụ, chạy tay quy trình logic nó xử lý để hiểu cách thức thôi hà. Như anh đã nói trong phần gợi ý đó: nếu đặt mốc $X = L$ và $Y = T - X$, nếu $Y \le R$ thì lúc này em sẽ thấy nó có các cặp theo kiểu:
cứ thế… đến khi nào $X \ge Y$ thì dừng.
Thì công thức tính nhanh như anh đã đưa ra là: tính khoảng cách ngay từ đầu giữa $Y$ và $X$. Nếu khoảng cách đó mà chia hết cho 2 thì đáp án chính là $\frac{Y - X}{2}$, còn nếu khoảng cách đó không chia hết cho 2 thì đáp án chính là $\frac{Y - X}{2} + 1$ (chia nguyên).
Còn trường hợp nếu đặt $X = L$, tính $Y = T - X$ mà thấy $Y > R$ thì reset cho $Y = R$ (tức là giảm $Y$ đi 1 khoảng bằng hiệu giữa $Y$ lúc chưa giảm và $R$), và $X$ cũng tăng đồng thời với khoảng cách hiệu đó. Rồi xét nếu $X$ vẫn thoả $X < Y$ thì đáp án vẫn được tính nhanh như công thức trên: tính hiệu $(Y - X)$, nếu chia hết cho 2 thì đáp án là $\frac{Y - X}{2}$, nếu không chia hết cho 2 thì đáp án là $\frac{Y - X}{2} + 1$.
Lý do vì sao thì anh nháp qua nhiều tình huống và luôn thấy công thức này đúng :)) chứ chưa đi chứng minh làm gì, nhưng nháp qua cả chục trường hợp nhẩm thấy đều đúng cả. Ở đây mình viết thêm phần chứng minh ngắn cho bạn nào thích chắc chắn:
Còn câu lệnh if đầu tiên trong code là để loại sớm trường hợp không có cặp nào: cặp nhỏ nhất có thể là $L + (L + 1) = 2L + 1$, cặp lớn nhất có thể là $(R - 1) + R = 2R - 1$. Nếu $T < 2L + 1$ hoặc $T > 2R - 1$ thì đáp án là $0$.
Mô phỏng ý tưởng
Em nhập $L, R, T$ (đoạn ngắn thôi, $R - L \le 20$) rồi bấm Tiếp để xem từng bước: đặt mốc $X, Y$, dời mốc nếu $Y > R$, ghép từng cặp và so với công thức:
Cách 2Code của anh – công thức O(1)
Ok đây là code của anh cũng đã AC, code này thì anh code nhanh ra ngay khi nhìn thấy ý tưởng chứ cũng chưa có clean code và cũng không đảm bảo ý tưởng này là tối ưu nhất nha em:
#include <bits/stdc++.h>
using namespace std;
// L <= a < b <= R, a + b = t
long long solve2(long long l, long long r, long long t){
if(t < l + l + 1 || t > r + r - 1){
return 0;
}
long long x = l;
long long y = t - x;
if(y <= r){
long long res = (y - x) / 2;
if((y - x) % 2 != 0){
res++;
}
return res;
}
// y > r
x += y - r;
y = r;
if(x < y){
long long res = (y - x) / 2;
if((y - x) % 2 != 0){
res++;
}
return res;
}
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long l, r, t;
cin >> l >> r >> t;
cout << solve2(l, r, t);
return 0;
}# L <= a < b <= R, a + b = t
def solve2(l, r, t):
if t < l + l + 1 or t > r + r - 1:
return 0
x = l
y = t - x
if y <= r:
res = (y - x) // 2
if (y - x) % 2 != 0:
res += 1
return res
# y > r
x += y - r
y = r
if x < y:
res = (y - x) // 2
if (y - x) % 2 != 0:
res += 1
return res
return 0
l = int(input())
r = int(input())
t = int(input())
print(solve2(l, r, t))Đánh giá độ phức tạp:
long long (khoảng $\pm 9.2 \cdot 10^{18}$) nên yên tâm không bị tràn.Cách 3Code AC của em – nhìn từ giữa ra hai bên
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
long long r,l,n;
cin >> l >> r >> n;
if (n<l*2||n>r*2)
{
cout << 0;
}
else
{
if (n%2==0)
{
cout << min(n/2+1-l,r+1-n/2)-1;
}
else
cout << min(n/2-l+1,r+1-(n-n/2))-(n<0);
}
}def half(n):
# chia nguyên kiểu C++ (làm tròn về 0), khác với // của Python khi n âm
return n // 2 if n >= 0 else -((-n) // 2)
l = int(input())
r = int(input())
n = int(input())
if n < l * 2 or n > r * 2:
print(0)
elif n % 2 == 0:
print(min(half(n) + 1 - l, r + 1 - half(n)) - 1)
else:
print(min(half(n) - l + 1, r + 1 - (n - half(n))) - (1 if n < 0 else 0))Thì em đúng em mới AC đó :)) Có nhiều cách thức xác định khác nhau mà, anh thì nhìn ra hướng như trên, em thì nhìn ra hướng khác, không sao, miễn cùng giải quyết được vấn đề, AC thể hiện rõ điều đó.
Mình giải thích thêm hướng của em cho các bạn dễ hình dung: em đứng ở chính giữa $\frac{n}{2}$ rồi toả ra hai bên $(\frac{n}{2} - 1, \frac{n}{2} + 1)$, $(\frac{n}{2} - 2, \frac{n}{2} + 2)$… Số cặp bị chặn bởi bên nào chạm biên trước: bên trái chạm $L$ hay bên phải chạm $R$, nên mới có min(...). Với $n$ chẵn thì cặp $(\frac{n}{2}, \frac{n}{2})$ không hợp lệ vì $x < y$ nên mới trừ 1. Với $n$ lẻ âm thì phép chia của C++ làm tròn về 0 (ví dụ $-7 / 2 = -3$ chứ không phải $-4$), nên phần tử bên trái bị lệch lên 1 và em phải trừ thêm (n < 0). Chi tiết này rất dễ sai, cũng là lý do bản Python mình viết thêm phải tự viết hàm chia kiểu C++.
Kiểm traCông cụ so sánh với code vét cạn
Còn nếu em lo lắng thì thử làm cái tool check cách tối ưu với cách vét cạn xem có trường hợp nào sai không? Nếu em chưa biết cách làm thì xem code dưới đây nha.
Hàm solve1 là code vét cạn của anh, solve2 là code tối ưu của anh, solve3 là code tối ưu của em. Thử random cùng bộ dữ liệu chạy vào 3 hàm xem có cùng trả ra kết quả giống nhau không? Nếu để tầm vài phút mà vẫn thấy toàn chữ OK thì ổn, nếu thấy chữ FAIL hiện ra thì có test case cụ thể được in ra và 3 đáp án trả ra để theo đó kiểm tra lại xem là cách làm nào bị sai. Khả năng chỉ có thể solve2 hay solve3 sai chứ solve1 là code vét cạn thì khó mà sai lắm.
#include <bits/stdc++.h>
using namespace std;
long long solve1(long long l, long long r, long long t){
long long res = 0;
for(long long i = l; i <= r; ++i){
for(long long j = i + 1; j <= r; ++j){
if(i + j == t){
res++;
}
}
}
return res;
}
// L <= a < b <= R, a + b = t
long long solve2(long long l, long long r, long long t){
if(t < l + l + 1 || t > r + r - 1){
return 0;
}
long long x = l;
long long y = t - x;
if(y <= r){
long long res = (y - x) / 2;
if((y - x) % 2 != 0){
res++;
}
return res;
}
// y > r
x += y - r;
y = r;
if(x < y){
long long res = (y - x) / 2;
if((y - x) % 2 != 0){
res++;
}
return res;
}
return 0;
}
long long solve3(long long l, long long r, long long n)
{
if (n<l*2||n>r*2)
{
return 0;
}
else
{
if (n%2==0)
{
return min(n/2+1-l,r+1-n/2)-1;
}
else
return min(n/2-l+1,r+1-(n-n/2))-(n<0);
}
}
int main(){
srand(time(0));
while(1){
long long l = -100 + rand() % 100;
long long r = l + rand() % 100;
long long t = rand() % 300;
long long res1 = solve1(l, r, t);
long long res2 = solve2(l, r, t);
long long res3 = solve3(l, r, t);
if(res1 == res2 && res2 == res3){
cout << "OK\n";
}
else{
cout << "FAIL\n";
cout << l << " " << r << " " << t;
cout << "\nres1 = " << res1;
cout << "\nres2 = " << res2;
cout << "\nres3 = " << res3;
break;
}
}
return 0;
}import random
import time
def solve1(l, r, t):
res = 0
for i in range(l, r + 1):
for j in range(i + 1, r + 1):
if i + j == t:
res += 1
return res
# L <= a < b <= R, a + b = t
def solve2(l, r, t):
if t < l + l + 1 or t > r + r - 1:
return 0
x = l
y = t - x
if y <= r:
res = (y - x) // 2
if (y - x) % 2 != 0:
res += 1
return res
# y > r
x += y - r
y = r
if x < y:
res = (y - x) // 2
if (y - x) % 2 != 0:
res += 1
return res
return 0
def solve3(l, r, n):
if n < l * 2 or n > r * 2:
return 0
else:
if n % 2 == 0:
return min(n // 2 + 1 - l, r + 1 - n // 2) - 1
else:
return min(n // 2 - l + 1, r + 1 - (n - n // 2)) - int(n < 0)
random.seed(time.time())
while True:
l = -100 + random.randint(0, 99)
r = l + random.randint(0, 99)
t = random.randint(0, 299)
res1 = solve1(l, r, t)
res2 = solve2(l, r, t)
res3 = solve3(l, r, t)
if res1 == res2 and res2 == res3:
print("OK")
else:
print("FAIL")
print(f"{l} {r} {t}")
print(f"res1 = {res1}")
print(f"res2 = {res2}")
print(f"res3 = {res3}")
breakOK.
Nhận xét
Đăng nhận xét