---
# System prepended metadata

title: Daily Challenges

---

# Daily Challenges - Team III

::::spoiler Thành viên
[Nguyễn Phi Đăng](https://hackmd.io/@NPDang) - Trưởng Nhóm
[Bùi Hải Nam](https://hackmd.io/@BHNam) - Phó Nhóm
[Tống Bảo Khang](https://hackmd.io/@TBKhang)
[Bùi Trọng Nguyên](https://hackmd.io/@TBKhang)
::::

::::spoiler <b>01/11/2025</b>

:::spoiler GIẢI THÍCH

**Xét các số tự nhiên ta thấy:**

$2^2=2.2=2.3-2$

$3^2=3.3=3.4-3$

$4^2=4.4=4.5-4$

$...$

$n^2=n.n=n(n+1)-n$

Suy ra

$$
\sum_{i=1}^{n} i^2 
= 1\cdot2 + 2\cdot3 + \dots + n(n+1) - (1 + 2 + \dots + n)
$$

$$
= \left( \sum_{i=1}^{n} i(i+1) \right) -\left( \sum_{i=1}^{n} i \right)
$$

Vậy nên:

$$
\sum_{i=1}^{n} i(i+1) 
= 1^2 + 2^2 + \dots + n^2 + (1 + 2 + \dots + n)
$$

$$
= \left( \sum_{i=1}^{n} i^2 \right) + \left( \sum_{i=1}^{n} i \right)
\quad \text{(1)}
$$


Mà ta có công thức tính tổng bình phương $n$ số tự nhiên liên tiếp là $\Large\frac{n(n+1)(2n+1)}{6}$ và tổng $n$ số tự nhiên liên tiếp là $\Large\frac{n(n+1)}{2}$. Vậy nên biểu thức $(1)$ có thể biến đổi lại thành:

$$\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}$$

$$=\frac{n(n+1)(2n+1) + 3n(n+1)}{6}$$

$$=\frac{n(n+1)(2n+1+3)}{6}$$

$$=\frac{2n(n+1)(n+2)}{6}$$

$$=\frac{n(n+1)(n+2)}{3}\quad{(2)}$$

Thế nên ta đã suy ra được công thức... 
> **Ủa WTH vậy cái $\large{\frac{n(n^2-1)}{3}}$ trong code ở đâu ra v :skull: ?!!**

## GIẢI THÍCH CODE:

Um thì lúc em **(Đăng)** rút gọn cái biểu thức $(1)$ thì em lại đi lấy cái $\underset{i=1}{\overset{n}\sum}i^2$ trừ cho $\underset{i=1}{\overset{n}\sum}i$ mới ra cái đó ;-;

Nhưng mà vô tình công thức này vẫn <font style="color:green"><b>đúng</b></font> :clown_face::clown_face::clown_face:

***Lí do:***
Nếu $n-1$ vào công thức đúng $(2)$ để tính thì ta thấy biểu thức sẽ trở thành:

$$\frac{(n-1)((n-1)+1)((n-1)+2)}{3}$$

$$=\frac{n(n-1)(n+1)}{3}$$

Ồ... nó vẫn ra <font style="color:green"><b>đúng</b></font> như công thức <font style="color:red"><b>sai</b></font> :exploding_head: :sweat: 

Thế nên nhận ra rằng công thức của em là sẽ đi tính giá trị của biểu thức với $n-1$ nên để tính $n$ theo công thức sai thì $n$ sẽ được cộng $1$

:::

:::spoiler Code
```cpp=
#include <iostream>

using namespace std;

long long SUM_CON_PROD(int n){
    return n*(n*n - 1)/3;
}

int main(){
    int n;
    cin >> n;
    cout << solve(n + 1);
    return 0;
}
```
:::
:::spoiler Ví dụ
$n=2$ thì : $1.2 + 2 . 3 = (2 + 1) .( (2 + 1) . (2 + 1) - 1 ) / 3 = 8$ 
$n=4$ thì : $1.2 + 2.3 + 3.4 + 4.5 = (4 + 1).( (4 + 1).(4 + 1) - 1 ) / 3 = 40$
$n=5$ thì : $1.2 + 2.3 + 3.4 + 4.5 + 5.6 = (5 + 1) .( (5 + 1) . (5 + 1) - 1 ) / 3 = 70$
$n=100$ thì : $1.2 + 2.3 + ... + 100.101 = (101 + 1) .( (101 + 1) . (101 + 1) - 1 ) / 3 = 343400$
:::

::::

::::spoiler <b>04/11/2025</b>

## GCD of an Array - 1493D
> Tags: brute force - data structures - hashing - implementation - math - number theory - sortings - two pointers


![image](https://hackmd.io/_uploads/S1jajDnJWe.png)

----

## Giải thích CTDL

Bài trên được giải bằng cách dùng CTDL **map** có sẵn trong STL C++

**Vai trò của map:** Là 1 cấu trúc dữ liệu lưu biến value dựa theo key. Để truy cập vào 1 giá trị, ta đưa cho map 1 key tương ứng với giá trị đó. Do map được xây dựng trên self-balancing binary search tree nên nó có độ phức tạp mỗi lần truy cập là $O(log\space{n})$ với $n$ là kích thước của map. Kích thước của nó tương đương với số key đã được gán 1 value khác giá trị mặc định. Khi truy cập 1 key chưa được gán thì map sẽ trả về giá trị mặc định tùy theo kiểu dữ liệu của value. VD: *int/long* sẽ trả về *0*; *string* thì trả về *""*.

Map còn có các **"anh em song sinh"** khác như: $unordered\_map$, $multimap$, $unordered\_multimap$. Tùy theo điểm tối ưu, điểm hạn chế  của từng loại sẽ có hướng sẽ dụng cho những bài khác nhau.

Các hàm thường được dùng với các hàm sau:
- insert(): Thêm phần tử mà không ghi đè nếu phần tử đã tồn tại
- at(): Truy cập phần tử
- erase(): Xóa phần tử
- clear(): Xóa toàn bộ map
- find(): Tìm phần tử; trả về một iterator đến phần tử
- count(): Trả về số lượng phần tử có key được cho; đối với map chỉ trả về 1 (có phần tử) hoặc 0 (không có phần tử)
- size(): Trả về số lượng phần tử
- empty(): Trả về true nếu map rỗng, ngược lại trả về false

::::

::::spoiler **05/11/2025**
![image](https://hackmd.io/_uploads/rJnpcP3JZe.png)

----

:::spoiler GIẢI THÍCH
Bài trên được giải bằng cách dùng mảng tổng tiền tố (Prefix Sum).
- Lợi ích lớn nhất và duy nhất của tổng tiền tố là giúp tính tổng của một đoạn (subarray) bất kỳ trong mảng ban đầu với thời gian O(1) (hằng số).
- Dùng khi:
    - Truy vấn tổng đoạn
    - Tìm tổng mảng con bằng k
    - Tìm điểm cân bằng
:::


::::

::::spoiler **06/11/2025**
## Tổng dồn bằng `std::accumulate`

::::