Bài toán tổng cặp

[ntmtmn (Nguyen Tuan)]

Bài này giải sao để không bị TLE vậy mn( time limit là 1s)

Nguồn: BKOI 2018

[SITUVN.gcd]

Thế bạn đã làm gì chưa?

[ntmtmn (Nguyen Tuan)]

giải O(N^2) nên bị TLE ạ

[tntxtnt]

em đừng ghép cặp từng đôi một :V mà “ghép” ăn gian 1 tí bằng cách ko cộng vào ấy. Ví dụ 1 ghép với 31 ra 131, nhưng em viết code ghép là 1 * 100 + 31 thì đừng có cộng vào ngay lúc đó mà để dành cộng sau cùng :V Khi này em thấy số 1 nhân với 100 sở dĩ là do 31 có 2 chữ số. Nếu 1 ghép với 56 thì cũng nhân với 100 vì 56 cũng có 2 chữ số. Còn số 31 vì nó đứng sau nên ko nhân với số nào, là chính nó. Từ đây em tính lẹ được rồi :V

vd S = {1,3,10} có n=3 phần tử thì tổng là

1*(3-1) + 3*(3-1) + 10*(3-1) // 3-1 là n-1 vì số 1 đứng sau n-1 số là 3 và 10, 3 đứng sau 1 và 10, v.v...
+ 1*10*1 // số 1 sau cùng là vì trong S chỉ có 1 phần tử có 1 chữ số và khác 1
+ 3*10*1 // số 1 sau cùng là vì trong S chỉ có 1 phần tử có 1 chữ số và khác 3
+ 10*10*2 // số 2 sau cùng là vì trong S có 2 phần tử có 1 chữ số
+ 1*100*1 // số 1 sau cùng là vì trong S có 1 phần tử có 2 chữ số
+ 3*100*1 // số 1 sau cùng là vì trong S có 1 phần tử có 2 chữ số
+ 10*10*0 // số 0 sau cùng là vì trong S có 0 phần tử có 2 chữ số và khác 100 :V 
= 28 + 40 + 600 = 668

[kisuluoibieng (Tên Gì Cũng Được)]

mảng a:
a[1] = [1, 3, 10]
từ mảng a đăt ra mảng a’ như sau
a’[i] = tổng tất cả phần tử có i chữ số ở mảng a
a’[1] = 4, a’[2] = 10

duyệt mảng 2 chiều a và a’ (a’ tối đa chỉ có 9 phần tử nên không cần phải lo, vẫn là O(n))
với mỗi i, j ta được

1. số chữ số của a[i] khác j: t += a[i] * 10^j + a'[j]
2. số chữ số của a[i] bằng j. Nghĩa là bộ số ghép đằng sau a[i] sẽ có chứa a[i] trong đó, nên loại nó ra. Khi loại lại có 2 trường hợp:
   2.1 Nếu a[i] = a’[j], tức là bộ số có j chữ số chỉ có mình a[i], nên nếu loại a[i] ra bộ số có j chữ số đó thì hết => t += 0
   2.2 Nếu a[i] < a’[j], tức là sộ số có j chữ số đó có a[i] và những chữ số khác nữa, nên ta có công thức tương tự bước 1: t += a[i] * 10^j + (a'[j] - a[i])

loại bài này là loại ngon ăn nhất trong các kì thi, vì nó không đòi hỏi kiến thức giải thuật, chỉ cần nhạy bén với toán là được (bài này chủ yến là tính chất giao hoán và tính chất kết hợp của toán mà con nít cấp 1 cũng đã học)

[rogp10]

Khi nối hai số a, b lại sẽ ra a*10^(số chữ số của b) + b. Vậy ta gom thừa số a, b đặt nhân tử chung sẽ ra thôi.

var foo = function(numbers){
   var a = [10, 100, 1000, 10000, 100000];
   var dc = n => a.find(v => v>n);
   var counts = numbers.map(dc);
   var sump = counts.reduce((r,v) => r+a[v]); // số hạng bên trái
   return counts.reduce((r,s,i) => r+numbers[i]*(numbers.length-1+sump-a[s]), 0);
}

sao có 566 thôi nhỉ?

[SITUVN.gcd]

10^1 + 10^1 + 10^2 = 120
arrayLen - 1 = 2

(1*120 + 1*2 - 1*10^1)
+ (3*120 + 3*2 - 3*10^1)
+ (10*120 + 10*2 - 10*10^2)
= 668

[noz1995 (Trần Hoàn)]

bạn bị TLE ở case nào?

[rogp10]

À, hóa ra là do chưa khởi tạo nên không nhận giá trị đầu.

Một số sẽ xuất hiện ở bên phải (*1) đúng n-1 lần và bên trái n-1 lần, ứng với mỗi số trong dãy. Do số không tự bắt cặp với chính nó nên số hạng bên trái muốn tính tổng phải trừ ra số chữ số của chính nó.

[tcm (Người bí ẩn)]

Bài này mình nghĩ cũng có thể giải khá đơn giản bằng mảng cộng dồn là được. Nếu bạn tư duy theo kiểu phân rã bài toán lớn thành bài toán nhỏ, tức thay vì tìm tổng cặp của dãy từ 1 -> n, mình tìm tổng cặp 1 -> i và sau đó ghép thằng i + 1 vào. Lúc này ta chỉ việc lấy tổng cộng dồn ps[1…i] * 10^[x] + i*x . ([x] là số chữ số của A[i+1] = x)

[rogp10]

Hướng này thì lại khá bí vì còn trường hợp A[i+1] nằm bên trái nữa (chỗ này mới là AC hay không).

[tcm (Người bí ẩn)]

Thì đảo mảng lại và tính như thế thêm 1 lần nữa là ra mà anh